Šlechtíme roboty: Line follower pomocí evoluce

(Autoři: Antonín Jareš, Petr Martišek)
Vytvoření robota jezdícího po čáře je klasickou vstupní úlohou do světa robotiky. Co se týče algoritmu, pro nováčky se nejedná o úlohu triviální, a tak, abychom si ušetřili práci, jsme se rozhodli nechat za nás tento problém vyřešit evoluci.

S čím pracujeme

1. Robot: Parallax Boe-Bot, opatřen dvěma koly s přidanou lištou s pěti senzory, které při jízdě detekují černou/bílou. Změnou signálů vysílanou do každého kola pak může robot ovlivňovat jejich rychlost.
2. Neuronové sítě: Robot je řízen neuronovou sítí o pěti vstupech (senzory) a dvou výstupech (kola). Právě tato síť bude předmětem evoluce.
3. Simulátor vlastní výroby: Model robota a jeho prostředí.
4. Neataptic.js: Knihovna implementující evoluci neuronových sítí.

Co je neuronová síť?

Neuronová síť je výpočetní model inspirovaný fungováním biologického mozku. Základní jednotkou je umělý neuron, který ze svých vstupů počítá výstup pomocí tzv. aktivační funkce¹. Neurony v síti jsou spojeny tzv. synapsemi, které propojují výstup jednoho neuronu se vstupem jiného. Každá synapse má asociovanou váhu (reálné číslo). Jako vstup pro aktivační funkci se typicky používá přímo vážená suma vstupních signálů neuronu². Celá síť je obvykle strukturována do vrstev, kdy synapse existují pouze mezi dvěma sousedními vrstvami. Počet neuronů v první (vstupní) vrstvě odpovídá velikosti vstupu neuronové sítě, počet neuronů v poslední (výstupní) vrstvě odpovídá výstupu neuronové sítě.

Celá neuronová síť pak funguje následovně: neurony v první vrstvě spočtou na základě vstupů neuronové sítě své výstupy, ty se pak použijí jako vstupy pro druhou vrstvu atd. až nakonec získáme výstup neuronů v poslední vrstvě – ten je pak výstupem celé sítě. Popsaný model odpovídá tzv. dopředné neuronové síti³.

Chování jedné konkrétní neuronové sítě je přímo závislé jednak na architektuře (počet skrytých vrstev⁴, počet neuronů ve vrstvách, typ aktivační funkce) a jednak na nastavení vah synapsí. Klasický přístup je takový, že architekturu zvolí experimentátor a váhy se síť naučí sama. Pro učení je třeba trénovací množina vstupů i s očekávanými výstupy, s nimiž se pak síť může porovnávat. Klasické učení neuronových sítí je rozebráno například zde.

Evoluce

Alternativní možností, jak nalézt nejlepší síť řešící zadaný problém, je využití evolučního algoritmu namísto učení. Základní myšlenkou je, že budeme simulovat přirozenou evoluci a necháme jedince v populaci mezi sebou soupeřit, abychom si „vyšlechtili“ optimálního jedince⁵. Základní proces je následující:

1. Vytvoříme startovní populaci náhodně inicializovaných jedinců.
2. Každého jedince ohodnotíme podle toho, jak dobře řeší zadaný problém (tj. přiřadíme mu skóre podle tzv. fitness funkce).
3. Vytvoříme novou generaci křížením jedinců z původní populace, kdy pravděpodobnost výběru jedince pro křížení je úměrná jeho skóre (tzv. rodičovská selekce).
4. Jisté procento populace necháme podstoupit mutaci, tedy náhodnou změnu nějakých parametrů.
5. Jisté malé procento nejlepší části populace necháme podstoupit bez mutace a bez křížení (tzv. elita populace).
6. Pokračujeme od kroku 2. dokud nedosáhneme ukončovací podmínky, typicky maximální počet generací.

