Zkouška

u zkoušky se objeví čtyři otázky; mrkni na teorii, která se zkouší nejčastěji

Úvod

• historie robotiky
  • automatizace už ve starověkém Řecku – když dohořela zápalná oběť, tak se otevřely dveře chrámu
  • biskup Albertus Magnus: kovový sluha
  • da Vinci: mechanický rytíř
  • Descartes: Ma fille Francine
  • mechanická kachna
  • R.U.R.
  • Elektro – robot pro světovou výstavu v New Yorku, 1939
  • pes Sparko
  • průmyslové manipulátory
  • Shakey – Stanford, 1960
  • Khepera – dá se použít i k hardwarové evoluci
    • e-Puck – varianta Khepery
  • Honda: robot ASIMO
• jak vypadá evoluční vývoj
  • máme robota, ten se pohybuje v nějakém světě
  • definujeme úlohu, např. má hledat nějaký objekt v tom světě
  • jeho řízení zakódujeme do chromozomů – jeden chromozom kóduje celý řídicí systém
  • tak jsme dostali nultou generaci
  • vyzkoušíme každý chromozom, ohodnotíme je fitness funkcí (podle toho, jakých dosahovali výsledků)
  • přechod k další generaci
    • selekce (vybereme ty nejlepší)
    • reprodukce (např. křížení)
    • mutace
• alternativy k evoluční robotice
  • behavior-based robotics (robotika založená na chování)
    • robot má sadu několika základních chování, ta mezi sebou interagují
      • příklady chování: plním konkrétní úkol, hledám potravu, …
      • dochází mi energie → musím hledat potravu (na úkor plnění úkolu)
    • chování spolu můžou soutěžit
      • kompetitivní koordinace – jeho řízení vítězí → subsumption method
      • kooperativní koordinace – jednotlivá řízení přispívají k celkovému výsledku
    • vnímání je těsně navázané na akce – při generování reakce se nepoužívá abstraktní reprezentace světa
    • hierarchie chování
  • robotické učení
    • řídicí systém se učí pomocí neúplných dat a generalizuje
    • typicky se učí zobrazení, které mapuje vstupy senzorů na výstupy motorů
    • týká se pouze řízení (kdežto evoluční robotika se může zabývat i návrhem konstrukce robota)
  • umělý život
    • simulace světa, kde se pohybuje více organismů
    • cílem je vyvinout systém, který se dokáže přizpůsobit změnám prostředí
    • vychází z teorie dynamických systémů – lokální interakce prvků na nižší úrovni vede ke globálnímu chování na vyšší úrovni
    • modely „umělého života“ jsou asi poměrně abstraktní – kdežto evoluční robotika se zaměřuje na reálné roboty
• k čemu by to mohlo být dobré
  • evoluce by nám mohla pomoct navrhnout řízení i morfologii robota, aby mohl řešit úlohu
  • můžeme se inspirovat přírodou a naopak – možná nějaké takové mechanismy zpětně objevíme v přírodě
  • přístupy k návrhu řídicích systémů – rozdělení na podúlohy
    • klasický – perception, planning, execution
    • behavior-based – rozdělení do jednotlivých základních chování
    • evoluční – necháme to na evoluci
  • příklad: chceme najít předmět v bludišti a zůstat tam
    • je snadné určit jednotlivé úlohy, které robot musí plnit, ale je těžké je zkombinovat
    • evoluční robotika tohle řeší (nehledají se podúlohy, pouze jedno globální chování)
  • evoluční robotika může čerpat z oborů, které popisují chování živočíchů na různých úrovních
    • superorganismus: evoluční biologie, ekologie, sociologie
    • organismus: psychologie, neurologie
    • suborganismus: anatomie/fyziologie, biologie buňky, genetika, molekulární biologie
  • biologie
    • přirozená evoluce – jak je možné, že se vyvinula taková spousta úspěšných forem života?
    • chceme vytvořit podobně úspěšnou umělou evoluci
    • v přírodě funguje jedno kritérium – přežití druhu (schopnost reprodukce)
• bootstrap problém (problém inicializace)
  • když náhodně vygenerujeme řídicí systémy, neřeší problém → skóre 0
  • evoluce se nemá čeho chytit
  • možná řešení
    • inkrementální evoluce
      • začneme s jednodušší úlohou, postupně přidáváme obtížnost, až se dostaneme k reálné úloze
      • je jednodušší upravovat výběrové kritérium (fitness funkci) než navrhovat přímo řízení
      • zvláštní případ: koevoluce
        • např. dravec a kořist
        • dravec se snaží ulovit kořist, kořist se snaží utéct před dravcem
        • vlastně závody ve zbrojení
        • neměníme kritérium, ale stejně dochází k postupnému zlepšování
    • celoživotní učení
      • jedinec umí využívat senzorické vjemy, učí se, adaptuje svoje řízení
      • evolucí můžou vzniknout dva druhy jedinců schopných dobře fungovat v proměnlivém prostředí
        1. plastic general (učenlivý) – nemá obecnou strategii, ale umí se přizpůsobit prostředí
        2. full general (umí všechno) – má obecnou strategii vhodnou pro různé typy prostředí → nemusí se přizpůsobovat
      • někdy se full general jedinec nedá vytvořit (nebo je moc složitý)
    • evoluce zobrazení z genotypu na fenotyp
      • v přirozené evoluci se to zobrazení evolučně vyvíjí, v umělé evoluci to obvykle zadává autor experimentu
• využití
  • nemusíme navrhovat každý detail, něco za nás řeší evoluce – někdy najde překvapivá řešení
  • může spolu interagovat biologie a robotika – např. v rojové robotice
  • evoluční biorobotika
    • biorobotika – stavění modelů, které se podobají živým organismům (např. mečoun)
    • pomocí evoluční robotiky se robot naučí řízení
  • vývojová robotika
    • jak se mládě vyvíjí v dospělce?
    • mohl by se podobně vyvíjet robot?
    • proces dospívání
    • snažíme se vyvinout robota, který je schopný se doučit, dorůst
  • evolučně-vývojová robotika (evo-devo-robo)
    • zkušení jedinci můžou ovlivňovat méně zkušené
    • v přírodě: postupná evoluce pohybu po souši
      • mládě se plazí, dospělec kráčí
      • později dojde k přeskočení plazení a jedinec rovnou kráčí
    • robotické organismy z krychlí s klouby
  • rojová robotika
    • koordinace robotů ve skupině
  • modulární robotika
    • moduly se můžou spojovat do větších celků podle potřeby
  • měkká robotika
    • kombinace pružných a pevných dílů, velká flexibilita pohybů
    • zvednutí vajíčka pomocí (pod)tlaku vzduchu

Evoluční algoritmy

• genetické algoritmy
  • populace umělých chromozomů se cyklicky podrobuje selektivní reprodukci, která upřednostňuje výkonnější jedince, a náhodným změnám
  • umělý chromozom (genotyp) = řetězec symbolů kódující vlastnosti jedince (fenotyp)
    • může to být binární hodnota proměnné nebo posloupnost hodnot proměnných
    • mnoho typů kódování (binární, Grayův kód, reálná čísla)
      • Grayův kód – dvě čísla v posloupnosti se liší o jeden bit
        • je jednoduché ho sestavit (opíšu v opačném pořadí, doplním o nuly a jedničky)
        • příklady: 1, 0; 10, 00, 01, 11
    • abecedy – např. binární, ternární, …
  • fitness funkce – kritérium výkonosti (zobrazení: genotyp → reálné číslo)
  • obecný algoritmus
    • vytvoř populaci $N$ náhodně vygenerovaných chromozomů
    • opakuj: 1) dekóduj všechny chromozomy a spočítej jejich fitness, 2) vytvoř novou populaci
    • skončí, když se objeví hledaný jedinec (který plní úlohu) nebo když to trvá dlouho…
• Hillclimber – gradientní algoritmus
  • $N=1$
  • novou populaci tvoříme tak, že zmutujeme chromozom a nahradíme jim ten původní, pokud má lepší fitness
  • nemůže nastat zhoršení
  • $\mu$ … pravděpodobnost mutace
  • najde jenom lokální maximum
  • možná řešení
    • začít z různých pozic
    • dovolit zhoršení fitness (simulované žíhání)
  • simulované žíhání
    • velikost kroku i směr závisí na teplotě, která se postupně snižuje
    • pravděpodobnost přijetí zhoršení fitness (= teplota) se s časem zmenšuje
    • na začátku jsou kroky téměř náhodné
    • po ochlazení v podstatě deterministické
• jednoduchý genetický algoritmus (Goldberg)
  • víc než 1 chromozom v populaci
  • selektivní reprodukce, křížení, mutace
  • algoritmus
    • vytvoř populaci $N$ náhodně vygenerovaných chromozomů
    • opakuj
      • dekóduj všechny chromozomy a spočítej jejich fitness
      • vytvoř novou populaci selektivní reprodukcí
      • rekombinuj chromozomy (křížení)
      • mutuj chromozomy
    • skonči, když se objeví hledaný jedinec (který plní úlohu) nebo když fitness nejlepšího neroste
• jednoduchá selekce
  • čím lepší jedinec, tím více jeho kopií se může objevit v nové populace
  • reprodukce ruletou
    • každý jedinec dostane výseč kruhu úměrnou své fitness funkci (musí být nezáporná)
    • výseč ~ pravděpodobnost, že bude reprodukovaný
    • ruletou se otočí $N$-krát
  • problémy
    • všichni mají podobnou fitness → náhodné prohledávání (nic moc se neděje)
    • jeden jedinec (nebo dva) má obrovskou fitness → téměř všichni v populaci budou kopií toho stejného jedince
  • řešení
    • škálování – zvětšení nebo zmenšení rozdílů
    • selekce podle pořadí (rank based) – nezáleží na konkrétní hodnotě fitness
    • rank based s ořezáváním – nejlepších $M$ zkopírujeme $O$-krát, aby $N=M\times O$ (vlastně zahodíme spodní část seznamu)
    • turnajová selekce – náhodně se vyberou dva jedinci, ten lepší jedinec s určitou pravděpodobností vyhraje a bude zkopírován (jinak ten druhý)
  • elitismus – nejlepší jedinci se beze změny zkopírujou (abychom nepřišli o dosud nejlepší řešení)
    • podobný koncept (používá se v koevoluci): síň slávy (nejlepší jedinci ze všech předcházejících generací)
