Genetické programování pro řízení hejna robotů

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Michal Filippi Genetické programování pro řízení hejna robotů Katedra teoretické informatiky a matematické logiky

Vedoucí bakalářské práce: Mgr. Martin Pilát, Ph.D. Studijní program: Informatika Studijní obor: Obecná informatika

Praha 2015

Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona.

V . . . . . . . . dne . . . . . . . . . . . .

Podpis autora

i

Chtěl bych poděkovat všem, kteří mi během mého studia na MFF UK byli jakýmkoliv způsobem nápomocní, především pak rodině za podporu a zázemí během celého studia. Hlavně bych ale chtěl poděkovat vedoucímu mé bakalářské práce panu Mgr. Martinovi Pilátovi, Ph.D. za pomoc při výběru tématu práce a také za odborné rady a podněty v průběhu vypracovávání.

ii

Název práce: Genetické programování pro řízení hejna robotů Autor: Michal Filippi Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí bakalářské práce: Mgr. Martin Pilát, Ph.D., Katedra teoretické informatiky a matematické logiky Abstrakt: Homogenní robotická hejna bývají zpravidla řízena programem, který je vytvořen ručně programátorem. Tato práce se zabývá alternativním přístupem, a to možností tvorby řídících programů pomocí techniky inspirované biologickou evolucí, genetickým programovaním. Za tímto účelem byl naprogramován jednoduchý simulátor 2D prostředí, ve kterém je možné vytvořené řídící programy na homogenním hejnu virtuálních robotů testovat a pozorovat. Schopnost genetického programování vytvářet řídící programy je zkoumána na třech různých scénách, ve kterých má robotické hejno za úkol plnit tři různé úkoly. Součástí práce je také porovnání genetického programování s technikou využívající neuronovou síť učenou evolučními strategiemi. Klíčová slova: homogenní robotická hejna; evoluční algoritmy; genetické programování

Title: Genetic Programming for Control of Robotic Swarms Author: Michal Filippi Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Mgr. Martin Pilát, Ph.D., Department of Theoretical Computer Science and Mathematical Logic Abstract: Homogeneous robotic swarms are usually controlled by a manually created program. This thesis studies an alternative approach, the possibilities of creating control programs by means of a technique inspired by biological evolution called genetic programming. A simulator of a simple 2D environment was created for this purpose. This allows us to observe and examine newly created control programs for virtual homogeneous robotic swarm. The ability of genetic programming to create control programs is examined on three different scenarios in which the robotic swarm should deal with three different tasks. The thesis also contains the comparison of genetic programming with a technique that use neural network and evolutionary strategies. Keywords: homogeneous robotic swarms; evolutionary algorithms; genetic programming

1

Obsah Úvod

4

1 Genetické programování a související algoritmy

6

1.1

1.2

Evoluční algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.1.1

Jedinec a populace . . . . . . . . . . . . . . . . . . . . . .

7

1.1.2

Fitness funkce . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.3

Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.1.4

Mutace a křížení . . . . . . . . . . . . . . . . . . . . . . .

9

Genetické programování . . . . . . . . . . . . . . . . . . . . . . .

10

1.2.1

Jedinec v GP . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.2.2

Inicializace nulté generace . . . . . . . . . . . . . . . . . .

11

1.2.3

Evoluční operátory . . . . . . . . . . . . . . . . . . . . . .

12

1.2.4

Silně typované GP . . . . . . . . . . . . . . . . . . . . . .

12

1.2.5

Nekontrolovatelný růst . . . . . . . . . . . . . . . . . . . .

12

2 Rojová robotika 2.1

14

Strojová tvorba řídících programů robotického hejna . . . . . . . .

15

3 Simulátor

18

4 Experimenty

20

4.1

4.2

4.3

Experiment 1: Vyhýbání se překážkám . . . . . . . . . . . . . . .

20

4.1.1

Popis scény . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.1.2

Cíl experimentu . . . . . . . . . . . . . . . . . . . . . . . .

21

4.1.3

Model robota . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.1.4

Nastavení evoluce . . . . . . . . . . . . . . . . . . . . . . .

22

4.1.5

Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Experiment 2: Shlukování . . . . . . . . . . . . . . . . . . . . . .

28

4.2.1

Popis scény . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4.2.2

Cíl experimentu . . . . . . . . . . . . . . . . . . . . . . . .

28

4.2.3

Model robota . . . . . . . . . . . . . . . . . . . . . . . . .

29

4.2.4

Nastavení evoluce . . . . . . . . . . . . . . . . . . . . . . .

30

4.2.5

Metoda evolučních strategií a neuronové sítě . . . . . . . .

30

4.2.6

Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Experiment 3: Prohledávání oblasti . . . . . . . . . . . . . . . . .

36

4.3.1

36

Popis scény . . . . . . . . . . . . . . . . . . . . . . . . . . 2

4.3.2

Cíl experimentu . . . . . . . . . . . . . . . . . . . . . . . .

37

4.3.3

Model robota . . . . . . . . . . . . . . . . . . . . . . . . .

37

4.3.4

Nastavení evoluce . . . . . . . . . . . . . . . . . . . . . . .

38

4.3.5

Metoda evolučních strategií a neuronové sítě . . . . . . . .

40

4.3.6

Člověkem vytvořený řídící program . . . . . . . . . . . . .

40

4.3.7

Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Závěr

46

Seznam použité literatury

48

Obsah přiloženého CD

51

3

Úvod S rostoucí automatizací většiny procesů roste také počet robotů plnících lidmi zadané úkoly. Takoví roboti v některých případech musí být schopni vykonat náročné činnosti, což zvyšuje jejich cenu a složitost konstrukce. Alternativním přístupem může být využití skupiny jednodušších robotů, kteří by samostatně úkol sice nezvládli, ale jejich počet a možnost kooperace jim rozšiřuje pole působnosti. Velkou výhodou takového hejna je možnost decentralizace, kdy při poruše libovolného robota z hejna nebudou funkčnost ani výkon celé skupiny výrazně ovlivněny. Právě proto se robotická hejna hodí do prostředí, kde hrozí vážné riziko poškození. Například je možné hejno jednodušších robotů využít k asistenci hasičského sboru při zásazích v továrních budovách, které jsou velmi rozsáhlé a hasičům zde hrozí nebezpečí a ztráta orientace [1]. V takovém případě může hejno provádět prohledávání hořícího objektu, hledání obětí nebo navigování hasičů. Výzvou pro programátory je navržení a zpracování řídících systémů pro roboty v hejnu tak, aby byli schopni efektivně vykonávat zadaný úkol. Možným řešením může být takový program netvořit lidskou silou, ale využít některou z metod strojové tvorby programů, jako je například genetické programování.

Cíl práce Cílem této práce je vyzkoušet, popsat a zhodnotit možnost vytváření řídících programů pomocí genetického programování (GP) [2] pro homogenní hejno autonomních robotů, tedy hejno stejných robotů řízených identickým programem, kteří se rozhodují pouze na základě vlastních informací a nejsou řízeni žádným centrálním bodem. Testování proběhne na sérii scénářů vyžadujících plnění jednodušších úkolů hejnem. Za tímto účelem vyvineme simulátor, ve kterém bude možné vytvořené programy testovat a pozorovat. Na vybraném scénáři implementujeme také některou z jiných metod strojové tvorby programu a provedeme srovnání s genetickým programováním.

Struktura práce Práce je rozdělena do několika částí. První část je věnována obecnému seznámení s genetickým programováním a souvisejícími algoritmy na úrovni nutné k pochopení jejich principů. V druhé části jsou zmíněny související práce zabývající se 4

rojovou robotikou a především programováním robotického hejna s důrazem na použité metody pro návrh a tvorbu řídících programů. Dále následuje série vlastních experimentů založených na genetickém programování, které jsou v závěru práce zhodnoceny.

5

1. Genetické programování a související algoritmy Genetické programování (GP) [2] spadá do skupiny algoritmů stochastického prohledávání inspirovaného přirozenou selekcí a biologickou evolucí. Tato skupina se nazývá evoluční algoritmy (EA) [3]. EA si v další části popíšeme obecněji a následně se zaměříme na samotné GP.

1.1

Evoluční algoritmy

Následující část popisující evoluční algoritmy je vypracována na základě knih od A. Eiben a spol. [3] a D. Fogela a spol. [4]. Snaha hledat řešení problémů pomocí principů Darwinovy evoluce sahá až do 40. let 20. století, tedy ještě před rozmach počítačů. Nicméně k prvním experimentům spuštěným na počítači začalo docházet až na přelomu 50. a 60. let, za těmito pokusy stáli například Friedberg (1958) [5] nebo Bremermann (1962) [6]. Ke konci 60. let začaly vznikat EA v podobách, jaké je známe dnes. V Německu v roce 1965 dal I. Rechenberg vzniknout evolučním strategiím (ES) [7], L. Fogel v roce 1966 položil základ evolučnímu programování (EP) [8] v Kalifornii a genetické algoritmy (GA) vznikly v roce 1975 v Michiganu zásluhou J. Hollanda [9]. GP se do rodiny EA přidalo až na začátku 90. let, a to díky J. Kozovi [10]. ES, EP a GA se v této práci budeme věnovat pouze okrajově. Jak již bylo naznačeno výše, EA slouží k nalezení suboptimálního řešení optimalizačního problému prohledáváním prostoru řešení pomocí metod inspirovaných přírodou. Hledání EA probíhá iterativně v krocích nazývaných generace, každá generace obsahuje populaci (multimnožinu1 ) řešení, neboli jedinců. Každou generaci je každý jedinec v populaci ohodnocen funkcí fitness, která hodnotí jedince na základě kvality řešení, které jedinec reprezentuje. Přechod mezi jednotlivými generacemi probíhá vytvořením nových jedinců a výběrem nové populace. Tvorba nových řešení probíhá buď kombinací několika již stávajících jedinců, tedy křížením jedinců, nebo upravením nějakého řešení, neboli mutací jedince. Většinou se aplikují obě tyto operace. Výběr jedinců pro křížení (tj. rodičů) a jedinců, kteří vytvoří novou generaci, zajišťuje proces zvaný selekce. Ukončující podmínkou algoritmu typicky bývá dosáhnutí předepsaného počtu generací, nalezení dostatečně dobrého jedince, dosažení časového limitu nebo kombinace 1

Multimnožina je zobecnění množiny, které může obsahovat více identických prvků.

6

Obrázek 1.1: Schéma jednoduchého EA. předchozích. Obecný EA se všemi základními komponentami znázorňuje obrázek 1.1. Je nutné zdůraznit, že většina částí EA je řízena náhodou. Vysoká hodnota fitness funkce nezaručuje jedincovi přežití do další generace ani přežití jeho případných potomků, pouze poskytuje větší šanci. Stejně tak křížení a mutace nastává pouze s jistou pravděpodobností, navíc způsob křížení a mutace bývá zpravidla také náhodný. Řízení náhodou poskytuje EA diversitu populace a částečnou ochranu před uvíznutím v lokálním optimu. EA jsou vhodnou metodou na řešení problémů, u nichž neumíme nalézt optimální ani suboptimální řešení klasickými deterministickými metodami, případně by jejich hledání bylo velmi náročné, ale jsme schopni posoudit kvalitu každého možného řešení. Dobrým příkladem takových problémů mohou být NP-úplné problémy. Následuje detailnější popis a vysvětlení jednotlivých komponent EA zmíněných v předchozích odstavcích.

1.1.1

Jedinec a populace

