# 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