• křížení
  • jedinci jsou náhodně spárováni a každý pár je s danou pravděpodobností zkřížen
  • jednobodové nebo vícebodové křížení
• mutace
  • abychom měli možnost prohledat celý prostor
  • aby nám algoritmus nekonvergoval příliš brzo
  • uniformní mutace – každý znak každého jedince je s určitou pravděpodobností nahrazen náhodným znakem
• nedeterminismus
  • GA je nedeterministický, používá náhodné veličiny
  • typicky se sleduje průměrná a maximální fitness, aby se GA mohl ve vhodnou chvíli zastavit (nebo se zastavuje po dosažení určitého počtu generací)
  • GA se pouští opakovaně se stejnými nebo pozměněnými parametry
  • výsledkem je nejlepší jedinec vybraný z finálních generací ze všech běhů GA
• fitness krajina (fitness landscape)
  • tvar fitness funkce – v mnohadimenzionálním prostoru
  • chceme, aby se fitness postupně zvětšovala
• schémata
  • schéma – oproti chromozomu má jeho abeceda jeden prvek navíc (typicky hvězdičku $*$)
  • je to jakoby maska popisující víc chromozomů
  • schéma s $r$ hvězdičkami reprezentuje $k^r$ řetězců ($k$ je velikost původní abecedy)
  • každý řetězec délky $m$ je reprezentovaný $2^m$ schématy
  • $o(S)$ … řád schématu – počet pevných symbolů (různých od $*$)
  • $\delta(S)$ … definiční délka schématu – vzdálenost mezi první a poslední pevnou pozicí ve schématu
  • $\phi(S,t)$ … fitness schématu v čase $t$ (průměrná fitness řetězců reprezentovaných daným schématem)
  • $\xi(S,t)$ … počet řetězců v populaci $P(t)$, které jsou reprezentované schématem $S$
  • kolik jedinců určených daným schématem bude v dané populaci?
    • jak schéma ovlivní selekce?
      • $\xi(S,t+1)=\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}$
      • kde $\bar F(t)$ je průměrná fitness populace $P(t)$
      • tedy „nadprůměrné“ schéma pokryje v následující generaci více řetězců (jejich počet roste geometrickou řadou)
    • jak schéma ovlivní křížení?
      • když křížím jedince ze stejného schématu, tak jsou pokrytí i potomci
      • když je jeden rodič mimo schéma, tak potomek může být mimo schéma
        • ale záleží, kde se kříží (viz hvězdičkový prefix/suffix)
      • pravděpodobnost zničení schématu křížením je $\leq\frac{\delta(S)}{m-1}$
      • takže pravděpodobnost zachování příslušnosti ke schématu je $\geq 1-p_k\cdot\frac{\delta(S)}{m-1}$
    • co mutace?
      • musí se změnit jeden z pevných symbolů schématu
      • tj. pravděpodobnost, že mutace zachová schéma je $(1-p_m)^{o(S)}\approx 1-o(S)\cdot p_m$
        • aproximace funguje, protože $p_m$ je hodně malé (takže v součtu podle binomické věty budou dominantní první dva členy, kde figuruje $p_m^0$ a $p_m^1$)
    • tedy $\xi(S,t+1)\geq\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}\cdot (1-p_k\cdot\frac{\delta(S)}{m-1})\cdot (1-o(S)\cdot p_m)$
    • $\geq\xi(S,t)\cdot\frac{\phi(S,t)}{\bar F(t)}\cdot (1-p_k\cdot\frac{\delta(S)}{m-1}-o(S)\cdot p_m)$
      • schéma $S$ přežívá dobře, pokud má malé $\delta,o$
  • věta o schématech
    • krátká nadprůměrná schémata s nízkým řádem pokrývají exponenciálně rostoucí počet řetězců v po sobě jdoucích generacích genetického algoritmu
    • pozor, máme omezenou velikost populace
  • hypotéza o stavebních blocích
    • genetický algoritmus hledá řešení blízké optimu řetězením krátkých schémat
    • evoluce nefunguje dobře, když se optimum nedá poskládat z krátkých bloků
    • není to věta
• jsou GA dobrou simulací biologické evoluce?
  • evoluce nekončí a nezačíná vždy od nuly (bootstrapping)
    • SAGA – proměnlivá délka genotypu; značně zkonvergovaná populace se mění postupnými mutacemi, ne křížením
    • neutrální sítě – drobné náhodné změny v genotypu nemusí měnit fitness, ale můžou populaci posunout jinam
  • další variace GA spojené s dospíváním a učením (fitness se mění v průběhu života jedince)
  • co se nemění – genetická reprezentace jedince, interakce s prostředím
• vylepšení GA
  • dělení na druhy
    • definuje se vzdálenost – míra podobnosti jedinců
    • křížení jenom v rámci druhu
    • ochrana nových druhů – jedinec má čas, aby se zdokonalil
      • po omezenou dobu od vzniku nového druhu se při selekci jedinců zohledňuje jenom fitness v rámci jejich vlastního druhu
  • proměnlivá velikost populace
    • optimální velikost populace se těžko určuje
    • stárnutí – jedinec je po určitém počtu generací vyřazen
      • těžko se nastavují parametry
  • kódování – různé přístupy
    • konečná doména – pevný počet bitů
      • potenciální problém: pro rozlišení pěti prvků potřebujeme tři bity, ale tím dostaneme osm prvků
    • celá čísla – binární, Grayův kód
    • reálná čísla – různá kódování (omezený rozsah, pevný počet desetinných míst, plovoucí desetinná čárka)

Neuronové sítě

• umělá neuronová síť
  • soubor neuronů propojených ohodnocenými spoji, které přenášejí signály
  • neurony: vstupní, výstupní, skryté
    • pracují paralelně
  • různé aktivační (přenosové) funkce: lineární, skoková, sigmoida, ReLU
  • architektura: dopředné šíření, rekurentní
• učení
  • s učitelem, bez učitele
  • online (spřáhnuté) × offline (dávkové)
    • upravují se váhy rovnou na základě každého vstupu nebo až najednou pro celou dávku?
  • algoritmus zpětného šíření
  • na začátku náhodné hodnoty vah, pak gradient descent (případně se používá ještě momentum)
• rekurentní neuronové sítě (RNN)
  • posuvné okénko (tzn. síť předpovídá další prvek v řadě na základě minulých $k$ prvků pro fixní $k$) někdy nestačí – potřebujeme, aby si síť pamatovala informace
  • jak si se zpětnou hranou poradí algoritmus zpětného šíření?
    • neurony zdvojíme, vystačíme si s dopřednými hranami
    • při úpravě vah klonů upravujeme váhy původních neuronů
  • LSTM, GRU
  • někdy se používá reinforcement learning
  • základní architektury rekurentních sítí
    • Elman – uchovávají se stavy ze skrytých neuronů
    • Jordan – uchovávají se stavy z výstupních neuronů
• kombinace evoluce a NS
  • NS nám zajistí hladkost prohledávaného prostoru (malá změna váhy trochu změní výstup)
  • různé úrovně granularity
    • fylogenetická – jenom GA
    • vývojová – síť doroste
    • ontogenetická – síť se učí
  • přímočaré zobrazení „senzory → motory“
  • robustnost vůči šumu
• evoluce vah a parametrů učení
  • proč
    • GA zkoušejí celou populaci sítí – ne jen jednu síť
    • nejsme omezeni architekturou ani aktivační funkcí (nemusí být diferencovatelná)
    • nepotřebujeme detailně znát výstup sítě pro každý vzor
  • kódování vah
    • řetězec reálných čísel
    • řetězec binárních čísel – jako čísla s pevnou desetinnou čárkou se zadanou přesností
      • varianta: dynamické kódování – v průběhu učení zafixujeme vyšší bity a síť se učí jen ty nižší (tzn. zajistíme jistou kvalitu řešení)
  • příklad: k analýze sonarových signálů fungoval GA lépe než zpětné šíření
  • jiná strategie: kombinace evoluce a učení s učitelem
    • zpětné šíření je citlivé na počáteční nastavení vah – GA nám ho může najít
  • gen může kódovat i hyperparametry a typ architektury
    • naopak nemusíme kódovat váhy
    • přímé (kód obsahuje přesné váhy) vs. nepřímé kódování
• evoluce architektury
  • genetický kód může obsahovat plán budování sítě
    • posloupnost segmentů = vrstev
    • jeden segment kóduje vlastnosti uzlů (počet neuronů, aktivační funkce, geometrické rozložení) a vlastnosti spojení (hustota, parametry učení)
    • pak se použije backpropagace
    • ve fitness se dá penalizovat počet spojů nebo počet cyklů učení
  • genotyp může kódovat přepisovací pravidla – výsledkem přepisování je binární matice sousednosti (spojení) mezi neurony
  • dozrávání – síť roste v době, kdy se robot pohybuje ve světě
    • genotyp kóduje pozici neuronu, směr růstu axonů, délku axonů
    • růst závisí i na aktivitě robota
  • taky se dá dělat evoluce pravidel učení

Evoluce programů a robotů

• genetické programování
  • genetický řetězec nekóduje řešení problému, ale program řešící problém
  • typicky to vychází z LISPovské reprezentace programů
  • postup
    • zvolí se množina funkcí $F$ a terminálů $T$
      • funkce musí být uzavřené, tj. všude definované
    • náhodně se vygeneruje počáteční populace
    • dále jako genetický algoritmus
  • křížení – vezmeme dva jedince (stromy), prohodíme jejich větve
    • tak nám vzniknou syntakticky správné programy
  • mutace – zvolí se uzel a zruší se nebo se tam vytvoří nový podstrom
    • moc se nepoužívají
  • vylepšení: automaticky definované funkce (funkce nahrazuje celý podstrom)
    • chromozom obsahuje např. 3 stromy
    • první (hlavní) strom může obsahovat reference na ten druhý a třetí
    • druhý strom může obsahovat reference na ten třetí