Jedinec je datová struktura kódující jedno řešení optimalizačního problému. Volba konkrétní reprezentace jedince je základní krok EA a je od něj odvozena volba dalších komponent, především křížení a mutace. Také proto typ jedince slouží jako základní způsob dělení EA, jak ukazuje tabulka 1.1. Populace je multimnožina jedinců v rámci jedné generace. Její velikost bývá typicky konstantní po celý běh EA, což je zajištěno selekcí jedinců. Na začátku EA bývají jedinci tvořící nultou generaci generováni náhodně, ale v některých

7

Tabulka 1.1: Jednoduché rozdělení EA na základě reprezentace jedince a významu operátorů. Typ EA

Jedinec

Evoluční operátory

Genetické algoritmy

Vektor celých čísel

Mutace, křížení

Genetické programování

Strom

Mutace (ne vždy), křížení

Evoluční strategie

Vektor floating-point Mutace (výraznější) i křížení

Evoluční programování

čísel Konečný automat

Většinou pouze mutace

případech je vhodné použít i jedince vzniklé v dřívějším běhu EA nebo jinak vzniklé jedince.

1.1.2

Fitness funkce

Fitness funkce přiřazuje jedincům hodnoty podle kvality řešení, které kódují, a je tedy přímo svázána s optimalizovaným problémem. Z pohledu evoluce fitness reprezentuje podmínky, kterým se populace snaží přizpůsobit, samotné přizpůsobování populace pak zajišťují evoluční operátory, tedy selekce, mutace a křížení. Jednodušší EA uvažují o fitness funkci jako o zobrazení ff it : X → R, kde X je množina všech možných jedinců. Některé pokročilejší EA se ale snaží optimalizovat řešení s několika kritérii [11] a chápou tak fitness jako zobrazení ff it : X → Rk , kde k je počet kritérií. Takové EA již obecně vyžadují komplikovanější verze selekcí, jelikož nemusí existovat vhodné uspořádání na Rk , které by šlo použít pro porovnávání hodnot fitness funkce (nešlo by tedy vždy říci, je-li jedno řešení lepší než druhé). V této práci budě věnována pozornost pouze jednodušší variantě fitness funkce používané v jednokriteriální optimalizaci. Vzhledem k zadání některých optimalizačních problémů může být přirozené zvolit fitness funkci tak, že dobrá řešení funkci minimalizují, mluvíme pak o minimalizačním optimalizačním problému. Takový problém se snadno převede na maximalizační například uvažováním negace funkce nebo převrácením hodnoty funkce (pokud původní ff it : X → (0, ∞)). Pokud nebude uvedeno jinak, budu uvažovat fitness funkci jako maximalizační. Fitness funkce může být také definována jako dynamická funkce, tedy měnící se v čase (rozumějme napříč generacemi). To lze využít pro rozdělení evoluce na několik částí, kdy v každé části jsou přidávány další kritéria fitness funkce. To může mít pozitivní vliv na rychlost hledání řešení díky postupnému vývoji jedinců.

8

1.1.3

Selekce

Selekce slouží k výběru užší skupiny jedinců z populace, což během EA bývá využito ve dvou fázích. První fází je výběr rodičů pro křížení, druhou je pak výběr jedinců pro přežití do další generace. Druhá fáze bývá občas vynechána a EA je nastavený tak, aby každou generaci vyprodukoval tolik potomků, jaká je velikost populace. Další generace je pak tvořena pouze vzniklými potomky. Nejjednodušší metodou selekce je výběr k nejlepších jedinců podle hodnoty fitness funkce. Taková selekce ale může rychle zmenšit genetický fond populace nebo odstraňovat nadějná řešení, která pouze nedostala dostatek času na zdokonalení. Není proto téměř využívána. Naopak nejčastěji používané metody jsou ruletová selekce a turnajová selekce. Obě metody v základní verzi předpokládají fitness typu ff it : X → R, viz 1.1.2. Ruletová selekce při výběru k jedinců pracuje v k krocích. V každém kroku P vygeneruje náhodné číslo r v rozsahu h0, ni=0 fi ), kde n je počet jedinců, ze kterých je užší skupina vybírána, a f1 , f2 , . . . , fn jsou jejich hodnoty fitness. V P každém kroku je vybrán ten jedinec jm , pro kterého platí, že m−1 i=0 fi ≤ r < Pm i=0 fi . Turnajová selekce při výběru k jedinců uspořádá k turnajů, do každého z nich je náhodně vybráno t jedinců (t je parametr turnajové selekce). Každou t-tici jedinců seřadí sestupně podle hodnoty fitness (v případě minimalizačního optimalizačního problému vzestupně) a s pravděpodobností ptur (druhý parametr turnajové selekce) vybere prvního jedince, s pravděpodobností ptur · (1 − ptur ) vybere druhého jedince, třetího s pravděpodobností ptur · (1 − ptur )2 atd. Parametr ptur bývá často nastaven na 1, pak turnajová selekce vždy vybere nejlepšího jedince z turnaje. V případě, že by se v populaci objevil jeden velmi nadprůměrný jedinec, u ruletové selekce by se mohlo stát, že by jedinec a jeho potomci během jedné generace obsadili téměř celou populaci a snížili tak genetický fond celé populace. Tomu turnajová selekce brání náhodným výběrem jedinců do každého turnaje. Často je také využívána technika zvaná elitismus, ta garantuje nejlepším jedincům v populaci přežití do další generace bez ohledu na výsledek selekce.

1.1.4

Mutace a křížení

Mutace i křížení jsou nástroje zajišťující hledání nových řešení problému během EA, jejich princip je ale různý. Mutace je unární operace nad jedinci sloužící obecně k rozšiřování genetického

9

fondu populace, čehož dosahuje náhodnými úpravami jedinců v populaci často na té nejelementárnější úrovni, jakou reprezentace jedince nabízí. Křížení, na rozdíl od mutace, je n-ární (alespoň binární) operace, jejíž cílem je kombinovat již nalezená řešení k hledání nových, v ideálním případě lepších, řešení. Obě operace nenastávají pokaždé, ale pouze se zadanou pravděpodobností. Při neprovedeném křížení bývají často za vzniklé potomky označeni samotní rodiče, to zaručuje konstantní počet vzniklých potomků napříč generacemi, což lze využít k vypuštění selekce na konci generace k výběru přeživších. Role evolučních operátorů se napříč různými EA velmi různí. Například u GP je hlavním operátorem křížení, naopak u ES je většinou křížení úplně vynecháno a tvorbu nových řešení zajišťuje pouze mutace. Samotný způsob mutování a křížení jedinců je přímo spjat s jejich reprezentací, konkrétní metody jsou tedy zmíněny až v sekci 1.2.3 ve spojení se samotným GP.

1.2

Genetické programování

Genetické programování je typ EA umožňující vytvářet celé počítačové programy. K tomu GP reprezentuje jedince souvislou stromovou strukturou (ukázky jednoduchých jedinců jsou zobrazeny v obrázku 1.2). Podobnou strukturou disponuje i řada programovacích jazyků, ve spojení s nimiž bývá GP většinou používáno. Za zmínku takového jazyka stojí například jazyk LISP2 , který použil i J. Koza, považovaný za otce GP, ve svých prvních experimentech v 90. letech [12] a je stále ve spojení s GP používán. Dále v této sekci budou opět podrobněji popsány komponenty EA, nyní ale ve formě, v jaké jsou používány přímo v GP. Následující části jsou čerpány z knih R. Poliho a spol. [2] a M. Mitchella [13].

1.2.1

Jedinec v GP

Strom, kterým je jedinec kódován, je tvořen dvěma typy vrcholů. Terminálové vrcholy se mohou nacházet pouze v listech stromu, naopak funkční vrcholy tvoří vnitřní vrcholy stromu. Každý funkční vrchol má pevně zvolený počet vstupních parametrů (arita funkce). Například u prvního jedince v obrázku 1.2 je množinou funkcí množina {/, +, sin} a množinou terminálů je množina {1, 0, 9}, u druhého příkladu jsou to množiny {if, <} a {x, 1, move, stay}. 2

Lisp je rodina programovacích jazyků, jejichž původní specifikace je z roku 1958. Jedná se

o stále aktivní programovací jazyky používané především v oblasti umělé inteligence.

10

Obrázek 1.2: Dva příklady jednoduchých stromů (jedinců) reprezentující výraz (sin(0) + 9)/1 a program if(x < 7) than move; else stay.

1.2.2

Inicializace nulté generace

Jako u jiných EA bývá nultá generace jedinců vytvořena náhodně, ale nabízí se zde několik možností, jak při generování postupovat. Rozeznáváme tři základní druhy inicializace, u všech je stanoven pevný limit na hloubku3 jedince h. Metoda grow (růstová metoda) staví jedince postupně od kořenu níže. Pokud je hloubka vkládaného vrcholu nižší než h, je tento vrchol vybrán náhodně z množiny funkcí i terminálů. Pokud je hloubka rovna h, je vrchol vybírán pouze z množiny terminálů. Náhodný výběr z obou množin zároveň je velmi náchylný na poměr mezi velikostmi jednotlivých množin. Pokud je množina terminálů výrazně větší, generuje tato metoda malé jedince málokdy dosahující hloubky h. Naopak je-li poměr obrácený, chová se metoda grow téměř stejné, jako následující metoda full. Metoda full (úplná metoda) vygeneruje jedince jako úplný strom hloubky h, tedy strom, ve kterém jsou všechny listy v hloubce h. Při generování jsou tedy vrcholy náhodně vybírány z množiny funkcí až do hloubky h, kdy je vrchol vybírán pouze z množiny terminálů. Třetí metodou je tzv. ramped half-and-half (půlená metoda), která půlku jedinců generuje pomocí metody grow a druhou pomocí metody full. Navíc během generování upravuje stanovenou hloubku h. Generuje tak širší spektrum jedinců než předchozí metody samotné. 3

Hloubka jedince je hloubka nejhlubšího vrcholu v jedincovi. Hloubkou vrcholu rozumíme

délku cesty z vrcholu do kořene.

11

1.2.3

Evoluční operátory

V této části zmíním pouze několik vybraných operátorů používaných v GP, jejich širší přehled lze nalézt například ve výše zmíněné knize od J. Poliho a spol. [2, kap. 2.4]. Jednou ze základních mutací v GP je tzv. subtree mutation (mutace podstromu), která celý podstrom zavěšený pod náhodně vybraným vrcholem v jedinci nahradí nově vygenerovaným stromem. Generování nového podstromu je typicky řízeno technikami grow nebo full zmíněných v sekci 1.2.2. Jinou mutací upravující jedince mírněji než předchozí metoda je tzv. point mutation (bodová mutace), která vymění náhodný vnitřní vrchol jedince za jiný z množiny funkcí se shodnou aritou. Příkladem křížení může být subtree crossover (křížení podstromem), který v obou rodičích vybere náhodně a nezávisle vrchol křížení a prohodí podstromy zavěšené pod těmito vrcholy. Bod křížení není nutné vybírat čistě náhodně, ale může být vhodné vybírat vrcholy ve větší hloubce, aby změna jedinců nebyla tak markantní. Selekce nebere reprezentaci jedince nijak v úvahu, není proto nutné upravovat metody představené v sekci 1.1.3.

1.2.4

Silně typované GP

