Komunikace a paměť pro plausibilní agenty

Komunikace a paměť pro plausibilní agenty Vojtěch Kopal, Ondřej Sýkora Univerzita Karlova v Praze, Matematicko-fyzikální fakulta Malostranské námestí 25, 118 00 Praha 1 [email protected], [email protected]

Abstrakt

To, že skupina komunikujících a spolupracujících agentů může dosáhnout lepších výsledků, než nezávislí agenti, je jedna ze základních myšlenek teorie multiagentních systémů. Výměna informací mezi agenty může přispět k rychlejšímu prozkoumávání prostředí a zároveň kompenzovat omezené znalosti a schopnosti jednotlivých agentů. V této práci zkoumáme vztah mezi komunikací a prostorovou pamětí situovaných agentů a vliv paměti a komunikace na schopnost agentů přežít v simulovaném prostředí. Ukazujeme, že komunikace může významně zvýšit životaschopnost agentů a kompenzovat omezené vnímání a kapacitu paměti agentů.

1

Úvod*

V současné informační společnosti je pro jednoho člověka velmi obtížné pojmout veškeré dostupné informace. A to jak zapamatovat si je, tak je sám dál zpracovávat. Z toho je zřejmé, nakolik je důležitá schopnost delegovat proces uvažování a zpracování informací v rámci skupiny. Samotný problém rozhodování ve skupinách či týmech je v literatuře studován již dlouho [3]. Za předpokladu, že pro zpracování informací a vyhodnocení rozhodnutí jsou k dispozici jen omezené prostředky, v tomto případě paměť, musejí být informace nutné pro rozhodování rozděleny a efektivně předávány mezi členy skupiny. Naše rozhodnutí mohou být buď vědomá či podvědomá, v závislosti na našich potřebách. Podobně jako v mikroekonomii lze použít užitek (utility) jako míru relativního uspokojení [12] a pomocí něj sledovat, jak lidi zvládají naplňovat své potřeby. Klíčové pro úspěšné naplnění potřeb jedince jsou jeho znalosti, které ukládá v paměti a průběžně je obnovuje. S neomezenou pamětí, do které by bylo možné informace ukládat a libovolně z ní vybavovat, by bylo snadné dosáhnout optimálního rozhodování. Lidská paměť je však omezená. Když hovoříme o tom, že lidská paměť je omezená, máme na myslí, že si nejsme schopni pamatovat cokoliv. Určité části informací se vytrácejí samovolně s postupem času, nebo jako následek uložení nových faktů. V této práci zkoumáme, zda-li a jak moc může intenzivní

komunikace nahradit nedostatečnou paměť za předpokladu konstantního užitku. Předpokládáme přitom, že přidání komunikace zlepší šance agentů na přežití.

2

Související práce

V této práci se zabýváme modely prostorové paměti pro agenty a komunikací mezi agenty. Přitom navazujeme především na výzkum v oblasti agentů a umělého života a na výzkum zybývající se modelováním paměti v multiagentních systémech. V následujících odstavcích shrnujeme základní pojmy z obou oblastí.

2.1

Agenti

Pro pojem agent existuje řada definic pocházejících z různých oborů, mj. z psychologie a ekonomie. V umělé inteligenci je pojem agent několik významů, bez přesně vymezené definice [13]. Nejčastěji se tento pojem ale používá pro pojmenování entity, která vnímá prostředí, ve kterém se nachází, a vykonává akce, pomocí kterých své prostředí ovlivňuje [10]. Přitom je třeba dát pozor, že jak agent, tak prostředí jsou abstraktní pojmy, které nevyžadují, aby prostředí bylo reálné fyzické prostředí, nebo aby se v něm agent nacházel na konkrétní, přesně definované, pozici. Agent tak může být stejně dobře robot provádějící průzkum cizí planety, jako entita bez fyzické reprezentaca, která prochází Internet a vyhledává na něm informace. Velmi často se pojem agent používá v kontextu multiagentních systémů, tedy systémů, ve kterých se pohybuje několik agentů současně. Tito agenti spolu mohou komunikovat a spolupracovat na řešení svých úkolů. Spolupráce agentů ovšem není nutná vlastnost multiagentního systému a agenti sledují především svoje vlastní zájmy. Základní taxonomie agentů [13] obsahuje několik typů agentů rozdělených podle jejich vlastností a vlastností jejich chování. Racionální agenti (rational agents) jsou agenti, kteří vybírají akce tak, aby maximalizovali vlastní zisk [6]. Věrohodní agenti (plausible agents) jsou agenti implementováni pomocí metod inspirovaných poznatky z psychologie a biologie, které se snaží napodobit