• alternativní přístup: gramatická evoluce
  • evoluce programu v libovolném programovacím jazyce
  • používá to lineární genom (kdežto GP používá stromy)
  • zobrazení z genotypu na fenotyp se dělá podle gramatiky
  • jak se má uplatnit pravidlo? na to se používá kodon (číslo)
    • tzn. konkrétní prvek v genotypu slouží k výběru správné pravé strany přepisovacího pravidla
    • vždycky přepisujeme nejlevější neterminál
      • tudíž ten algoritmus vlastně generuje stromy, které se zanořují doleva
  • přesný postup
    • začneme s výchozím neterminálem
    • interujeme přes prvky genetického kódu
      • zvolíme nejlevější neterminál, tomu v naší gramatice odpovídá seznam pravidel
      • aktuální prvek genetického kódu nám říká, kolikáté pravidlo ze seznamu máme aplikovat
• evoluce robotů
  • problémy
    • mechanická odolnost
    • přívod energie
    • analýza – vyvinutý řídící systém může být hodně složitý
    • časová náročnost
    • návrh fitness funkce
  • přístupy
    • evoluce fyzických robotů – Khepera
    • simulovaná evoluce – pozor, často zneužívá rozdíl mezi simulací a realitou

Schéma evolučního experimentu

• přemístění
  • jedince umístíme na náhodné místo
  • kdybychom v simulaci recyklovali pozici, v níž skončil minulý jedinec, tak by to mohlo dalšímu jedinci ztížit podmínky
  • kdybychom používali vždycky stejnou výchozí pozici, tak by se robot mohl naučit pevnou posloupnost kroků
• simulovaná evoluce
  • fyzická evoluce trvá dlouho a různí roboti se můžou chovat různě
  • dává smysl nejdřív použít simulovanou evoluci a pak vyzkoušet nejlepší jedince na reálných robotech (abychom si byli jistí, že to vůbec funguje)
  • je důležité zvážit, jak moc má simulace odpovídat realitě
• interakce robota s prostředím (jak to modelovat v simulaci)
  • senzory a motory můžou fungovat rozdílně, i když jsou identické
  • je potřeba nějak modelovat šum
  • tělo robota a charakteristiky prostředí musejí být přesně reprodukované (mřížka jako model prostředí často nestačí)
  • často chceme sestavit minimální simulaci – modelovat toho co nejmíň
    • tzv. základní množinu charakteristik (jak robot interaguje s prostředím) musíme modelovat přesně
      • mezi pokusy se přiměřeně mění, aby bylo řízení dostatečně robustní
    • simulace má pak ještě tzv. implementační aspekty
      • ty neodpovídají realitě, jsou to čistě vlastnosti simulace
      • musíme je mezi pokusy měnit, aby je robot nemohl použít k „podvádění“
• charakteristiky fitness funkce
  • funkcionální × behaviorální
    • funkcionální: měří mechanické komponenty nebo interní stavy, které se podílejí na výsledném chování (např. jaká je frekvence, s jakou robot kráčí)
    • behaviorální: měří celkové efekty / výsledky chování (např. jakou vzdálenost robot ujde)
  • explicitní × implicitní
    • explicitní: říká robotovi, jak řešit úkol – přísně ohraničuje chování pomocí pravidel, která musí být splněna (např. hýbej se dopředu, udržuj 10cm vzdálenost ode zdí, netoč se na místě)
    • implicitní: sdělíme robotovi cíl, aniž bychom mu řekli, jak ho má dosáhnout (např. jak dlouho vydržel pracovat)
  • externí × interní
    • externí: dá se měřit jenom zvenku (v simulaci lze snadno použít)
    • interní: je dostupná robotovi z jeho senzorů
  • jak zvolit fitness
    • „inženýrský přístup“ – FEE (funkcionální, explicitní, externí)
    • pro neznámé a nepředvídatelné prostředí potřebujeme BII
      • to je nejlepší kombinace (teoretický ideál) – neříkáme robotovi, jak má problém řešit; evoluce má volné ruce
      • problém s implicitní fitness: může být hodně těžká pro náhodného robota (bootstrapping problem)
    • subjektivní fitness (jedinci jsou hodnoceni člověkem) → BEE
• přímý pohyb s obcházením překážek
  • lze použít Braitenbergovo autíčko
    • motory jsou přímo spojené se senzory (pomocí vážených spojů)
    • pozor, existují rovnovážné body, kde se vstupy navzájem anulují – autíčko se zastaví (ten problém řeší rekurentní spoje, ale ty se špatně nastavují)
  • můžeme uvažovat neuronovou síť bez skrytých neuronů
    • 8 vstupních neuronů (infračervené snímače)
    • 2 výstupní neurony (motory, sigmoida zajišťuje vhodný rozsah výstupů)
    • další 2 „vstupní“ neurony přenášejí výstup z minulého kroku zpátky na vstup
  • teoreticky by robot mohl couvat, ale vždy preferoval směr, kde má více senzorů
  • fitness
    • $\phi=\frac 1n\sum_k \phi_k$
    • $\phi_k=V_k(1-\sqrt{\Delta V_k})(1-i_k)$
      • fitness za $k$-tý krok
    • $V_k=|l_k|+|r_k|$
    • $\Delta V_k=|l_k-r_k|$
    • $l_k,r_k$ … rychlosti motorů
    • $i_k$ … normalizovaná hodnota nejaktivnějšího infračerveného senzoru

Vizuální navigace, readaptace, reaktivní inteligence

• vizuální navigace
  • jak zpracovat obraz
    • klasicky – předzpracování, segmentace, hledání vzorů…
    • evolučně
  • Harvey, 1994 – portálový robot („gantry robot“)
    • kamera je zavěšená z portálového jeřábu řízeného počítačem
    • obraz přes zrcadlo, má 64 pixelů
    • vývoj SAGA
    • současná evoluce neuronové sítě a recepčních polí
      • recepční pole jsou popsány pomocí polárních souřadnic
      • z celého pole se rovnoměrně vybere 25 pixelů, jejich jas se zprůměruje a převede na 4bitové číslo
    • řešené úlohy
      • vyhýbání se překážkám
      • sledování pohyblivých cílů
      • rozlišování objektů
    • bootstrapping (pro úlohu nalezení bílého trojúhelníku a vyhýbání se bílému obdélníku)
      • přímá evoluce neúspěšná
      • fungovala evoluce ve 3 stádiích s různými fitness funkcemi i prostředím
        1. najdi bílou stěnu
        2. najdi bílý obdélník
        3. cílová úloha
      • problém: inkrementální evoluci musí navrhnout experimentátor
• readaptace
  • jak modifikovat řídicí systém při změnách vnějších podmínek
  • dvě úrovně
    • jedinec – využije robustnost a generalizaci neuronových sítí
    • populace – využije se různorodost jedinců v populaci
      • readaptace po změně robota
        • např. místo Khepery použijeme Koalu, protože má silnější motory
        • Koala má víc IR senzorů, tak použijeme jenom půlku z nich
      • přechod ze simulace do reality
        • úspěch přechodu může záviset na tom, jak v simulaci modelujeme šum
        • přechod ze simulace do reality je také krokem inkrementální evoluce
  • evoluce robotů je kontinuální proces s otevřeným koncem
• reaktivní inteligence
  • reaktivní systémy – senzory jsou přímo připojené k motorům a na stejný stav senzorů systém reaguje stejně
    • systém může mít pomocné stavy, které slouží k určení motorických akcí
    • vtělené systémy – mají tělo, to má nějaké vstupy a výstupy
    • situační systémy – nacházejí se v externím prostředím a můžou reagovat s tímto prostředím
  • senzorově-motorická koordinace
    • nepotřebujeme vnitřní reprezentaci prostředí / složité vnitřní stavy
    • stačí nám koordinace vnímání a akcí
  • problém nejednoznačnosti vjemů
    • může se stát, že dva objekty generují stejné vjemy, ale vyžadují různé odezvy
    • řešení: vykonáme takové akce, které vjemy rozliší
      • tzv. aktivní vnímání – robot může jít vjemům „naproti“
  • může se stát, že se od sebe dva různé vjemy ze senzorů dají špatně rozlišit (ale chtěli bychom je umět rozlišit)
    • to může řešit překódování stavů senzorů – zesílí se užitečné příznaky
      • typicky to řeší skrytá vrstva v neuronové síti
    • nebo to taky můžeme řešit pomocí aktivního vnímání
    • příklad: válec/stěna
      • pohyblivý robot odjel, jakmile objekt správně klasifikoval
      • takže měl paradoxně méně vjemů, kde došlo ke správné klasifikaci
    • index geometrické separability
      • chtěli bychom, aby vjemy pro stejné třídy byly blízko sebe
      • zaznamenáme si vjemy v průběhu experimentu
      • každému vjemu přiřadíme třídu
      • spočítáme podíl vjemů, jejichž nejbližší jiný vjem má stejnou třídu
  • další možné řešení: atraktor chování
    • robot na signály senzorů reaguje takovým způsobem, že na určité pozici vznikne atraktor – robot se tam nakonec dostane a bude tam oscilovat
    • je to emergentní chování, vzniká pouze interakcí agenta s prostředím
• umělá evoluce využívá omezení modelu
  • příklad: krysy hledají potravu
  • Khepera – pohybuje se po zakřivené dráze a nutně najde dlouhou stěnu
  • když odebereme omezení prostředí – např. náhodně generujeme velikost arény – tak je úloha těžší, evoluce nemůže tato omezení zneužívat

Moduly

• modulární architektura
  • v evoluční robotice nejsou moduly nutné, ale možná budou fungovat dobře
  • přizpůsobíme tomu architekturu
  • úlohy: sběr odpadu, navigace s návratem domů
• sběr odpadů
  • Khepera čistič s ramenem
  • dlouhá posloupnost akcí – najdi válec, seber ho, odvez ho za hranici arény (přitom se vyhýbej dalším válcům a stěnám…)
  • testování několika architektur
    • bez skryté vrstvy
    • se skrytou vrstvou
    • s rekurentními spojeními
    • s dvěma sadami výstupů – podle stavu chapadla
    • emergentní modulární architektura
      • místo jednoho výstupu uvažujeme několik modulů (např. 2)
      • každý modul sestává z arbitra a výstupu
      • arbitři spolu soutěží – použije se výstup vítězného modulu
  • aby evoluce fungovala lépe, tak se po uchopení válce robotovi objevil v cestě uměle přidaný válec, který musel objet
  • emergentní modulární architektura umožnila najít správné řešení rychleji než jiné architektury a umožnila vývoj robustnějšího řešení (pro přenesení na reálného robota výkon příliš nepoklesl)
    • ale arbitři nefungovali tak, jak bychom čekali – moduly se přepínaly velmi rychle, žádný neodpovídal nějakému základnímu chování
    • vypadá to, že hlavní úlohou modulů je zlepšení schopnosti rozlišování objektů – robot vlastně provádí aktivní vnímání pomocí přepnutí modulů