Silně typované GP [2, kap. 6.2.2] je metoda sloužící jako ochrana proti vzniku syntakticky nesprávných programů během GP. Tomu silně typované GP brání typováním funkcí a terminálů. Každý terminál je označen typem, stejně tak i každá funkce má označené typy parametrů, které přijímá, a typ vrácené hodnoty. Každý vnitřní vrchol stromu tedy může obsahovat pouze syny odpovídající typu parametrů funkce. Například druhý jedinec v obrázku 1.2 by mohl být vhodný kandidát na použití silně typovaného GP. Prvním parametrem funkce if je zde zřejmě výraz vracející hodnotu true nebo false, bylo by tedy syntakticky nesprávné vložit jako prvního syna terminál obsahující číslo 7. Taková omezení při stavbě jedince pak vyžadují pozměněnou inicializaci nulté generace, mutaci i křížení.

1.2.5

Nekontrolovatelný růst

Velikost jedince není v GP nijak principiálně omezena, může se tedy stát, že se zvyšujícím se počtem generací jedinci narůstají do obřích rozměrů, které třeba 12

dalece přesahují velikost optimálního řešení. Metody bránící těmto situacím se nazývají bloat control metody (metody kontrolování růstu) [2, kap. 11.3] a několik základních metod dále popíši. Přirozenou obranou proti bloatu je nastavení pevné maximální velikosti nebo hloubky jedince. V případě, že by při mutaci či křížení vznikl jedinec překračující tyto hodnoty, by byl takový jedinec zahozen a proces mutace či křížení by se opakoval. Alternativou může být neopakování procesu mutace či křížení a vložení původního jedince do nové populace. Bloat mohou kontrolovat i evoluční operátory, například size-fair crossover (spravedlivé křížení), který funguje podobně jako subtree crossover popsané v sekci 1.2.3. Rozdílná je volba bodu křížení ve druhém rodiči. Ta není zcela náhodná, ale probíhá tak, aby oba podstromy zavěšené pod body křížení byly podobně veliké a nenastávala tak situace, že potomek bude výrazně větší než rodič. Podobně lze upravit i subtree mutation ze sekce 1.2.3. Tedy generovat nový podstrom podobně veliký nebo menší než původní podstrom zavěšený pod bodem mutace. Jinou jednoduchou mutací kontrolující bloat je shrink-mutation (zkracující mutace), která náhodně vybraný bod a celý jeho podstrom nahradí pouze jedním terminálem. I selekci lze použít jako metodu obrany před bloatem. Například metoda zvaná parsimony pressure nepracuje během selekce přímo s hodnotou fitness, ale s její hodnotou sníženou o součin velikosti jedince a vhodné konstanty. Velkým jedincům je tedy snížena šance na reprodukci a přežití do další generace, takoví jedinci pak budou více vymírat a v populaci se budou šířit menší jedinci. Zajímavé srovnání bloat control metod vypracoval Luke a Panit v roce 2006 [14]. Podle této práce by napříč různými problémy měla nejlepších výsledků dosahovat linear parametric parsimony pressure (pokročilejší verze parsimony pressure). Druhým zajímavým poznatkem je, že každá z pokročilejších metod si vedla alespoň stejně dobře, pokud byla doplněna základním omezením hloubky jedinců.

13

2. Rojová robotika Tato část bude popsána na základě přehledových prací Tana a spol. [15] a Mohana a spol. [16]. Rojová robotika se zabývá výzkumem v oblasti početnějších skupin jednoduších robotů spolupracujících za účelem vykonávání komplexnějších úkolů. Takový přístup je inspirován mnoha organismy v přírodě, například hejny ptáků a ryb nebo primáty. Především je ale inspirovaný některými zástupci hmyzu žijících v koloniích, kteří pouze za pomoci lokální a omezené komunikace dokáží plnit velké množství obtížných úkolů, jako například shánění potravy pro celou kolonii, bránění a stavbu rozsáhlých hnízd nebo pečování o mladé jedince [17]. Oproti alternativnímu přístupu, tedy komplexnímu robotovi, který vykonává zadaný úkol sám, se robotický roj vyznačuje především: Paralelností Robotické hejno se může bez většího omezení věnovat více úkolům zároveň podle aktuálního přerozdělení hejna. Škálovatelností Komunikace mezi samotnými roboty bývají zpravidla lokální a omezené, řídící program tedy musí zvládat komunikaci s libovolným množstvím dalších robotů, kteří jsou zrovna v dosahu. To umožňuje, aby se kdykoliv do hejna mohl přidat či z hejna odebrat další robot, aniž by to výrazně ovlivnilo činnost celého roje. Stabilitou Poškození nebo zničení malé části hejna nemá díky škálovatelnosti zásadní vliv na provádění úkolu. Ekonomičností Cena návrhu a vytvoření roje robotů je výrazně nižší než návrh a výroba složitého robota, a to především díky nižším nárokům na spolehlivost, možnosti velkovýroby, jednoduchosti robotů. Dosahem Jednoduchost robotů v hejnu umožňuje roboty zkonstruovat v menších rozměrech než komplexního robota, což hejnu umožňují dostat se na místa, kam by se vetší a složitý robot nedostal. Díky výše zmíněným vlastnostem se robotické roje hodí do prostředí, která jsou těžko dostupná a hrozí v nich robotům velké riziko poškození. Toho využívala 14

i práce [1] zmíněná v úvodu, která navrhovala robotické hejno asistující hasičským jednotkám při zásazích v hořících budovách. Jako jiný příklad využití rojové robotiky je možné zmínit projekt Seaswarm [18], který vznikl na Massachusetts Institute of Technology. Seaswarm je hejno robotů určených k odstraňovaní ropných havárií na mořích a oceánech. Každý robot zabírá přibližně plochu 10m2 , je plně autonomní, poháněný sluneční energií a je schopen komunikovat s ostatními členy hejna za účelem koordinace úklidu ropy. K samotnému úklidu pak využívá speciální materiál, který dokáže absorbovat až dvacetinásobek své váhy v ropě. Dalším příkladem může být práce N. Corrella a A. Marinoliho [19], ve které autoři navrhli hejno malých robotů kontrolující stav proudových turbín letadel. Při reálné aplikaci rojové robotiky je mimo samotné konstrukce robotů potřeba vyřešit také navržení a naprogramování řídícího programu robotů. To je zatím zpravidla řešeno klasickým přístupem pomocí lidského programátora. Nabízí se ale také možnost nechat řídící program vytvořit počítačem.

2.1

Strojová tvorba řídících programů robotického hejna

Odborných článků zaměřených na robotické roje je k nalezení poměrně velké množství, ale pouze jejich malá část se zabývá přímo strojovým návrhem řídícího programu pro robotický roj. Většina těchto prací pak využívá evoluční strategie, a to k hledání vah neuronové sítě, která rozhoduje o akcích robota na základě hodnot přečtených z jeho senzorů. V této oblasti je velmi aktivní především Middle East Technical University v Turecku a Université Libre de Bruxelles v Belgii. Jedním z prvních článků je práce z roku 2003 od V. Trianniho a spol. [20], ve které se autoři zabývají shlukováním homogenního hejna tzv. s-botů na mapě. S-bot je model autonomního robota disponující dvojicí kol, sérií osmi senzorů přiblížení rozmístěných podél těla robota, trojicí mikrofonů a jedním všesměrovým reproduktorem s omezeným dosahem. Roboti také disponovali uchytávacím zařízením, které jim umožňovalo se připojit k jinému s-botovi a vytvářet tak shluky robotů. Této schopnosti robotů autoři nevyužili, cílem jejich práce bylo pouze shlukování hejna. Shlukování hejna spočívá v hledání se robotů navzájem a vytváření skupin robotů koncentrovaných na jednom místě. Samotné shlukování nebylo nijak řízeno vnějšími podmínkami, jako je například světelnost nebo vlhkost, jednalo se tedy o tzv. samovolné shlukování. Řízení robota zajišťovala jednoduchá neuronová síť složená pouze ze vstupních neuronů (senzory robota) a dvou výstupních neuronů (levé a pravé kolo robota). Váhy této neuronové sítě 15

byly hledány pomocí evolučních strategií. Část této práce byla také věnována rozdělení vyvinutého chování na statické shlukování a dynamické shlukování. Během statického shlukování se roboti přestali po shluknutí pohybovat, naopak během dynamického shlukování roboti dále pokračovali v pohybu, což jim znemožňovalo přiblížit s k ostatním robotům do těsné blízkosti. Na druhou stranu se dynamické shlukování ukázalo jako robustnější a změna velikosti robotického hejna nebo velikosti prostředí měla výrazně menší vliv na schopnost se shluknout. Dynamické shlukování bylo stále schopné vytvářet velké skupiny robotů, zatímco statické shlukování mělo tendenci vytvářet větší množství menších shluků. Na tuto práci v roce 2004 nepřímo navázali Dorigo a spol. [21], kteří se nezabývali pouze shlukováním s-botů, ale také koordinovaným pohybem celé skupiny s-botů propojených uchytávajícím zařízením. Za tímto účelem byli roboti vybaveni dalším senzorem, který jim pomáhal určit směr pohybu celé skupiny. Řízení robotů probíhalo velmi podobně jako v předchozí práci, tedy pomocí neuronové sítě řízené ES. V rámci koordinovaného pohybu byly robotům pro jednoduchost odstraněny senzory přiblížení. Bez nich mohlo robotické hejno rozpoznávat okolní překážky pouze po kolizi s některým z členů shluku díky senzoru pohybu skupiny. Nicméně i přes takové omezení bylo propojené hejno robotů schopno se překážkám do značné míry vyhnout a na žádné z překážek roj neuvízl. Koordinovaným pohybem propojených robotů se zabýval i G. Baldassarre a spol. [22] v roce 2006. Úkolem robotů ale nebyl samotný koordinovaný pohyb, ale hledání zdroje světla v aréně. Ta obsahovala mimo samotných překážek také žlábky a díry, které samotní s-boti nejsou schopni překonat, ale v propojeném stavu toho schopni jsou. Práce také ukazuje schopnost vyvinutého řešení velmi dobře zvládat změnu počtu propojených robotů tvořících pohybující se shluk. Koordinovaný pohyb byl také předmětem práce V. Trianniho z roku 2006 [23]. Ta byla zaměřena především na vyhýbání se spojených robotů dírám v povrchu, které již byly dostatečně velké na zapadnutí celé skupiny propojených robotů. Pro rozpoznávání děr v povrchu byli roboti vybaveni čtyřmi senzory přiblížení, které byly umístěny pod robotem a nasměrovány do země. Odlišný úkol se snažili řešit V. Sperati a spol. [24] v roce 2011, kteří dali hejnu robotů za úkol navigovat se mezi dvěma vzdálenými oblastmi. V rámci svých simulací využívali model tzv. e-puck robota. E-puck je kruhový robot poháněný dvěma koly, vybavený osmi senzory přiblížení, senzorem reagujícím na barvu povrchu pod robotem, osmi RGB LED, díky kterým roboti dokázali reprezentovat určité stavy, a senzory detekující barvy vyzařované okolními roboty. V rámci této

16