fungování lidského mozku. V tomto textu budeme hovořit především o situovaných agentech, tedy o agentech, kteří se pohybují v určitém prostředí a jejichž inteligence je založena na interakci s tímto prostředím.

2.1

Modely paměti

Mluvíme-li v této práci o paměti, nejedná se o paměť v technickém smyslu, například paměť počítače. Spíše jde o modely a algoritmy, které agenti využívají pro ukládání a vybavování informací o svém prostředí a interakcích s ním. Typy paměti, které agenti používají, závisejí na typu agenta a na úloze, kterou vykonává. V tomto textu se zabýváme především prostorovou pamětí, tedy pamětí určenou pro uložení informací o rozložení objektů v prostředí a navigaci v něm. V psychologické literatuře nacházíme typicky dva základní typy paměti: krátkodobou paměť, která je výrazně omezená co do kapacity, ale nabízí snadné zapamatování a vybavení informací, a dlouhodobou paměť s vysokou kapacitou, ale pomalejším procesem učení [1,2,11]. Agenti v reálném prostředí typicky nemají k dispozici neomezené prostředky nebo neomezený čas pro nalezení optimální strategie. Racionální agenti proto musejí hledat rovnováhu mezi kvalitou plánu a časem nutným pro jeho vytvoření. Bratman, et al. [4] popisují, jak je možné pracovat s omezenými prostředky při plánování; podobná omezení je nutné uvažovat i při modelování paměti pro reálné agenty. Modely paměti pro uvěřitelné agenty byly studovány zejména v kontextu autobiografických agentů. Jedná se o agenty, kteří zaznamenávají své vlastní interakce s prostředím a s ostatními agenty. Ho, et al. [8] studoval schopnost agentů vybavených pamětí ve scénářích s komunikací a bez komunikace přežít v komplexním multiagentním prostředí. Ve své práci popisuje tři typy agentů: čistě reaktivní agenty, agenty s krátkodobou pamětí a agenty s dlouhodobou pamětí. Krátkodobá paměť byla tvořena pomocí spojového seznamu pevné délky; dlouhodobá paměť byla založena na psychologických modelech paměti. Závěry studie odpovídají očekávání, tj. agenti používající složitější modely paměti dosahují lepších výsledků a výměna informací umožňuje agentům lépe se vyrovnat s dynamickým prostředím. Brom, et al. [5] navrhuje model paměti, pomocí kterého si agenti mohou zapamatovat umístění věcí v prostředí, ve kterém se pohybují. Tento model se od předchozích liší zejména hierarchickým rozdělením prostoru. Autoři model popisují v kontextu bytu; dělení v tomto případě je na jednotlivé místnosti a dále na kusy nábytku v těchto místnostech. Model zároveň umožňuje popisovat změny v prostředí (například dané aktivitou ostatních agentů) pomocí přemisťování v prostředí. Agent si tak vytváří pravděpodobnostní model umístění předmětů a implicitně

i pravidla pro procházení prostoru při hledání určitého předmětu. V této práci se zaměřujeme spíše na efekty komunikace mezi agenty a proto používáme jednodušší modely paměti založené na samoorganizaci a strojovém učení, bez hierarchické struktury a bez explicitního dělení na krátkodobou a dlouhodobou paměť.

3

Simulace prostředí

