Een agent-gebaseerde simulatie van redeneren over de omgeving.

Eindproject voor MAS 2007/2008
Lise Pijl s1463543,
Popke Altenburg s1444239


Inleiding | Probleemomschrijving | Aanpak | Implementatie | Resultaten | Discussie | Conclusie | Applet

Inleiding


Het interessante aan een multi agent system is dat het geheel meer is dan de som der delen. Dit gaat zeker op in een omgeving die niet geheel observeerbaar is voor een agent, maar waarbij door alle agents gezamenlijk meer over de omgeving geconcludeerd kan worden dan door de agents op zich.

We beschouwen een simulatie, waarbij de agents in een discrete omgeving worden geplaatst die bestaat uit een 2-dimensionaal grid. Alle agents hebben een plattegrond van de omgeving, maar weten niet waar ze zich bevinden. De agents willen er, door middel van zo beperkt mogelijke communicatie, achter komen waar zij zelf en anderen zich in de wereld bevinden. Op basis van die beperkte communicatie en hun eigen kennis van hun omgeving, kunnen ze redeneren over hun eigen locatie en die van anderen. Doel is dat ze door uitwisselen van informatie uiteindelijk er achterkomen waar zij en andere agents zich bevinden in de wereld. Het oplossen van dit probleem is gebaseerd op het muddy-children problem.

inhoud


Probleemomschrijving

Het positiebepalen van agents noemen we het lokalisatieprobleem en we formaliseren het als volgt:
Een of meerdere agents zijn geplaatst in een omgeving die bestaat uit een vierkant, discreet, 2-dimensionaal grid. In elk vakje kan ofwel niets staan, ofwel een andere agent of een muur. Per coördinaat bevindt zich slechts één object. Elke agent weet niet waar hij zich bevindt in deze wereld. Wel kan hij in een bereik van 1 vakje om zich heen kijken. Ook heeft de agent beschikking over een kaart van deze wereld. Een voorbeeld van een wereld kan er als volgt uitzien:












1



0







2

 

Het doel van de agent is om te bepalen waar in deze wereld hij staat en om te bepalen waar de andere agents staan. Hij kan beperkt communiceren met andere agents: hij kan ze vragen of zij weten waar ze staan. Deze communicatie verloopt simultaan en niet in beurten. De agent heeft twee methoden om te bepalen wat zijn locatie is:
  • observatie van zijn omgeving
  • kennis over locatie van andere agents

Aanpak

Eerst bespreken we een mogelijke aanpak van het muddy-children probleem, vervolgens hoe we het lokalisatieprobleem aanpakken. Daarbij wordt ook de vergelijking getrokken met het muddy-children probleem.

 

Muddy-children probleem

 

In het (bekend veronderstelde) muddy-children probleem moeten de kinderen bepalen of ze zelf modderig zijn. Een manier om dit probleem te benaderen voor één van de kinderen is door voor dit kind alle mogelijke werelden op te stellen. Zodra het aantal mogelijke werelden is gereduceerd tot é én wereld, weet het betreffende kind of het modderig is of niet. Door te redeneren over wat de anderen weten en door informatieuitwisseling (door al dan niet naar voren te stappen als vader zijn vraag heeft gesteld), kunnen werelden worden geélimineerd.

Als de situatie bijvoorbeeld twee kinderen betreft, kind 1 en kind 2, kunnen we de informatie over de wereld weergeven als twee bits die voor beide kinderen respectievelijk aangeven of ze niet (0) of wel (1) modderig zijn. Als kind 1 ziet dat kind 2 modderig is, houdt deze dus twee werelden voor mogelijk: '01' (hij is schoon en kind 2 is vies) en '11' (hij is vies en kind 2 is vies). Dit kunnen we noteren als:


        K1(01 OR 11),


dus dat agent 1 weet dat of de ene wereld waar is, of de andere. Vervolgens kunnen we ook kennis van andere agents toevoegen. Omdat ieder kind goed kan redeneren en iedereen dat ook van elkaar weet, kan agent 1 afleiden wat agent 2 weet voor elk van de mogelijke werelden van agent 1, wat genoteerd kan worden als


        K1( (01 AND K2(00 OR 01)) OR (11 AND K2(10 OR 11)) ).