práce byly diody pro jednoduchost omezeny pouze na modrou a červenou barvu. Řízení robotů pak zajišťovala neuronová síť, která mimo vstupních neuronů (senzory robota) a výstupních neuronů (kola robota a LED) obsahovala také tři skryté neurony. Učení neuronové sítě opět zajišťovaly ES. V prostředí bez překážek robotický roj dokázal po nalezení obou oblastí, mezi kterými se měli roboti pohybovat, vytvořit řetězec pohybujících se robotů a efektivně se tak navigovat mezi oběma oblastmi. Navíc díky pohybu v řetězeci našli roboti postupem času přímou trasu mezi oběma oblastmi. V roce 2006 publikovali O. Soysal a spol. [25] práci, která se, jako již dříve zmíněné práce, zabývala samovolným shlukováním robotického roje v simulátoru obsahujícím překážky. Krom toho se ale také práce zaměřila na možnosti nastavení několika zajímavých parametrů evoluce, které mají výrazný vliv na výsledná nalezená řešení. Některé z popsaných doporučení jsou dále vypsány. 1. Volné výpočetní prostředky by měly být využity k vícenásobnému otestování jednoho jedince při výpočtu fitness funkce (za předpokladu, že každá simulace vrací jiný výsledek, tedy např. při náhodném rozestavování robotů po ploše na začátku simulace) raději než k prodloužení délky jednotlivých simulací. Délku simulací je vhodné nastavit na nejkratší délku, která by robotům měla stačit ke splnění zadaného úkolu. 2. Optimální poměr mezi počtem generací a počtem simulací při vyhodnocení fitness funkce nelze dopředu určit. Doporučeným postupem je spustit několik málo běhů s velkým počtem generací a na základě těchto běhů rozhodnout o vhodném počtu generací. 3. Při vícenásobném spouštění simulace při výpočtu fitness funkce je vhodné parametry simulace měnit, například měnit rozestavení překážek, velikost arény, velikost robotického hejna atd. To napomáhá vyvinutí robustnějších jedinců, kteří lépe zvládají případné další změny v simulátoru. Výše zmíněné práce dosahovaly pomocí EA a neuronové sítě dobrých výsledků, robotické roje byly schopny zadané úkoly plnit dostatečně kvalitně. Hlavní výhodou ale byla robustnost nalezených řešení, změna velikosti hejna nebo změna prostředí většinou neznamenala výrazný problém pro plnění úkolu. K tomu navíc většina zmíněných prací využívala model robotů s-bot, který je navržen tak, aby do značné míry zaručovat i přenositelnost řídících programů na fyzické roboty.

17

3. Simulátor Součástí této práce je také simulátor, na kterém v další části provedeme sérii experimentů. Všechny části simulátoru jsou naprogramovány v jazyce Python 2.7, některé jeho části jsou pak také implementovány v jazyce C, což umožňuje uživateli zvýšit výkon simulátoru. Simulátor je možné spustit dvěma možnými způsoby, a to skrze programy run_evolution.py a animator.py. Program run_evolution.py slouží ke spouštění samotných evolučních algoritmů pomocí knihovny DEAP [26]. Vyvinuté jedince v rámci vyhodnocení fitness funkce program testuje v simulátoru jednoduchého 2D prostředí na homogenním robotickém hejnu. Typ a nastavení evolučního algoritmu spolu s konfigurací simulátoru prostředí jsou uloženy v externím souboru, který je programu předáván jako parametr. Lze tedy tento simulátor využít i k jiným evolučním algoritmům než jen GP, což bude v této práci také využito. Tento program nemá grafický výstup, výstupem je pouze průběh evoluce vypisovaný do konzole a výstupní soubor. V něm jsou především uloženi všichni vyvinutí jedinci a nastavení evoluce, během které vznikli. Výstupní soubor z programu run_evolution.py slouží jako vstupní soubor pro program animator.py, který uživateli dovoluje prohlížet si vyvinuté jedince a především pomocí videa pozorovat jejich chování v simulátoru. Tento program obsahuje jednoduché grafické prostředí 3.1, které uživateli dovoluje snadno upravovat parametry arény, tedy měnit její rozměr, upravovat překážky a zdroje světla, měnit délku simulace a velikost robotického hejna. Zároveň také program umožňuje upravovat vyvinuté řídící programy, případně navrhovat své vlastní. Na CD přiloženém k této práci je celý simulátor uložen i spolu s uživatelskou a programátorskou dokumentací. Na tomto CD jsou umístěny také všechny výstupní soubory ze všech evolucí provedených v rámci této práce. Ty je možné snadno zopakovat, návod, jak to lze provést, je napsán v uživatelské dokumentaci.

18

Obrázek 3.1: Jednoduché grafické prostředí programu animator.py pro pozorování vyvinutých jedinců EA.

19

4. Experimenty Cílem série experimentů provedených v této části je popsat a zhodnotit možnost vytváření řídících programů pro homogenní hejno robotů pomocí GP. Jedincem v GP bude celý řídící program, který je v rámci fitness funkce testován na hejnu robotů v jednoduchém 2D simulátoru. Ten kromě samotné simulace také ohodnotí schopnost robotů řízených tímto programem plnit zadaný úkol. Simulace je omezena počtem kroků, po dosáhnutí tohoto limitu je simulace zastavena a kvalita řídícího programu ohodnocena (způsob ohodnocení se liší podle konkrétního úkolu). V každém kroku simulace je v každém robotovi z hejna spuštěn řídící program, který na základě senzorů rozhodne, jakou činnost v tomto kroku robot provede. Vzhledem k typu hledaného řešení (program) bylo zvoleno silně typované GP, jehož parametry byly ve všech experimentech nastaveny stejně kromě počtu generací a množin funkcí a terminálů. Tato rozdílná nastavení jsou vždy popsána až v sekcích se samotnými experimenty. Během všech experimentů byla velikost populace nastavena na 100 jedinců, použita byla turnajová selekce vybírající vždy nejlepšího jedince v turnaji, přičemž velikost turnaje byla 8 jedinců. Mutací byla subtree mutation, kde nové podstromy byly generovány metodou grow s maximální hloubkou 2, a křížením byla metoda subtree crossover, obě tyto metody byly zmíněny v sekci 1.2.3. Pravděpodobnost, že nastane mutace, byla nastavena na 0.2 a pravděpodobnost, že nastane křížení, na 0.8. Jako ochrana před bloatem byla na obou těchto operátorech nastavena maximální hloubka vzniklého jedince na 10. Nultá generace byla vytvářena metodou ramped half-and-half s hloubkou stromu mezi 1 a 3. Záznamy všech evolucí provedených během všech následujících experimentů jsou uloženy v příloze této práce, kde je také k dispozici program animator.py umožňující pozorovat chování vyvinutých řídících programů na virtuálních robotech v arénách.

4.1

Experiment 1: Vyhýbání se překážkám

Prerekvizitou komplexnějšího chování robotů je jejich schopnost vyhnout se kolizím s ostatními prvky v aréně. Proto první experiment je zaměřen právě na samotné řízení jízdy a vyhýbání se překážkám.

20

4.1.1

Popis scény

Scéna simulace je tvořena čtvercovou arénou s délkou hrany 40 jednotek ohraničenou neprůchodnou bariérou. V aréně se také vyskytují překážky různých tvarů bránící robotům ve volném pohybu. Během GP jsou jedinci testováni v arénách se čtyřmi různými sestaveními překážek, všechny jsou znázorněny v obrázku č. 4.1. Každá simulace trvá právě 400 kol a do simulátoru bylo vždy vpuštěno hejno robotů čítající 5 členů. Počáteční pozice a natočení každého robota jsou při každé simulaci zvoleny náhodně.

Obrázek 4.1: Nákres arén použitých během experimentu č. 1. Šedý okraj reprezentuje ohraničení arény, oranžové oblasti reprezentují překážky.

4.1.2

Cíl experimentu

Cílem experimentu je vyvinout pomocí GP řídící program robotů, který se především snaží vyhnout srážkám s ohraničením bariéry, s překážkami v aréně a s ostatními roboty. Takové kritérium by nejlépe splňovali roboti, kteří by pouze stáli na místě, proto druhou žádanou vlastností řídících programů je snaha najezdit s roboty co nejdelší vzdálenost.

4.1.3

Model robota

Model robota má kruhový tvar o průměru 1 jednotka a disponuje trojicí senzorů přiblížení pravidelně rozmístěných na přední straně robota pod úhly −45◦ , 0◦ , +45◦ od směru pohybu. Výstupem každého z těchto senzorů je hodnota min(1, d3 ), kde d je vzdálenost k nejbližšímu objektu ve směru senzoru. Ze předchozího vzorce lze také vyčíst, že dosah těchto senzorů jsou 3 jednotky. Každý robot je dále vybaven párem nezávisle poháněných kol, každé kolo se tedy může otáčet jinou rychlostí, což umožňuje robotovi zatáčet. Kola mají dovolený i pohyb zpět, to robotům dovoluje se otáčet na místě nebo se pohybovat pozpátku. Rychlost robota nemůže překročit 0.5 jednotek za jeden krok simulace. Kola jsou ve vzájemné vzdálenosti 0.5 jednotek. Model robota je nakreslen v obrázku č. 4.2. 21

Obrázek 4.2: Model robota použitého v experimentu č. 1. Modrý oblouk znázorňuje přední stranu robota, zelené obdélníky znázorňují kola a červené úsečky znázorňují senzory přiblížení (jejich délka proporcionálně neodpovídá dosahu senzorů, všechny 3 senzory mají stejný dosah).

4.1.4

Nastavení evoluce

Evoluce byla ukončena po 40. generaci. Terminály i funkce byly pouze dvou typů, a to float (desetinné číslo) a tuple (dvojice desetinných čísel). Celý jedinec po vyhodnocení vrací dvojici (wl , wr ) (kořen jedince tedy musí být typu tuple), která je použita k určení rychlosti levého a pravého kola v aktuálním kroku simulace. Rychlost levého resp. pravého kola se pak spočítá jako wl0 ∗ S resp. wr0 ∗ S, kde S je maximální rychlost robota a pro wl0 a wr0 platí:

wl0 =

    −1 pokud wl < −1, 1 pokud wl > 1,    w jinak. l

wr0 =

    −1 pokud wr < −1, 1 pokud wr > 1,    w jinak. r

Samotnou množinu funkcí resp. terminálů, ze kterých jsou jedinci konstruováni, lze nalézt v tabulce č. 4.1 resp. tabulce č. 4.2. Vzhledem k náhodnému rozmisťování robotů na začátku každé simulace nebylo možné vzniklé řídící programy hodnotit na základě jedné simulace. Každý jedinec byl tedy do simulátoru vložen 8x, dvakrát na každou z map vykreslených v obrázku č. 4.1. Během každé simulace byl zaznamenáván počet kolizí se zdí (Cw ), počet kolizí s překážkou (Co ), počet kolizí mezi roboty (Cb ). Mimo to byla také zaznamenávána celková ujetá vzdálenost roboty (D), do které byl započítáván pouze pohyb směrem dopředu. Pokud by se započítával i pohyb zpět, s 22

Tabulka 4.1: Množina funkcí použitá během GP v experimentu č. 1. Zápis Typ Arita Typy argumentů Popis con

tuple 4

float, float, tuple,

Podmínka if arg1 > arg2

float

tuple float, float, float,

then arg3 else arg4 Podmínka if arg1 > arg2

wheels tuple 2

float float, float

then arg3 else arg4 Vytvoření dvojice pro ovládání kol.

add

float

2

float, float

Operátor sčítání.

sub

float

2

float, float

Operátor odčítání.

mul

float

2

float, float

Operátor násobení.

con2

4

Tabulka 4.2: Množina terminálů použitá během GP v experimentu č. 1. Zápis Typ Popis (0, 0)

tuple Reprezentace stání na místě.

(1, 1)

tuple Reprezentace pohybu dopředu plnou rychlostí.

(−1, −1) tuple Reprezentace pohybu zpět plnou rychlostí. (0, 1)

tuple Reprezentace otáčení se doleva s pohybem vpřed.