Pro testování chování agentů jsme vytvořili simulátor prostředí pro situované agenty. Toto prostředí je dvourozměrná čtvercová mřížka, ve které se agenti pohybují. Každý agent se v každém kroce simulace nachází na právě jednom poli a v danou chvíli může vnímat pouze omezené okolí své pozice. Aby se dozvěděl o tom, co se děje v oblastech mimo jeho dohled, musí tyto oblasti navštívit. Tím ovšem ztratí aktuální informace o oblasti, kterou opustil. Agent své znalosti o prostředí doplňovat buď sám tím, že opakovaně prochází celé prostředí, nebo je získávat pomocí komunikace s ostatními agenty. Ukázka vizualizace prostředí během simulace je zachycena na Obr. 1.

Obr. 1. Vizualizace paměti agenta v simulovaném prostředí. Čtverce znázorňují mřížku simulovaného prostředí a rozmístění potravy. Pruhy na levé straně jsou hodnoty potřeb agenta; kruhy znázorňují rozložení potravy, jak je uložené v paměti agenta. Simulace prostředí je diskrétní simulace, ve které všichni agenti provádějí své akce současně. Simulace se v každém kroce skládá z následujících kroků: 1.

Všichni agenti získají aktuální informace ze svého okolí.

2.

Na základě svého vnitřního stavu a informací z okolí agenti vyberou akci, kterou v tomto kole provedou. Akce agenta může být buď pohyb na jedno ze

sousedních polí, nebo konzumace potravy na poli, na kterém se právě nachází. 3.

Jsou vyhodnoceny potřeby agenta a agenti, pro které některá z potřeb dosáhla kritické hranice, jsou označeni jako mrtví a odstraněni ze simulace.

Rozhodovací proces, na základě kterého agenti vybírají své akce je podrobněji popsán v odstavci 4.2.

3.1

Potřeby a potrava

Kromě agentů tato mřížka obsahuje různé typy potravy, kterou agenti musejí sbírat, aby přežili. Každý agent má několik potřeb, které se postupně zvyšují. Ve chvíli, kdy dosáhnou dané hranice, agent zemře a odstraněn ze simulace. Cílem agentů je přežít v simulaci co nejdéle. Konzumací patřičného typu potravy se hodnota dané potřeby snižuje. Potřeba agentů ale nemůže klesnout pod danou hranici. Agenti si proto nemohou vytvářet zásoby potravy a musejí potravu konzumovat průběžně. Potrava, kterou agenti spotřebují, z prostředí mizí. V prostředí se ovšem v průběhu simulace objevují nové instance potravy. Nová potrava se ale v prostředí objevuje na náhodně zvolených pozicích a agenti proto musejí potravu hledat po celou dobu simulace.

3.2

4.1

Architektura agenta

V kontextu tohoto článku je agent entita, která se skládá ze čtyř základních komponent: aktuálního stavu potřeb agenta, prostorové paměti, chování při prozkoumávání prostředí a chování při vyhledávání potravy. Aktuální stav potřeb ovlivňuje přepínání mezi oběma režimy chování agenta. Tyto režimy pak ovlivňují, v jaké části simulovaného prostředí se agent pohybuje a tím i jaké informace jsou ukládány do prostorové paměti. Informace z prostorové paměti pak ovlivňují navigaci agenta po prostředí, pokud právě vyhledává určitý typ potravy. Schéma architektury agenta je zachyceno na Obr. 2.

Agent Hodnoty potřeb

Chování pro hledání potravy

Prostorová paměť

Chování pro zkoumání prostředí

Obr. 2. Schéma architektury agenta.

Komunikace agentů