• roboti s vnitřní dynamikou
  • úloha: návrat domů k nabíječce
  • simulovaná baterie
  • třívrstvý perceptron, 5 neuronů ve skryté vrstvě s rekurentními spoji
  • nabíječka v jednom rohu společně se zdrojem světla
  • chceme, aby robot jezdil co nejrychleji mimo nabíječku – tomu odpovídal výpočet fitness
  • jeden skrytý neuron „monitoroval baterii“ – ovlivňoval vnímání prostředí v závislosti na stavu baterie
  • další krok experimentu: zkoumání readaptace
    • zdroj světla se přesunul do jiného rohu (takže už nebyl u nabíječky)
    • robot se rychle přizpůsobil
    • nejsnáze se přizpůsobil, když se světlo přesunulo do opačného rohu

Učení a evoluce

• učení a evoluce
  • dvě různé formy biologické adaptace
  • evoluce – na populaci, operuje na genotypu
  • učení (ontogenetická adaptace) – v jednom jedinci po dobu jeho života, ovlivňuje jenom fenotyp
    • budeme uvažovat umělé neuronové sítě (učení vah)
  • konekcionismus rozlišuje
    • učení – změny synaptických vah
    • paměť – změny aktivačních stavů neuronů v rekurentních sítích
  • učení se zpětnou vazbou z prostředí pracuje rychleji než evoluce
    • ale výsledky učení se přímo nepřepisují do genotypu
• výhody učení
  • učení zjednodušuje přizpůsobení se rychlým změnám v prostředí
  • učení má bohatší zpětnou vazbu z prostředí než evoluce
  • i evolučně suboptimální jedinci můžou přežít, pokud se dovedou dobře učit
    • ale učení stojí čas, takže evoluce upřednostňuje jedince, kteří mají dané vlastnosti od narození
  • učení umožňuje vytvořit složité fenotypy z krátkých genotypů – část informací se extrahuje z prostředí
• nevýhody učení
  • ne vždy je možné naučit se, co je potřeba (když se nějaký podnět nevyskytne, tak na něj jedinec neumí reagovat)
  • učení trvá dlouho – dosud nenaučený jedinec se nechová optimálně
  • nenaučený jedinec si může ublížit
• jak učení pomáhá evoluci
  • učení dělá fitness funkci „hladší“
  • Hinton, Nowlan
  • kanalizační efekt
    • učení umožňuje prohledávání okolí kandidátů
    • zároveň když evoluce najde jedince s geny částečně fixovanými na správných hodnotách, tak jim začne dávat přednost oproti těm, které je fixované nemají (ale můžou se je naučit)
• učení a evoluce můžou mít různé cíle
  • pokud je fitness funkce evoluce definovaná jinak než chybová funkce učení
  • prostor učení a prostor evoluce pak vypadají jinak
  • příklad
    • evoluce je řízená schopností hledat potravu
    • neuronová síť
      • má jednu skrytou vrstvu
      • obsahuje mj. dva výstupní neurony, na nichž se snaží předpovědět další stav senzorů (po vykonání motorické akce)
        • zde může probíhat učení
      • výstupní neurony, které ovlivňují motorickou akci, se sice přímo neučí, ale skrytou vrstvu sdílí s učenými neurony (tzn. učení je také ovlivňuje)
    • jedinci, kteří se učí, umí potravu hledat lépe než ti, kteří se neučí
    • takže vysvětlení podle Hintona a Nowlana nestačí
  • ještě jiná interpretace učení (Harvey)
    • učení umožňuje napravit chyby způsobené mutací
• evoluce učení
  • Floreano, Mondala
  • genotyp kóduje architekturu a pravidla učení pro váhy (ne jejich hodnoty)
  • můžeme mít různé druhy učících pravidel – určují, jak se mění spoje mezi neurony v závislosti na jejich aktivaci
  • výsledky
    • vyvinuté váhy zodpovídaly za učení i chování
    • učení začalo až po chvíli pohybu robota
    • vyvinuté chování vzniklo interakcí s prostředím, váhy se vyvíjely jen u senzorů, kde byla nějaká aktivita
• sekvenční úloha – zapnutí světla vypínačem
  • Urzelai, Floreano, 2001
  • robot má stisknout vypínač (rozsvítí světlo), pak jít ke světlu a tam zůstat
  • učení jedinci si uměli poradit se změnou barvy stěn (jedinci s genetický kódovanými váhami nikoliv)
  • podobně si poradili se změnou polohy vypínače a světla
• adaptace na rychlé změny prostředí
  • Ackley, Littman, 1991
  • organismus se skládal ze dvou modulů
    • výkonný – určuje pravděpodobnost vykonání akcí
    • vyhodnocovací – poskytuje zpětnou vazbu na základě výstupu hodnotícího modulu
  • genetický algoritmus vyvíjel váhy obou modulů
  • učení měnilo jenom váhy výkonného modulu na základě zpětné vazby z vyhodnocovacího modulu
    • kladná hodnota zvyšuje váhu, záporná ji snižuje
    • finální váhy se do genotypu nazpět nepřepisují
  • organismy se můžou reprodukovat, když mají dostatek energie a blízko sebe partnera, který je také připraven k reprodukci
  • potomkové vznikají křížením a mutací
  • organismy umírají, když jsou staré nebo nemají energii
  • autoři porovnávali
    • evoluci bez učení
    • učení bez evoluce
    • evoluci s učením – nejvýkonnější
• proměnlivé stěny
  • Nolfi, Parisi
  • Khepera hledá cíl v aréně, kde stěny můžou měnit barvu
  • fitness je vyšší, čím dřív Khepera najde cíl
    • ale Khepera nepozná, že už ho našla
    • takže musí důkladně prozkoumat arénu
  • dvě prostředí: tmavé stěny nebo světlé stěny
  • tmavé stěny Khepera detekuje, až když je velmi blízko
    • takže Khepera musí poznat, v jakém prostředí se ocitla, aby mohla vhodně zvolit strategii
  • porovnání učení × neučení
    • vyvinutí učící se jedinci byli před učením horší než neučící a po učení lepší
    • vyvinutí učící se jedinci měli predispozice k učení – ne k chování
• učená může být i morfologie (stavba těla)
  • Peter Krčah
  • tělo z kvádrů spojených panty, pohyb pantů řízený NS
  • evoluční algoritmus NEAT
  • jedinci se měli co nejrychleji pohybovat v kapalinách s různou viskozitou
    • dvě úlohy: pohyb ve volné vodě, pohyb při dně
  • učení – hillclimbing s mutacemi rozměrů kvádrů
  • fitness = nižší z průměrných rychlostí v obou prostředích
  • 8 mutací s krátkými testy rychlosti (případně se změna vrátila zpět), pak dlouhé měření rychlosti

Koevoluce, dravec-kořist

• kompetitivní koevoluce
  • současná evoluce dvou nebo více populací s provázanou fitness funkcí
  • „závody ve zbrojení“ – strategie se stávají složitější
  • dochází ke zlepšování, aniž bychom měnili prostředí nebo selekční kritéria
  • co když necháme fixní kořist a vyvíjíme dravce
    • strategie bude méně obecná – když se kořist změní, tak nemusí fungovat
    • pokud bude kořist dokonalá, tak nám u dravců nefunguje selekce, protože jsou všichni špatní
  • koevoluce může pomoct vyhnout se lokálním minimům
  • koevoluce nemusí vést ke zdokonalování jedinců – strategie se můžou pouze cyklicky opakovat
    • lze brzdit pomocí síně slávy – to ale neodpovídá přirozené evoluci a nemusí to vést k lepšímu výkonu
• jak sledovat vývoj?
  • když se zlepšuje jeden druh, tak se skoro jistě (relativně) zhoršuje druhý
  • takže se používá CIAO (current individual vs. ancestral opponents)
    • necháme nejlepšího jedince z aktuální generace utkat se s nejlepšími soupeři z minulých generací
    • generujeme bitmapu N×N, kde N je počet generací – pixel je černý nebo bílý podle toho, kdo vyhrál
    • ideálně by dravec z $i$-té generace měl porazit kořisti z všech předcházejících generací – matice by měla mít černou a bílou polovinu (podle hlavní diagonály)
  • po skončení evoluce můžeme uspořádat tzv. mistrovství – necháme nejlepšího z dané generace utkat se s nejlepšími ze všech generací (ideálně by křivka měla růst)
• aplikace koevoluce
  • třídicí sítě
    • cíl: třídící algoritmus pro data s určitými vlastnostmi (např. jsou částečně setříděné)
    • souboj: třídicí programy vs. testovací programy (unit testy)
  • hráč pro tic-tac-toe, Nim, zmenšenou verzi Go