(1, 0)

tuple Reprezentace otáčení se doprava s pohybem vpřed.

(0, −1)

tuple Reprezentace otáčení se doprava s pohybem vzad.

(−1, 0)

tuple Reprezentace otáčení se doleva s pohybem vzad.

(1, −1)

tuple Reprezentace otáčení se na místě doprava.

(−1, 1)

tuple Reprezentace otáčení se na místě doleva.

1

float

Číslo 1.

0

float

Číslo 0.

−1

float

Číslo -1.

uni(0, 1)

float

Náhodně vygenerovaná hodnota v intervalu od 0 do 1.

irL

float

Hodnota čtená z levého senzoru přiblížení.

irF

float

Hodnota čtená z předního senzoru přiblížení.

irR

float

Hodnota čtená z pravého senzoru přiblížení.

23

velkou pravděpodobností by byl nejúspěšnějším jedincem program, který by se pohyboval plnou rychlostí rovně až do rozpoznání překážky, na kterou by zareagoval pohybem plnou rychlostí zpět. To by kvůli absenci paměti robotů vyústilo v zastavení všech robotů před překážkou a střídání pohybu dopředu a zpět, což jistě není chtěné chování. Každá jedna simulace pak byla ohodnocena funkcí l1 · D + l2 · Cw + l3 · Co + l4 · Cb , R·N kde N je počet robotů v simulátoru, R je počet kroků simulace a l1 , l2 , l3 , l4 Fexp1 =

jsou konstanty. Na základě série pokusů byly tyto konstanty nastaveny na l1 = 1, l2 = l3 = −2.5, l4 = −0.5. Výsledky všech osmi simulací byly zprůměrovány a průměr vrácen jako hodnota fitness funkce.

4.1.5

Výsledky

Většina vyvinutých řídících programů se v simulátoru chovala velmi podobně. Roboti se pohybují dopředu až do chvíle, kdy narazí na nějaký objekt. Na ten zareagují primárně otočením doleva, pokud otočení doleva není možné, zvolí opačný směr. To v menším počtu robotů vyústí v kroužení robotů po obvodu arény proti směru hodinových ručiček. Pokud některá z překážek brání pohybu okolo ohraničení arény, krouží roboti po menším prostoru. Chování nejlepšího jedince z poslední generace GP na všech testovaných sestaveních překážek je znázorněno v obrázku č. 4.3. U nejlepšího jedince z poslední generace byla také testována škálovatelnost, neboli schopnost řídícího programu obstát i v simulaci s jiným nastavením, než v jakém byl program vyvinut. Během evoluce byl program testován na 4 různých skupinách překážek, což by do značné míry mělo zaručovat jeho schopnost dobře se pohybovat i mezi jinými překážkami, než na kterých byl vyvinut. To bylo také úspěšně ověřeno pomocí série experimentů. Velikost arény a hejna ale byla během evoluce neměnná, nabízí se proto otestovat vlastnosti programu při změně těchto parametrů. Konkrétně je především zajímavý jejich poměr, neboli hustota robotů v aréně. Proto během tohoto testu zůstala velikost arény na 40 jednotkách, měnila se pouze velikost robotického hejna, a to v rozmezí od 1 robota do 50 robotů. Test proběhl na druhém sestavení překážek z obrázku 4.1 s délkou simulace 400 kroků. Výsledky jsou zaneseny v obrázcích č. 4.4, 4.5 a 4.6. Test škálovatelnosti vyvinutého řídícího programu ukázal, že velikost hejna má největší vliv na počet srážek mezi samotnými roboty, který se zdá, že roste

24

Obrázek 4.3: Znázornění chování nejlepšího jedince z poslední generace GP v experimentu č. 1 na všech testovaných arénách. Šedé tečky jsou původní pozice robotů na začátku simulace, modré tečky jsou koncové pozice robotů na konci simulace, modré křivky reprezentují pohyb robotů po aréně.

25

Obrázek 4.4: Graf znázorňující počet srážek mezi roboty v průměru na jednoho robota během celé simulace v závislosti na velikosti robotického hejna. Zobrazena je také směrodatná odchylka. Pro každou velikost hejna byla simulace spuštěna 100x.

Obrázek 4.5: Graf znázorňující počet srážek robota s překážkou v aréně v průměru na jednoho robota během celé simulace v závislosti na velikosti robotického hejna. Zobrazena je také směrodatná odchylka. Pro každou velikost hejna byla simulace spuštěna 100x.

26

Obrázek 4.6: Graf znázorňující počet srážek robota s ohraničením arény v průměru na jednoho robota během celé simulace v závislosti na velikosti robotického hejna. Zobrazena je také směrodatná odchylka. Pro každou velikost hejna byla simulace spuštěna 100x. lineárně s velikostí robotického hejna. To do značné míry může být dáno i nižším počtem senzorů přiblížení, kvůli kterému nemají v některých případech roboti možnost druhého robota zaznamenat. To v extrémních případech může vyústit v dočasné nebo trvalé zaklesnutí dvou robotů do sebe. Ti takovou situaci nemohou rozpoznat, jelikož nemají žádnou zpětnou vazbu při nárazu. Tyto situace jsou viditelné i v grafu, kde způsobují velký nárůst směrodatné odchylky. O něco lépe si program vedl v kontextu počtu srážek robotů s překážkou, který zůstal pro všechny velikosti hejna velmi malý. Zajímavý je zde velký nárůst směrodatné odchylky okolo hejna čítající 30 robotů a více. To je pravděpodobně způsobeno velkou koncentrací robotů na malém prostoru, který může vyústit ve vytlačení některého z robotů do překážky, na které může robot uvíznout. Nejmenší vliv měla velikost hejna na počet srážek s ohraničením bariéry, které jsou dostatečně velké na to, aby je robot za každé situace byl schopen pomocí senzorů přiblížení rozpoznat. Většina nárazů do ohraničení navíc proběhne na začátku simulace, a to kvůli náhodnému rozmisťování robotů po aréně, kdy je některý z robotů umístěn příliš blízko okraji arény a otočený směrem do ohraničení.

27

Shrnutí Vyvinuté řídící programy zadaný úkol plnily poměrně úspěšně, valná většina simulací dopadla velmi uspokojivě. Slabší stránkou byla absence zpětné vazby při nárazu, kvůli které robot nemá žádné prostředky, jak určit, jestli v předchozím kole nebyla jeho snaha popojet zablokována jiným objektem. To způsobilo, že v několika málo bězích robot uvízl na překážce či ohraničení arény nebo se roboti zaklesli do sebe. V takové pozici často zůstali dlouho. Přidání senzoru indikující náraz by mohlo pomoci robotovi v detekci okolních předmětů, které třeba nemohl zaznamenat pomocí senzorů přiblížení, a tím vylepšit jeho výkon.

4.2

Experiment 2: Shlukování

Síla robotického roje spočívá v jeho velikosti a především v kooperaci robotů, k té je ale často potřeba roboty nejdříve seskupit na jedno místo. A právě shromažďování robotického hejna v simulátoru bude cílem tohoto experimentu. Samovolné shlukování bylo také cílem několika dřívějších prací [20, 21, 25] používajících k tomu evoluční strategie ve spojení s jednoduchou neuronovou sítí. Proto v rámci tohoto experimentu také implementujeme i tento postup a provedeme jeho srovnání s GP.

4.2.1

Popis scény

Vyvinutí jedinci budou testování opět ve 4 různých prostředích, které se liší rozestavením překážek a navíc také rozměrem čtvercové arény. Dvě menší arény mají délku hrany 40 jednotek, větší arény pak 60 jednotek. S velikostí arén se také pojí délka simulace a počet jedinců v aréně. U menších arén simulace trvá 300 kol a v aréně je pětičlenné hejno robotů a u větších trvá simulace 450 kroků a hejno robotů čítá osm členů. Arény, ve kterých budou vyvinutí jedinci testováni, jsou zobrazeny v obrázku č. 4.7.

4.2.2

Cíl experimentu

Cílem experimentu je nalézt řídící programy vedoucí roboty k samovolnému vytváření shluků na mapě a zároveň se vyhýbat kolizím s ostatními prvky v aréně. Dobrá řešení by měla preferovat vytváření menšího počtu velkých shluků, v ideálním případě pak jediný shluk robotů v celé aréně.

28

Obrázek 4.7: Nákres arén použitých během experimentu č. 2. Šedý okraj reprezentuje ohraničení arény, oranžové oblasti reprezentují překážky. Okraj arén je vždy široký 5 jednotek, což lze využít k lepšímu získání odhadu velikosti arény.

4.2.3

Model robota

Základ modelu robota zůstane stejný jako v předchozím experimentu, ale vzhledem k úkolu, který mají roboti plnit, musí být každý robot navíc schopen rozpoznat množství dalších robotů ve svém okolí. Za tímto účelem bylo robotům přidáno vybavení inspirované již zmíněnými pracemi [20, 21, 25], které se také zabývali shlukováním robotů. Konkrétně se jedná o reproduktor, který neustále vysílá do svého okolí signál, a 4 mikrofony pravidelně rozmístěné po obvodu robota, které jsou schopny zachytit signál z reproduktorů vzdálených až 20 jedP notek. Výstup z každého mikrofonu lze spočítat jako r∈R d1r 2 , kde R je množina reproduktorů vzdálených od daného mikrofonu do 20 jednotek a dr je vzdálenost mikrofonu od reproduktoru r. Model robota je znázorněn v obrázku č. 4.8.

Obrázek 4.8: Model robota použitého v experimentu č. 2. Oproti modelu z experimentu č. 1 přibyl reproduktor (reprezentován fialovým kolečkem) a 4 mikrofony na okraji robota (reprezentované šedými čtverci).

29

4.2.4

Nastavení evoluce

Délka evoluce byla nastavena na 100 generací. Typ jedince a způsob jeho vyhodnocení není potřeba oproti předchozímu experimentu měnit, zůstal tedy stejný, byla pouze rozšířena sada terminálů GP pokrývající nově přidané senzory robotů. Přidané terminály jsou vypsány v tabulce č. 4.3. Tabulka 4.3: Přidané terminály v experimentu č. 2. Zápis Typ Popis micF

float Hodnota čtená z předního mikrofonu.

micB

float Hodnota čtená z zadního mikrofonu.

micL

float Hodnota čtená z levého mikrofonu.

micR

float Hodnota čtená z pravého mikrofonu.

Princip výpočtu fitness funkce se od experimentu č. 1 také příliš nezměnil, každý jedinec byl opět do simulátoru vložen 8x, dvakrát na každé různé sestavení překážek. Výsledná fitness je průměr z ohodnocení všech 8 simulací. Samotné ohodnocení simulace musí nově hodnotit nejen schopnost vyhnout se kolizím, ale také schopnost robotů se v aréně shluknout. Za účelem hodnocení schopnosti se shluknout byla zavedena ekvivalence ρ na množině robotů N taková, že: x, y ∈ N : ρ(x, y) ⇔ (d(x, y) < 5) ∨ (∃z ∈ N : ρ(x, z) ∧ ρ(y, z)), kde d(x, y) je vzdálenost robotů x a y. Třídy ekvivalence ρ tedy odpovídají skupinám robotů tvořících jedno seskupení (mezní hranice pro dva roboty tvořící jedno seskupení je vzdálenost 5 jednotek mezi roboty). Schopnost robotů se P shluknout lze pak vyjádřit jako Fshluk = X∈N/ρ (|X|/|N |)2 . Funkce Fshluk tedy nabývá hodnot od