V prostředí se pohybuje najednou několik agentů. Ve chvíli, kdy se k sobě dva agenti přiblíží, mohou si navzájem vyměňovat znalosti o okolním prostředí. V případě simulovaného prostředí jde především o výměnu informací o rozmístění potravy. Protože agenti mohou používat různé implementace pamětí, nemohou si vyměňovat informace přímo ve formátu, v jakém jsou uloženy v jejich paměti. Komunikace proto probíhá podle jednoduchého protokolu, který je nezávislý na použitém typu paměti. Vysílající agent pošle svému partnerovi několik pozic, o kterých se domnívá, že se na nich nachází potrava. V případě agentů, kteří v paměti udržují seznam potravy přímo, může jít o skutečné pozice potravy, které agent pozorovat. V případě agentů, kteří používají jinou reprezentaci, například aproximaci pravděpodobnostního rozdělení, podle kterého je potrava generovaná, může jít o náhodný výběr z tohoto rozdělení. Příjemce tyto pozice může buď přímo uložit, nebo použit jako vstupy pro učící algoritmus pro vlastní paměť.

4.2

4

Pro provedení experimentů popsaných v tomto článku jsme implementovali několik typů agentů, kteří se liší podle použitého modelu pamětí. Abychom mohli použité modely paměti zasadit do kontextu, vytvořili jsme také dva typy agentů, kteří nepoužívají paměť.

Agenti a paměť

V následujících ostavcích popisujeme architekturu agentů a modely prostorové paměti použité v této práci.

Chování agentů

Chování agentů závisí na tom, v jakém stavu se v daném okamžiku nacházejí. Pokud je některá z potřeba agenta vyšší než určitá kritická hodnota, agent aktivně vyhledává potravu odpovídající potřebě s nejvyšší hodnotou. Pokud se tento typ potravy nachází v dohledu agenta, agent se pohybuje přímo k potravě. Pokud se požadovaný typ potravy nenachází ve viditelném okolí agenta, agent hledá tento typ potravy na základě informací, které si vybavuje ze své paměti. V případě, že ani paměť agenta neobsahuje informace o tomto typu potravy, pak se agent pohybuje náhodně. Pokud jsou všechny potřeby agenta pod určitou hranicí, agent nemusí aktivně hledat potravu a věnuje se zkoumání prostředí. Agent se v takovém případě pohybuje po prostředí náhodně. Schéma rozhodování agenta je zázorněno na Obr. 3.

4.3

Typy agentů

Potřeba nad kritickou hranicí?

Ulož známé pozice potravy do paměti

rozložení v prostředí. Díky tomu je tento model méně náchylný k přeučení a může lépe reprezentovat odpovídající pravděpodobnostní rozdělení.

NE

ANO

5

Vybav si známé pozice potravy a vyber nejbližší.

Vybraná pozice je přístupná?

Pro testování vlivu komunikace a typu použité paměti na schopnost agentů přežít v simulovaném prostředí jsme navrhli dva typy experimentů.

NE

5.1

ANO

Pohybuj se směrem k vybrané pozici.

Pohybuj se směrem k vybrané pozici.

NE

Je na pozici požadovaný typ potravy?

Experimenty

Pohybuj se směrem k vybrané pozici.

ANO

Zkonzumuj potravu.

Obr. 3. Schéma rozhodování agenta v jednom kroce simulace. Náhodný agent Základní typ agenta, který nepoužívá paměť, a po prostředí se pohybuje vždy náhodně. Náhodný agent představuje dolní hranici pro životaschopnost agentů. Přestože náhodný agent nevyužívá paměť, náhodný agent může přežít určitou dobu díky potravě, která je v jeho dohledu. Agent s perfektní pamětí Agent s perfektní znalostí prostředí vidí po celou dobu simulace celé prostředí. Díky tomu se může pohybovat v simulaci optimálním způsobem a dosahovat maximální délky života za všech agentů. Grid agent Základní typ paměti je implementovaný pomocí pravidelné mřížky, která je namapovaná na pole v simulovaném prostředí. Agent pro uložení informací o rozložení potravy používá stejnou dvourozměrnou mřížku, na které se agent pohybuje. Uložené pozice jsou díky tomu přesné. Protože ale potrava není generována vždy na stejné pozici, ale podle určitého pravděpodobnostního rozdělení, může tento typ paměti snadno podlehnout přeučení. Growing Neural Gas Pokročilý typ paměti založený na modelu Growing neural gas [7,9]. Jde o typ neuronové sítě založené na myšlenkách samoorganizace. Model založený na GNG na rozdíl od předchozího neukládá přímo pozice, na kterých agent pozoroval potravu, ale spíše hustotu jejího

