Uvažování agenta

From Simulace.info
Jump to: navigation, search


Uvažování agenta je proces, při kterém daný agent rozhoduje o svých budoucích akcích. Tato rozhodnutí provádí na základě informací o okolním agentním prostředí, které získal pomocí svých senzorů nebo při komunikaci s jinými agenty.

Přístupy k uvažování agentů

Principy a přístupy k uvažování agentů se liší v závislosti na typu a složitosti agenta. Na složitosti použitého rozhodovacího přístupu také závisí nutný vypočetní výkon pro jeho realizaci a z toho plynoucí omezení v případě simulací většího rozsahu.

Reaktivní agenti

Reaktivní agenti jsou nejjednodušším typem agentů a při rozhodování používají primitivní IF-THEN logiku. Z tohoto důvodu jsou nejméně nároční na výpočetní výkon a vhodní pro masivní, ale jednoduché simulace.

Deliberativní agenti

Deliberativní agenti používají pro rozhodování složitější přístupy než prostá IF-THEN pravidla. Neexistuje dominantní přístup používaný pro uvažování deliberativních agentů. Základním dělením přístupů k uvažování těchto agentů je na základě čeho se rozhodují o provedení akcí.

Přístup podle cíle

Přístup podle užitku

Přístup podle vnitřní logiky

BDI (Beliefs-Desires-Intentions) Přístup

Přístup podle cíle

Agenti rozhodují o svých akcích podle toho, které dosáhnou daného cíle. Cíl agenta je takový stav, který daný agent vyhodnotí za úspěšný. Pomocí simulace následků akcí, které jsou danému agentu k dispozici, agent vybere takovou, která dosáhne zadaného cíle. V případě potřeby musí vytvořit alternativní nebo dílčí, krátkodobé cíle. Deliberativní agenti musí kontrolovat své krátkodobé cíle, aby se ujistil, že zůstávají proveditelné a relevantní pro jeho dlouhodobé cíle nebo poslání. Cílové uvažování je monitorovací funkce na nejvyšší úrovni a agent musí průběžně vyhodnocovat neočekávané události, které mohou zasahovat do současných cílů. [1]

Přístup podle užitku

Agenti rozhodují o svých akcích podle toho, které jim přinesou největší užitek. Zatímco cílové založený přístup rozeznával pouze dva možné výsledky – úspěch a neúspěch (1 a 0), užitkově založený přístup může využít pro ohodnocení výsledku celou číselnou škálu.

Pro ohodnocení možných výsledků se používá užitková funkce:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f: p(x) \rightarrow u ; u \in R}

Pokud nelze ohodnotit jednotlivé výsledky na nominální stupnici (přiřazuje každému výsledku reálné číslo), je možné využít jednodušší, ordinální stupnice (řadí jednotlivé výsledky za sebou bez znalosti přesného rozdílu užitku mezi výsledky). Ordinální stupnice je samozřejmě méně přesná než nominální, ale je také méně náročná na výpočetní výkon.

Nejjednoduší případy jsou řešitelné jako Klasický plánovací problém. Pro použití tohoto postupu je nutné, aby agentní model splňoval tyto podmínky [2] [3]:

Konečný systém: konečný počet stavů, akcí a událostí

Plně pozorovatelný: agent vždy vidí současný stav

Deterministický: každá akce má vždy jen jeden výsledek

Statický: model je ovlivňován pouze akcemi agenta

Dosažitelné cíle: existuje sada cílových stavů, do kterých se agent chce dostat

Posloupnost plánů: zkoumané plány jsou lineárně seřazené akce

Implicitní doby: akce netrvají žádný čas, model je vyjádřen jako sekvence okamžitých stavů

Off-line plánování: plánování probíhá před samotným provedením

Pří řešení problému hledáme takovou posloupnost akcí, která má jako konečný stav jeden z definovaných cílových stavů. Náročnost tohoto problému se s narůstajícím počtem možných akcí a stavů zvyšuje exponenciálně a často není k celkové analyze dispozici potřebná výpočetní síla.

Pokud není zkoumaný model deterministický a obsahuje náhodné proměnné, lze pro vyhodnocení akcí s největším užitkem použít Markovův rozhodovací proces.

Příklady složitosti plánování podle cíle/užitku

Vizualice problému sedmi mostů města Královce [4]

Sedm mostů města Královce

Slavný matematický problém, vyřešený Leonhardem Eulerem pomocí teorie grafů. Probémem je navrhnout takovou trasu prohlídky města, která by přešla každý ze sedmi mostů právě jednou. [5]