1 |N |

(pokud nevznikne žádný shluk) do 1 (pokud všichni roboti

tvoří jeden shluk). Vyhýbání se kolizím již dobře hodnotila funkce Fexp1 =

D−2.5·Cw −2.5·Co −0.5·Cb R·N

použitá v předchozím experimentu, kde D je ujetá vzdálenost, Cw je počet kolizí se zdí, Co počet kolizí s překážkou, Cb počet kolizí mezi roboty, R je počet kroků simulace a N je počet robotů v hejnu. Celkově pak byla každá simulace ohodnocena podle vzorce Fexp1 + c · Fshluk , kde konstanta c byla na základě série pokusů nastavena na 10.

4.2.5

Metoda evolučních strategií a neuronové sítě

V této části představíme metodu, kterou k řízení robotických hejn využívali některé z předchozích prací [20, 21, 25]. V závěru experimentu provedeme srovnání 30

této metody a GP. Metoda využívající místo GP evoluční strategie a neuronovou síť se od GP velmi neliší. Jedná se také o EA, jedincem zde ale není celý program řídící robota, ale pouze k-tice čísel (k-prvkový vektor čísel). Samotného robota pak řídí jednoduchá neuronová síť reprezentovaná úplným bipartitním grafem 4.9, kde jedna partita je tvořena senzory robota (3 senzory přiblížení a 4 mikrofony) a druhá pak výstupy robota (levé a pravé kolo). V každém kroku simulace je pak výstup wl na levé kolo resp. výstup wr na pravé kolo spočítán následovně: wl =

X

ki,l · vi ,

wr =

i∈I

X

ki,r · vi ,

i∈I

kde I je množina všech vstupů robota, vi je hodnota čtená ze vstupu i a ki,l , ki,r pro i ∈ I jsou konstanty. S hodnotami wl a wr je dále zacházeno stejně, jako v případě GP, což bylo popsáno v dřívější části 4.1.4.

Obrázek 4.9: Schéma jednoduché neuronové sítě použité k řízení robota během experimentu č. 2 při použití ES. Některé ze zmíněných prácí ještě rozšiřovaly neuronovou síť o další vstup se stálou hodnotou 1. Případně výstupy na levé a pravé kolo modifikovaly funkcí sigmoida1 . Obě tyto varianty byly v rámci této práce vyzkoušeny, nejlepších výsledků ale dosahovala původní varianta popsaná výše. Výsledky popsané v této práci se tedy týkají pouze této jedné varianty. Samotná evoluce pak pouze hledá vektor konstant ki,l , ki,r pro i ∈ I, tedy pro 7 vstupů je to vektor 14 reálných čísel. Evoluce byla nastavena tak, aby se co nejvíce podobala verzi používající GP, tedy běžela po dobu 100 generací s velikostí populace 100 jedinců a jako selekce byla zvolena turnajová selekce 1

Sigmoida je funkce definovaná vztahem F (x) =

funkce.

31

1 1+e−x .

Jedná se o speciální případ logistické

s velikostí turnaje 8 jedinců. Vzhledem k rozdílnosti typů jedinců musela být použita jiná mutace a jiné křížení. Po vzoru práce V. Trianniho [20] nebylo použito žádné křížení, naopak mutace zde nastává na každém jedinci každou generaci. Mutace probíhá po jednotlivých prvcích vektoru, kde ke každému prvku je s pravděpodobností

3 14

přičteno náhodné číslo řídící se Gaussovým rozdělením se

střední hodnotou 0 a s rozptylem 1. Fitness funkce byla použita stejná, jako v případě GP.

4.2.6

Výsledky

Metoda využívající GP vytvářela řídící programy, které úkol plnily velmi hezky a jednoduše. Roboti se v aréně neorganizovaně pohybovali až do chvíle, kdy se jim podařilo pomocí mikrofonů zachytit signál dalšího robota, ke kterému se začali přibližovat. Přiblížení nikdy neproběhlo úplně, naopak si roboti drželi pomocí krouživého pohybu malý odstup, a tím vytvořený shluk připomínal spíše pohybující se roj. Takové chování umožňovalo, aby se dva blízké shluky mohly spojit do jednoho většího. Chování nejlepšího jedince ze všech běhů GP na všech testovaných arénách je zobrazeno v obrázku č. 4.10. O něco hůře si vedli jedinci vytvoření ES, kteří k úkolu většinou přistupovali mírně odlišně. Základem jejich chování byla jízda po obvodu arény (případně jen po části arény, pokud tomu některá z překážek bránila), což navedlo roboty v aréně do podobné trajektorie a zvýšilo šanci na nalezení dalšího robota. Na signály přijaté pomocí mikrofonů ale roboti reagovali až při těsné blízkosti, což způsobilo, že shluky se vytvářely především v rozích arény, kde se roboti dostávali do větší blízkosti. V některých případech se ale celé hejno dostalo do stavu, kdy rozestupy mezi jednotlivými roboty při objíždění arény byly dostatečně velké na to, aby k žádnému shluku nedošlo. V takovém případě pak roboti kroužili podél arény až do konce simulace. Navíc shluky vytvářené jedinci ES byly především statické, tedy shluknutí roboti se dále nepohybovali, a tak dvě sousedící seskupení se již dále nespojovala. Chování nejlepšího jedince ze všech běhů ES na všech testovaných arénách je zobrazen v obrázku č. 4.11. Základní schopnost vyhnout se překážkám a okrajům arény se vyvinula ve všech bězích GP i ES. Rozdílný přístup měli jedinci ES a GP ke srážkám mezi roboty. ES nebraly na tyto srážky ohled a při vytváření shluků do sebe roboti velmi často nabourávali. Naopak GP vytvářelo jedince, kteří se velmi dobře vyhýbali i srážkám mezi roboty, a to právě díky udržování větší vzdálenosti mezi samotnými roboty při vytváření shluků.

32

Obrázek 4.10: Znázornění chování nejlepšího jedince z poslední generace ze všech běhů GP v experimentu č. 2 na všech testovaných arénách. Šedé tečky jsou původní pozice robotů na začátku simulace, modré tečky jsou koncové pozice robotů na konci simulace, modré křivky reprezentují pohyb robotů po aréně.

33

Obrázek 4.11: Znázornění chování nejlepšího jedince z poslední generace ze všech běhů ES v experimentu č. 2 na všech testovaných arénách. Šedé tečky jsou původní pozice robotů na začátku simulace, modré tečky jsou koncové pozice robotů na konci simulace, modré křivky reprezentují pohyb robotů po aréně.

34

Srovnání GP a ES Jak je možné vyčíst z průběhu všech evolucí 4.12, ES se daří nalézt své maximum velmi rychle, přibližně od 15. generace se jedinci výrazně nezlepšovali, naopak GP potřebovalo k nalezení svého maxima mnohonásobně více generací. Zároveň podávaly ES stabilnější výsledky, rozdíly mezi jednotlivými běhy byly menší, než tomu bylo u GP, které častěji uvízlo v lokálním optimu. Tyto nevýhody GP vyvážilo kvalitnějšími jedinci, kteří v simulátoru dosahovali výrazně lepších výsledků, než kterých dosahovali jedinci ES.

Obrázek 4.12: Graf znázorňující průměrnou hodnotu fitness funkce nejlepšího jedince se směrodatnou odchylkou v závislosti na generaci. Hodnoty byly počítány z 18 různých nezávislých běhů GP a ES. Pomocí Mann-Whitney U-testu bylo na vzorcích (viz. tabulka 4.4) 18 běhů ES a 18 běhů GP ověřeno, že rozdíl mezi implementovanými metodami je statisticky významný při hladině významnosti 0.01. Shrnutí Experiment ukázal, že GP představuje dostatečně silný nástroj pro vytváření řídících programů vedoucí roboty k vytváření shluků v simulátoru, kteří navíc ve shluku nezůstali statičtí, ale pokračovali v pohybu i po shluknutí. Navíc se jedincům velmi dobře dařilo vyhýbat se překážkám, okrajům arény a především ostatním robotům. Také bylo v tomto experimentu ukázáno, že GP dosahuje lepších výsledků než 35

Tabulka 4.4: Hodnoty fitness nejlepšího jedince v poslední generaci v 18 různých bězích GP a ES. Tyto data byla použita k srovnání obou metod pomocí MannWhitney U-testu. GP

ES

8.43233

7.26096 7.49027

6.71724

8.34826

7.1911

7.20528

6.68419

7.87844

7.16462 7.01663

6.60076

7.78986

6.94266 6.99907

6.59656

7.70554

6.87691 6.92929

6.52763

7.62359

6.79143 6.84474

6.52118

7.49868

6.78502 6.80728

6.45745

7.39282

6.28091 6.74888

6.05775

7.3818

6.11357 6.74239

6.05122

spojení ES a jednoduché neuronové sítě, které bylo často používáno na Middle East Technical University v Turecku. Cenou za kvalitu řešení je pak delší doba výpočtu GP oproti ES.

4.3

Experiment 3: Prohledávání oblasti

Poslední experiment provedený v této práci bude inspirován článkem [1] zmíněným v úvodu, kde bylo robotické hejno využíváno, mimo jiné, k hledání obětí v hořících budovách. Místo obětí požáru budou v tomto experimentu použity tzv. zdroje světla, které budou roboti hledat pomocí nových senzorů reagujících na světlo. Podobně jako v předchozím experimentu se pokusíme stejný problém řešit za pomoci ES a neuronové sítě. V této části se ale také navíc pokusíme vytvořit řídící program ručně a provedeme porovnání s GP.

4.3.1

Popis scény

Oproti předchozím experimentům se v simulátoru bude nacházet mimo samotných robotů a překážek také několik zdrojů světla, které mají roboti za úkol hledat. Po nalezení zdroje světla robotem je zdroj odstraněn z arény simulátoru až do konce simulace, přičemž nalezení zdroje znamená přiblížení se robotem na dotek ke zdroji. Během evoluce budou jedinci testováni na třech různých nastaveních simulá-

36

toru. První aréna je 30 jednotek veliká, simulace na ní trvá 300 kol a bude se v ní pohybovat pouze jeden robot. Zbylé dvě jsou určeny pro 3 roboty, simulace potrvá 250 resp. 350 kol a aréna je veliká 30 jednotek resp. 40 jednotek. Arény včetně pozic překážek a zdrojů světla jsou znázorněny v obrázku č. 4.13.

Obrázek 4.13: Nákres arén použitých během experimentu č. 3. Šedý okraj reprezentuje ohraničení arény, oranžové oblasti reprezentují překážky a žluté tečky reprezentují hledané zdroje světla.

4.3.2

Cíl experimentu

Cílem experimentu je otestovat, zda se pomocí GP podaří nalézt kvalitní řídící program pro hejno homogenních robotů. Kvalitní řídící program by měl roboty vést k rychlému prozkoumávání arény a hledání světelných zdrojů.

4.3.3

Model robota

Základem robota je v tomto experimentu opět model z experimentu č. 1, tedy robot se třemi senzory přiblížení a dvěma koly. Na něm je přichycen všesměrový reproduktor a 3 mikrofony na obvodu robota pod úhly −60◦ , 180◦ , 60◦ od směru pohybu. K hledání světelných bodů v aréně budou roboti využívat tři světelné senzory, které jsou umístěné ve středu robota a natočené pod úhly −90◦ , 0◦ , 90◦ od směru pohybu. Každý světelný senzor dokáže zaregistrovat všechny zdroje světla ve výseči (−22.5◦ , 22.5◦ ), pokud nejsou schované za některou z překážek. P Výstup ze senzoru světla je hodnota z∈Z d1z 2 , kde Z je množina zdrojů světla viditelných z daného senzoru pod úhlem mezi −22.5◦ a 22.5◦ a dz je vzdálenost zdroje z od senzoru. Model celého robota je znázorněn v obrázku č. 4.14.