Als vader nu verteld dat er minstens één modderig kind is reduceert dit de kennis van agent 1 tot


        K1( (01 AND K2(01)) OR (11 AND K2(10 OR 11)) ),


waarbij kind 1 dus een wereld voor mogelijk houdt waarin kind 2 weet dat hij modderig is. Als vervolgens wordt gevraagd of de modderige kinderen naar voren willen stappen, en kind 2 stapt niet naar voren, is het dus niet waar dat kind 2 zijn eigen modderigheidstoestand weet en kan de wereld (01 AND K2(01)) geschrapt worden in kind 1's mogelijke werelden lijst. Dus blijft er nog één mogelijkheid over, en weet kind 1 nu dat het zelf modderig is.

 

Lokalisatieprobleem


Het lokalisatieprobleem is echter complexer van aard. Elke agent kan in een beperkte mate om zich heen kijken, en met de kaart in de hand moet deze vervolgens bepalen wat zijn mogelijke locaties zouden kunnen zijn. De agent weet, gegeven onderstaand plaatje, op welke locaties hij zou kunnen staan en op welke niet. Aan de hand van de kaart die ze hebben (onderstaand plaatje, maar dan zonder de agents) mappen ze hun observaties binnen het vastgestelde bereik (1 vakje) op de kaart. Agent 1 bijvoorbeeld ziet linksonder agent 0 en rechtsonder een muur. Op basis van deze observaties zou hij op twee locaties kunnen staan: op coördinaat {2,0} of op coördinaat {1,1}. Agent 0 houdt 1 locatie voor mogelijk, namelijk locatie {1,1}. Op {2,2} kan hij niet staan, omdat agent 1 dan buiten de omgeving zal vallen. Locaties die buiten de kaart vallen (alle observaties van agent 1 ten noorden van hem), worden beschouwd als lege locaties.




1


0











De agent stelt nu allerlei mogelijke werelden op waarin hij zich zou kunnen bevinden. Niet alleen genereert hij verschillende werelden voor elke positie waar hij zich zou kunnen bevinden, ook genereert hij werelden waarin de andere agents ook verschillende posities kunnen hebben. Voor een simpele 4x4-wereld met drie agents levert dit al heel erg veel verschillende werelden op. Deze set werelden kunnen, voordat enige kennisuitwisseling plaatsgevonden heeft, aanzienlijk gereduceerd worden:

  • De agent kan, op basis van zijn observaties, bepalen op welke locaties in de omgeving hij zich zou kunnen bevinden. De werelden waarin hij een locatie heeft die zich niet in de lijst van mogelijke locaties bevindt, worden verwijderd.
  • Als een andere agent in het gezichtsveld van de agent staat, kunnen veel werelden verwijderd worden. Als de tweede agent bijvoorbeeld ten oosten van de eerste agent staat, hoeft de eerste agent alleen de werelden voor mogelijk te houden waarin de tweede agent zich ten oosten van de agent bevindt.
  • Wanneer een andere agent niet binnen het gezichtsveld van de agent staat, hoeft de agent geen werelden te overwegen waarin dit wel het geval is.


Vervolgens kan het redeneerproces beginnen. Binnen het muddy-children probleem kunnen de kinderen mogelijke werelden genereren zoals hierboven beschreven. Voor de agents die hun eigen locatie en die van anderen proberen te bepalen, is dit eveneens het geval. Voor elke wereld die de agent voor mogelijk houdt, kan hij, uitgaande van die wereld, alle mogelijke werelden voor een tweede agent genereren. Deze werelden van de tweede agent zijn dus gebaseerd op één van de werelden die de eerste agent voor mogelijk houdt. Vervolgens begint de informatieuitwisseling. Elke agent vertelt aan alle andere agents of hij weet waar hij is. Voor elk van de werelden die de eerste agent voor mogelijk houdt, kan hij nu bepalen of in die wereld de tweede agent al dan niet weet waar hij is, op basis van zijn observaties. Wanneer in die voor mogelijk gehouden wereld een contradictie optreedt tussen wat de tweede agent zegt dat hij weet en wat de tweede agent zou moeten weten op basis de door agent 1 voor mogelijk gehouden wereld, dan weet agent 1 dan zijn voor mogelijk gehouden wereld niet mogelijk is. Immers, in die wereld zou agent 2 al dan niet zeker moeten zijn van zijn lokatie op basis van zijn observaties en hij beweert het tegenovergestelde.