• příklad: dravec-kořist s roboty
  • kořist vidí dravce, až když je velmi blízko
  • jedinec byl testovaný proti nejlepším soupeřům z předcházejících 10 generací
  • fitness kořisti = čas do kontaktu / maximální čas
  • fitness dravce = 1 – fitness kořisti
  • různé strategie, lze je pozorovat a popsat (ale těžko)
    • různí jedinci v populaci můžou mít různé strategie
  • fitness oscilovala, CIAO nepřehledné
  • aby se předešlo cyklení, dává smysl vybírat ze všech předchozích generací (ne jen z 10 předcházejících)
    • nedá se úplně zabránit cyklení strategií – těch tříd je konečně mnoho
    • metoda síně slávy fungovala líp – každý jedinec zápasí z 10 soupeřů náhodně vybraných z nejlepších jedinců ze všech předcházejících generací
      • metoda síně slávy vede na obecnější strategie
  • problematické třídy strategií (které se snadno cyklí)
    • dravec: pronásleduj kořist × sleduj kořist, zaútoč, až když je vůči tobě ve speciální pozici
    • kořist: stůj na místě krytá při stěně (dravec nechce narazit do stěny) × rychle se pohybuj (a vyhýbej se dravcovi i stěnám)
  • zkusili vylepšit kořist (dali jí vidění)
    • standardní koevoluce nebyla horší než síň slávy
  • experimenty s jednoduchou evolucí
    • evoluci se povedlo najít efektivní strategii proti jedné nejlepší strategii
  • experimenty bez vidění
    • jednoduchá evoluce dravce nefungovala, koevoluce fungovala lépe
    • jednoduchá evoluce pro kořist fungovala
  • existují úlohy, kde neexistuje úplně obecné řešení – pak je zacyklení strategií nevyhnutelné a optimální
  • experimenty s celoživotním učením
    • idea: jedinec se dokáže adaptovat na změnu strategie soupeře už v průběhu jedné generace
    • dva druhy úspěšných jedinců
      • úplně obecný – s jednou univerzální strategií
        • efektivnější, ale může být nedostupný
      • plasticky obecný – umí si vybrat vhodnou strategii z jednoduchých strategií
        • může být těžké ho najít
    • další experiment: genotyp kóduje taky pravidla učení
      • kořisti adaptace nepomáhala, měla slabé senzory (ve variantě, kde dravec viděl a kořist ne)
• koevoluce tvaru těla
  • Karl Sims
  • kvádry spojené klouby
  • organismy soupeří o kostku – vyhrává ten, kdo je k ní blíž
  • různé přístupy k soutěžím: každý s každým, napříč druhy, uvnitř druhů, …
• hra Tron
  • koevoluce stroj vs. člověk
  • programy byly reprezentované jako stromy, bylo použito genetické programování
  • poražení lidského protihráče → vyšší pravděpodobnost reprodukce
  • počítačové programy se zlepšovaly, lidská populace se nevyvíjela (lidé se učili jenom mezi po sobě jdoucími hrami)

Zobrazení genotypu na fenotyp

• zobrazení genotypu na fenotyp
  • dosud 1:1
  • ale dekódování genotypu na fenotyp může být ovlivněno prostředím
    • tak je to v přirozené evoluci – chceme se jí přiblížit (jak kvůli zlepšení umělé evoluce, tak kvůli zkoumání přirozené evoluce)
  • výsledná fitness je daná fenotypem
  • jedinec se může vyvíjet postupně – mít vývojová stádia
• genetické kódování
  • přímé kódování
    • jednoduché na implementaci, ale chtěli bychom něco s větší vyjadřovací silou (na krátkém rozsahu)
  • co bychom chtěli
    • vyjadřovací sílu
      • aby se daly kódovat různé aspekty robota
    • kompaktnost
      • aby se opakující struktury daly snadno kódovat kratším kódem
    • možnost rozvoje
      • aby se kód mohl zlepšovat pomocí genetických operátorů
      • pleiotropie – jeden gen může ovlivňovat více fenotypických rysů
        • to bychom chtěli omezit (aby se robot zároveň v nějakých charakteristikách nezlepšoval a v jiných nezhoršoval)
      • vhodná je modulární organizace zobrazení genotypu na fenotyp
        • může to být způsob, jak bránit pleiotropii
• kódování instrukcí růstu axonů
  • Nolfi, Miglino, Parisi, 1994
  • soustava neuronů s axony v rovině
  • genotyp obsahuje pokyny pro růst a větvení axonů
    • když axon doroste k jinému neuronu, tak vznikne spoj
    • axon roste jen tehdy, když aktivita neuronu překročí určitou hranici (je daná geneticky) → prostředí také ovlivňuje růst axonů
  • genotyp je rozdělený na bloky kódující charakteristiky jednotlivých neuronů a instrukce pro růst axonů
    • celkově max. 32 neuronů (10 vstupních, 17 vnitřních, 5 výstupních)
    • blok obsahuje osm prvků
      • práh pro růst
      • pozici (dvě souřadnice)
      • úhel větvení axonu
      • délku segmentů axonu
      • váhu (všechny spoje vycházejícího z jednoho neuronu mají stejnou váhu)
      • práh neuronu
      • typ neuronu (např. jestli řídí levý nebo pravý motor – pak se průměrují neurony, které řídí ten stejný motor)
  • úloha: najít cíl náhodně umístěný v aréně, cílová oblast může (ale nemusí) být osvětlená
• adaptace architektury NS
  • příliš malé sítě se nedovedou naučit správné zobrazení
  • příliš velké sítě špatně generalizují
  • tři metody automatického návrhu topologie sítě při učení
    • růst
      • kaskádový algoritmus učení korelací
      • začíná se vstupními neurony přímo spojenými s výstupními
      • přidává další neurony (připojené na vstup a na výstup), žádné spoje neodebírá
    • prořezávání
      • začne se velkou sítí, postupně ruší spoje, dokud se chyba nezhorší
      • např. ruší spoje s váhami blízkými nule
    • dekompozice
      • máme skupinu podsítí s různou architekturou (ale stejnými vstupy a výstupy)
      • různé podsítě se naučí různé vzory
  • tyhle metody jsou založeny na učení s učitelem – potřebujeme mít dostatek trénovacích dat
• kódování na úrovni buněk
  • v přírodě roste nervová soustava postupně – buňky se dělí a diferencují (stanou se z nich neurony), přesunou se na správná místa, vyrostou spoje
  • Cangelosi (1994) – dělení buněk a migrace
    • počet dělení je geneticky shora omezený
  • Gruau (1994) – dělení a diferenciace
• Gruauova simulace šestinohého robota
  • genotyp: binární strom (14 různých symbolů, některé s parametrem)
  • přepis do fenotypu – založí se neuron odpovídající kořeni stromu
    • uzel popisuje operace, které se mají na buňce vykonat
  • vylepšená verze: terminální uzel se může odkazovat na jiný strom
    • ADNS (automatické definování neuronových podsítí)
  • aplikace: šestinohý robot
    • křížení – záměna podstromů
    • s ADNS fungoval lépe, genotyp obsahoval 3 stromy
  • fitness: ušlá vzdálenost
  • při evoluci použil 32 ostrovů na toroidu – pravděpodobnost spárování byla úměrná vzdálenosti na toroidu
  • s ADNS byly výsledné sítě dobře strukturované
• jednoduché geometricky orientované kódování buněk
  • Kodjabachian a Meyer, 1998
  • simulovaný šestinohý robot
  • opět z neuronů rostou axony
  • křížení – záměna podstromů jako v GP
  • genotyp – 6 instrukcí
  • fitness: ušlá vzdálenost + člen podporující pohyb nohou
  • stabilní genetický algoritmus
    • konstantní počet jedinců
    • při vytvoření nového jedince se z aktuální populace vybere nějaký jedinec, který se zahodí
    • dá se dobře paralelizovat – akorát se pak nedá jasně říct, kdy začíná a končí generace
  • jedinci jsou rozmístění na kružnici
    • náhodně se zvolí bod na kružnici
    • v blízkosti tohoto bodu zvolíme dva jedince, vyrobíme nového jedince
    • turnajem zvolíme souseda v blízkosti toho bodu, který bude nahrazen novým jedincem

Kráčející stroje

• kráčející stroje
  • složitější než kolečka – noha potřebuje aspoň 2 stupně volnosti
    • trik: můžeme použít symetrie
    • ale všechny nohy se nemůžou pohybovat stejně
  • asi chceme využít symetrii, abychom si úlohu zjednodušili
  • statická × dynamická chůze – podle toho, jestli je těžiště stále nad mnohoúhelníkem dotyku noh
    • trojkrok – statická chůze
• první pokusy s kráčením
  • Brooks – každá noha má stejný (ručně sestavený) konečný automat
  • Maes, Brooks – koordinace noh se dá naučit metodou pokus-omyl
  • Beer, Gallagher – simulovaný šestinohý brouk
    • evoluce může najít systém chůze s minimem předem zadaných parametrů
    • noha
      • má dva stavy – dole (na zemi), nahoře (zvednutá)
      • může se hýbat nahoru a dolů a také se otáčet dopředu/dozadu
      • má senzor – úhel mezi nohou a tělem
      • 5 neuronů – 2 skryté, 3 ovládají pohyby
    • když ztratí rovnováhu, tak padá (obviously 🙃)
    • vždy se vyvinul trojkrok
    • 4 vypozorované fáze učení
      1. zatlačil všemi šesti nohami a spadl dopředu
      2. nekoordinované pohyby nohou, časté pády
      3. nejlepší měli statickou stabilní chůzi
      4. doladěný statický krok
• pokročilejší kráčející roboti
  • Lewis – fyzický šestinohý robot
    • každá noha s dvěma stupni volnosti
    • inkrementální evoluce a funkcionální dekompozice
      • evoluce řízení jedné nohy
      • koordinace nohou
    • genotyp – váhy v Grayově kódu
    • 2 neurony na jednu nohu – zdvih, švih
      • když oscilovaly s fázovým posunem 90°, tak noha dělala kroky
    • první fáze – evoluce řízení pro nohu
      • fitness se určuje vizuálně podle obrazovky počítače
    • druhá fáze – evoluce řízení oscilátorů
      • nejprve vlnění, pak trojkrok
    • robot nemá senzory
  • Gomi, Ide – 8nohý robot bez senzorů
    • celý vývoj na fyzickém robotu
    • nejprve vlnitá chůze, potom čtyřkrok
  • Jakobi – řízení pro stejného robota, ale formou minimální simulace, navíc měl robot senzory
    • oproti předchozím experimentů nebylo řízení tak robustní, bylo na hraně technických možností
  • Gruau – evoluce architektury (viz výše)
  • Ijspeert – na základě modelu mihule vyvinul model mloka, který uměl plavat i chodit
    • propojené generátory řídicích signálů (tzv. CPG, central pattern generator)
  • Sony – pes Aibo
  • Honda – humanoid ASIMO
• někteří roboti se dovedou přestavět – změnit svoji morfologii
  • např. rozdělit se na menší roboty nebo metamorfovat
  • ukázka s modulárními polokostkami/poloválci
  • M-TRAN – kombinace magnetů a paměťových pružin
  • zase generátory signálů – každý modul má svůj CPG, které spolu komunikují
    • realizované jako oscilující neurony
  • příklad robota popsaného tak, že se na něj dá použít evoluční algoritmus
    • genotyp – posloupnost segmentů
    • křížení jenom na hranici segmentů
    • mutace zamění celý segment

