== 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ů).
===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====
=====BDI=====
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ů
=====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").
#* 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, používá RETE algoritumus
#* může nastat impass (žádné pravidlo nestřílí, více neporovnatelných pravidel, nelze aplikovat operátor), řešení: nový stav + 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í===
===Srovnání s plánovacími technikami===
{{TODO}}
== Problém hledání cesty; navigační pravidla, reprezentace terénu ==
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, Kripkeho sémantika možných světu. ==
{{TODO}}
== Etologické motivace, modely populační dynamiky. ==
{{TODO}}
== Metody pro učení agentů; zpětnovazební učení, základní formy učení zvířat ==
{{TODO}}
=== 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.]]