Experimentální prostředí

Všechny experimenty byly provedeny v prostředí o velikosti 128x128 polí se šesti typy potravy, kterým odpovídalo šest potřeb. Všechny potřeby nabývají hodnoty v intervalu [0, 1]. Hodnota 1 je kritická a pokud některá z potřeb dosáhne této hodnoty, agent umírá a je odstraněn ze simulace. Nová potrava byla do prostředí přidávána po každých 50 krocích simulace. Dohled agentů byl nastaven na 30 polí. Stejná hodnota byla použita pro vzdálenost, na kterou mohou agenti komunikovat. Během testování jsme použili prvních 100 000 kroků simulace. Během experimentů jsme měřili hodnoty všech potřeb všech agentů v simulaci.

5.2

Homogenni prostředí

Jako první test jsme provedli sérii experimentů, ve kterých se v simulaci vyskytoval vždy jen jeden typ agentů. Cílem těchto experimentů bylo zjistit, jakým způsobem se daný typ agenta chová “sám o sobě”, bez toho, aby od jiných typů dostával informace, které by sám nedokázal zjistit. Tento experiment jsme provedli pro všechny implementované typy agentů, ve variantách s komunikací a bez komunikace. V tomto případě výsledky experimentů odpovídaly očekávání. Agenti s perfektní informací mají kompletní informace o prostředí i bez komunikace, v této variantě jsme podle očekávání dosáhli stejných výsledků ve variantě bez komunikace i ve variantě s komunikací a průměrná hodnota potřeb byla 0,512. V případě náhodného agenta byla ve variantě bez komunikace průměrná hodnota všech potřeb rovna jedné prakticky po celou dobu simulace. Protože náhodní agenti nepoužívají paměť, komunikace pro ně znamená pouze částečné rozšíření zorného pole o zorné pole ostatních agentů, kteří jsou dostatečně blízko pro komunikaci. V praxi se toto rozšířené zorné pole ukázalo jako dostatečné zlepšení pro snížení průměrné hodnoty potřeb všech agentů z 1 na 0,85. Výraznější zlepšení jsme dosáhli u growing neural gas agenta, a to z průměrné hodnoty 1 bez komunikace na průměrnou hodnotu 0,508. V případě grid agenta jsme naopak dosáhli lepších výsledků ve variantě bez komunikace než ve variantě s komunikací. Toto zhoršení přikládáme přeučení v kombinaci se zastaráváním

informací v paměti. Vývoj hodnot potřeb pro grid agenta a Growing neural gas agenta ve variantě s komunikací a bez komunikace je zachycen na Obr. 4 a 5.

typu growing neural gas. V této variantě žádný z agentů neměl k dispozici kompletní informace o prostředí a agenti ho díky tomu museli aktivně porovnávat. Ve druhé variantě byl v simulaci navíc agent s perfektní informací o prostředí, díky kterému mohli ostatní agenti získat informace o libovolném typu potravy jen za pomocí komunikace. Oba experimenty byly opět provedeny ve variantě s komunikací a bez komunikace. Ukázalo se, že výsledky závisejí především na tom, zda agenti mohou komunikovat. V případě, že agenti mohli komunikovat, dosahovali v obou variantách téměř optimálních výsledků; naopak přítomnost agenta s kompletní informací neznamenala výrazné změny v hodnotách potřeb agentů. Vývoj hodnot potřeb v experimentu s agentem s perfektní informací, ve variantě s komunikací i bez komunikace jsou na Obr. 6 a 7.

Obr. 4. Průměrné hodnoty potřeb agentů typu growing neural gas bez komunikace v průběhu simulace.