Evoluční učení neuronových sítí

• mozek se vyvinul evolučně
  • když to dokáže mozek, tak by to mělo jít i s umělou neuronovou sítí v umělé evoluci
  • neuronové sítě jsou výkonné ve spoustě oblastí – především když neexistuje dobrá teorie
  • předpokládalo se, že neuroevoluce nahradí zpětné šíření chyby (tzn. při učení s učitelem)
    • ale zajímavějších výsledků neuroevoluce dosahuje v situaci, kdy nemáme správné výstupy (tzn. když nemůžeme jednoduše použít backpropagaci)
    • evoluční strategie jsou dosud nejlepší metodou, jak optimalizovat hyperparametry sloužící k učení NS
• sekvenční úlohy z rozhodování
  • skrytý Markovovský model (POMDP)
  • temporal difference reinforcement learning
    • Q-učení
    • těžké, když je stavový prostor rozsáhlý/spojitý a když má prostor skryté stavy (partial observability)
  • neuroevoluce je jiná
    • hledáme přímé nelineární zobrazení ze senzorů na akce
    • rozsáhlost/spojitost za nás řeší neuronová síť
    • skryté stavy můžeme řešit pomocí paměti (RNN)
• dva přístupy k neuroevoluci
  • dosud jsme měli optimalizaci vah a pevnou architecturu sítě = konvenční neuroevoluce
  • mohli bychom ale také optimalizovat architekturu
• základní metody neuroevoluce
  • máme pevnou topologii (obvykle pevné propojení)
  • evolučně se vyvíjejí váhy sítě (nepoužívá se algoritmus zpětného šíření)
  • genotyp – řetězec bitů nebo reálných čísel
    • pevná topologie
    • úplné propojení
    • náhodně generovaná počáteční populace
  • problémy
    • předčasná konvergence
    • příliš mnoho parametrů optimalizujeme naráz (tisíce vah)
    • různé kódy odpovídají stejným sítím (liší se jenom permutace neuronů)
      • křížení pak vytváří málo nových jedinců
      • tzv. permutační problém
• pokročilá neuroevoluce s pevnou architekturou sítě – metody
  • SANE
  • ESP
  • CoSyNE
• symbiotická adaptivní neuroevoluce (SANE)
  • jedna skrytá vrstva, vyvíjejí se jednotlivé skryté neurony
  • při vyhodnocení se z nich vybere $k$ neuronů a složí se síť
  • to se opakuje, aby byl každý neuron vyhodnocený aspoň 10×
  • fitness neuronu je průměrná fitness přes všechny testy, kde jsme ho použili
  • takže se neurony specializují a fungují v symbióze s ostatními
  • každý neuron má 5 spojů, ty můžou vést ze vstupní vrstvy nebo do výstupní vrstvy (o tom rozhoduje parametr, který je součástí genetického kódu)
  • porovnání symbiotické a standardní evoluce – u standardní rychle klesá diverzita (měří se pomocí Hammingovské vzdálenosti)
  • příklad: cartpole
• vynucené subpopulace / enforced sub-populations (ESP)
  • neurony jsou rozdělené na druhy – vyvíjejí se v rámci druhů
  • jeden skrytý neuron odpovídá jedné subpopulaci
  • možnost vyvíjet i rekurentní sítě
  • úspěšné při řešení těžkých úloh – např. balancování dvou tyčí
  • velký prohledávaný prostor tak vlastně rozdělíme na podúlohy
• kooperativní synaptická neuroevoluce (CoSyNE)
  • máme subpopulace pro váhy
  • váhy pro $i$-tou synapsi jsou v subpopulaci $P_i$
    • $i$-tý řádek matice
  • sloupec $x_j$ jsou hodnoty vah pro všechny synapse v síti
    • sítě $x_1,\dots,x_m$ se vyhodnotí a dostanou fitness
    • nejhorší sloupce se nahradí novými potomky
  • kooperativní koevoluce pro každou subpopulaci odděleně
    • několik prvků z populace se vybere a zamíchá (takže se vymění hodnoty dané váhy napříč sloupci/sítěmi)
    • víc se permutují prvky s nižší fitness
  • také se někdy používá CMA-ES
    • covariance matrix adaptation evolution strategy
    • vyvíjejí se jednotlivé celé sítě
    • při mutacích se zohledňují korelace mezi váhami
• NEAT
  • začíná se s malou sítí, sítě můžou růst
  • smysluplné křížení sítí s různou topologií
  • ochrana inovací pomocí druhů
  • uzly a váhy v síti mají tzv. historické značky
    • podle nich se párují při křížení
    • potomci dědí historické značky svých rodičů
  • přidání spoje je mutace
  • musíme si hlídat, aby měl konkrétní spoj v celé generaci jenom jednu historickou značku
    • u neuronů to asi nehlídáme
    • je to taková heuristika, kterou se trochu bráníme proti permutačnímu problému
  • křížení
    • zarovnají se geny hran se stejnými značkami
    • potomek dostane náhodně jeden z genů se stejnými značkami (tzv. odpovídající si geny)
    • disjunktní geny z obou se zkopírují
    • přesahující geny se zkopírují jenom od rodiče s vyšší fitness
      • to jsou ty geny, jejichž časové značky jsou větší než všechny časové značky ve druhém rodiči
  • ochrana inovací
    • dělíme jedince do druhů (k tomu musíme mít nějakou metriku – vzdálenost mezi jedinci)
      • $\delta=\frac{c_1E}N+\frac{c_2D}N+c_3\bar W$
      • $E$ … počet přesahujících genů
      • $D$ … počet disjunktních genů
      • $N$ … počet genů ve větším jedinci
      • $\bar W$ … průměrný rozdíl vah odpovídajících si genů
      • $c_1,c_2,c_3$ … konstanty určující váhy kritérií
    • nový druh je po několik generací chráněný – jedinci soutěží jenom mezi sebou
    • jedinci sdílejí zdroje s ostatními jedinci svého druhu – mají upravenou fitness
      • také si hlídáme, aby jeden druh nepokryl celou populaci
    • rozdělení do druhů můžeme ovládat nastavováním vzdálenostních konstant v každé generaci
    • používáme elitismus
  • při vyhodnocení na cartpolu fungoval NEAT podobně jako ESP
    • na těžší úloze byl lepší
• cellular encoding
  • Gruau, Whitley, Pyeatt, 1996
  • viz Gruauova simulace šestinohého robota
  • pravidla růstu – gramatika
  • nepřímé kódování – genom je komprimovaný

Od simulace k realitě

• Karl Sims – kvádroví roboti
  • fenotyp robota – strom
    • vrcholy reprezentují kvádry, hrany reprezentují spoje
    • každý vrchol grafu navíc obsahuje neuronovou síť, rozměry kvádru atd.
  • genotyp je graf, ne nutně strom
    • hrany můžou tvořit cykly
    • je tam jeden speciální kořenový uzel
  • přepis genotypu na fenotyp
    • rekurzivním procházením grafu po hranách
    • začíná se v kořeni
    • navštívené hrany a uzly se kopírují do fenotypu
    • opakované návštěvy vloží kopie
      • jsou tam rekurzivní limity – maximální povolené počty opakování – aby se předešlo nekonečným cyklům
    • hrana může být označená jako reflexivní podle osy x/y/z, pak je podstrom zkopírovaný symetricky
• Hornby – L-systém
  • řízení robota se vyvíjí spolu s jeho morfologií (tzv. vtělená umělá inteligence)
  • generativní kódování – aby se pomocí jednoduchého genotypu dal popsat složitý robot
  • Tinkerbot
    • morfologie popsaná L-systémem
    • genotyp je bezkontextový 0L-systém vyvíjený genetickým algoritmem
    • podle L-systému se vygeneruje popis těla robota ve speciálním konstrukčním jazyku (podobný jazyku Logo)
  • L-systém – jako bezkontextová gramatika, akorát v každém kroku musím přepsat všechny neterminály najednou
• Lipson, Pollack – GOLEM
  • Genetically Organized Lifelike ElectroMechanics
  • robot skládající se z tyčích spojených kulovými klouby
  • vyvíjený v simulaci
  • řízení
    • neuronová síť bez omezení spojů
    • neuron může být připojený na tyč a ta se stane svalem – její délka se mění podle výstupu neuronu
  • cíl evoluce: co nejrychlejší pohyb po rovině
  • výsledný robot vytištěný na 3D tiskárně, potom se do tyček vložily motory
• projekt ERO
  • studentský softwarový projekt
  • genotyp analogický tomu Simsovému
  • hierarchický NEAT
• soft robots
  • příroda používá tvrdé i měkkné materiály!
  • přímé kódování nefunguje dobře
  • nepřímé kódování vyvíjené algoritmem HyperNEAT funguje líp
    • generující síť CPPN (compositional pattern producing network) dostává na vstupu 3D souřadnice a vzdálenost od středu a vrací materiál voxelu (+ informaci, zda má být vůbec přítomný)
• growing soft-bodied creatures
  • růst (morfologický vývoj) je odpovědí na stimuly z prostředí
    • kořeny rostlin sledují, kde jsou v půdě živiny
    • lidské kosti a tkáně přizpůsobují svoje vlastnosti v reakci na mechanickou zátěž
  • vlastnosti materiálu těla organismu ovlivňují evoluci i adaptivní chování
    • hypotéza: tvrdost/měkkost stavebního materiálu dovoluje vyvinout inteligentní chování
    • hypotéza: při správné kombinaci geometrie, vlastností materiálu a procesu růstu může robot využívat tzv. morfologické počítání
  • dva generátory CPPN – jeden určuje, zda je voxel plný nebo prázdný, druhý určuje, zda se smršťuje nebo roztahuje