Celkový počet možných stavů: 64

Rubikova kostka

Slavný hlavolam se může nacházet v 8! (rozmístění rohů) x 37 (orientace rohů) x 12!/2 (rozmístění hran) x 211 (orientace hran) = 4.325 · 1019 možných stavech [6]

Přeprava nákladu

• 10 letišť

• 50 letadel

• 200 kusů nákladu

Celkový počet možných stavů: 1050 x (50+10)200 = 10405

Problémy plánování podle cíle/užitku

Procházet všechny možné stavy evidentně není vůbec fyzicky možné a pří řešení je nutné využívat sofistikovanějších algoritmů. Dalším problémem přístupu podle užitku je vrozená subjektivnost hodnot, podle kterých se hodnotí užitek daného stavu v případech, kdy nemá výsledek přímou číselnou hodnotu (Pokud nám jde například o maximalizaci peněžního zisku či minimalizaci spotřeby materiálu, lze naopak užitek vyjádřit snadno). S tímto problémem souvisí další, určení v jakém časovém horizontu chceme užitkovost stavů zkoumat. Co je výhodné krátkodobě, nemusí být správné řešení dlouhodobě.

Přístup podle vnitřní logiky

Agenti se rozhodují na základě vnitřních logických pravidel. Přístup má kořeny v symbolické umělé inteligenci a je založen na logických pravidlech nad sadou známých výroků. Nechť S je sada logických výroků uložených agenty, které obsahují záznamy o stavu agentního prostředí a výsledky procesních funkcí. Nechť σ∈S je jeden logický výrok jako součást agentního prostředí. Nechť ρ je sada logických pravidel, které agent používá pro rozhodování. Nechť Ac je soubor všech možných akcí agenta a α∈Ac je jedna konkrétní akce. V každém kole rozhodování agent projde každý predikát z S a pokusí se odvodit Do(α) pro každou akci α∈Ac. V případě, že takovou akci najde, tak ji provede. V případě, že se vhodnou akci najít nepovede, pokusí se najít takovou, která není výslovně zakázána pro daný stav σ. Pokud takovou akci nenajde, neprovede žádnou akci.

Příklad

Agentem je řidič, který se rozhoduje jestli pojede rychleji než je předepsaná rychlost, nebo ne. Pokud jede pozdě, může se rozhodnout, že pojede rychleji. V takovém případě přijede včas, ale je šance, že ho zpozoruje fotoradar a bude muset zaplatit pokutu.

Pravidla, kterými se agent řídí

• Pokud má agent méně času než potřebuje na dojezd do cíle včas, tak je ve spěchu.

time left (X) ⋀ time needed (Y) ⋀ (X < Y) ⇒ hurry

• Pokud není agent ve spěchu, pojede pomalu.

¬hurry ⇒ Do(go slowly)

• Pokud je agent ve spěchu a je velká šance, že po cestě narazí na radar, pojede pomalu.

hurry ⋀ risk of radar(high) ⇒ Do(go slowly)

• Pokud je agent ve spěchu a je malá šance, že po cestě narazí na radar, pojede rychle.

hurry ⋀ risk of radar(low) ⇒ Do(go fast)

Průběh simulace

Na počátku je agentova sada stavů S prázdná.

Během jízdy agentovy vstupní funkce aktualizují S s následujícími parametry:

time left(20)

time needed(30)

risk of radar(low)

Agentův inferenční mechanismus rozhodne o vygenerování záznamu hurry. Akční funkce projde všechna pravidla a zjistí, že Do(go fast) je logický výsledek výše zmíněných pravidel a záznamů o agentově prostředí a tuto akci se pokusí vykonat. [7]

BDI Přístup

Agenti se rozhodují na základě svých představ (Beliefs), přání (Desires) a záměrů (Intentions). BDI přístup vychází z modelu lidského praktického usuzování, vytvořeného filosofem Michaelem E. Bratmanem. Tento model předpokládá stejné základní postupy při rozhodování jako přístupy založené na cílech/užitku a zahrnuje vytvoření cíle, kterého chceme dosáhnout a plánování, jak ho dosáhneme. [8]

Architektura

Každý agent v simulace založené na BDI přístupu by měl mít tyto tři základní datové struktury. [9]

Představy (Beliefs): Představy vyjadřují povědomí agenta o světě, dalších agentech i o sobě samém. Představy mohou také obsahovat inferenční pravidla, které vedou ke transformaci představ na jiné. Představy se neoznačují jako znalosti, protože představy agentů nemusí být vždy pravdivé a mohou se v čase měnit (i bez změny dané oblasti modelu).

