== Rozsah látky ==
Oficiální seznam otázek ([http://www.mff.cuni.cz/studium/bcmgr/ok/i3b51.htm] léto 2011):
: Architektura autonomního agenta; percepce, mechanismus výběru akcí, paměť; psychologické inspirace. Metody pro řízení agentů; řídící architektury podle Wooldridge, symbolické a konekcionistické reaktivní plánování, hybridní přístupy (Belief Desire Intention, Soar), srovnání s plánovacími technikami. Problém hledání cesty; navigační pravidla, reprezentace terénu. Komunikace a znalosti v multiagentních systémech, ontologie, problém omezené racionality, Kripkeho sémantika možných světů. Etologické motivace, modely populační dynamiky. Metody pro učení agentů; zpětnovazební učení, základní formy učení zvířat.
:Umělá evoluce; genetické algoritmy, genetické a evoluční programování. Základní přístupy a pojmy: populace, fitness, rekombinace, genetické operátory; dynamická vs. statická selekce, mechanismus rulety, turnaje, elitismus. Reprezentační schémata, hypotéza o stavebních blocích. Pravděpodobnostní modely jednoduchého genetického algoritmu. Koevoluce, otevřená evoluce. Aplikace evolučních algoritmů (výběr akcí, evoluce expertních systému, konečných automatu, adaptace evolučních pravidel, neuroevoluce, řešení kombinatorických úloh).
==Materiály==
Materiály pro učení v současné době (2011) představují trochu problém. Slajdy z předmětu Umělé bytosti představují osnovu učiva, pro kvalitní naučení však nejsou dostatečné. :( Níže je uveden seznam možných zdrojů - slajdy z přednášek, doporučená literatura, ostatní.
'''Slajdy'''
:*slajdy z předmětu Umělé bytosti - [http://artemis.ms.mff.cuni.cz/main/tiki-index.php?page=A+lecture+on+Human-like+and+Animal-like+Agents odkaz]
:*slajdy na Evoluční algoritmy 1 a 2 od Romana Nerudy
:*vybrané kapitoly z přednášek Umělá inteligence 1 a 2 - [http://ktiml.mff.cuni.cz/~bartak/ui/lectures/lecture02.pdf agenti], [http://ktiml.mff.cuni.cz/~bartak/ui/lectures/lecture12.pdf úvod do plánování], [http://ktiml.mff.cuni.cz/~bartak/ui2/lectures/lecture12.pdf zpětnovazební účení]
:*slajdy na Znalosti v multiagentových systémech - první dvě lekce (k nalezení na [http://ktiml.mff.cuni.cz/index.php?select=teaching§ion=sources&lang=czech http://ktiml.mff.cuni.cz/index.php?select=teaching§ion=sources&lang=czech])
'''Knihy'''
Níže uvedený seznam je převzat z oficiální stránky obsahující ''seznam literatury, ze které se lze naučit na státnicový okruh Adaptivní agenti a evoluční algoritmy'' [http://artemis.ms.mff.cuni.cz/main/tiki-index.php?page=Adaptive+agents+and+evolutionary+algorithms]. Zvýrazněny jsou knihy skutečně dostupné v naší knihovně (z kterých jsem osobně čerpal při učení).
:*''Michael Wooldridge: An Introduction to MultiAgent Systems.'' Willey (2002) 1st ed. (nebo 2nd ed. v rozsahu 1st ed.) - '''Pozn.''': silně doporučuji, velice dobrý zdroj!!!
:*''Gerhard Weiss (editor): Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence''. - '''Pozn.''': velmi dobrý úvod
:*Richard S. Sutton and Andrew G. Barto: Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA (1998) kap. 1-7
:*''Hanna Kokko: Modelling For Field Biologists: and Other Interesting People''. Cambridge University Press (2007) (kap. 1, 2, 7, 8)
:*''Leah Edelstein-Keshet: Mathematical Models in Biology''. SIAM (2005) (kap. 4.1, 4.2, 6.1-6.3)
:*David J. Sweatt: Mechanisms of memory, Elsevier Academic Press, 2003 kap. 1
:*''Melanie Mitchell: An Introduction to Genetic Algorithms'', MIT Press, 1996 (kap. 1-4)
:*David E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning. (kap. 1-4)
:*Alternativní ke GA: ''Zbigniew Michalewicz: Genetic Algorithms + Data Structures = Evolution Programs'' (základy kap 1, 4; teorie kap 2-3; pokročilé a aplikace kap 8, 10, 12, 13)
:*Alternativní ke GA: John H. Holland: Adaptation in Natural and Artificial Systems (základy: kap 1-2; teorie: kap 4-5)
:*''Steve Rabin (ed.): AI Game Programming Wisdom I'', Charles River Media, 2002 (k. 4.3)
:*''Steve Rabin (ed.): AI Game Programming Wisdom IV'', Charles River Media, 2008 (k. 2.2, 2.3, 2.5, 2.6)
'''Ostatní'''
:*Donald L. DeAngelis and Wolf M. Mooij: INDIVIDUAL-BASEDMODELING OF ECOLOGICAL AND EVOLUTIONARY PROCESSES. In: Annu. Rev. Ecol. Evol. Syst. 2005. 36:147–68
:*[http://ksvi.mff.cuni.cz/~brom/thesis/brom_thesis.zip Text k virtuálním lidem - dizertační práce dr. Broma] (kap. 1, 3, 4.1 - 4.5, 7)
:*[http://sitemaker.umich.edu/soar/home SOAR homepage] (tutorial, dokumentace)
:*[http://www.red3d.com/cwr/nobump/nobump.html Craig W. Reynolds - Not Bumping Into Things] (něco k steeringu a obstacle avoidance)
:* [http://www.cs.cmu.edu/~motionplanning/lecture/lecture.html] - Něco k motion planning, hledání cest, atd.
== Architektura autonomního agenta ==
===Základní definice===
Neexistuje bohužel všeobecně přijímaná definice toho, co to je (inteligentní) agent. Zajímavým zdrojem v této otázce budiž článek [http://www.msci.memphis.edu/~franklin/AgentProg.html Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents]. Nicméně existuje určité vymezení, na kterém se autoři schodují:
====Inteligentní agent====
: Jedná se o entitu existující v nějakém prostředí (ať už skutečném, nebo virtuálním), které je agent schopen vnímat pomocí senzorů a ovlivňovat pomocí efektorů, přitom musí být agent schopen autonomně vybrat akci, kterou následně provede, a to tak, aby pokud možno dosáhnul zadaných cílů a dostatečne a adekvátně reagoval na případné změny v okolním světě.
Důležitá je ''autonomie'' (tzn. autíčko na dálkové ovládání ani obecně objekt v nějakém programu definici nesplní), ''působení v rámci nějakého světa'', ''reaktivita'' (schopnost reagovat na změny) a ''proaktivita'' (nestačí pouze reflexivní chování, agent vykazuje nějaké složitější chování vedoucí k určitému cíli, je schopen sám se ujmout iniciativy).
Existují i další, příbuzné pojmy:
====Avatar====
Virtuální bytost řízená člověkem
====Virtuální člověk====
: Virtuální člověk je počítačový model performativní, behaviorální stránky určitého člověka. Jeho nutnou součástí je virtuální tělo. Tělo je součástí virtuálního světa, které je modelem přirozeného lidského prostředí. Tento svět je většinou dynamický, nedeterministický a pouze částečně pozorovatelný. Tělo je většinou zobrazeno graficky. Virtuální člověk vykonává sekvence akcí. Akcí se obvykle rozumí takový proces, jenž může provádět člověk, jenž trvá řádově několik desítek milisekund až prvních jednotek sekund a který většinou interpretujeme jako uzavřený celek. Akce nemodelují lidské mentální, ani fysiologické procesy.
:Virtuální člověk je komplexní. To znamená zaprvé, že umí vykonávat větší počet úkolů, z nichž některé jsou konfliktní, minimálně dva. Za druhé, že jeho tělo modeluje celé lidské tělo.
'''Rozdíl oproti inteligentnímu agentu''' spočívá v tom, že u virtuálního člověka není vyžadována autonomie. Tedy ač je často žádoucí, aby virtuální lidé navenek vykazovali určitou míru autonomie (např. ve virtuálních simulacích), ve skutečnosti mohou být všichni řízeni nějakou centrální jednotkou. Na druhou stranu agent nemusí mít podobu a tělo člověka.
====Animat====
: Syntetická bytost žijící ve virtuálním prostředí, má tělo, které podléhá pravidlům (např. fyzikální model) platným v daném světě a pomocí kterého animat může se světem interagovat.
Jedná se o širší pojem, než je virtuální člověk; může jít o model v zásadě jakéhokoli živočicha. Častou jsou animati konstruováni za
účelem pochopení fungování živých organismů, ověřováním ekologických a etologických hypotéz, nikoli za účelem prosté imitace; narozdíl od virtuálních lidí. (Neformálně řečeno Virtuální lidé jsou věrohodní „zvenku“, animati „zevnitř“ )
====Bot====
: Bot je počítačem řízená umělá bytost, která simuluje postavu hráče v počítačová hře (obvykle se jedná o akční typ hry FPS). Boti mají tělo, podléhající zákonitostem virtuálního světa, a využívají předprogramované prostředky umělé inteligence vhodné pro daný typ hry, mapu a pravidla hry (Deathmatch, CTF).
Boty lze v zásadě chápat jako podtyp virtuálních lidí, ovšem s tím, že tyto herní postavy mají často podobu robotů či zvířat s antropomorfními rysy (což většinou nemývá vliv na mechanismus jejich řízení).
====Prostředí====
* plná / částečná pozorovatelnost
* statické / dynamické
* deterministické / nedeterministické
* diskrétní / spojité
* jedno- / multi-agentní
* realtime / step-based
* epizodické / neepizodické
===Abstraktní architektura agenta===
Agent přijímá vjemy a jeho chování je plně určeno posloupností všech vjemů, které kdy přijal. Formálně lze psát:
* S = {s1, s2, ... } je množina všech možných stavů prostředí
* A = {a1, a2, ... } je množina všech akcí, které může agent provést
* agent je reprezentován funkcí ''action'': S* → A (neboli na základě posloupnosti stavů světa vybere akci)
* (nedeterministické) chování prostředí lze modelovat funkcí ''env'': S x A → P(S)
Prostředí ale typicky není ''plně pozorovatelné'', agent vnímá svět pomocí senzorů. Je potřeba přidat funkci mapující svět na množinu perceptů P a upravit funkci ''action'':
* ''see'': S → P
* ''action'': P* → A
Toto je abstraktní matematický model agenta, pro skutečnou konstrukci agenta však nepoužitelný (není k dispozici nekonečný prostor pro zachycení všech možných posloupností vjemů).
===Percepce a paměť===
''viz slajdy č. 8 (Representation) k Umělým bytostem''
* reprezentace logickými fakty + RETE algoritmus
* [http://en.wikipedia.org/wiki/Affordance afordance], [http://en.wikipedia.org/wiki/Smart_objects smart objects]
** objekty samy nabízí činnosti, jaké s nimi lze dělat, případně napovídají další akce potřebné pro komplexnější aktivity
** problémy: otevírání konzervy otvírákem, tanec v páru, objekty musí nabízet různé akce různým agentům
* role-passing - pro různé činnosti mám specializované role svázané s daným objektem v prostředí
* deiktická reprezentace - v paměti agenta uchovávám jen objekty, které se týkají činnosti, kterou děláma a to formou ukazatele pojmenovaného podle role, jakou objekty mají v dané činnosti (http://www.cse.iitm.ac.in/~ravi/papers/Vimal_IJCAI_07.pdf)
Vysvětlení pojmů:
* '''affordance''': “The affordances of the environment are what it offers the animal, what it provides or furnishes, either for good or ill.” Affordances are resources that the environment offers any animal that has the capabilities to perceive and use them. (https://edisk.fandm.edu/tony.chemero/papers/adaptivebehavior07.pdf)
===Paměť===
''stručný výtah z Mechanisms of memory''
Paměť člověka
* Deklarativní (explicitní) - fakta, události
* Nedeklarativní (implicitní)
** procedurální paměť (rutina, návyky)
** priming
** klasické (asociativní, Pavlovské) podmiňování
** neasociativní učení
Struktura paměti (jiné dělení) - dělení dle učení, paměti (storage) a vyvolání vzpomínky (recall), vše vědomé nebo podvědomé (conscious, unconscious)
* podvědomé učení, podvědomá paměť
** vědomé vyvolání
*** trace conditioning (podobné jako Pavlovské podminování, ale mezi stimuly (zvoneček a jídlo) je časová mezera, využívá jiné okruhy v mozku než PP, specielně hippocampus)
*** operant conditioning (jako PP, ale je vyžadována motorická reakce místo reflexu)
*** paměť na chutě
*** podmíněná averze k chutím (jednou sním v dětství zkažené maso a můžu být celý život vegetarián, protože mi maso nikdy nebude chutnat)
*** kontextově podmíněný strach
** podvědomé vyvolání
*** neasociativní učení - habituace, senzitizace, dishabituace
*** asociativní učení - Pavlovské podmiňování, podmíněné mrkání, podnětově podmíněný strach
*** motorické učení
* vědomé učení, podvědomá paměť, vědomé vyvolání
** deklarativní učení
** prostorové učení
** vědomé asociativní učení
* pracovní paměť - vědomé učení, paměť i vyvolávání
** vizuálně-prostorový buffer
** epizodický buffer
** fonologická smyčka
{{TODO|Chybí tu ještě něco?}}
== Metody pro řízení agentů, řídící architektury ==
* řídící architektury podle Wooldridge (deliberativní-založené na odvozování; reaktivní-behaviorální; hybridní)
* symbolické a konekcionistické reaktivní plánování
* hybridní přístupy (Belief Desire Intention, Soar)
* srovnání s plánovacími technikami: klasické plánovací techniky těžko použitelné, potřebují svět deterministický, statický a plně pozorovatelný, autonomní agent se povětšinou pohybuje ve složitějším světě
===Řídící architektury podle Wooldridge===
====Čistě reaktivní agent====
Vyznačují se jednoduchou přechodovou funkcí <math>action: S \rightarrow A</math>, tzn. akce závisí pouze na aktuálních vjemech (agent nemá paměť).
====Agent se stavem====
Akce je určená aktuálním stavem: <math>action: I \rightarrow A</math>, stav se mění na základě vjemů <math>see: S \rightarrow P</math> a předchozího stavu: <math>next: I \times P \rightarrow I</math>
====Deductive reasoning====
=====Agent jako dokazovač (deliberate agents)=====
Stavy agenta = databáze faktů. Akce jsou kódovány jako predikáty <math>Do(A)</math>, kde <math>A \in actions</math>. Chování agenta je realizován odvozovacími pravidly tvaru implikace. Rozhodování pak má podobu dokazování. Vybere se akce, pro kterou je dokazatelné <math>Do(A)</math>. Když taková neexistuje, vybere se taková, pro kterou není dokazatelné <math>\neg Do(A)</math>
====Practical reasoning====
Skládá se ze dvou částí:
* '''deliberation''' - rozhodování, čeho chci dosáhnout.
* '''means-ends reasoning''' - plánování, jak toho dosáhnout.
Postavené na trojici beliefs - desires - intentions
'''Beliefs''' - domněný stav světa.
'''Intentions''' - stav mysli vyjadřující záměr něčeho dosáhnout. Řídí means-ends reasoning, přetrvávají (typicky dokud nejsou naplněné nebo se zásadně nezmění podmínky tak, že není racionální se jich nadále držet), omezují následující deliberation (na možnosti konzistentní se záměry), mají vliv na budoucí beliefs (věřím, že intentions naplním a podle toho se změní svět).
'''Desires''' (options) - budoucí možnosti agenta.
=====Abstract interpreter=====
do
// generate new possibilities
options ← option-generator ( events, B, D, I )
// select the best opportunities to perform
selected-options ← deliberate( options, B, D, I )
// adopt a selected opportunity as a subintention, or execute its actions
I ← I ∪ selected-options[non-atomic]
execute( selected-options[atomic] )
get-new-external-events( )
drop-successful-goals( B, D, I )
drop-impossible-goals( B, D, I )
until quit
====Reactive reasoning====
Agent neplánuje nic dopředu, reaguje pouze na vnitřní stav a nový vjem. Inteligence je simulována pomocí přímé interakce se světem.
=====If-then pravidla=====
* '''simple reactive planning''' - if-then pravidla s prioritou, co pravidlo, to konkrétní akce
* '''simple hierarchical planning''' - pod každým pravidlem může být akce nebo sada subpravidel (např. top-level goals, subgoals, tasks, atomic actions)
====Konečné automaty====
"Rozšířená if-then pravidla", eliminuji spaghetti návrh
* '''finite-state machine''' - konečný automat, ke každému stavu je asociovaný kód a přechodová funkce. Agent vykonává akce podle kódu v aktivním stavu.
* '''hierarchical FSM''' - konečný automat s přechodovou funkcí mezi stavy. Ve stavu je buď kód nebo další konečný automat.
* '''probabilistic FSM''' - FSM, přechodová funkce může obsahovat pravděpodobnost přechodu (za daných podmínek)
=====Subsumpční architektura=====
viz [http://cs.wikipedia.org/wiki/Subsump%C4%8Dn%C3%AD_architektura Subsumpční architektura]
====Hybrid reasoning====
Kombinují reaktivitu s plánováním, případně dalšími elementy
=====Vrstevnaté architektury=====
* horizontální (a) - všechny vrstvy se rozhodují samostatně a dávají návrhy akcí. Jednoduché, ale může vést k nekoherentnímu chování. Je třeba ''mediátor'', který vybírá, která vrstva má zrovna kontrolu. Mediátor je centralizovaný prvek, který může představovat bottlenect systému.
* vertikální - vrstvy si předávají nabízené akce, méně flexibilní, náchylnější k chybným rozhodnutím v jednotlivých vrstvách
** jednoprůchodové (c)
** dvouprůchodové (b)
[[File:Layered_reasoning_architectures.png]]
=====BDI architektura=====
BDI architektura je založená na practical reasoning, ale vyznačuje se jistými specifiky:
* means-ends se obvykle nevykonává, místo toho jsou k jednotlivým intentions předpočítané plány v podobě uložených struktur
* používá intentional stack - krom intentions přijatých na základě deliberation přijímám i subintentions jejich plánů
Pozn: https://www.aaai.org/Papers/ICMAS/1995/ICMAS95-042.pdf - paper, který doporučoval Neruda.
=====SOAR=====
======Algoritmus======
# '''Input phase''' - inputs are stored in the working memory
# '''Proposing phase''' - various if-then rules propose what to do next
#* if-then pravidla matchují pouze pracovní paměť, v které jsou uložené všechny informace (struktura viz slajdy "Soar intro").
#* používá RETE algoritumus
#* střílející pravidla vytváří dočasné struktury v paměti a nabízí operátory.
# '''Decision phase''' - just one proposal is chosen
#* výběr mezi nabízenými možnostmi
#* může nastat impass (žádné pravidlo nestřílí, více neporovnatelných pravidel, nelze aplikovat operátor), řešení: nový stav (''jak přesně to funguje? Spustím nějaké klasické plánování?'') + zapamatuji si řešení v dlouhodobé paměti
# '''Applying phase''' - new internal symbols or motor symbols are created by an if-then rule
#* vybrané pravidlo vytvoří trvalou strukturu v paměti
#* obvykle jen kopíruje akci vybraného operátoru do output-link
# '''Output phase''' - motor symbols are interpreted and the state of the environment is changed
======Central cognitive system======
The architecture involves
* a programming language
* a working memory (symbols -"variables")
* a long-term memory (if-then rules)
* a learning
===Symbolické a konekcionistické reaktivní plánování===
''Obrázky ze slajdů Cyrila Broma (zveřejněno s jeho svolením)''
====Symbolické plánování====
[[File:symbolic_planning.png]]
====Konekcionistické plánování====
[[File:connectional_planning.png]]
===Srovnání s plánovacími technikami===
Jde o:
* algoritmy hledání cesty (A* apod)
* plánovací techniky využívající dokazování v predikátové logice
* plánování v prostoru stavů/plánů
(viz slajdy z UI 1)
Klasické plánování má tyto problémy:
* není any-time - časté přeplánovávání v dynamickém světě vede k problémům
* vyžaduje plně pozorovatelný svět
== Problém hledání cesty; navigační pravidla, reprezentace terénu ==
Pokud máme agenta, který se má pohybovat v nějakém prostředí, je třeba řešit problém
navigace. Různá řešení závisí na tom, jaké informace máme k dispozici:
* Známe mapu prostředí?
* Známe svou pozici na mapě?
* Známe pozici cíle/směr k cíli?
=== Navigační pravidla ===
Pokud neznáme mapu prostředí, musíme se řídit podle jednoduchých navigačních pravidel.
Příkladem jsou Bug algoritmy, které předpokládají, že agent zná pouze směr k cíli a dovede v každém okamžiku zjistit,
jak je od cíle daleko.
* Bug1 - označí si ''hitpoint'' a ''leavepoint'' pokud narazí na překážku. Musí ji objet celou.
* Bug2 - označí si ''hitpoint'' a objíždí, dokud nenarazí na průsečík s přímkou k cíli, který je blíž než ''hitpoint''.
Vizualizace algoritmů: http://blip.tv/ussjoin/robot-navigation-bug-1-algorithm-1791510
=== Reprezentace terénu ===
Vytvoření mapy navigačních bodů nebo oblastí. Poté se problém převede na hledání cesty v grafu.
Přístupy:
* graf viditelnosti
* Voronoi diagramy
* lichoběžníková dekompozice
=== Waypoint / Navmash ===
Máme tedy nějakou hru s mapou terénu. Chceme použít A* algoritmus pro pohyb agenta mapou. Jednou možností je, že autoři hry do mapy ručně dají waypointy, což jsou body na mapě, kam bot může jít. Navigaci pak uděláme tak, že ze současné pozice bota (nemusí být na žádném waypointu) hledáme spojnici k nejbližšímu waypointu (těch waypointu může být opravdu hodně na mapě, pokud jich tam není dost, tak se může stát, že se bot prostě zasekne o něco, když se k waypointu snaží dostat) a pak spustíme A* algoritmus, tak jak ho známe z UI.
Waypointy jdou nahradit navigation mashem (navmash zkráceně), což je technika, která rozdělí mapu na konvexní polygony. V konvexním polygonu vede z libovolného bodu do libovolného jiného bodu cesta, která je přímkou. Použitím navmashů se typicky sníží čas, který potřebuje A* na nalezení cesty, protože se zmenší počet uzlů, se kterými A* musí počítat.
'''Pozn:''' http://udn.epicgames.com/Three/NavigationMeshReference.html - Rozdíl mezi waypoints a navigation mashes na obrázku.
=== Materiály ===
* http://artemis.ms.mff.cuni.cz/main/download/hagents/H-likeAgents4_Bajer060410.pdf - slajdy, které používá Brom
* http://harablog.files.wordpress.com/2009/06/beyondastar.pdf - Zřejmě zdroj předchozích slajdů. Velmi pěkně zpracované.
=== Poznámka ===
Určitě si nastudujte steering a obstacle avoidance. Patří sem i A*, LPA*, "rozdlaždicování" terénu (od dlaždic, šestiúhelníků, jejich hierarchických variant až po obecné polygony), waypointy atd. (experimentálně ověřeno, že na zkoušku je to dobré vědět :-) )
{{TODO}}
== Komunikace a znalosti v multiagentních systémech, ontologie, problém omezené racionality, Kripkeho sémantika možných světu. ==
* http://ssdi.di.fct.unl.pt/mas/0910/slides/7.pdf - tyto slajdy vypadaji jako vytah z Wooldridge, kde je komunikace popsana pekne
** [http://en.wikipedia.org/wiki/Knowledge_Interchange_Format KIF] (Knowledge Interchange Format)
** [http://en.wikipedia.org/wiki/Knowledge_Query_and_Manipulation_Language KQML]
** '''Ontologie''' velmi označuje terminologii. Agenti spolu komunikují pomocí zpráv (například pomocí KQML) a ve zprávách se právě uvádí jako jedna z hlaviček zpráv právě ontologie, takže když se agenti baví například o rozměrech součástek pro auto, tak vědí, co který pojem přesně znamená a budou vědět, že oba agenti pracují se stejnými fyzikálními jednotkami.
=== Kripkeho model možných světů ===
viz Wooldridge - 12. kapitola (Logic for Multiagent Systems) + http://ktiml.mff.cuni.cz/teaching/files/materials/A1_1.pdf
=== Problém omezené racionality ===
Každý agent, který se má racionálně rozhodovat v komplexním prostředí podléhá následujícím omezením:
* v daném okamžiku disponuje pouze ''omezenou informací'' o světě (např. vidí jenom na omezenou vzdálenost)
* má pouze ''omezené prostředky'' ke zpracování informací (např. RAM,CPU)
* musí se rozhodovat v ''omezeném čase'' (pokud jde o real-time agenta)
V konečném důsledku je pro takového agenta nemožné se rozhodovat racionálně (tzn. volit vždy optimální akce).
Musí se tedy spolehnout na heuristiky a omezenou znalost prostředí.
== Etologické motivace, modely populační dynamiky. ==
=== Modely populační dynamiky ===
==== Analytické modely ====
Analytické modely představují nástroj matematické biologie ke zkoumání vývoje populací nejrůznějších živých organismů.
Sestavují se na základě '''empirických dat''' (z pozorování). Analytický model je zpravidla tvořen diferenciálními rovnicemi, které popisují chování systému. Jejich nevýhodou je, že bývají příliš obecné.
'''Příklad:''' jednoduchá rovnice pro jednu populaci (<math>t</math> - čas, <math>b</math> - birth rate, <math>d</math> - death rate):
<math>N(t+\Delta t) = N(t) + b*N(t)*\Delta t - d*N(t)*\Delta t</math>
Existují složitější modely, které lépe modelují konkrétní prostředí a pomáhají zodpovědět otázky jako např. ''Za jak dlouho dojde k vyhubení chráněného živočicha XY?''
Existují také modely pro chování více populací (model ''predátor-kořist'', ''hostitel-parazit'' apod.).
==== Simulační modely ====
Simulační modely jsou založeny na umělých agentech zvaných '''animati''', kteří jsou plausibilní - chovají se realisticky.
Hlavní nevýhodou simulačních modelů je vysoký počet parametrů.
{{TODO}}
== Metody pro učení agentů; zpětnovazební učení, základní formy učení zvířat ==
Předpokládejme agenta, který se má naučit nějakou funkci $f: Input \rightarrow Output$.
Učení agentů se využívá především tam, kde nelze pokrýt všechny možné eventuality tím, že je do agenta naprogramujeme předem.
Při strojovém učení potřebujeme vědět:
* ''Jakou část agenta zlepšujeme?'' (př. rozhodovací mechanismus pro výběr akcí)
* ''Jakou odezvu má agent k dispozici?'' (př. žádnou, otagovanou trénovací množinu)
* ''V jaké podobě ukládáme naučená data?'' (př. rozhodovací strom, pravděpodobnostní rozdělení, sada pravidel)
Základní dělení metod strojového učení:
* '''S učitelem''' - máme: <math>(x_1,y_1),\ldots,(x_n,y_n)</math> a chceme: <math>f(x_i)=y_i</math>
* '''Bez učitele''' - máme: <math>\vec{x_1},\vec{x_2},\ldots,\vec{x_n}</math> a chceme: <math>P(X=\vec{x})</math>
* '''Zpětnovazební učení''' - máme: <math>s_0,a_1,s_1,a_2,\ldots</math> kde některé stavy mohou být odměněny a chceme <math>\Pi(s_i)</math> - nějakou sadu pravidel co dělat ve kterém stavu abychom posbírali co nejvíc odměn.
==== Učení s učitelem (supervised learning). ====
Je metoda, při které se používá následující schéma:
* Vezmeme data (množina dvojic '''(vstup,výstup)''' - <math>\lbrace(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\rbrace</math>) a rozdělíme je na
dvě disjunktní množiny: ''trénovací'' (<math>T</math>) a ''testovací'' (<math>E</math>). Pro hledanou funkci <math>f</math> platí: <math>\forall i:\ f(x_i)=y_i</math>
* Použijeme nějaký ''učící algoritmus'', pro nalezení ''hypotézy'' <math>h</math>, která aproximuje trénovací data.
O hypotéze řekneme, že je ''konzistentní'' s množinou trénovacích dat <math>T</math>, pokud platí:
<math>\forall (x_i,y_i)\in T:\ h(x_i)=y_i</math>
* kvalitu řešení (tj. nalezenou hypotézu $h$) otestujeme na množině testovacích dat <math>E</math>. Čím menší je suma <math>\Sigma_{(x_i,y_i)\in E}|h(x_i)-y_i|</math> tím lepší hypotézu jsme našli.
Pokud je obor hodnot hledané funkce diskrétní, jde o ''klasifikaci''. Je-li obor hodnot spojitý, jde o ''regresi''.
==== Učení bez učitele (unsupervised learning).====
Je metoda, při které se agent snaží ze vstupních dat odvodit nějaké zákonitosti (nemá při tom k dispozici správné výstupy a tímpádem ani zpětnou vazbu). To co se agent učí je pravděpodobnostní model vstupních dat, na základě kterého potom může klasifikovat nová data. Př. ''Bayesovské učení'', ''EM algoritmus''
==== Zpětnovazební učení ====
Zpětnovazební učení je metoda, při které se agent učí, jak má volit akce, aby našel optimální strategii pro dané prostředí.
Jde o učení bez učitele. Agent sice dostává odezvu, ale přímo z prostředí, takže musí experimentovat, a zjišťovat, které stavy jsou ''dobré'' a které ''špatné''. Něco jako, když hrajete hru, jejíž pravidla neznáte a po cca. 100 tazích Váš oponent řekne: "Prohráls saláte!".
Řeší se zde problém ''explorace'' vs. ''exploatace''. Pokud agent zkouší nové akce, jejichž výsledek nezná, jde o ''exploraci'', pokud provádí akce, o kterých ví, že mu přinášejí užitek, jde o ''exploataci''. Problém je, že optimální strategie nemůže být ani čistě ''explorační'' ani čistě ''exploatační'' - hledá se vyvážený kompromis.
* '''Pasivní učení''' - agent má pevně danou strategii a učí se, jak jsou ohodnocené jednotlivé stavy, do kterých se dostane.
* '''Aktivní učení''' - agent se učí jaké akce má volit a zároveň jak jsou ohodnocené.
=== Základní formy učení zvířat ===
* '''Habituace''' - úbytek reakce na opakování téhož podnětu (přitom je reakce na jiné podněty zachována - nejde tedy o únavu)
* '''Senzitizace''' - nárůst reakce na určitý podnět (opak habituace)
* '''Imprinting''' - proces učení vázaný k určité fázi vývoje jedince, který vede k trvalým a nezvratným změnám chování (kachny a Konrad Lorenz)
* '''Klasické podmiňování''' - Pavlov a jeho psi. ''Nepodmíněný podnět'' - sám vyvolává reakci, ''podmíněný podnět'' - vyvolává reakci až když je spojen s nepodmíněným podnětem.
* '''Operantní podmiňování''' - každá akce je tzv. ''operant''. Když dostane zvíře za provedení nějakého operantu odměnu, tak se upevní. Postupně se tak dá natrénovat komplikované chování složené z postupně podmíněných operantů.
== Umělá evoluce; genetické algoritmy ==
* Základní přístupy a pojmy: populace, fitness, rekombinace, genetické operátory; dynamická vs. statická selekce, mechanismus rulety, turnaje, elitismus
{{TODO}}
== Reprezentační schémata, hypotéza o stavebních blocích. ==
{{TODO}}
== Genetické a evoluční programování ==
{{TODO}}
== Pravděpodobnostní modely jednoduchého genetického algoritmu. ==
viz slajdy typu eva09-2
* Geneticke operatory, pravdepodobnosti vyskytu a selekce jedincu a velikost jejich zastoupeni v populaci muzeme vyjadrit jako matice/vektory.
* Nekonecne populace muzeme modelovat jako dynamicky system a hledat jeho pevne body. Jake jsou vlastne nevime.
* Vyvoj konecnych populaci muzeme modelovat jako Markovovsky proces. Lze odvodit, ze bude konvergovat k chovani nekonecnych populaci.
Komentar Romana Nerudy k vyse uvedenemu:
kdybych to zkousel ja, asi bych chtel v zasade ten nadhled, co rikate,
s durazem na to, jak se ty populace reprezentujou, t.j. u nekonecnych
zavedeni vektoru cetnosti a pravdepodobnosti vyberu, neco o tom, jaky
zobrazeni vlastne hledame, a co o nem muzeme rict, bez podrobnosti a
dukazu, no a u konecnych zase porozumneni tomu, nad cim ten markovsky
proces pracuje, co jsou stavy, jaky vyznam ma ta prechodova matice,
ze je velika, a zase samozrejme ty konkretni slozite vzorecky ne,
pamatovat se to neda a odvozuje se to nekolik desitek stranek. jeste
jsem to asi nikdy nepolozil jako samostatnou otazku, vetsinou na to
dojde rec v souvislosti s teorii schemat.
{{TODO}}
== Koevoluce, otevrená evoluce. ==
{{TODO}}
== Aplikace evolučních algoritmů ==
* výber akcí, evoluce expertních systému, konecných automatu, adaptace evolucních pravidel, neuroevoluce, rešení kombinatorických úloh
{{TODO}}
[[Category: Státnice Informatika Mgr.]]