• evolved electrophysiological soft robots
  • každý voxel má elektrický potenciál – rozdíl napětí uvnitř a vně buňky
    • když vnější napětí překročí práh, tak se buňka depolarizuje a prudce zvýší napětí
    • pak se napětí zase sníží (buňka se repolarizuje) a klesne do záporu
    • pak se buňka zotavuje (tzv. refrakční doba) a nedokáže přijmout impuls zvenku
  • organismus má centrální stimulátor, který pravidelně vysílá impulsy
  • CPPN je vyvíjený algoritmem HyperNEAT
  • excitovaná buňka může vybudit až 26 sousedních buněk
  • čas potřebný k excitaci sousední buňky je poloviční oproti době depolarizace, vzruchy se šíří jako vlny
  • refrakce trvá 5× déle než repolarizace
  • typy buněk
    • prázdná
    • vodivý sval
    • nevodivý sval
    • vodivá pasivní tkáň
    • nevodivá pasivní tkáň
    • stimulátor – přibližně uprostřed prostoru 10×10×10
  • fitness funkce odráží vzdálenost, kterou robot ušel (maximalizuje se), a také počet vodivých buněk (ten se minimalizuje? asi aby robot nebyl celý vodivý, ale měl pouze „nervy“)

Robotické roje

• znaky robotických rojů, technologické motivace
  • velké množství jedinců, ti jsou homogenní a poměrně jednoduší
  • interakce mezi jedinci jsou založeny na jednoduchých pravidlech, která používají pouze lokální informace
  • celkové chování je výsledkem samoorganizace
  • robustnost, škálovatelnost, všestrannost/flexibilita, nízká cena?
  • superlineárnost – roboti mají dohromady větší schopnosti než prostý součet jejich jednotlivých schopností
• koordinovaný průzkum
  • tři přístupy: monitorování prostředí, feromonová robotika, řetězení
  • monitorování
    • robotický roj se snaží lokalizovat zdroj vůně/zápachu
    • jednoduché chování založené na detekci zápachu a větru
    • komunikace může zlepšit efektivitu
    • algoritmus
      • když nedetekuješ zápach → pohybuj se po rozšiřující se spirále
      • když detekuješ zápach → pohybuj se proti větru
  • feromonová robotika
    • viz dále
  • řetězení
    • omezený dosah senzorů
    • signalizace barvami
