Ekologické Řídicí Algoritmy: Definice a Aplikace

Článek se zabývá ekologickými řídicími algoritmy, jejich definicí a využitím v kontextu multiagentních systémů. Dále se zaměřuje na metody učení agentů, evoluční přístupy a související koncepty.

Inteligentní Agent a Jeho Definice

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čně 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.
• 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.
• 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).

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:

Čtěte také: České supermarkety a bio

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)

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ů).

Agent se stavem

Akce je určená aktuálním stavem: action: I → A
Stav se mění na základě vjemů see: S → P a předchozího stavu: next: I × P → I

Deductive reasoning

Agent jako dokazovač (deliberate agents)Stavy agenta = databáze faktů. Akce jsou kódovány jako predikáty Do(A), kde A∈actions. 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é Do(A). Když taková neexistuje, vybere se taková, pro kterou není dokazatelné ¬Do(A)

Practical reasoning

Skládá se ze dvou částí:

Čtěte také: Jak podporovat projekty

• 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.

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)

Hybrid reasoning

Kombinují reaktivitu s plánováním, případně dalšími elementy

Vrstevnaté architektury

Čtěte také: Dávkování lignohumátu v ekologickém zemědělství

• 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.

Symbolické a konekcionistické reaktivní plánování

Obrázky ze slajdů Cyrila Broma (zveřejněno s jeho svolením)

Symbolické plánování:

Konekcionistické plánování:

Problém Hledání Cesty a Navigace

Pokud máme agenta, který se má pohybovat v nějakém prostředí, je třeba řešit problém navigace. 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. 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.

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.

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.

Komunikace a Znalosti v Multiagentních Systémech

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.

Problém Omezené Racionality

Agent:

• 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.

Etologické Motivace a Modely Populační Dynamiky

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 (tt - čas, bb - birth rate, dd - death rate):

N(t+Δt)=N(t)+b∗N(t)∗Δt−d∗N(t)∗Δt

Existují složitější modely, které lépe modelují konkrétní prostředí a pomáhají zodpovědět otázky jako např.

Metody pro Učení Agentů

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: (x1,y1),…,(xn,yn) a chceme: f(xi)=yi
• Bez učitele - máme: x1⃗,x2⃗,…,xn⃗ a chceme: P(X=x⃗)
• Zpětnovazební učení - máme: s0,a1,s1,a2,… kde některé stavy mohou být odměněny a chceme Π(si) - 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) - {(x1,y1),(x2,y2),…,(xn,yn)}) a rozdělíme je na dvě disjunktní množiny: trénovací (TT) a testovací (EE). Pro hledanou funkci ff platí: ∀i: f(xi)=yi

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.

Zpětnovazební učení

Př. 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.

Umělá Evoluce a Genetické Algoritmy

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).

Doporučená Literatura

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é. 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.
• 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.
• 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.
• David J. Sweatt: Mechanisms of memory, Elsevier Academic Press, 2003 kap. 1
• Melanie Mitchell: An Introduction to Genetic Algorithms, MIT Press, 1996 (kap.
• David E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning. (kap.
• Steve Rabin (ed.): AI Game Programming Wisdom I, Charles River Media, 2002 (k.
• Steve Rabin (ed.): AI Game Programming Wisdom IV, Charles River Media, 2008 (k. 2.2, 2.3, 2.5, 2.6)

tags: #ekologické #řídicí #algoritmy #definice

Oblíbené příspěvky:

• Rozměry popelnice 240 l
• Koše na odpadky Meliconi
• Ochrana ptactva v Americe
• Kompetice v ekosystémech
• Bakalářská práce o suchu