Een voorbeeld uitvoering van het programma kan er als volgt uit zien:
Gegeven is de volgende plattegrond:












1










0



In dit voorbeeld heeft agent 0 geen referentie punten binnen zijn zichtbereik en agent 1 wel.

Tijdens de initialisatie genereert elke agent het totaal aantal mogelijke werelden gegeven zijn observaties. Voor agent 0 zijn dit er heel veel omdat hij geen referentiepunten ziet, en dus voor zijn eigen positie veel mogelijkheden heeft, en hij agent 1 niet ziet, dus voor deze ook veel mogelijkheden heeft. Alle mogelijke combinaties van mogelijkheden levert een flink aantal mogelijke werelden op.
Agent 1 kan zijn mogelijke aantal werelden aanzienlijk beperken. Hij ziet namelijk een referentiepunt op de plattegrond, wat betekent dat hij maar op één punt kan staan, wat voor zijn eigen positie zijn aantal mogelijke werelden beperkt. De andere agent kan hij echter niet zien, dus moet voor diens positie nog een aantal mogelijkheden openhoudt. Voor agent 1 is dus eigenlijk al het doel bereikt, hij weet waar hij zelf staat.

Nu volgt een communicatiestap. Beide agenten maken aan elkaar kenbaar of ze weten waar ze zich bevinden; agent 1 weet het wel, hij houdt een positie voor zichzelf voor mogelijk, agent 0 weet het niet. Nu agent 0 weet dat agent 1 weet waar hijzelf staat, kan agent 0 een aantal afleidingen doen over de set van mogelijke werelden, en dus ook zijn eigen locatie. Omdat hij weet dat agent 1 zijn locatie weet, kan er een aantal werelden geschrapt worden. Ook over zijn eigen locatie kan hij afleidingen doen. Agent 0 weet weliswaar nog steeds niet zijn eigen locatie, maar heeft wel meer informatie gekregen zodat zijn aantal mogelijke locaties enigzins ingeperkt is.

inhoud


Implementatie

De code is intern vrij grondig gedocumenteerd. Het programma is qua userinterface, de grid waarin de objecten verspreid staan en het generen van de agents gebaseerd op de programmacode die aangeleverd is voor het vak Design of Multiagent Systems van dit jaar. Alle overige code voor het observeren, redeneren, bepalen van mogelijke locaties, et cetera is zelf ontwikkeld. Voor de geinteresseerden volgt kort een globale beschrijving van de werking van het programma.


Initialisatie

Bij het starten van het programma worden de (vooraf bepaalde aantal) agents en muren willekeurig over de wereld verspreidt. De wereld bestaat uit een 4 bij 4 grid. Elk element uit het grid bestaat uit een locatieklasse. Uit deze klasse kan opgevraagd worden wat de inhoud van een locatie is. Alle agents worden aangemaakt. Nadat alle objecten in het grid geplaatst zijn, maakt elke agents zijn eigen observaties aan. Dit doet hij door binnen zijn bereik (1 vakje) alle elementen uit het grid op te slaan. De agent heeft toegang tot de grid, waarin ook de locatie van andere agents vermeldt staan, maar maakt hier niet stiekem gebruik van om op een illegale manier zijn eigen locatie te bepalen. Vervolgens bepaalt de agent al zijn mogelijke locaties op basis van die observaties.



Genereren en reduceren van werelden

Na dit proces weet de agent waar hij allemaal zou kunnen staan. Echter, de agent kan nog niet redeneren over zijn situatie en die van anderen. Voor dat hij dit kan doen, moeten alle mogelijke werelden gegenereerd worden waarin hij zich kan bevinden. In de code staat beschreven hoe dit in zijn werk gaat. Het is voldoende om te zeggen dat alle mogelijke werelden gegenereerd worden waarbij alle agents overal binnen de wereld kunnen staan, behalve op een locatie waar al een object staat of een muur. Deze nu gegenereerde set van werelden is uitgebreider dan nodig is. Vervolgens worden alle werelden verwijderd waarin de agent een locatie heeft die niet voorkomt in zijn lijst met mogelijke locaties. Vervolgens worden alle werelden verwijderd waarin andere agents binnen zijn gezichtsveld in die wereld niet binnen zijn gezichtsveld of op een verkeerde plek ten opzichte van hemzelf staan. Tot slot worden alle werelden verwijderd waarbij agents wel binnen zijn gezichtsveld staan, maar waarbij die volgens zijn observaties niet zo is.



