Robot Voetbal Simulatie - Stage van Remco de Boer en Jelle Kok -------------------------------------------------------------- Op 18 september 2000 zijn wij, Remco de Boer en Jelle Kok, begonnen aan onze stage over multi-agent systemen toegepast op het gebied van robot voetbal simulatie. Normaal gesproken duurt een dergelijk stage-project 6 maanden die worden afgesloten met het schrijven van een scriptie. In ons geval ligt dit echter iets anders aangezien we allebei zowel Kunstmatige Intelligentie als Informatica studeren en dus een dubbele stage van ongeveer 12 maanden doen. Bovendien schrijven we ook twee scripties: eentje gericht op de AI-aspecten van de stage en eentje die de informatica-componenten belicht. Onze stage-begeleider is Frans Groen. Voor het project werken we met de RoboCup simulator die ook gebruikt wordt voor het practicum bij het vak Organisatie en Ontwerp van Autonome Systemen. Het is de bedoeling dat wij een voetbalteam implementeren dat in augustus gaat deelnemen aan de RoboCup (het WK robot voetbal) in Seattle (VS). We zullen ons hiervoor overigens eerst moeten kwalificeren. Verder zullen we in juni ook meedoen aan de German Open om te kijken waar we op dat moment staan in het internationale veld. Het RoboCup initiatief is een poging om een standaard probleem te formuleren dat voldoende complex is dat het real-world problemen omvat en waarbinnen verschillende technieken op het gebied van multi-agent systemen geintegreerd kunnen worden. Een voordeel van een dergelijke standaard is dat verschillende wetenschappelijke ontwikkelingen op een bepaald gebied goed met elkaar vergeleken kunnen worden omdat ze worden toegepast binnen hetzelfde domein. De RoboCup organisatie heeft verschillende competities in het leven geroepen: - De Middle Size League: hierin wordt gespeeld in teams van 4 robots van ongeveer een halve meter hoog op een veld van ongeveer 5 bij 9 meter. - De Small Size League: hierin speelt men 5 tegen 5 met robots van ongeveer 20 cm hoog op een veld ter grootte van een tafeltennistafel. - De Simulation League: hierin wordt gebruik gemaakt van een simulator; elk team bestaat uit elf virtuele spelers die op een virtueel veld staan. - De Humanoid League: hierin wordt gespeeld met mens-achtige robots; deze league staat nog in de kinderschoenen aangezien men er pas in 2000 mee is begonnen. - De Special Skills Competition: hierin staat het uitvoeren van een bepaalde taak centraal (in 2001 kijkt men bijvoorbeeld naar de capaciteiten van de coach in de simulatie competitie). De doelstelling van de RoboCup organisatie is om in 2050 een team van mens-achtige robots te hebben dat kan winnen van de menselijke wereldkampioen van dat moment. Om dit te bewerkstelligen moeten vele problemen worden overwonnen die zich op verschillende niveaus van abstractie bevinden. De voornaamste reden voor de opsplitsing in de verschillende leagues is dan ook dat binnen elke categorie een bepaald abstractie niveau centraal staat. In de Middle Size League is bijvoorbeeld vooral de interpretatie van sensorische informatie een moeilijk probleem. Voor de Simulation League is dit echter veel eenvoudiger en kan men zich meer concentreren op strategische aspecten zoals samenwerking. Het is de bedoeling dat de ontwikkelingen binnen de 'hogere' niveau leagues op een gegeven moment geintegreerd worden in de leagues op 'lagere' niveaus om uiteindelijk tot een team te komen dat het menselijke WK kan winnen. Zoals gezegd houden wij ons alleen bezig met de simulatie competitie. De UvA heeft hiermee overigens al eerder succes gehad: in 1998 werd het team Windmill Wanderers van Emiel Corten 3e bij het WK in Parijs. De maker van dit team is echter kort daarna overleden en sindsdien is het project niet verder voortgezet. Het is daarom onze taak om het project weer opnieuw op te starten zodat anderen er na ons afstuderen mee verder kunnen gaan. De RoboCup simulator gedraagt zich als een server die het gewenste robot voetbal domein verschaft. Elke speler kan gezien worden als een client die verbinding kan maken met de server via UDP sockets. De server simuleert de bewegingen van alle objecten in het veld en stuurt sensorische informatie terug naar de client. Elke client kan op zijn beurt opdrachten naar de server sturen om een bepaalde actie uit te voeren. De server werkt dan elke 100 ms (de lengte van een server-cykel) het veld bij aan de hand van deze opdrachten. Alles gebeurt dus real-time. De informatie die een speler binnen krijgt bevat overigens wel een bepaalde hoeveelheid ruis om de situatie zo realistisch mogelijk te maken. Veel van de problemen die je tegenkomt bij het implementeren van een simulatie team worden veroorzaakt door deze ruis. Elke speler ziet verder slechts een deel van het veld en heeft alleen de beschikking over enkele basis commando's zoals 'dash' (lopen), 'kick' (schoppen), 'turn' (draaien) en 'turn_neck' (draaien van de nek). De spelers verliezen bij elke actie een gedeelte van hun stamina en dit herstelt zich weer als de speler tijdens een aantal cykels geen actie uitvoert. Deze stamina heeft invloed op de loopsnelheid. Tenslotte is het ook mogelijk om te communiceren met andere spelers m.b.v. het 'say' commando. De boodschappen kunnen echter maar een beperkte lengte hebben en er is geen zekerheid of ze aankomen. Bovendien is het ook niet bekend van wie de boodschap afkomstig is. Er moet dus gebruik gemaakt worden van bepaalde communicatie protocollen om deze informatie te verschaffen. Een multi-agent systeem kan gezien worden als een groep van autonome agenten die samen werken om een gemeenschappelijk doel te bereiken. Binnen het robot voetbal is dit doel het winnen van een wedstrijd. Zo'n doel kan weer opgesplitst worden in verschillende subdoelen zoals het scoren van een doelpunt of het voorkomen van een tegentreffer. Op dezelfde manier kan het gedrag van een agent worden opgedeeld in verschillende abstractie niveaus. De architectuur van een agent bestaat dan ook uit meerdere lagen die elk een dergelijk abstractie niveau representeren. Het aantal lagen dat je hiervoor kiest heeft invloed op de complexiteit van het systeem: veel lagen betekent meestal een hoge complexiteit terwijl weinig lagen zorgen voor een beperktere functionaliteit. Het is op dit moment nog niet helemaal duidelijk hoeveel lagen wij willen gaan gebruiken voor onze spelers. Een mogelijke optie is een opdeling in drie lagen: - De onderste laag bevat de individuele basisacties van een speler zoals het onderscheppen van de bal, het schieten van de bal en het dribbelen met de bal. Bij het onderscheppen moet bijvoorbeeld rekening worden gehouden met de snelheid en de richting van de bal. Met deze informatie kan dan een richting en snelheid van de speler worden bepaald (rekening houdend met zijn huidige richting en snelheid) die nodig is om de bal te onderscheppen. Dergelijk gedrag kan geimplementeerd worden door gebruik te maken van analytische formules. Het is echter ook mogelijk om het gedrag te leren. Je kan bijvoorbeeld een neuraal netwerk gebruiken om de optimale parameters voor een dergelijke actie te bepalen. - De middelste laag maakt gebruik van de basisacties uit de onderste laag als onderdelen voor multi-agent gedrag op een hoger niveau. Een voorbeeld is 'pass evaluation': als een speler de bal heeft en de optie heeft om een medespeler aan te spelen dan moet hij kunnen inschatten of die medespeler de bal ook inderdaad goed zal kunnen ontvangen. Voor deze inschatting moet dus gebruik gemaakt worden van het onderscheppingsgedrag uit de onderste laag. Ook hier geldt dat je gebruik kan maken van analytische formules om het gewenste resultaat te krijgen of dat het gedrag geleerd kan worden. Voor dit laatste kan bv. een decision tree algoritme worden gebruikt dat een beslissing produceert gegeven een aantal attribuut-waarde paren die de huidige situatie beschrijven. - In de bovenste laag worden de acties uit de tweede laag weer gebruikt als onderdelen voor strategisch teamgedrag. Een voorbeeld hiervan is 'pass selection': als een speler de bal heeft moet hij beslissen naar welke speler hij de bal moet overspelen. Bovendien is het denkbaar dat overspelen niet de beste optie is en dat dribbelen of een schot op doel beter is. Het gedrag in deze laag kan geleerd worden m.b.v. reinforcement learning methoden hoewel die vaak duur zijn (vereisen veel leervoorbeelden). De beslissingsmodule kan echter ook hard worden gecodeerd als een complexe if-then-else constructie. Een moeilijk probleem binnen de robot voetbal simulatie is de synchronisatie met de server. Een speler kan namelijk elke 100 ms een actie naar de server sturen, maar ontvangt slechts elke 150 ms nieuwe visuele informatie. Aangezien je liever geen mogelijkheid tot het sturen van een actie wil overslaan moeten sommige acties die gekozen worden dus worden gebaseerd op oude visuele informatie. Dit vereist dat de speler in staat moet zijn om een schatting te maken van hoe de wereld er in de volgende cykel(s) uit zal zien. Deze schatting kan dan gebruikt worden om een optimale actie te kiezen. Dit proces is echter niet eenvoudig aangezien alle informatie die van de server afkomstig is ruis bevat. Verder weet een speler ook niet welke acties andere spelers in de toekomst uit zullen gaan voeren. Er is dus niet helemaal sprake van een Markov beslissingsproces waarin de agenten volledige informatie hebben over de toestandsovergangen van de wereld. Bovendien is het van belang dat je een synchronisatie methode ontwikkelt die de speler in staat stelt om de tijd binnen een cykel optimaal te benutten. Ons huidige team, UvA Trilearn 2001 genaamd, heeft hiervoor een geavanceerd algoritme waarin precies berekend wordt hoeveel tijd een speler nog heeft om een actie te kiezen voordat deze actie naar de server gestuurd moet worden. De actie die gestuurd wordt is bovendien voor zover mogelijk altijd gebaseerd op de meest recente informatie van de server. Voor ons team UvA Trilearn 2001 hebben we bovendien gekozen voor een multi-threaded architectuur voor elke speler. Dit zorgt ervoor dat de vertraging als gevolg van I/O (verwerken van informatie van de server en sturen van informatie naar de server) geminimaliseerd wordt. De huidige stand van zaken is dat we de multi-threaded architectuur van onze spelers hebben opgezet. We kunnen de informatie van de server goed verwerken en gebruiken om ons wereldmodel aan te passen. Bovendien zijn de spelers ook in staat om vooruit te redeneren over de situatie van de wereld op een later tijdstip. Verder is onze synchronisatie module ook voltooid. De resultaten hiervan zijn prima aangezien het aantal gestuurde acties per wedstrijd bijna optimaal is evenals de acties zelf, d.w.z. ze zijn voor zover mogelijk gebaseerd op de meest recente informatie. Wat ons lagenmodel betreft zijn we zo goed als klaar met de onderste laag. Onze spelers beschikken over een goede onderscheppingsactie en kunnen de bal nauwkeurig schieten naar een gewenste positie. Ons huidige team, ironisch 'De Meer 5' genoemd, heeft verder echter een hele eenvoudige beslissingsmodule voor het kiezen van een actie. Dit hebben we gedaan om de onderste laag eerst goed te kunnen testen. Toch bestaat De Meer 5 nu al uit ca. 14.000 regels C++ code. We hebben het laten spelen tegen een simpele versie van FC Portugal, de winnaar van het EK en WK van 2000, met een soortgelijke functionaliteit in de hogere lagen. Tegen dit team spelen we nu gemiddeld gelijk en dit betekent dat onze onderste laag nagenoeg even goed is. We zullen nu verder gaan met het implementeren van 'De Meer 4'. Dit betekent dat we de hogere lagen zullen gaan uitbreiden zodat we strategisch sterker worden. Ook zullen we ons bezig gaan houden met het implementeren van een coach die de spelers bepaalde adviezen kan geven gebaseerd op een analyse van het spel van de tegenstander.