Přání (Desires): Přání vyjadřují motivaci agenta. Popisují stavy nebo situace, kterých by agent rád dosáhnul. Přání, kterého se agent snaží aktivně dosáhnout, se označuje jako cíl. Cíle agenta by se neměly navzájem vylučovat, ačkoli přání mohou být v praxi protichůdná.

Záměry (Intentions): Záměry vyjadřují co se agent rozhodl udělat. Záměry jsou přání, ke kterým se agent určitým způsobem zavázal. V simulačních modelech jsou to taková přání, ke kterým agent začal vykonávat plán. Plán je posloupnost akcí, které agent vykonává za účelem dosáhnutí nějakého svého záměru. Plány mohou obsahovat jiné plány a mohou se v závislosti na změnách představ agenta měnit v jejich průběhu.

BDI přístup může být také rozšířen o povinnosti a poté mluvíme o BOID přístupu. Povinnosti zahrnují závazky, normy a standardy uvnitř sociálních struktur v modelu a vůči ostatním agentům. [10]

Další nedílnou součástí těchto simulací jsou události. Události jsou spouštěče reaktivních akcí agenta. Události mohou měnit představy, cíle či uvádět plány do pohybu. Mohou pocházet z vnějších zdrojů a mít efekt na agenta skrz jeho senzory nebo z vnitřních a spuštět nepropojené aktualizace stavů nebo aktivit.

Procesy BDI agenta

Schéma BDI procesů [11]

Základní model uvažování BDI agenta se skládá z [11]:

• Funkce pro revizi představ (Belief revision function): Na základě vnějších a vnitřních událostí mění agentovy představy o světě

Představy (Beliefs)

• Funkce pro vytváření přání (Option generation function): Na základě představ a záměrů agenta vytváří možná přání agenta

Přání (Desires)

Filtr přání (Filter): Představuje deliberační proces agenta, rozhodující o jeho aktuálních záměrech na základě jeho představ, přání a stávajícíh záměrů/plánů.

Záměry (Intentions)

• Funkce pro rozhodování (Action selection function): Vybírá akce, které agen provede a rozhoduje o pořadí jejich provedení na základě současných záměrů agenta.


Reference

  1. GHALLAB, Malik, Dana S. NAU a Paolo TRAVERSO. Automated planning and acting. New York, NY: Cambridge University Press, 2016. ISBN 978-1107037274.. Dostupné z: http://projects.laas.fr/planning/book.pdf
  2. MARIK Ing. Radek CSc. - Czech Technical University - Classical Planning [online]. Dostupné z: https://cw.fel.cvut.cz/old/_media/courses/ae3b33kui/lectures/lecture_09.pdf
  3. MALTE Helmert - The 28th International Conference on Automated Planning and Scheduling - Classical Planning Algorithms [online]. Dostupné z: http://icaps18.icaps-conference.org/fileadmin/alg/conferences/icaps18/summerschool/lectures/Lecture7-01.pdf
  4. MacTutor History of Mathematics archive [online]. Dostupné z: http://www-history.mcs.st-andrews.ac.uk/Extras/Konigsberg.html
  5. Mathematical Association of America - Leonard Euler's Solution to the Konigsberg Bridge Problem [online]. Dostupné z: https://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem
  6. Analyzing Rubik's Cube with GAP [online]. Dostupné z: http://www.gap-system.org/Doc/Examples/rubik.html
  7. ŠALAMON, Ing. et Ing. Tomáš, Ph.D., MBA - Podklady k předmětu 4IT495 - Simulace systémů
  8. BRATMAN, M. E. Intentions, Plans, and Practical Reason. Harvard University Press, Cambridge, MA, 1987. ISBN 1-57586-192-5.
  9. JENNINGS, Nick R. Specification And Implementation Of A Belief-Desire Joint-Intention Architecture For Collaborative Problem Solving. In Journal of Intelligent and Cooperative Information Systems 2 (3) 289-318. 1993. Dostupné z: https://eprints.soton.ac.uk/252091/1/IJICIS-2-3.pdf
  10. J. Broersen, M. Dastani, J. Hulstijn, Z. Huang, L. van der Torre The BOID architecture: conflicts between beliefs, obligations, intentions and desires. Fifth international conference on Autonomous agents, ACM New York, NY, USA
  11. 11.0 11.1 Instituto de informática UFRGS - BDI Architecture [online]. Dostupné z: http://www.inf.ufrgs.br/prosoft/bdi4jade/?page_id=46