Díky preferenci jedinců podle jejich schopnosti řešit problém (v bodě 3) se do dalších generací propagují dobrá řešení, díky křížení a mutaci v bodech 3 a 4 se udržuje diverzita populace a objevují se i zcela noví jedinci. Konvergence k optimálnímu řešení není zaručena, nicméně při dostatečně velkém počtu generací a vhodně nastavených parametrech lze dospět k velmi dobrým výsledkům.

Pro konkrétní problém je třeba definovat konkrétní varianty křížení, mutace a především fitness funkci⁶. Dalšími důležitými parametry, které musí experimentátor zvolit, jsou velikost populace, pravděpodobnost křížení, pravděpodobnost mutace, velikost elity a další.

Sofistikovanou a populární nadstavbou nad jednoduchou neuroevolucí je algoritmus NEAT, který přidává například koncept druhů a propracovaný algoritmus křížení (podrobný popis např. zde).

Vzhledem k tomu, že naším cílem je vytvořit reflexivního agenta, který pouze převádí signály z pěti senzorů na dva signály vedené do kol, můžeme si jeho chování představit jako neuronovou síť o pěti vstupech a dvou výstupech. Každá taková síť tedy bude jednoznačně převádět stavy senzorů na rychlost obou kol.

Simulátor

Evoluce ale dá práci, proto není vhodné ji nechat běžet na skutečných strojích. Pokud bychom čekali na výsledky chování jedinců v reálném světě, mohli bychom se dostat klidně na desítky vteřin za ohodnocení jedince (tak jak dlouho mu prostě akce reálně trvá), což by vzhledem k jejich počtu v řádech desítek tisíc (napříč generacemi) mohlo zabrat i několik týdnů nepřetržité práce. Proto je vhodné využít simulaci reality.

Pro tento projekt jsme vytvořili webový simulátor, ve kterém byli jednotliví roboti testováni. Na základě jejich fitness ohodnocení jsou pak vybráni vhodní jedinci a následně tvořeny další generace. V takovémto prostředí výpočet evoluce zabere maximálně pár hodin.

Samozřejmě vhodný simulátor nelze jednoduše vytvořit pro všechny typy úloh. Vzhledem k jednoduchosti našeho prostředí a robota však nebylo obtížné simulátor sestrojit. Simulátor si můžete pro jednoho robota vyzkoušet zde, odkaz na zdrojový kód pro robota ke stažení je níže na této stránce.

Výsledný proces

Strukturu neuronové sítě máme. Teď už stačí pouze nechat ji běžet, aby se vyvinuli kvalitní jedinci („evolvovat“). Samotná evoluce probíhá tak, že se náhodně vytvoří počáteční populace neuronových sítí reprezentujících robota (každá síť jednoho), která je následně spuštěna v simulátoru na určitý počet cyklů nebo dokud není splněna zastavující podmínka. Následně je vytvořena nová populace (dle evolučního algoritmu) a iteruje se.

Je důležité vhodně zvolit zastavující podmínku. Při prvních pokusech o evoluci jsme selhali s tím, že podmínka byla nastavena na „všechny senzory ukazují bílou“, což ale byl vcelku častý případ vzhledem k malému poloměru senzorů tohoto robota. Po změně podmínky na „všechny senzoru ukazují bílou alespoň 0.2 s“ se evoluce dařila mnohem lépe.

Nejdůležitější složkou celého evoluce je vhodný výběr fitness funkce. Funkce nesmí být příliš omezující, aby v prvních generacích neměli všichni jedinci nulové ohodnocení, ale ani příliš obecná, protože pak by nedostatečně popisovala hledané chování a výslední jedinci by se nedali použít.

Zbývá tedy spustit evoluci neuronových sítí s šikovně zvolenými parametry a vhodnou fitness funkcí a počkat na výsledek.

Příklad 1:
Fitness funkce: vzdálenost ujetá s čárou uprostřed
Zastavení: všechny senzory vidí bílou
Výsledek: Tento robot nezvládl ani první zatáčku. Zastavovací podmínka je totiž příliš přísná a skoro všichni na ní selhali.

