Masarykova univerzita Fakulta informatiky
Evoluce pohybu IV109
Tomáš Kotula, 265 287
Brno, 2009
Úvod Pohyb je jedním ze základních projevů života. Zdá se tedy logické, že stejně jako ostatní vlastnosti a chování živočichů, se pohyb vyvinul evolucí. Počítačovou obdobou evoluce jsou genetické algoritmy. Pomocí nich se dá naleznout řešení velmi složitých problémů s mnoha stupni volnosti. Tato práce se zabývá vývojem specifického chování pro pevně zvolené tělo. Tělo se skládá z kvádříků a pohybuje se ve 3D prostoru. K naprogramování byl použit programovací jazyk Java spolu s knihovnou jME Physics 2 [http://wiki.jmephysics.irrisor.net/tiki-index.php].
Hypotézy •
Genetickými algoritmy se podaří vyvinout efektivní chování pro pohyb.
•
Očekáváme chování, které se bude za daných podmínek snažit co nejlépe plnit danou hodnotící funkci (uražená vzdálenost – viz dále).
•
Pohyb, který se objeví bude podobný žijícím živočichům, protože ti se pohybují efektivně.
2D vs 3D Původním záměrem bylo simulovat 2D pohyb ve vodě podobné jako Springbots [2] nebo Genetic Robots [1]. Živočichové (lépe řečeno roboti) jsou v modelu jako grafy s proměnlivou délkou hran (rovnovážná délka pružiny). V případě pevných délek „kostí“ použijeme graf typu strom (kostra), aby v grafu nevznikaly cykly, což by nebylo produktivní (zabraňuje volnému pohybu). Jako pohony by pak sloužily klouby (vrcholy grafu), které by měly proměnlivou hodnotu úhlu mezi dvěma hranami. Ukázalo se, že naprogramování simulátoru – byť se jedná o jednoduchý fyzikální modelu pro 2D grafy – je velmi netriviální problém. Vhodných knihoven, které se zabývají 2D fyzikou také není příliš mnoho. Fyzika kapalin (pro pohyb ve vodě) také nebývá běžným prostředkem, protože voda má zvláštní charakteristiky. Nakonec jsem se rozhodl pro knihovnu jME Physics 2, která má svá omezení, ale v relativně krátkém čase umožňuje velké pokroky. Umožňuje použití základních prostorových tvarů (koule, kvádr) a jejich spojení pomocí kloubů.
Model Program modeluje vývoj pohybu pro pevně zvolené tělo. Zvolil jsem přijatelně jednoduchý tvar tak, aby byl schopen složitějšího pohybu, ale zároveň nebyl příliš složitý na koordinaci. Výsledná podoba připomíná housenku. Tělo se skládá ze čtyř kvádříků. Mezi nimi jsou dohromady tři klouby. Na jednom z konců je volně připojená hlava. Klouby jsou implementovány jako rotační síla působící v opačném směru na přilehlé části těla (na působišti síly nezáleží). O zbytek fyziky se postará použitá fyzikální knihovna. Na obrázku snímek aplikace. Roboti se snaží pohybovat doprava od počátku (zelený kříž).
Genetický algoritmus Pro fyzikální model bylo třeba vymyslet model chování, které by mělo vhodný rozsah možností. V úvahu připadaly neuronové sítě (ty jsou však náročné), fuzzy logika, cyklometrické funkce (různá fáze, amplituda) nebo obecné posloupnosti. Použil jsem poslední možnost. Genetická informace Předpokládám, že pokud se má tělo pohybovat neustále, pak se pohyb začne být po jisté době periodický. Zvolil jsem tedy posloupnost čísel pevné délky šest (může obsahovat i menší periody délky 1, 2 a 3; není ještě příliš složité). Každý kloub má svoji posloupnost. Hodnoty jsou v intervalu [-1; 1]. Znamenají v tomto okamžiku aplikuj na kloub sílu maximální*hodnota (znaménko odlišuje směr). Dohromady tedy charakterizuje jeden vzor chování 3*6=18 hodnot z intervalu [-1; 1]. Těchto 18 hodnot nám reprezentuje genetický kód. I kdybychom rozlišovali pouze mezi hodnotami {-1, 0, 1}, můžeme vytvořit 318 vzorů chování. Počítáme však s reálnými čísly. Fitness Pro genetický algoritmus je důležité stanovit hodnotící funkci. To znamená ohodnotit kvalitu každého jedince. V našem případě nám jde o to, jak rychle se jedinec pohybuje. Další hodnocení může být výška nebo délka skoku, elegance pohybu, strnulost v pozici nebo kvalita interakce s okolím (kopání do míče). Nemáme za cíl srovnávat bojové schopnosti proti sobě a obstání v konkurenci. Vzdálenost je
absolutní a neměnná charakteristika. Měříme, jak daleko bude v pevně stanoveném čase hlava jedince (mohli bychom zvolit i jinou část těla nebo jiné kritérium vzdálenosti). Stanovená doba měření je klíčová. Je-li příliš krátká, zvítězí nejspíše jedinci, kteří obětují všechno úsilí na jediný skok. Naopak příliš dlouhá doba je zbytečná a neodliší ty, kteří se náhodou zasekli, od pomalých. Protože měříme vždy stejný okamžik, můžou se vyvinout jedinci, kteří jsou právě v tomto okamžiku v maximu, ale jinak nevynikají. Vhodná doba se experimentálně pohybuje v rozmezí 3–7 cyklů chování. Na grafu je ohodnocení jedinců v průběhu času. Bílá místa oddělují generace. Je vidět rostoucí tendence, velikost různorodosti a taky role náhody.
Generace Generace je soubor jedinců existujících současně. Na její velikosti závisí rychlost a kvalita výpočtu. Běžně používám počet 10ti jedinců. Méně je už pro genetický algoritmus opravdu málo a více jedinců je náročnější počítat najednou. Fyzikální knihovna pracuje v reálném čase, není tedy možné simulaci urychlit. Na druhé straně zvládá špatně mnoho jedinců a to vede k nepřesnostem. Je nemožné odsimulovat jedno chování dvakrát stejně, což je mrzuté. Na druhou stranu to vede ke vzniku náhody a klade na jedince větší nároky na robustnost chování jedinců. Křížení a mutace Po uběhnutí zvoleného času poslední generací, se přiřadí jedincům hodnocení podle vzdálenosti, kterou urazili. Na řadu přichází alchymie s nastavováním pravděpodobnosti přežití, rozmnožení a mutací. S malou pravděpodobností může jedinec zmutovat (změní se mu jedna z hodnot genu na náhodnou hodnotu). Nejlepší jedinci se náhodně zkříží (použije se prvních n hodnot prvního a zbylých 18-n hodnot genu druhého jedince). Kvalitnější jedinci mají větší šanci na rozmnožení, nekvalitní mají větší
šanci na vyhynutí.
Výsledky Model je citlivý na chaos (vzorkování fyzikálního chování může pro jedno chování dávat jiné hodnocení). Simulovat 2D pohyb ve 3D způsobuje komplikace (vyvrácení jedince do strany a dále se nemůže pohybovat). Z náhodného chování často vznikne pomocí GA v krátké době poměrně efektivní chování. Bohužel se zatím nepodařilo nastavit GA tak, aby konvergoval aspoň do lokálního optima, takže výsledkem není populace dokonalých jedinců. Algoritmu se však daří najít nějaký velmi dobrý optimální běh. Na totální maximum se často dostane během prvních desítek generací. Vzory chování připomínají chování existujících živočichů (postupná vlna stonožka, odrážení a skákání, valení těla přes sebe). Na druhou stranu se vyskytují také chaotické a trhané. Přirozené pohyby jsou úspěšnější.
Závěr I přes nepřesnosti modelu (je to model) se podařilo vytvořit širokou škálu efektivních vzorů chování. I pro člověka by byl nelehký úkol vytvořit je za daných podmínek ručně. Genetické algoritmy jsou pro danou tématiku velmi vhodným nástrojem. Svědčí o tom také spousta videí na internetu. Model je závislý na reprezentaci fyzikálních podmínek a na nastavení parametrů GA. Pro základní pochopení principů je tento model vhodný, pro další výzkum bych volil raději ověřené nástroje.
Literatura [1] Genetic Robots http://www.teamten.com/lawrence/projects/genetic_robots/ [2] Springbots http://www.youtube.com/watch?v=U4vJP5q3jlo&feature=related [3] Self aware robot http://www.ted.com/index.php/talks/hod_lipson_builds_self_aware_robots.html [4] Přednášky IV109 Modelování a simulace jaro 09