Communiceren & redeneren
Alle agents overwegen nu zo weinig mogelijk werelden als maar kan op basis van hun eigen observaties. Alle agents stellen elkaar op de hoogte van hun kennis: of ze weten hun locatie of niet. Vervolgens start het redeneerproces. Voor elke wereld die de agent overweegt, genereert hij alle werelden die de tweede agent zou overwegen als die agent zich werkelijk in die wereld zou bevinden. Deze werelden die hij voor agent 2 genereert, worden eveneens gereduceerd. Dit alles vindt plaats op basis van de observaties die de tweede agent zou doen als hij zich werkelijk in die wereld zou bevinden. Nu wordt voor elke wereld die de eerste agent voor mogelijk houdt gekeken of gegeven de gegenereerde set voor agent 2, of agent 2 in die wereld zou moeten weten wat zijn locatie is. Als dit niet overeenkomt, hoeft agent 1 de desbetreffende wereld niet meer voor mogelijk te houden. Op basis van zijn redenatie over deze wereld met behulp van het antwoord van agent 2, is hij tot de conclusie gekomen dat die wereld niet geldig is.

Resultaten

We hebben een systeem gemaakt dat kan redeneren over de locatie van zichzelf en andere agents op basis van observaties en beperkte communicatie. De code is te vinden in dit zip-bestand. Het applet kan je hier starten. De wereld die gebruikt wordt in het applet is en 4x4 wereld met twee agents en een object. Grotere werelden met meer agents waren om computationele problemen niet mogelijk. De set van mogelijke werelden breidt zich heel erg uit en dit kost te veel rekenkracht.

inhoud

Discussie

Redeneren over redenaties
De belangrijkste functionaliteit die we voor ogen hadden toen we onze plannen opstellen, was het geven van de mogelijkheid aan agents om te redeneren over redenaties van andere agents. Wanneer een agent 1 een bericht binnenkrijgt, redeneert hij, gegeven een mogelijke wereld over mogelijke kennis van agent 2. Wat niet mee wordt genomen is het redeneren dat agent 2 zou moeten doen over de binnengekomen informatie. Dit is, net als het creeren van grotere werelden met meer agents, computationeel gewoonweg te zwaar. Daarnaast hadden we te weinig tijd om dit uit te werken. Dit zou niet zoveel tijd meer moeten kosten, omdat de basis er al ligt. Als we extra tijd hadden gehad, hadden we dit graag verder ontwikkeld.

Betere resultaten in complexere werelden
Graag hadden we een systeem ontwikkeld waarbij agents wel zeker kunnen zijn van hun lokatie op basis van communicatie en redenatie. Probleem bleek de exponentiele uitbreiding van de hoeveelheid werelden bij een grotere omgeving en bij meer agents. In de kleine 4x4-omgeving waarmee we werkten, waren er geen werelden mogelijk waarbij agents baat hadden bij meer communicatie dan eenmalige informatie-uitwisseling. Dit heeft alleen zin als per ronde nieuwe informatie bekend wordt. De enige situatie waarin dit gebeurt is wanneer een agent op een enige unieke positie staat en andere agents deze agent in zijn bereik staan. Dit wordt toegelicht aan de hand van onderstaande wereld.
















0




1
2
  
  



Zoals je kunt zien, bevindt agent 0 zich op een unieke positie. Hij weet meteen waar hij is en weet ook waar agent 1 is. Bijkomend verschijnsel is dat de agent niet alleen op een unieke positie staat, maar ook op de enige unieke positie. Zowel agent 1 als agent 2 houden verschillende locaties voor mogelijk. Agent 2 weet alleen dat hij zich rechts van agent 1 bevindt en dat verder de hele omgeving om hem heen leeg is. Verder heeft agent 2 geen besef waar agent 0 zou kunnen staan. Dit geeft voor agent 2 een ruime set mogelijke werelden. Voor agent 1 is die set iets kleiner: hij weet dat hij zich rechtsonder van agent 0 bevindt en links van agent 2. Voor hem zijn ook een aantal mogelijke werelden te bedenken.