37

Obrázek 4.14: Model robota v experimentu č. 3. Robot disponuje dvojicí kol (zelené obdélníky), třemi senzory přiblížení (červené úsečky), všesměrovým reproduktorem (fialový kruh), třemi mikrofony (šedé čtverce) a trojicí světelných senzorů (oranžové oblouky).

4.3.4

Nastavení evoluce

Evoluce byla opět ukončena po 100. generaci a množina terminálů GP byla upravena 4.5 tak, aby odpovídala senzorům robotů. Každý jedinec je během výpočtu fitness vložen 6x do simulátoru, dvakrát na každou z testovaných arén, každá simulace je samostatně ohodnocena a průměr všech 6 ohodnocení je vrácen jako hodnota fitness funkce. Základem pro ohodnocení jedné simulace opět zůstala funkce Fexp1 zavedená v experimentu č. 1, která hodnotila jedince podle jejich schopnosti vést robotické hejno k pohybu bez kolizí s ostatními prvky v aréně. Dále definujeme funkci hodnotící schopnost jedinců hledat zdroje světla v aréně P Fhled =

tl − 0.2 · R ) , |L|

l∈L0 (1

kde L je množina všech zdrojů světla, L0 ⊆ L je množina zdrojů, které se hejnu podařilo nalézt, tl pro l ∈ L0 je číslo kola simulace, ve kterém se robotům podařilo nalézt zdroj l, a R je celkový počet kol simulace. Za každý nalezený zdroj je tedy k hodnotě Fhled přičtena hodnota mezi

0.8 |L|

a

1 |L|

v závislosti na rychlosti objevení

zdroje. Funkce Fhled nabývá hodnot mezi 0 (pokud hejno neobjevilo žádný zdroj) do 1 (pokud roboti objeví všechny zdroje v nultém kole simulace, při inicializaci simulace by tedy musel být do těsné blízkosti každého zdroje umístěn robot).

38

Tabulka 4.5: Množina terminálů použitá během GP v experimentu č. 3. Zápis Typ Popis (0, 0)

tuple Reprezentace stání na místě.

(1, 1)

tuple Reprezentace pohybu dopředu plnou rychlostí.

(−1, −1) tuple Reprezentace pohybu zpět plnou rychlostí. (0, 1)

tuple Reprezentace otáčení se doleva s pohybem vpřed.

(1, 0)

tuple Reprezentace otáčení se doprava s pohybem vpřed.

(0, −1)

tuple Reprezentace otáčení se doprava s pohybem vzad.

(−1, 0)

tuple Reprezentace otáčení se doleva s pohybem vzad.

(1, −1)

tuple Reprezentace otáčení se na místě doprava.

(−1, 1)

tuple Reprezentace otáčení se na místě doleva.

1

float

Číslo 1.

0

float

Číslo 0.

−1

float

Číslo -1.

uni(0, 1)

float

Náhodně vygenerovaná hodnota v intervalu od 0 do 1.

irL

float

Hodnota čtená z levého senzoru přiblížení.

irF

float

Hodnota čtená z předního senzoru přiblížení.

irR

float

Hodnota čtená z pravého senzoru přiblížení.

micB

float

Hodnota čtená z zadního mikrofonu.

micL

float

Hodnota čtená z levého mikrofonu.

micR

float

Hodnota čtená z pravého mikrofonu.

lsL

float

Hodnota čtená z levého světelného senzoru.

lsF

float

Hodnota čtená z levého světelného senzoru.

lsR

float

Hodnota čtená z pravého světelného senzoru.

39

Celkově je tedy jedna simulace ohodnocena jako Fexp1 +c·Fhled , kde konstanta c byla na základě série pokusů nastavena na 5.

4.3.5

Metoda evolučních strategií a neuronové sítě

Oproti předchozímu experimentu musíme provést několik málo úprav. S jinými počtem použitých senzorů musí samotná neuronová síť mírně změnit tvar. Nyní bude obsahovat o dva vstupní neurony více, celkem tedy 9 vstupních neuronů (3 senzory přiblížení, 3 mikrofony a 3 světelné senzory). Počet výstupních neuronů se nezmění. Změny v neuronové síti pak přímo ovlivní jedince ES, kterými nyní budou vektory 18 reálných čísel. Ostatní nastavení ES zůstane nezměněné. Samozřejmostí je použití stejné fitness funkce jako v případě GP.

4.3.6

Člověkem vytvořený řídící program

Ačkoliv není návrh a tvorba řídícího programu člověkem předmětem této práce, vytvoříme v této části jednoduchý řídící program Man-made, který v závěru tohoto experimentu srovnáme s řídícími programy vytvořenými GP. Vytvořený program bude zkonstruovaný stejnými prostředky, jako jedinci GP, bude tedy tvořit strom složený z množiny funkcí a terminálů. Základní struktura Man-made bude tvořena čtyřmi jednoduchými větvemi: if predniSezorSvetla > 0 # zdroj před robotem, jeď k němu jizdaVpred() elif levySezorSvetla > 0 # zdroj nalevo, otoč se za ním otocSeVlevo() elif pravySezorSvetla > 0 # zdroj napravo, otoč se za ním otocSeVpravo() else # žádný viditelný zdroj, prohledej arénu prozkoumavaniAreny() Místo funkcí otocSeVlevo() resp. otocSeVpravo() postačí triviální wheels(0, 1) resp. wheels(1, 0). Naopak funkce jizdaVpred() a

40

prozkoumavaniAreny() je třeba navrhnout tak, aby při nich roboti zohledňovali své okolí a vyhýbali se kolizím. Funkci jizdaVpred() lze asi nejjednodušeji zapsat pomocí wheels(irR,irL), které vede robota k pohybu vpřed a zároveň zajišťuje jednoduchý mechanismus vyhýbaní se kolizím. Návrh funkce prozkoumavaniAreny() je již obtížnější, jelikož roboti nedisponují žádnou pamětí, která by například umožnovala rozeznávat situace, kdy robot sledoval stěnu, která náhle skončila, a kdy zatím na žádnou stěnu nenarazil. Funkci tedy založíme na jízdě po velkém kruhu ve směru hodinových ručiček a, v případě přiblížení se k dalšímu objektu, otočce doleva. To na testovaných arénách připomíná pohyb podél překážek a ohraničení, což by robotům mělo umožňovat prozkoumávání arény. V zápisu funkcí a terminálů pak funkci prozkoumavaniAreny() lze zapsat například jako con(add(irR, irL), 1.5, wheels(irR, sub(irL, 0.05)), wheels(0, 1)).

4.3.7

Výsledky

Nejlepší řídící programy vyvinuté GP řešily prohledávání oblasti metodou sledování stěn po levé straně robota. To na testovaných arénách robotům zajistilo, že prozkoumají celou arénu (pokud dříve nevyprší časový limit simulace) a mohou tak nalézt všechny zdroje světla. V případě přiblížení se ke zdroji světla se roboti dočasně odchýlili od sledované stěny a odstranili zdroj z arény. Chování nejlepšího jedince ze všech 18 běhů GP je znázorněno v obrázku č. 4.15. Ačkoliv byli roboti vybaveni také mikrofony, aby byli schopni omezeným způsobem detekovat ostatní členy roje, většina vyvinutých řídících programů je během svého rozhodování o dalším kroku nijak nezohledňuje. Nesnaží se tedy nijak zamezit tomu, aby například dva roboti prohledávali stejný úsek arény. To je pravděpodobně způsobeno nedostatečnou informací, které mikrofony robotům poskytují. Srovnání GP a ES Srovnání v tomto případě vychází velmi jednoznačně pro GP. Z průběhu evolucí v obrázku č. 4.16 je opět možné vyčíst, že ES našly své maximum velmi rychle. Oproti předchozímu experimentu ale nastal obrovský rozdíl mezi kvalitou řešení GP a ES. GP problém řešilo relativně hezky a efektivně, naopak ES problém téměř neřešily. Chování jedinců ES v simulátoru obnášelo pouze pohyb po aréně a vyhýbání se překážkám a dalším robotům. Jedinci pohyb robotů po simulátoru světelným

41

Obrázek 4.15: Znázornění chování nejlepšího jedince z poslední generace GP v experimentu č. 3 na všech testovaných arénách. Šedé tečky jsou původní pozice robotů na začátku simulace, modré tečky jsou koncové pozice robotů na konci simulace, modré křivky reprezentují pohyb robotů po aréně, fialové tečky jsou původní pozice nalezených světelných zdrojů světla a žluté tečky jsou pozice nenalezených zdrojů světla.

42

Obrázek 4.16: Graf znázorňující průměrnou hodnotu fitness funkce nejlepšího jedince se směrodatnou odchylkou v závislosti na generaci. Hodnoty byly počítány z 18 různých nezávislých běhů GP a ES. zdrojům prakticky nepřizpůsobovali, docházelo tedy pouze k náhodným nálezům zdrojů. Srovnání GP s programem vytvořeným člověkem Jednoduchý řídící program Man-made, který jsme představili v předešlé části byl testován ve stejných arénách a na stejně velkém robotickém hejnu, na jakém byli testováni jedinci během GP. Na 500 simulacích byla na každé z arén zaznamenávána hodnota funkce Fhled (znázorněno v obrázku č. 4.17) a celkový počet kolizí (znázorněno v obrázku č. 4.18). Spolu s Man-made byli do grafů pro srovnání zaneseni i nejlepší jedinec (GP-best) z 18 běhů GP a jedinec odpovídající mediánu nejlepších jedinců posledních generací (GP-med). Samotné hledání světelných zdrojů se Man-made programu dařilo na první a třetí aréně srovnatelně jako GP-med a jen o něco hůře než GP-best. Největší rozdíl nastal na aréně č. 2, ve které funkce prozkoumavaniAreny() programu Man-made velmi často způsobila uvíznutí robotů na malé části arény, což robotům zabraňovalo hledat další zdroje. Výrazně hůře pak dopadl program Man-made v kontextu kolizí robotů s dalšími prvky v aréně. Navržené funkce jizdaVpred() a prozkoumavaniAreny() naprosto nedostatečně zabraňovaly kolizím robotů, například na aréně č. 3 roboti řízení programem Man-made měli v průměru kolizi 60x častěji než roboti řízení 43

Obrázek 4.17: Graf znázorňující průměrnou hodnotu Fhled řídících programů se směrodatnou odchylkou na každé z testovaných arén. Znázorněné řídící programy jsou ručně vyrobený řídící program (Man-made), nejlepší jedinec (GP-best) a medián jedinců (GP-med) z 18 běhů GP. Na každé aréně byl každý řídící program testován 500x.

Obrázek 4.18: Graf znázorňující průměrný počet kolizí na jednoho robota na jedno kolo simulace se směrodatnou odchylkou na každé z testovaných arén. Znázorněné řídící programy jsou ručně vyrobený řídící program (Man-made), nejlepší jedinec (GP-best) a medián jedinců(GP-med) z 18 běhů GP. Na každé aréně byl každý řídící program testován 500x. 44

programem GP-best. Oba zmíněné nedostatky programu Man-made byly způsobeny nedostatečným odladěním funkcí jizdaVpred() a prozkoumavaniAreny(). Vylepšení obou funkcí a jejich ladění by ale obnášelo volbu několika vhodných konstant, na kterých je chování závislé. To je ale pro člověka poměrně obtížné a výrazné vylepšení těchto funkcí by tedy pravděpodobně stálo neúměrně více času. Shrnutí GP nacházelo řídící programy, které velmi úspěšně hledaly v arénách zdroje světla a dobře řídily jízdu tak, aby se roboti vyhýbali překážkám. Nepodařilo se ale vyvinout jedince, kteří by zohledňovali také pozice ostatních členů hejna a snažili se hledání tímto způsobem optimalizovat. To je pravděpodobně způsobeno mikrofony, které poskytovaly dostatečné množství informací pro shluknutí se, ale k efektivnějšímu hledání jsou nevhodné. Pro vyvinutí inteligentnějšího průzkumu by bylo vhodnější, kdyby byli roboti schopni přímo komunikovat mezi sebou nebo sdílet např. informace o prozkoumané části. Tento experiment ukázal, že prohledávání oblasti je příliš složitý problém pro ES a neuronovou síť. ES nedokázaly během žádného běhu nalézt ani jedno uspokojivé řešení. Je ale potřeba zdůraznit jednoduchost použité neuronové sítě. Při využití složitějších variant by pravděpodobně došlo k výraznému nárůstu výkonu jedinců ES. Během srovnávání GP s člověkem navrženým programem Man-made se ukázalo, že i přes svoji relativní jednoduchost Man-made dokázal plnit úkol hledání srovnatelně jako programy z GP. Výrazně ale zaostával v řízení samotné jízdy, kde mnohem častěji způsoboval kolize, což bylo způsobeno nerobustností funkcí jizdaVpred() a prozkoumavaniAreny(), které nedokázaly dostatečně rozpoznávat překážky za všech situací a způsobovaly kolizi. Odladění by ale pro člověka znamenalo mimo jiné hledání vhodných konstant a tedy často metodu pokus-omyl. Nabízí se zde tedy možnost kombinace obou metod, kde základní struktura řídícího programu je navržena ručně programátorem a dílčí funkce jsou vytvořeny samostatně pomocí GP. Takové řešení by mohlo kombinovat výhody obou metod, tedy čistotu a jednoduchost návrhu programátora a dostatečnou robustnost jedinců GP.

45

Závěr V rámci této práce byl implementován jednoduchý 2D simulátor umožňující vizualizaci chování homogenního hejna robotů v prostředí s překážkami a zdroji světla. Zároveň byl také vytvořen program využívající techniky EA (především GP) k vytváření řídících programů pro robotické hejno plnící zadané úkoly. Vytvořené programy byly použity k sérii experimentů testujících schopnost GP hledat vhodné řídící programy. Úkolem robotického hejna během těchto experimentů bylo postupně vyhýbání se překážkám, shlukování a prohledávání arény. Bylo ukázáno, že GP představuje dostatečně silný nástroj pro vytvoření řídících programů, vyvinutí jedinci plnili všechny tři zadané úkoly uspokojivě. Během druhého a třetího experimentu bylo také provedeno srovnání GP s ES v kombinaci s jednoduchou neuronovou sítí, tedy technikou používanou především na Middle East Technical University v Turecku k řízení robotického hejna. V rámci druhého experimentu bylo ukázáno, že GP nacházelo řešení, která byla o něco více kvalitní než řešení nalezené ES. Cenou za to ale bylo pomalejší hledání těchto řešení. To je především dáno větší obecností GP, kdy každé řešení vzniklé ES lze snadno zapsat také jako řešení GP. Obrácený postup pak vždy nelze. Srovnání v rámci třetího experimentu již dopadlo velmi jednoznačně ve prospěch GP, které produkovalo dobrá řešení problému, zatímco ES se problém nepodařilo uspokojivě vyřešit. V rámci třetího experimentu proběhlo také krátké srovnání s řídícím programem vytvořeným člověkem, které především poukázalo na možnost kombinovat oba tyto postupy. Nevytvářet tedy celý program pomocí GP, ale vytvořit kostru programu ručně a GP využít k vytvoření menších úseků programu. Více jsme se ale této možnosti nevěnovali.

Možná rozšíření Zajimavým pokračováním této práce by byla aplikace GP na pokročilejších robotech disponujících například přímou komunikací mezi samotnými roboty nebo pamětí. To by umožňovalo inteligentnější chování robotů a řešení komplikovanějších úkolů. Na takových robotech by také bylo zajímavé prozkoumat možnosti tvorby řídících programů člověkem v kombinaci s GP. Další možností je také pokusit se přenést vyvinuté programy na fyzické roboty. K tomu by bylo ale potřeba nejen zkonstruovat samotné roboty, ale také rozšířit simulátor tak, aby věrohodněji simuloval reálné prostředí. Pokus o přenos řídících

46

programů vzniklých během této práce na skutečné roboty by pravděpodobně nedopadl úspěšně, jelikož použitý simulátor prostředí příliš zjednodušoval nebo zanedbával některé fyzikální zákony. Například všechny senzory v této práci byly dokonale přesné, nebyly ovlivňovány žádným šumem okolí ani žádnou chybou měření, což jistě neodpovídá skutečnosti.

47

Seznam použité literatury [1] PENDERS, Jacques, ALBOUL, Lyuba, WITKOWSKI, Ulf, NAGHSH, Amir, SAEZ-Pons, Joan, HERBRECHTSMEIER, Stefan, EL-HABBAL, Mohamed. Robot Swarm Assisting a Human Fire-Fighter. Advanced Robotics, 2011, Vol.25(1-2), pp.93-117. ISSN 0169-1864. [2] POLI, Riccardo, KOZA, John, W LANGDON a Nicholas F MCPHEE. A field guide to genetic programming. S.l.: [S.n.], 2008, xiv, 233 p. ISBN 9781409200734. [3] EIBEN, Agoston E. a SMITH J. Introduction to evolutionary computing. New York: Springer, 2003, xv, 299 p. ISBN 3540401849. [4] FOGEL, David B, Thomas BACK a Zbigniew MICHALEWICZ. Evolutionary computation. Philadelphia: Institute of Physics Publishing, c2000, 2 v. ISBN 07503066532. [5] FRIEDBERG, R.M. A Learning Machine: Part I. IBM Journal of Research and Development, 1958, vol.2, pp.2-13. ISSN 0018-8646. [6] BREMERMANN, Hans-Joachim. Optimization through evolution and recombination. Self-Organizing Systems. 1962. [7] RECHENBERG, I. Cybernetic Solution Path of an Experimental Problem. Ministry of Aviation, Royal Aircraft Establishment (U.K.). 1965. [8] FOGEL, Lawrence J. Artificial intelligence through simulated evolution. Wiley, New York. 1966. [9] HOLLAND, John H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press, 1975, viii, 183 p. ISBN 0472084607. [10] KOZA, John. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. Stanford University Computer Science Department. 1990, STAN-CS-90-1314. [11] ZITZLER, Eckart. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Swiss Federal Institute of Technology Zurich. 1991. 48

[12] Koza, John R. Genetic programming: on the programming of computers by means of natural selection. Cambridge, Mass.: MIT Press, c1992, xiv, 819 p. ISBN 0262111705. [13] MITCHELL, Melanie. An introduction to genetic algorithms. 1st ed. Cambridge: The MIT Press, 1998, viii. ISBN 0262133164. [14] LUKE, Sean a PANAIT, Liviu. A Comparison of Bloat Control Methods for Genetic Programming. Evolutionary Computation. 2006, vol.14(3), pp.309344. ISSN 1063-6560. [15] TAN, Ying a Zhong-yang ZHENG. Research Advance in Swarm Robotics. Defence Technology. 2013, pp.18-39 . ISSN 22149147. [16] MOHAN, Yogeswaran, PONNAMBALAM, S.G. An extensive review of research in swarm robotics. Nature & Biologically Inspired Computing, 2009, pp.140-145. ISBN 978-1-4244-5053-4. [17] SHARKEY, A.J.C. Robots,Insects and Swarm Intelligence. The Artificial Intelligence Review, 12, 2006, vol. 26, no. 4. pp. 255-268. ISSN 02692821. [18] Seaswarm

[online].

[cit.

2015-07-02].

Dostupné

z:

http://senseable.mit.edu/seaswarm/index.html [19] CORREL, Nikolaus, MARTINOLI, Alcherio. Towards optimal control of self-organized robotic inspection systems. École Polytechnique Federale de Lausanne. 2006. [20] TRIANNI, Vito, GROB, Roderich, LABELLA, Thomas H., SAHIN, Erol, DORIGO, Marco. Evolving aggregation behaviors in a swarm of robots. Lecture Notes in Artificial Intelligence. 2003, vol. 2801, pp. 865–874. [21] DORIGO, Marco, TRIANNI, Vito, SAHIN, Erol, GROB, Roderich, LABELLA, Thomas, BALDASSARRE, Gianluca, NOLFI, Stefano, DENEUBOURG, Jean-Luis, MONDADA, Francesco, FLOREANO, Dario, GAMBARDELLA, Luca Evolving Self-Organizing Behaviors for a Swarm-bot. Autonomous Robots. 2004, vol.17(2), pp.223-245. ISSN 1573-7527. [22] BALDASSARRE, Gianluca, PARISI, Domenico, NOLFI, Stefano. Distributed Coordination of Simulated Robots Based on Self-Organization. Artificial Life. 2006, vol.12(3), pp.289-311. ISSN 1064-5462.

49

[23] TRIANNI, Vito, NOLFI, Stefano, DORIGO, Marco. Cooperative hole avoidance in a swarm-bot. Robotics and Autonomous Systems. 2006, 54(2), pp.97-103. ISSN 09218890. [24] SPERATI, Valerio, TRIANNI, Vito, NOLFI, Stefano. Self-organised path formation in a swarm of robots. Swarm Intelligence. 2011, vol.5(2), pp.97119. ISSN 1935-3820. [25] SOYSAL, Onur, BAHCECI, Erkin, SAHIN, Erol. Aggregation in Swarm Robotic Systems: Evolution and Probabilistic Control. Turkish Journal of Electrical Engineering and Computer Sciences. 2007, vol.15(2), pp.199-225. [26] FORTIN, Felix-Antoine, DE RAINVILLE, Fran¸cois-Michel, GARDNER, Marc-André, PARIZEAU, Marc, GAGNÉ, Christian. DEAP: Evolutionary Algorithms Made Easy. Journal of Machine Learning Research, vol.13, pp.2171–2175, 2012.

50

Obsah přiloženého CD adresář simulator Adresář obsahující zdrojové kódy simulátoru použitého během této práce. Především jsou obsaženy soubory animator.py a run_evolution.py. run_evolution.py Spuštění simulátoru v režimu evoluce. animator.py Spuštění simulátoru v režimu prohlížení. soubor uzivatelska_dokumentace.pdf Uživatelská dokumentace k programům animator.py a run_evolution.py. soubor programatorska_dokumentace.pdf Programátorská dokumentace k programům animator.py a run_evolution.py a všem doprovodným modulů. adresář data Adresář obsahující výstupní soubory všech evolucí provedených v rámci této práce. Pomocí těchto souborů a samotného simulátoru je také možné zopakovat všechny provedené experimenty. Návod, jak to lze provést, je napsán v uživatelské dokumentaci. adresář videa Adresář obsahující záznamy chování několika vybraných jedinců v simulátoru.

51