Obr. 6. Průměrné hodnoty potřeb agentů typu v simulaci bez komunikace.

6

Obr. 5. Průměrné hodnoty potřeb agentů typu growing neural gas s komunikací v průběhu simulace.

5.3

Heterogenní prostředí

Jako druhý experiment jsme provedli srovnání úspěšnosti agentů v případě, kdy se v prostředí vyskytují různé typy agentů. Tento experiment jsme realizovali ve dvou variantách. V první variantě se v prostředí vyskytovali pouze náhodní agenti, agenti s pamětí typu grid a pamětí

Diskuze a další výzkum

Experimenty popisované v tomto textu chápeme především jako experimenty pro otestování simulovaného prostředí a použitých typů pamětí. Zároveň otevírají několik možností pro další výzkum ve dvou oblastech: jednak jde o výzkum zaměřený na schopnost agentů adaptovat se na rychle se měnící prostředí a zkoumání vlivu šumu v komunikaci na úspěšnost agentů a následně také testování situací, ve kterých někteří agenti záměrně vnášejí do komunikace nepravdivé informace. Takové experimenty navíc vyžadují paměti, které kromě samotných dat ukládají také informace o pravdivosti nebo důvěryhodnosti těchto dat.

[6]

Friedman, M. Essays in positive economics. University of Chicago Press, 1953.

[7]

Fritzke, B. A growing neural gas network learns topologies. In Advances in neural information processing systems 7, str. 625-632. MIT Press, 1995.

[8]

Ho, W., C., Dautenhahn, K., Nehaniv, C., L. Computational memory architectures for autobiographic agents interacting in a complex virtual environment: a working model. Connect. Sci, 20, str. 21-65. 2008.

[9]

Martinetz, T. M., Shulten, K. J. A neural-gas network learns topologies. In Artificial neural networks, str. 397-402. 1991.

[10] Russell, S., Norvig, P. Artificial intelligence: a modern approach. Prentice Hall, 3. vydání, 2009.

Obr. 7. Průměrné hodnoty potřeb agentů v simulaci s komunikací.

7

Závěr

V této práci jsme se zabývali implementací prostorové paměti a komunikací agentů a jejich vlivem na schopnost agentů přežít v dynamickém simulovaném prostředí. V provedených experimentech jsme testovali dva typy prostorové paměti a srovávali s agenty, kteří paměť nevyužívaji, a agenty, kteří mají k dispozici kompletní informace o prostředí. Provedené experimenty ukázaly, že komunikace mezi agetny může výrazným způsobem zvýšit jejich schopnost přežít v simulovaném prostředí a že v některých případech může vést ke stejným výsledkům, jako kompletní znalost prostředí.

Literatura [1]

Atkinson, R. C., Shiffrin, R. M. Human memory: A proposed system and its control processes. In The psychology of learning and motivation: advances in research and theory (vol. 2), str. 89-105. 1968.

[2]

Atkinson, R. C., Shiffrin, R. M. The control of short-term memory. Scientific American. 225(2), 1971.

[3]

Black, D. On the rationale of Group Decision-making. Journal of Political Economy, 56(1), pp. 23-34. 1948.

[4]

Bratman, M., E., Israel, D. J., Pollack, M., E., Plans and resource-bounded practical reasoning. In Computational Intelligence, 4(3(:349-355, 1998.

[5]

Brom, C., Korenko, T., Lukavský, J. How do place and objects combine? “What-where” memory for human-like agents. In Proceedings of the 9th International Conference on Intelligent Virtual Agents, str. 42-48. 2009. Springer-Verlag.

[11] Sternberg, R. J. Cognitive psychlogoy. Wadsworth publishing, 2002.

[12] Varian, H. R. Intermediate microeconomics: a modern approach. W W. Norton, New York. 1987.

[13] Wooldridge, M. Intelligent agents. In Multiagent systems: a modern approach to distributed artificial intelligence, str. 27-77. MIT Press, 2000.