• feromonová robotika
  • roj se skládá z autonomních robotů bez centrálního řízení
  • agent pracuje jenom s lokálními informacemi
    • nemá mapu prostředí (mapa prostředí se v dynamickém prostředí špatně udržuje)
    • používá feromonovou stopu (dá se detekovat jen lokálně, odpařuje se a šíří se do okolí, agent může feromon vylučovat)
  • rozptýlení robotů
    • roboti, kteří se vidí, ale jsou daleko od sebe, se přitahují
    • roboti, kteří se vidí, ale jsou příliš blízko sebe, se odpuzují
  • robot, který najde cíl, začne vydávat (virtuální) feromon
  • virtuální feromon – zprávy posílané mezi roboty v dosahu
    • zpráva obsahuje typ feromonu a počet přeskočení (přes kolik robotů už prošla)
    • každý agent dostane více zpráv se stejným typem, tak vybere tu, která má nejnižší počet přeskočení, zvýší ho o jedna a pošle ji sousedům
    • nejkratší cestu k cíli robot najde tak, že se vydá směrem, odkud přišla zpráva s nejnižším počtem přeskočení
  • pokrytí grafu
    • navštívit každý uzel / projít každou hranu
    • klasický přístup: zmapovat graf, navrhnout plán na průchod grafem
      • vyžaduje to mít složitý hardware, který to zvládne spočítat, také bychom museli při změně grafu počítat nový pán
    • plánování v reálném čase
      • používáme jenom lokální informace (značky na uzlech/hranách)
      • jednoduché algoritmy
      • při změně grafu se algoritmus nemění
    • algoritmus (na začátku jsou počítadla nulová)
      • zvyš počítadlo aktuálního uzlu o jedna
      • přesuň se na sousední uzel s nejmenším počítadlem
  • varianty algoritmu pokrytí uzlů
    • na začátku kroku jsme na pozici $s$, pak se přesouváme na pozici $s'$ (sousední uzel s nejnižší hodnotou počítadla)
    • změna hodnoty počítadla na pozici $s$ (tedy změna $u(s)$) se ale dá implementovat různě
    • Koenigovo pravidlo: $u(s)\leftarrow u(s)+1$ (tzn. základní verze)
      • exponenciální čas $O(n^{\sqrt n})$
      • funguje i pro skupinu $k$ mravenců
      • věta: souvislý graf bude vždy pokrytý nezávisle na počtu mravenců
        • důkaz sporem: uvažujme část grafu, která je opakovaně navštěvovaná
        • takže existuje podmnožina $V$ vrcholů grafu, která je navštěvovaná cyklicky, tedy $u$-hodnoty vrcholů tam rostou neomezeně a překročí hodnoty ve všech uzlech, do nichž se dá z nějakého uzlu z $V$ dostat
        • při návštěvě uzlu z $V$, který má souseda mimo $V$, musí být navštíven uzel mimo $V$ → spor
      • důkaz funguje i pro Korfovo pravidlo
      • robustnost: po zastavení se může pokračovat z libovolného uzlu; náhodné přemístění (ne moc časté) také nevadí
    • Korfovo pravidlo … $u(s)\leftarrow u(s')+1$
      • polynomiální $O(n^2)$
      • learning real-time A*
      • $u(s)$ aproximuje součet minimální $u$-hodnoty souseda a ceny, za kterou se dá do souseda dostat
      • dokud nebyly navštíveny uzly, tak platí…
        • $u(s)=0$ znamená, že uzel nebyl navštíven
        • $u(s)$ je odhadem vzdálenosti uzlu od nejbližšího nenavštíveného uzlu
      • → „běž do souseda s nejnižší $u$-hodnotou, abys mohl navštívit nejbližší dosud nenavštívený uzel“
      • v průběhu algoritmu jsou přípustné $u$-hodnoty $0\leq u(s)\leq gd(s)$
        • $gd(s)$ … nejkratší vzdálenost do cílového uzlu (nejbližšího nenavštíveného?)
      • $u$-hodnota nikdy neklesá
        • lze nahlédnout z toho, že se agent vždycky volí nejnižšího souseda
      • podle pravidla … $u_{t+1}(s_t)=u_t(s_{t+1})+1$
      • věta: mravenec potřebuje maximálně $2\sum_s gd(s)\leq 2\sum_{i=1}^n i=n^2-n$ k tomu, aby došel na cílový uzel
        • důkaz pomocí potenciálu
      • potenciál grafu v čase $t$ … $2\sum_s u_t(s)-u_t(s_t)$
      • dokážeme, že potenciál v čase $t+1$ je vyšší než v čase $t$
      • $(2\sum_s u_{t+1}(s)-u_{t+1}(s_{t+1}))-(2\sum_s u_t(s)-u_t(s_t))=$
      • $=(2u_{t+1}(s_t)-u_{t+1}(s_{t+1}))-(2u_t(s_t)-u_t(s_t))=$
      • $=2u_{t+1}(s_t)-u_t(s_{t+1})-u_t(s_t)=$
      • $=2u_{t+1}(s_t)-(u_{t+1}(s_t)-1)-u_t(s_t)=$
      • $=u_{t+1}(s_t)-u_t(s_t)+1\geq 1$
    • další polynomiální pravidla
      • Wagnerovo pravidlo … if $u(s)\leq u(s')$, then $u(s)\leftarrow u(s)+1$
      • Thrunovo pravidlo … $u(s)\leftarrow \max(u(s)+1,\ u(s')+1)$
    • využití: robotický vysavač
  • úloha: projít všechny hrany grafu
    • EAW (edge ant-walk)
    • každý uzel má směrovku (ukazuje na hranu nebo spíše na uzel odpovídající hraně)
    • při projití směrovku otočíme, aby směřovala do další hrany (po řadě)
    • idea: mravenec se vydává cestou, kterou nejdéle nikdo nešel
    • zaručuje pokrytí hran v čase $O(n^3)$
• přemisťování a shlukování
  • koordinované přemisťování objektu
    • vyžaduje spolupráci
    • bez explicitní komunikace
    • přistup založený na chováních
    • zotavení ze stagnacie inspirované od mravenců
  • slepé hrnutí (bulldozing)
    • radlice s detekcí síly odporu
    • při srážce s jiným robotem nebo při detekci odporu na radlici počkáme a pak zase hrneme
  • shlukování
    • důležité mechanismy: komunikace, pozitivní a negativní zpětná vazba
    • příklad pravidla
      • pravděpodobnost uchopení objektu je nepřímo úměrná počtu vnímaných objektů
      • pravděpodobnost odložení objektu je přímo úměrná počtu vnímaných objektů
  • kooperativní manipulace
    • pouštní mravenci spolupracují při vytahování dlouhých objektů z písku
    • lze napodobit s roboty
    • jak dlouho čekat na kamaráda?
    • superlineární výkon
      • optimální výkon, když má skupina cca 6 členů
• rekonfigurovatelní roboti
  • modulární roboti skládající se s několika identických částí, které se můžou přeorganizovat, aby vytvořili vhodný tvar pro řešení úlohy
  • inspirace buňkami (celulární automaty) a jednotlivci (roje)
  • různé tvary robotů: řetězce, mřížky, mobilní rekonfigurovatelní, …
  • příklad robota řetězcového typu: CONRO
    • spojené zásuvky se západkami
    • infračervené navádění
    • dobrá mobilita
    • řízení se dokáže vyrovnat s náhlými změnami morfologie robota
  • další řetězcový robot: PolyBot
    • modul s jedním stupněm volnosti
  • robot mřížkového typu: A-TRON
    • dvě polokoule
    • 4 samčí a 4 samičí konektory
    • semo-spojování jednoduché, samo-rekonfigurace složitější
  • hybridní robot: M-TRAN
    • dvě propojené polokulaté krychle
    • hybridní mřížkový a řetězcový typ
    • magnety nebo mechanické háčky
    • pravidla pro celulární automaty
  • mobilní rekonfigurovatelní roboti
    • skládají se do spojených objektů
    • příklad: záchrana člověka
• stimergie
  • komunikace prostřednictvím změn prostředí
  • výsledek činnosti jedince zanechá trvalou značku, která ovlivňuje následující akce i jiných jedinců
  • cyklus stimul–reakce
  • příklad: budování vosího hnízda
    • pravidlo: přidej buňku do kouta, když tam jsou 2 nebo 3 stěny
    • může být deterministické nebo stochastické
• distribuované budování
  • každý robot dostane binární bitmapu finálního útvaru
  • sledování hranice – robot se pohybuje v pevné vzdálenosti od středu nejbližšího stacionárního robota
  • gradient – každý robot si nastaví gradient o jedna vyšší než nejnižší gradient souseda (počáteční robot má fixní gradient 0)
  • lokalizace – robot určuje svoji polohu pomocí komunikace s už lokalizovanými roboty (těmi v počátku, kteří určují globální souřadnice)
  • na začátku budování se jako první dávají do pohybu roboti, kteří jsou nejdál od počátku (mají nejvyšší gradient)
  • kolektivní budování inspirované termity: TERMES
    • umí se hýbat dopředu/dozadu, otáčet se na místě, chodit do schodů, přemisťovat kvádry

Pokročilé evoluční NS

• NEAT
  • neuroevolution of augmenting topologies
  • principy
    • začíná se s malou sítí, sítě můžou růst
    • dochází ke (smysluplnému) křížení sítí s různou topologií
    • ochrana inovací pomocí druhů
  • topologie se vyvíjí zároveň s váhami sítě
  • každý uzel a každá váha mají svou historickou značku, ta se dědí
  • kříží se uzly se stejnými značkami
• nepřímé kódování
  • komprimovaný genom
  • možné přístupy: kódování založené na L-systémech, cellular encoding (pravidla růstu jsou popsány pomocí gramatiky), analogové genetické kódování
  • analogové genetické kódování (AGE)
    • implicitní kódování synapsí a vah v síti
    • genom je sekvence znaků z nějaké konečné abecedy
    • kód neuronu
      • začíná „device tokenem“ (pevná krátká sekvence)
      • pak kód vstupního konce (ukončený koncovým tokenem)
      • pak kód výstupního konce (také ukončený)
    • váhy spojů mezi neurony se spočítají nějakou funkcí $I$, která dostane vždycky výstupní kód jednoho neuronu a vstupní kód druhého neuronu
    • když device token není následovaný dvěma úseky zakončenými koncovými tokeny, tak je kód neuronu neplatný
      • úseky mezi kódy neuronů se nevyužívají
    • vstupní a výstupní neurony mají odlišné device tokeny
    • genetické operátory
      • přidání/smazání/nahrazení znaku
      • smazání/posunutí/zdvojení náhodného úseku genomu
      • přidání zařízení (neuronu)
      • homologické křížení
      • zdvojení celého genomu
    • generování počáteční populace: každý genom jako náhodná sekvence, do které je vložený zadaný počet neuronů s náhodnými terminálními sekvencemi
    • testováno na úloze balancování dvou tyčí bez znalosti rychlostí
      • lepší než NEAT
• HyperNEAT
  • ke generování sítě, která řeší úlohu, se použije generátor CPPN
    • funkce $f_1$ ze souřadnic neuronu určí jeho přenosovou (aktivační) funkci
    • funkce $f_2$ ze souřadnic dvou neuronů určí váhu spoje mezi nimi
  • CPPN se vyvíjí algoritmem NEAT
  • vhodné na úlohy, které vykazují symetrie
  • experimentátor rozhoduje, kde na substrátě budou umístěné neurony a kolik jich bude
  • článek: adding the connection cost technique to HyperNEAT produces neural networks that are more modular, regular, and higher performing
  • alternativa: ES-HyperNEAT (ES = evolving substrate)
    • algoritmus sám určuje hustotu a pozici neuronů na substrátě
• deceptive tasks (zavádějící úlohy)
  • žádná kombinace malých stavebních bloků nevede na optimální řešení
  • úloha je tím těžší, čím je složitější fitness krajina
    • klamavá fitness – ukazuje nesprávný směr k řešení
  • řešení
    • sdílení zdrojů (fitness sharing) spolu se zavedením druhů → podobná řešení se dělí o fitness, čímž se vynucuje hledání nových druhů
    • hierarchical fair competition
      • subpopulace podle úroveň fitness
      • každá subpopulace má vstupní úroveň a exportní úroveň fitness
        • jedinec překročí vstupní úroveň → je přijat do subpopulace
        • jedinec překročí exportní úroveň → přechází do vyšší subpopulace
      • v nejnižší úrovni je generátor náhodných jedinců
      • úrovně buď pevné, nebo adaptivní
    • fitness uniform selection scheme
      • místo hodnoty fitness se hodnotí jedinečnost fitness
      • náhodně zvol hodnotu fitness, vyber jedince s nejbližší fitness
    • reorganizace genomu
      • pořadí genů se mění tak, aby byly korelované geny blízko sebe a křížení je tak často nerozdělovalo
    • více fitness funkcí
      • různé fitness funkce zachycují různé vlastnosti jedinců
      • buď se dynamicky vybírá jedna fitness, nebo se dělá multikriteriální optimalizace
    • další přístupy: koevoluce, novelty search, kreativní přístup, …
• novelty search (hledání novinek)
  • fitness funkce se nahradí mírou novosti (novelty metric) – měří novost chování
  • archiv novinek – uchovává staré jedince, kteří přišli s novým chováním
  • příklad míry: průměrná vzdálenost ke $k$ nejbližším chováním
    • jedince porovnáváme vůči aktuální populaci a archivu novinek
  • když je míra dost velká, tak je jedinec zařazený do archivu (je to podobné síni slávy u koevoluce)
  • také kontrolujeme, jestli už jsme nenašli vyhovující řešení
  • funguje u zavádějících úloh, pokud můžeme intuitivně charakterizovat chování a pokud je počet možných chování omezen
  • dá se dobře kombinovat s NEAT
  • příklad: navigace v bludišti
    • tři varianty: fitness funkce (podle vzdálenosti od cíle na konci), novelty search (vzdálenost od ostatních robotů na konci), náhodná fitness
    • všechny tři varianty používaly NEAT
    • novelty search byl úspěšnější
    • problém: metrika pro chování je silně redukovaná (uvažuje se jenom koncová poloha)
    • taky by se místo přesné polohy dala použít jenom poloha v mřížce (to by byla ještě silnější redukce)
  • příklad: dvojnohý kráčející robot
  • není hledání novinek prostě prohledávání prostoru hrubou silou?
    • experiment: prohledávání bludiště (porovnáme novelty search s náhodně generovanými roboty a s tradiční evolucí)
    • testujeme, co se stane, když nejlepšího jedince přesuneme do nového bludiště
    • postup
      • 50 běhů NEAT s hledáním novinek (novelty search) v bludišti
      • první jedinec, který v daném běhu najde cíl, je přenesen do druhého bludiště a změří se jeho výkon
        • pokrytá plocha, uražená vzdálenost
      • evoluce pokračuje v druhém bludišti (50 generací)
        • použijí se různá cílová místa
    • kontrolní algoritmy
      • naivní hledání – náhodně generovaní jedinci s jediným skrytým neuronem
      • NCC (network complexity control) – náhodně generované sítě, $i$-tá síť má stejný počet neuronů jako nejlepší síť $i$-tého běhu novelty searche
      • random search – evoluce, ale s náhodnou hodnotou fitness funkce
  • závěr: novelty search produkuje specialisty
• curiosity search (zvědavé prohledávání)
  • novelty search produkuje specialisty – jedinec je porovnávaný s celou populací a stačí, když umí něco nového
  • curiosity search hledá jedince, kteří se chtějí každý naučit co nejvíc schopností – jedinec je porovnávaný jen sám se sebou
  • příklad: dlaždice a dveře
    • zavřené dveře je potřeba aktivně otevřít (pak zůstanou otevřené)
    • robot má 6 senzorů: vzdálenost od překážky, počet nenavštívených dlaždic, vzdálenost od zavřených dveří × 4 (červená, zelená, modrá, žlutá)
    • výstupy sítě: ovládání motorů, otevírání dveří dané barvy (tzn. celkem 6 výstupů)
    • porovnávané algoritmy
      • curiosity search – odměna za to, že jedinec navštíví všechna místa
      • novelty search – vzdálenost mezi dráhami $NS_T$ (nebo aspoň koncovými body drah $NS_E$)
      • curiosity + novelty (tzv. NSGA-II, non-dominated sorting genetic algorithm II)
        • dvě složky fitness funkce
        • definujeme si, kdy řešení dominuje jiné řešení (když není v žádné složce horší a je aspoň v jedné složce lepší)
        • populaci rozdělíme na fronty
          • fronta 1: řešení, která nejsou dominovaná žádným jiným řešením
          • fronta $i$: řešení, která nejsou dominovaná jiným řešením kromě řešení v nižších frontách
        • elitismus, explicitně zachovává diverzitu (crowding distance), vrací nedominovaná řešení
        • selekce pomocí operátoru crowded tournament selection
          • vítězí řešení, které dominuje to druhé
          • pokud jsou řešení ze stejné fronty, tak vítězí to s větší crowding distance
            • tzn. v dané frontě jsou ostatní řešení dost daleko
      • základní algoritmus (koncové body / target endpoints)
        • minimalizuje se vzdálenost koncové polohy od libovolného z koncových bodů
        • nenutí robota prozkoumávat celé bludiště
    • výsledky
      • novelty search prohledá všechno, ale ne jedním jedincem
        • porovnání celých drah vede na jedince, kteří sami prohledají větší část bludiště
      • kombinace curiosity + novelty toho prohledá víc
        • je skoro jedno, jestli používáme $NS_T$ nebo $NS_E$
      • curiosity search překonává target endpoints a novelty search
        • ale nejlíp funguje curiosity + novelty
      • celá populace u všech metod dohromady prozkoumá celé bludiště, samotný jedinec ale nikdy nezvládne prozkoumat celé bludiště (takového jedince se nám nepodařilo najít)
• kreativní myšlení
  • novelty search má problém, když mutace nedokáže vytvořit dost odlišné chování
    • tzv. novelty plateau
  • kreativní myšlení = curiosity search na vnitřních stavech (skrytých neuronech)
    • curiosity search se zabývá jenom výstupními neurony (chováním)
  • experiment: zavádějící bludiště
    • úloha nebyla dost těžká, tak na tom nebylo moc poznat
  • pro těžší úlohu (přemisťování míčků do osvětlené části) byl výsledek jasnější
    • kreativní myšlení bylo jasně lepší