Příklad 2:
Fitness funkce: kombinace vzdálenosti ujeté s čárou uprostřed a rychlosti
Zastavení: všechny senzory vidí bílou po alespoň 0.2 s.
Výsledek: Tady jsme měli radost, že hodnota fitness nejlepšího jedince v populaci během evoluce rapidně rostly, ale po spuštění simulátoru jsme se divili, že se robot nehýbe. Robot se však hýbal, a to přesně tak, aby maximalizoval fitness funkci: jezdil tam a zpět na místě maximálně rychlostí… toto tedy také nebylo správné řešení.

Příklad 3:
Fitness funkce: kombinace vzdálenosti ujeté s čárou uprostřed a rychlosti, navíc s velkou penalizací za couvání.
Zastavení: všechny senzory vidí bílou po alespoň 0.2 s.
Výsledek: Vítěz! Síť zvládla navigovat robota bezchybně napříč testovací dráhou a zvládala i nové dráhy, které dříve neviděla.

Vyšlechtili jsme tedy neuronovou síť => vzhledem k tomu, že se vlastně jedná o mapování 5 binárních vstupů na 2 výstupy, můžeme výslednou síť implementovat jako pole dvojic určující řízení dvou motorů pro každou kombinaci možných vstupů, čili pole o 32 prvcích.

A jak si síť vedla po portování ze simulátoru na samotného robota? To už jste viděli ve videu v úvodu 🙂

Je samozřejmě otázkou, zda je pro náš jednoduchý úkol potřeba takto složitá neuronová síť – ale kdo jsme, abychom rozporovali výsledek evoluce…⁷

Parametry experimentu

Evoluce
pravděpodobnost mutace: 0.8
velikost populace: 100
počet skrytých neuronů na začátku: 3
maximum generací (ukončovací podmínka): 400
elitismus: 5 nejlepších

Robot
interval spínání senzorů: 20ms
max. rychlost: 20 cm/s
mapování serv: 1500 – stop, 1300/1700 max rychlost
rozvor: 10.5 cm
vzdálenosti senzorů od středu osy kol: podle osy $x$ 4 cm pro všechny senzory, podle osy $y$ 5, 1.5, 0, -1.5, -5 cm.
poloměr senzorů: 0.15 cm

Vzorečky:
Sigmoidální funkce: $f(x)={1 \over 1+e^{-kx}}$
Hyperbolická tangenta: $f(x)={2 \over 1+e^{-kx}}-1$

Zdrojový kód robota
Ke stažení zde: LineFollowerEvolution.zip (.ino pro Arduino, .js do simulátoru).

---

Poznámky:

1. Jako aktivační funkce neuronu se používá mnoho různých funkcí, nejpopulárnější jsou sigmoidální funkce nebo hyperbolická tangentoida (vzorečky jsou na konci článku, ucelený přehled například zde).
2. Hodnota „přicházející“ z každé synapse se vynásobí vahou synapse, a to se všechno sečte dohromady
3. Existují i pokročilejší varianty jako jsou rekurentní nebo modulární sítě, ty jsou však nad rámec tohoto článku
4. Skryté vrstvy jsou druhá až předposlední, tj. vrstvy „skryté“ mezi vstupní a výstupní vrstvou.
5. V našem kontextu je jedincem jedna konkrétní instance neuronové sítě
6. Křížení je třeba implementovat opatrně s ohledem na strukturu sítí. Mutace může být v případě neuronových sítí například změna váhy nějaké synapse, změna typu aktivační funkce, přidání či odebrání synapse nebo dokonce přidání či odebrání neuronu.
7. Poznámka editora: Ve skutečnosti je podstatné, že se na této velejednoduché úloze dá mechanismus fungování neurosítí vysvětlit a pochopit, takže je pak možné neuronové sítě použít i na velmi složité úlohy, které by pro úplného začátečníka byly nejspíš úplně nesrozumitelné.