Přednáška

• cvičení
  • jeden domácí úkol → 10 bodů
  • dva online kvízy s neomezeným časem (budou na ně dva týdny) → 10 bodů
  • na konci zápočtový projekt – navrhnout řízení pro virtuálního robota (ale mohl by být i hardwarový, akorát tam se nedá dělat evoluce) → 15 bodů
• závěrečná zkouška (60 %)
  • čtyři otázky, písemná odpověď, společně to projdeme
• historie
  • automatizace už ve starověkém Řecku
  • da Vinci: mechanický rytíř
  • Descartes
  • biskup Albertus Magnus
  • mechanická kachna
  • R.U.R.
  • robot pro světovou výstavu v New Yorku, 1939
  • manipulátory
  • Shakey
  • Khepera – dá se použít i k hardwarové evoluci
    • e-Puck – varianta Khepery
• simulátory
  • Webots
    • www.cyberbotics.com
    • simuluje mobilní roboty, umí fyziku (Open Dynamic Engine)
  • CoppeliaSim
    • www.coppeliarobotics.com
• soutěže
  • Robocup – cílem je v roce 2050 sestavit robotické mužstvo, které porazí mistry světa ve fotbale
  • Istrobot
  • Eurobot
• návrh robota
  • hardware – mechatronika (mechanika a elektronika)
  • řídicí software
• evoluční robotika
  • chceme, aby robot řešil úlohu
  • dochází k tomu pomocí selektivní reprodukce (na základě interakce s prostředím)
  • používají se neuronové sítě, přírodou inspirovaný design, …
• 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
• učení vs. evoluce
  • učení je během života robota
  • evoluce je mezi generacemi
• 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
  • 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ů
• 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í
• 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
  • klasický – perception, planning, execution
  • behavior-based – rozdělení do jednotlivých základních chování
    • ale může se stát, že základní chování bude složitější než původní chování
  • evoluční – necháme to na evoluci
• 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ší
• 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
• 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í
    • 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í
      • příklad: dvě neuronové sítě v robotovi, jedna předpovídá výsledky té druhé (?)
• jak dobře se organismus může vyvíjet? (přizpůsobovat změnám prostředí)
  • genotyp – množina dědičných charakteristik
  • fenotyp – konkrétní realizace genotypu ve formě chování
    • na základě konkrétního prostředí
  • tzn. prostředí ovlivňuje vývoj konkrétních znaků (tedy jak se genotyp zobrazí na fenotyp)
  • v evoluční robotice je problém zobrazení z genotypu na fenotyp problémem reprezentace
  • 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
  • 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-robot)
    • zkušení jedinci můžou ovlivňovat méně zkušené
    • v přírodě: postupná evoluce pohybu po souši – plazení, běh, létání
    • robotické organismy z krychlí s klouby
  • rojová robotika
    • koordinace robotů ve skupině
    • malé robotické moduly, které se dovedou poskládat dohromady
  • měkká robotika
    • 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é hodnoty)
    • 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
  • $p_k(\mu)$ … pravděpodobnost, že se počet jedniček zvýší z $k$ na $k+1$
  • 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
• 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á)
  • 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$
    • 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í)
• 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
  • s určitou pravděpodobností flipneme bit
• 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
  • GA se pouští opakovaně se stejnými nebo pozměněnými parametry
• 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 abecedu 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ů ($r$ je velikost původní abecedy)
  • každý řetězec délky $m$ je reprezentovaný $2^m$ schématy
  • řád schématu – …
  • kolik jedinců určených daným schématem bude v dané populaci?
    • jak schéma ovlivní selekce?
      • …
    • 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)
    • co mutace?
      • musí se změnit jeden z pevných symbolů schématu
  • 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ů
• 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ě
  • další variace GA spojené s dospíváním a učením
  • 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
  • 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