Nu vindt de communicatie plaats: agent 0 deelt mee dat hij zijn locatie weet, agent 1 deelt mee dat hij zijn locatie niet weet en agent 2 deelt mee dat hij zijn locatie niet weet. Vervolgens gaan ze allen met deze resultaten aan het redeneren. Agent 0 kan een aantal werelden wegreduceren waarin agent 2 wel geweten zou hebben waar hij stond. Agent 1 weet echter nu wel waar hij is: hij verwijderd uit zijn mogelijke wereldenset alle werelden waarin agent 0 niet weet wat zijn locatie is, en houdt alleen de werelden over waarbij agent 0 zich op de enige unieke positie bevindt. In diezelfde wereld staat ook zijn eigen locatie opgeslagen en die van agent 2. Agent 1 houdt dus nog maar één wereld voor mogelijk en weet nu alles! Agent 2 kan nu alleen werelden reduceren waarin agent 1 niet zeker zou zijn geweest over zijn locatie. Zijn mogelijke wereldenset is verkleind, maar hij weet zijn locatie nog niet precies.

Vervolgens vindt er nog een communicatieronde plaats. Agent 0 deelt mee dat hij zijn locatie weet, agent 1 deelt mee dat hij zijn locatie weet en agent 2 deelt mee dat hij zijn locatie niet weet. Nu komt het interessante gedeelte. Agent 2 reduceert zijn werelden opnieuw zodat er alleen nog werelden zijn waarin agent 1 zijn lokatie wel weet. Dit kan alleen de wereld zijn zoals die hier getekend is! Bij elke andere wereld had agent 1 zijn locatie al eerder geweten (en die werelden zijn in de vorige ronde al weggereduceerd) of zou agent 2 zijn eigen locatie moeten weten (en die werelden zijn ook al weggereduceerd). Bij een laatste communicatieronde kan vervolgens ook agent 0 bedenken, op basis van de mededeling dat tot slot agent 2 ook zijn locatie weet, hoe de wereld in elkaar zit. Bij dergelijke complexere werelden is doorredeneren dus wel zinnig. Echter, vanwege computationele problemen bleek dit niet mogelijk.

Liegende agents

Oorspronkelijk wilden we ook liegende agents mogelijk maken in het systeem. Hiervoor zijn echter meer agents nodig dan twee. In een grotere wereld met meer agents waren dit soort problemen ook op te lossen geweest , maar vanwege enorme grootte van de hoeveelheid werelden, bleek dit computationeel niet haalbaar. Problemen met liegende agents zouden volgens dit zelfde principe opgelost kunnen worden: de set van werelden is alleen nog veel uitgebreider omdat ook rekening gehouden moet worden met het feit dat een agent liegt.

Als meer tijd beschikbaar was geweest, hadden we dit graag uitgezocht. De code is volledig geschikt om op dit vlak uitgebreid te worden. Het proces van het genereren en daarna reduceren van wereldensets zou zwaar geoptimaliseerd moeten worden. Dit kregen we echter niet in korte tijd voor elkaar.

inhoud

Conclusie

We hebben een implementatie gegeven van redeneren over kennis van anderen. Onbekende informatie, zoals positie, kan hieruit worden afgeleid. Dit kan van waarde zijn in een bepaalde multi-agent toepassingen, met name wanneer communicatie een beperkende factor is. Omdat de informatie die gecommuniceerd wordt in principe uit één bit bestaat is de communicatie minimaal gehouden. Echter, zelfs met een kleine wereld en weinig agents wordt de set werleden die voor mogelijk gehouden kunnen worden zo verschrikkelijk groot, dat we alleen kleine en simpele werelden besproken hebben waarin het alleen zin heeft om maximaal 1 stap te communiceren. We hebben echter laten zien dat, als die problmen overwonnen worden, het wel degelijk zin heeft om door te redeneren en informatie uit te wisselen.