Katholieke Hogeschool Sint-Lieven Departement Industrieel Ingenieur Opleiding Elektronica-ICT Afstudeerrichting informatie- en communicatietechnieken Gebroeders Desmetstraat 1, 9000 Gent
¨ Simulatie van gedistribueerde voetbal strategieen
Eindverhandeling ingediend tot het behalen van ¨ Wetenschappen: de graad van Master in Industriele Elektronica-ICT en aangeboden door: Tim Vermeulen
Promotor: dr. Katja Verbeeck Copromotoren: ing. Tony Wauters, ing. Koen Vangheluwe, Opdrachtgever: ing. lic. Filiep Vincent
Academiejaar 2009 - 2010
Hierbij geven de auteur(s) van dit eindwerk aan het bestuur van het departement industrieel ingenieur van KaHo Sint-Lieven de uitdrukkelijke toestemming om dit werk in bruikleen af te staan aan eender welke persoon, organisatie of firma, het ten dienste te stellen van de studenten en het geheel of gedeeltelijk te kopi¨eren.
Deze eindverhandeling was een examen; de tijdens de verdediging vastgestelde fouten werden niet gecorrigeerd. Het gebruik als referentie in publicaties is toegelaten na gunstig advies van de promotor van KaHo Sint-Lieven, vermeld op het titelblad.
Dankwoord Graag wil ik iedereen bedanken die heeft bijgedragen bij de totstandkoming van deze thesis. In het bijzonder wil ik mijn promotoren bedanken voor de hulp bij het oplossen van problemen, dr. Katja Verbeeck, ing. Tony Wauters en ing. Koen Vangheluwe. Ook wil ik ing. lic. Filiep Vincent van DSPValley bedanken, de opdrachtgever van deze thesis. Dank gaat ook uit naar het RoboCup.be team voor de tussentijdse evaluaties en het advies dat ik van hen mocht ontvangen. Ook wil ik iedereen bedanken die mijn thesis heeft nagelezen en gecontroleerd. Tijdens de verwezenlijking van mijn thesis heb ik vele dagen mogen doorbrengen in het lokaal van de vakgroep it. Mijn dank gaat dus ook uit naar hen voor de gezellige omgeving en alle hulp en advies bij grotere en kleinere problemen. Vermeulen Tim Januari 2010
iv
Abstract Robocup.be kadert in een internationaal project dat AI en robotica onderzoek wil stimuleren. Onder leiding van DSP Valley en in samenwerking met andere Hogescholen (Erasmushogeschool in Brussel en Lessius Hogeschool, campus De Nayer in Sint-Katelijne Waver) werkt onze school mee aan een Belgisch team van kleine, rijdende voetbalrobots om in de toekomst deel te nemen aan internationale wedstrijden. Naast een goed hardware ontwerp voor de robot is de software die deze moet besturen misschien nog belangrijker. Deze thesis omvat het bestuderen en evalueren van verscheidene strategie¨en die momenteel toegepast worden in de huidige succesvolle robotteams. Het uiteindelijke doel is om een simulatie tool aan te bieden waarin succesvolle voetbalstrategie¨en voor het Belgische team ontwikkeld kunnen worden. We ontwerpen een simulatieomgeving die tijdsrovende testen met echte robots kan vermijden en vooral het ontbreken van de hardware compenseert. In een eerste stap cre¨eren we een fysische simulatie omgeving gebruikmakend van een fysische engine om de realiteit zo goed mogelijk te benaderen. In een tweede stap koppelen we een multi-agenten systeem aan deze fysische omgeving om zo tot een simulator te komen waarin we intelligente multi-agent voetbalstrategie¨en kunnen ontwikkelen en testen. Gebruikmakend van de ontwikkelde simulatieomgeving bestuderen we nieuwe voetbalstrategie¨en. Eerder dan de populaire reactieve strategie¨en te ontwikkelen, leggen we de focus op co¨ordinatie en lokale intelligentie. Zo kan men overwegen om op de robot regels te implementeren die botsingen met andere spelers moeten voorkomen in plaats van dit gedrag centraal te regelen. Co¨ordinatie is dan weer nodig bij het geven en ontvangen van een pas. Trefwoorden: Robocup, agenten, simulatie
v
Inhoudsopgave 1
2
Inleiding
1
1.1
Situering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Onderdelen van de thesis . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.1
Bestuderen andere teams . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.2
Simulatie omgeving . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.3
Implementeren en cre¨eren van een strategie . . . . . . . . . . . . .
2
Achtergrond
4
2.1
Multi-agenten simulatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.1
Definitie van een agent . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.2
De omgeving . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.1.3
Eenvoudige regels resulteren in complex gedrag . . . . . . . . . . .
6
2.1.4
Hoe een multi-agenten systeem opbouwen? . . . . . . . . . . . . .
6
2.1.5
Voordelen van simulatie . . . . . . . . . . . . . . . . . . . . . . .
7
Studie ETDP andere teams . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.1
Plasma-Z (Thailand) eerste plaats 2008 [8] . . . . . . . . . . . . .
8
2.2.2
CMDragons (USA) tweede plaats 2008 [35] . . . . . . . . . . . . .
8
2.2.3
Skuba (Thailand) derde plaats 2008 [29] . . . . . . . . . . . . . . .
9
2.2.4
ZjuNLict (China) vierde plaats 2008 [34] . . . . . . . . . . . . . .
9
2.2.5
B-Smart (Duitsland) kwartfinales 2008[18] . . . . . . . . . . . . .
10
2.2.6
RoboDragons (Japan) kwartfinales 2008[3] . . . . . . . . . . . . .
11
2.2.7
Besluiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2
3
Opbouw simulatie omgeving
13
3.1
Multi-agenten omgeving . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.1.1
Keuze van de omgeving . . . . . . . . . . . . . . . . . . . . . . .
13
3.1.2
Configuratie van Repast . . . . . . . . . . . . . . . . . . . . . . .
15
3.1.3
GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
vi
3.2
3.3
3.4
3.5 4
17
3.2.1
Keuze van de omgeving . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.2
Configuratie van Phys2D [12] . . . . . . . . . . . . . . . . . . . .
17
Interface tussen Repast en Phys2D . . . . . . . . . . . . . . . . . . . . . .
21
3.3.1
WorldModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.3.2
RefereeBox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.3.3
RobotCommander . . . . . . . . . . . . . . . . . . . . . . . . . .
24
Algemene regels Robocup . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.4.1
Afmetingen van het veld . . . . . . . . . . . . . . . . . . . . . . .
24
3.4.2
Afmetingen van het doel . . . . . . . . . . . . . . . . . . . . . . .
24
3.4.3
De robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.4.4
Afmetingen van de bal . . . . . . . . . . . . . . . . . . . . . . . .
26
3.4.5
De RefereeBox . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Besluiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
Testen in de simulatie omgeving
28
4.1
Definitie van een toestand . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.1.1
Rollen en balbezit . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4.1.2
Bepalen van de toestand . . . . . . . . . . . . . . . . . . . . . . .
30
4.1.3
Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
4.1.4
Totale toestand versus gedeeltelijke toestand . . . . . . . . . . . .
32
De acties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.1
Van actie tot vaardigheid . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.2
Verplaatsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.2.3
Draaien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.2.4
Schieten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Testen van strategie¨en . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.3.1
Strategie 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.3.2
Strategie 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
4.3.3
De strategie wijzigen via de GUI . . . . . . . . . . . . . . . . . . .
40
Lokale intelligentie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.4.1
Vermijden van botsingen . . . . . . . . . . . . . . . . . . . . . . .
41
4.4.2
Vermijden om buiten te lopen met de bal . . . . . . . . . . . . . .
41
4.4.3
Afstand houden van de bal . . . . . . . . . . . . . . . . . . . . . .
42
Besluiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.2
4.3
4.4
4.5 5
Fysische omgeving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Besluiten
43
5.1
Resultaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
5.2
Uitbreidingen en verbeteringen . . . . . . . . . . . . . . . . . . . . . . . .
44
5.2.1
Overgang naar 3D . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.2.2
Uitbreiden van de toestand . . . . . . . . . . . . . . . . . . . . . .
44
5.2.3
Uitbreiden van de vaardigheden . . . . . . . . . . . . . . . . . . .
44
5.2.4
Toevoegen van lerende strategie¨en . . . . . . . . . . . . . . . . . .
44
5.2.5
Verbeteren van de vaardigheden . . . . . . . . . . . . . . . . . . .
45
5.2.6
Beter vermijden van botsingen . . . . . . . . . . . . . . . . . . . .
45
5.2.7
Toepassen van het volledige reglement voor de Small-Size League .
45
A UML
49
B Strategie voorbeeld
58
C Beschrijving van deze masterproef in de vorm van een wetenschappelijk artikel 62 D Poster
70
Lijst van figuren 1.1
Voorbeeld van enkele robots. . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.1
Boids simulatie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1
UML Class Diagram voor de structuur van de agenten en hun weergave in Repast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.2
Overzicht van de verschillende tabbladen van de GUI. . . . . . . . . . . . .
18
3.3
Voorbeeld venster van Phys2D. . . . . . . . . . . . . . . . . . . . . . . . .
19
3.4
UML Class Diagram voor de implementatie van Phys2D. . . . . . . . . . .
20
3.5
Voorstelling van een speler in Phys2D . . . . . . . . . . . . . . . . . . . .
20
3.6
UML Class Diagram voor de interfaces tussen Repast en Phys2D. . . . . .
22
3.7
Afmetingen voetbalveld . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.8
Afmetingen doel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.9
Afmetingen robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1
Bepalen van de beste hoek om naar een doel te schieten. . . . . . . . . . .
32
4.2
Voorstelling mogelijke basisvaardigheden . . . . . . . . . . . . . . . . . .
34
4.3
Wijzigen van de strategie via de gui . . . . . . . . . . . . . . . . . . . . .
41
A.1 UML Class Diagram voor de interfaces tussen Repast en Phys2D. . . . . .
50
A.2 UML Class Diagram voor de implementatie van Phys2D. . . . . . . . . . .
51
A.3 UML Class Diagram voor de structuur van de agenten en hun weergave in Repast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
A.4 Overzicht mogelijke basisvaardigheden . . . . . . . . . . . . . . . . . . .
53
A.5 Overzicht opbouw spelers en hun strategie . . . . . . . . . . . . . . . . . .
54
A.6 Overzicht opbouw verschillende voorstellingen van de toestand . . . . . . .
55
A.7 Sequentie Diagram dat de verschillende stappen bij het toepassen van een strategie weergeeft. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
A.8 Sequentie Diagram dat de stappen weergeeft bij het updaten van een NewTotalState. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
ix
Lijst van tabellen 4.1
De gebruikte toewijzing van verplaats-vaardigheden aan PlayerActions . . .
35
4.2
De gebruikte toewijzing van draai-vaardigheden aan PlayerActions . . . . .
37
4.3
De gebruikte toewijzing van schiet-vaardigheden aan PlayerActions . . . .
38
x
Hoofdstuk 1
Inleiding 1.1
Situering
RoboCup.be kadert in een internationaal project dat AI en robotica onderzoek wil stimuleren. Onder leiding van DSP Valley en in samenwerking met enkele andere onderwijs- en onderzoeksinstellingen (Erasmushogeschool in Brussel, Lessius Hogeschool, campus De Nayer in Sint-Katelijne Waver en Vrije Universiteit Brussel) werkt onze school mee aan het ontwerp van een Belgisch team van voetballende robots. Het Belgische team richt zich op de Small Size League, hierbij gaat het om een team van 5 kleine rijdende voetbal robots met een maximum hoogte van 15 cm zoals afgebeeld in Figuur 1.1.
Figuur 1.1: Voorbeeld van enkele robots. (Afbeelding overgenomen van http://small-size.in formatik.uni-bremen.
de)
De intentie van RoboCup.be is om op langere termijn met het Belgische team deel te nemen aan internationale RoboCup wedstrijden. In deze jaarlijkse voetbalwedstrijden voor robots demonstreren teams van verschillende landen hun kunnen. De vorige editie, in Juli 2009, werd gehouden in Graz, Oostenrijk. 21 teams deden mee en Skuba, een team van Thailand, bleek het beste te zijn. Een volledig overzicht van de resultaten is terug te vinden op de website van RoboCup 2009, www.robocup2009.org. 1
1 Inleiding
2
Het Belgische team is nog in volle ontwikkeling. Zowel het software ontwerp als het hardware ontwerp zit vol uitdagingen wat het geheel tot een boeiend project maakt. Terwijl andere hogescholen zich richten op de ontwikkeling van de hardware richt onze school zich, samen met de VUB, eerder op de software. Deze thesis zal zich concreet richten op een eerste ontwerp van een simulatie omgeving voor het cre¨eren en testen van intelligente voetbal strategie¨en voor de robots.
1.2 1.2.1
Onderdelen van de thesis Bestuderen andere teams
In een eerste fase worden andere teams bestudeerd en ge¨evalueerd. Elk team dat wil deelnemen aan internationale wedstrijden moet een Team Description Paper (TDP) uitbrengen. In deze TDP wordt zowel de hardware als de software van de robots beschreven. Elk team dat in de finale komt moet bovendien een Extended Team Description Paper uitbrengen, hierin worden de robots nog uitgebreider beschreven. Het bestuderen van deze ETDP is dus een ideale manier om kennis te maken met de huidige werking van de robots.
1.2.2
Simulatie omgeving
Vervolgens wordt een simulatie omgeving ontwikkeld bestaande uit een multi-agenten omgeving die een gesimuleerde realiteit aanstuurt. Deze omgeving moet zo ontwikkeld worden dat ze gemakkelijk uitgebreid en aangepast kan worden in latere fasen van het RoboCup.be project. Dit omdat zal overgegaan worden van simulatie naar aansturen van echte robots en omdat de mogelijkheden van het systeem steeds uitgebreid zullen worden. Bovendien moet het eenvoudig zijn om nieuwe strategie¨en te implementeren en te testen. Eerst zal gezocht moeten worden naar een geschikt raamwerk voor multi-agenten simulatie. Er worden verschillende raamwerken bestudeerd en ge¨evalueerd. Voor de evaluatie maken we gebruik van verschillende criteria. De voorwaarde om over een continue ruimte te beschikken is uiteraard bindend. Vervolgens verdienen omgevingen die ook 3 dimensies ondersteunen een voorkeur om een latere uitbreiding naar een 3-dimensionale weergave van de werkelijkheid te vergemakkelijken. Bovendien moet ook een geschikte fysische omgeving gezocht worden. Deze zal de fysische wetten simuleren waartegen uiteraard geen overtredingen mogen gemaakt worden. De omgeving simuleert de plaats van de spelers en de bal op het veld alsook hun snelheid, versnelling, rotatie en rotatie versnelling.
1.2.3
Implementeren en cre¨eren van een strategie
Het gebruik van de omgeving zal dan gedemonstreerd worden door het ontwikkelen van een eigen strategie. Een strategie van een speler bestaat uit verschillende delen. Eerst moet
1 Inleiding
3
op een slimme manier de toestand van de speler beschreven worden. Vervolgens moet een set van acties gecre¨eerd worden die de robot zullen besturen. En tot slot is dan een policy nodig die de juiste actie zal selecteren in de huidige toestand. Bij het defini¨eren van het gedrag van de agenten zal ook de overweging gemaakt moeten worden of het nuttig zou zijn om bepaalde delen van het gedrag op de robot zelf te implementeren. Op deze manier kunnen vertragingen vermeden worden en kan dus sneller gereageerd worden. Het nadeel hiervan is dan weer dat op de robot minder rekenkracht beschikbaar is.
Hoofdstuk 2
Achtergrond 2.1
Multi-agenten simulatie
Multi-agenten simulatie is een vrij recente werkwijze waarbij een systeem wordt gemodelleerd als een systeem van interagerende software agenten die samenwerken en co¨ordineren om hun doel te bereiken. Multi-agenten simulatie wordt bijvoorbeeld gebruikt voor het simuleren van een aandelenbeurs [23], maar ook het bestuderen van de verspreiding van een virus [11] en het boarden van vliegtuigen [4] zijn nuttige toepassingen. In deze thesis wordt het gebruikt voor het simuleren en aansturen van voetbal robots. De bespreking hieronder is gebaseerd op Tutorial on agent-based modeling and simulation part ” 2” [7] en het boek An introduction to MultiAgent Systems” [33] van Michael Wooldridge. ”
2.1.1
Definitie van een agent
Er bestaan veel verschillende definities voor een agent. Er bestaan heel algemene definities die elke onafhankelijke component als een agent beschouwen, waarbij zowel software als personen als agenten beschouwd kunnen worden. Meestal echter, is de mogelijkheid om autonoom beslissingen te kunnen nemen een belangrijke voorwaarde. Deze beslissingen kunnen dan genomen worden op basis van simpele reactieve regels of op basis van complexere zelflerende structuren. Agenten zijn dus actieve componenten. Er wordt aan een agent niet gevraagd om een bepaalde actie te ondernemen, integendeel, de agent heeft zelf een bepaald gedrag. De agent bepaalt dus zelf welke actie hij zal ondernemen op basis van zijn gedefinieerde gedrag. Volgende eigenschappen zijn in meer of mindere mate van toepassing op de agent. • Een agent moet identificeerbaar en aflijnbaar zijn De agent is een geheel van eigenschappen en regels. Men moet duidelijk kunnen stellen of een bepaalde regel of eigenschap tot de agent behoort of niet.
4
2 Achtergrond
5
• Een agent leeft in een omgeving De agent interageert met de wereld en de andere agenten in deze wereld. Zijn beslissingen kunnen afhangen van de toestand van de omgeving en de andere agenten in deze omgeving. Hiertoe bestaat een protocol om te communiceren met de omgeving. • Een agent is doelgericht Dit doel kan zowel het maximaliseren van een bepaalde waarde zijn als het realiseren van een bepaalde handeling. Op die manier kan het resultaat van de beslissingen van een agent ge¨evalueerd worden. • Een agent is autonoom Een agent heeft een bepaald gedrag en is in staat zelf handelingen te stellen naar dit gedrag. Het is dus de agent die de beslissingen neemt en de acties uitvoert. Het verschil met een gewoon software object is hierbij dat een object enkel uitvoert, de beslissingen worden elders genomen. • Een agent kan leren Een agent kan op basis van ervaringen zijn gedrag aanpassen. Een agent kan dus beschikken over een gedrag om zijn gedrag aan te passen.
2.1.2
De omgeving
De agent leeft in een bepaalde omgeving. Deze omgeving heeft verschillende eigenschappen. Michael Wooldridge[33] verwijst naar het werk van Russell en Norvig[26] om onderscheid te maken op basis van volgende eigenschappen. • toegankelijk of ontoegankelijk Een omgeving is toegankelijk indien de agent een volledig, nauwkeurig en up-to-date beeld krijgt van de omgeving. De meeste re¨ele omgevingen dienen dus als niet toegankelijk beschouwd te worden. • deterministisch of niet-deterministisch Een omgeving is deterministisch als een bepaalde actie steeds hetzelfde effect zal hebben op de omgeving. Men kan dus op voorhand de nieuwe toestand van de omgeving bepalen bij het kiezen van een bepaalde actie. • statisch of dynamisch Een omgeving kan als statisch beschouwd worden als de enige wijzigingen van de omgeving veroorzaakt worden door de agent zelf. Als er andere, externe factoren zijn die de wereld be¨ınvloeden is deze dus dynamisch. • discreet of continue Een omgeving wordt als discreet gezien als er slechts een vast, eindig aantal acties ondernomen kan worden. In het andere geval is de omgeving continue.
2 Achtergrond
6
Deze eigenschappen hebben uiteraard een grote invloed op de mogelijkheden bij het bepalen van het gedrag van een agent. Zo zal in een omgeving die ontoegankelijk, niet-deterministisch, dynamisch en continue is het gedrag van een agent een stuk ingewikkelder zijn. De agenten omgeving die we zelf gaan simuleren is deels toegankelijk voor de agent, niet-deterministisch, dynamisch en continue. Dit komt voornamelijk omdat we in een multi-agenten omgeving werken, waarbij de agenten de omgeving steeds voor elkaar wijzigen.
2.1.3
Eenvoudige regels resulteren in complex gedrag
Men kan voor elke agent een kleine set eenvoudige regels defini¨eren. Deze kunnen eventueel zelf gebaseerd zijn op slechts een gedeeltelijk beeld van de wereld. Toch kan een complex gedrag gemodelleerd worden. Dit wordt onder andere gebruikt bij het defini¨eren van zwerm gedrag, het gedrag van een zwerm vogels of een kolonie mieren. Als voorbeeld wordt in Figuur 2.1 het gedrag voorgesteld dat ontstaat door het boids algoritme [24]. Dit gedrag defini¨eren in een centraal systeem zou een heel complexe zaak zijn. Door met agenten te werken kan dit gerealiseerd worden met vrij eenvoudige regels.
(a) De start situatie
(b) Het zwermgedrag
Figuur 2.1: Boids simulatie. (Afbeeldingen overgenomen uit Tutorial on Agent-based Modeling and Simulation Part 2 [7])
Op gelijkaardige wijze kan het gedrag van autonome robots gedefinieerd worden opdat zij co¨ordineren en samenwerken om hun doel te bereiken.
2.1.4
Hoe een multi-agenten systeem opbouwen?
De aanpak die hier gedefinieerd wordt is gebaseerd op deze voorgesteld in Tutorial on ” agent-based modeling and simulation part2” [7]. We overlopen volgende stappen.
2 Achtergrond
7
1. Zoeken naar agenten Er wordt gezocht wat de verschillende agenten zijn, en wat niet. Vervolgens wordt voor elke agent het gewenste gedrag bepaald. 2. Defini¨eren van de omgeving Er wordt afgelijnd wat tot de omgeving behoort en wat niet. Men bepaalt welke gegevens relevant zijn en hoe ze gemodelleerd worden. 3. Beeld van de wereld Hoe krijgt een agent een beeld van de wereld? Wat kan de agent zien? Hoe communiceert de agent met de wereld en hoe kan hij zelf de wereld be¨ınvloeden. 4. Communicatie met andere agenten Hoe communiceren agenten met elkaar? gebruikt?
Welke protocollen worden hiervoor
5. Implementatie Tot slot wordt dit model dan ge¨ımplementeerd.
2.1.5
Voordelen van simulatie
Simulatie, virtueel testen, heeft verschillende voordelen ten opzichte van testen in de realiteit. We geven enkele voordelen die relevant zijn voor het simuleren van robots. • Bij simulatie moet geen hardware in gereedheid worden gebracht, waardoor de hiermee gepaard gaande vertragingen worden vermeden. • Bij simulatie worden hardware kosten vermeden. • Er kan getest worden met grote hoeveelheden die in werkelijkheid niet bestaan of niet gebruikt kunnen worden. • Er kan zelfs getest worden zonder dat de hardware reeds bestaat. • Experimenten kunnen versneld gesimuleerd worden waardoor er sneller resultaten zijn. • Er kunnen zonder probleem meerdere experimenten gelijktijdig lopen. • Bij simulatie kunnen geen ongewenste effecten de hardware beschadigen. • Er kan eenvoudig getest worden met verschillende parameters. • ...
2 Achtergrond
2.2
8
Studie ETDP andere teams
Om vertrouwd te raken met de gebruikelijke strategie¨en worden de Extended Team Description Papers van enkele belangrijke teams besproken. Elk jaar wordt een RoboCup wedstrijd georganiseerd waarop teams van over de hele wereld het tegen elkaar op nemen. Elk team dat deelneemt aan RoboCup wedstrijden moet een Team Description Paper indienen waarin ze de werking van hun robots beschrijven, zowel de hardware als de software. Team’s kunnen echter zelf bepalen hoeveel details ze vrijgeven. Daardoor krijg je meestal een globaal beeld van de software, maar belangrijke details worden meestal achterwege gelaten. In deze paragraaf wordt een samenvatting gegeven van het software gedeelte van de ETDP van enkele team’s die vorig jaar goed gepresteerd hebben.
2.2.1
Plasma-Z (Thailand) eerste plaats 2008 [8]
De strategie van hun spelers bestaat uit 7 lagen: • Manager: deze laag bepaalt op basis van de score, het bal bezit, de opstelling van tegenstanders en signalen van de scheidsrechter de ’play’ die zal gebruikt worden. • Play: deze laag bepaalt de gebruikte strategie en de opstelling van de spelers. Ze kent ook een bepaalde ’Group’ toe aan elke speler. • Group: Vb.: aanvaller, verdediger, ... • Skill: Een basis handeling die de speler kan uitvoeren. Vb.: Beweeg naar een punt, beweeg naar de bal, schiet, dribbel met de bal. De Skill bepaalt path, dribbling en kicking commando’s. Zo zal het pad van een speler die naar een bepaald punt moet anders zijn als hij met de bal dribbelt. • Trajectory: Op basis van de Skill wordt een pad gemaakt. • Control: Het Trajectory wordt omgezet naar specifieke commando’s voor de robot zodat op de robot zelf weinig rekenwerk moet gebeuren. Voor de simulatie maken ze gebruik van een .NET framework en de Open Dynamic Engine (ODE) [27]. Voor het plannen van de paden maken ze gebruik van een systeem gebaseerd op de Force Field aanpak zoals beschreven in hun ETDP.
2.2.2
CMDragons (USA) tweede plaats 2008 [35]
Hun software bestaat uit 3 delen, een server en 2 cli¨enten. De server verwerkt de beelden, verzorgt de communicatie met de robots en staat in verbinding met de 2 cli¨enten. De eerste cli¨ent is het voetbal programma dat het gedrag van de spelers bepaalt. Een tweede cli¨ent visualiseert de spelers en de bal op het veld.
2 Achtergrond
9
Voor de simulatie maken ze gebruik van NVIDIA’s PhysX engine die de rol van server op zich kan nemen. Deze bouwt intern echter een gesimuleerd wereld model op. Er wordt een uitgebreide 3D simulatie gedaan van de robot en zijn dribbel mechanisme om het dribbelen en bewegen met de bal uitgebreid te kunnen simuleren. In de beschrijving van hun strategie vernoemen ze 3 facetten: evaluatie van de toestand van de wereld en daaruit een speltechniek selecteren, vaardigheden en technieken, navigatie. In hun strategie maken ze ook een opsplitsing tussen actieve en ondersteunende rollen waarbij ze meer rekentijd geven aan actieve rollen. Ze geven een bespreking van de verschillende afwegingen die ze maken bij het schieten. De hoek die moet berekend worden, of ze n`u moeten schieten of beter wachten, direct schieten of eerst controleren en dan schieten, ... Voor het plannen van het te volgen pad maken ze gebruik van een op RRT [5] gebaseerd systeem met facetten van RRT-Connect [16] en Bidirectional Multi-Bridge ERRT [5].
2.2.3
Skuba (Thailand) derde plaats 2008 [29]
De strategie van deze ploeg is gebaseerd op Cornell Big Red 2002 1 en bestaat uit een aantal stappen: • Een manager bepaalt eerst een groep van ’Plays’ om te gebruiken, dit is afhankelijk van het toernooi dat gespeeld zal worden. Een aantal voorbeelden van Plays zijn: OffensePlay, DefensePlay, FreeKickUsPlay. • Elke Play kent een rol toe aan een speler met een bepaalde positie. Een aantal voorbeelden van rollen: ForwardRole, GoalieRole. Een aantal voorbeelden van posities: Blocker, Defender, Aggressor, Creator. • Om een bepaalde rol uit te voeren beschikt de speler dan over verschillende skills. Enkele voorbeelden van skills: ShootingSkill, GetBallSkill. • De skills zullen dan een bestemming bepalen. Op basis van deze bestemming en het WorldModel zal een pad bepaald worden. Hiervoor maken ze gebruik van Real-Time Randomized Path Planning for Robot Navigation dat op zijn beurt gebaseerd is op RRT [5]. Voor de simulatie maken ze ook gebruik van een simulatie omgeving gebaseerd op ODE [27].
2.2.4
ZjuNLict (China) vierde plaats 2008 [34]
Dit team meet de vertraging ontstaan door het versturen en verwerken van de camerabeelden. Op basis daarvan worden dan voorspellingen gedaan over de werkelijke 1 Cornell Big Red is de algemene naam van de sport teams van Cornell University, http://www. cornellbigred.com
2 Achtergrond
10
huidige positie van objecten. Ze voorspellen onder andere het traject van een vliegende bal zodat ze weten waar deze zal landen. Voor het bepalen van een pad maken ze gebruik van het A* algoritme [19]. Ze houden rekening met vertragingen bij het doorsturen van commando’s. Bij het doorsturen van een snelheidscommando wordt namelijk niet direct die gewenste snelheid aangenomen. Dit verschil proberen ze te compenseren met een neuraal netwerk. Ze gebruiken enkele fucties die de beste plaats bepalen om een assist te krijgen, de beste plaats om naar het doel te schieten en de beste plaats om een pas te ontvangen.
2.2.5
B-Smart (Duitsland) kwartfinales 2008[18]
Hun software applicatie is verdeeld in drie module groepen. De pre-behavior modules verzamelen algemene informatie aan de hand van het model van de wereld. Hier wordt onder andere de opstelling bepaald. Ook vorig gekozen gedrag wordt hier ge¨evalueerd. De behavior modules bepalen een gewenste verplaatsing voor elke robot. Om hun gedrag te beschrijven maken ze gebruik van XABSL [25]. De post-behavior modules bepalen dan bewegingsvectoren uit de gegevens bepaald in de vorige stap. Hierbij maken ze gebruik van path-planning met detectie van botsingen en vermijden van obstakels. Rollen Ze defini¨eren drie basisrollen: keeper, verdediger en aanvaller. Aanvaller verdelen ze opnieuw in twee subrollen: aanvaller met bal en aanvaller zonder bal. Deze kunnen elk enkele taken uitvoeren. • Keeper – schiet de bal weg – verklein de hoek om te scoren, zonder verdedigers – verklein de hoek om te scoren, met verdedigers • Verdediger Deze wordt een aanvaller als hij de bal krijgt – de bal proberen afnemen van een robot – standaard doel verdedigen – verdedigen op spelers waarnaar de tegenstander met bal eventueel kan passen
2 Achtergrond
11
• Aanvaller zonder bal – vrijlopen • Aanvaller met bal – naar het doel schieten – naar een teamgenoot passen die meer kans heeft om te scoren – door de lucht naar een teamgenoot passen die meer kans heeft om te scoren – in de richting van een teamgenoot schieten – in de richting van het doel van de tegenstander schieten Path-planning Ze gebruiken een algoritme gebaseerd op ”Real-Time Randomized Path Planning for Robot Navigation” [5]. Dit combineren ze met een algoritme om botsingen te vermijden, Dynamic Safety Search (DSS). B-Smart Simulator Voor de simulatie wordt gebruikgemaakt van een op ODE physics engine [27] en OpenGL gebaseerd systeem. Voor een speler wordt de term ’agent’ gebruikt, wat multi-agenten simulatie suggereert, maar daar wordt niet dieper op ingegaan. Om wedstrijden na te kunnen spelen hebben ze een tool ontwikkeld die het model van de wereld voortdurend bijhoudt en opslaat.
2.2.6
RoboDragons (Japan) kwartfinales 2008[3]
Dit team maakt gedeeltelijk gebruik van de GUI van CMDragons. Dit komt omdat ze vroeger nog samen hebben gewerkt. Er wordt ook gebruik gemaakt van rollen en vaardigheden. De definitie is hier wel verschillend van wat doorgaans gebruikt wordt. Enkele voorbeelden van vaardigheden: keeper, verdediger, verdediging op speler, aanvaller.
2.2.7
Besluiten
Strategie De meeste teams hebben een structuur waarbij ze een algemene strategie bepalen. Op basis daarvan bepalen ze dan welke rollen aan de robots toegedeeld moeten worden. Op basis van de huidige plaats van de robots op het veld wordt meestal een bepaalde rol toegedeeld aan een bepaalde robot. De keeper wordt vast gekozen. Elke robot beschikt over een set vaardigheden. De rol is dan bepalend voor welke vaardigheid er wordt gebruikt.
2 Achtergrond
12
Path-planning Het verplaatsen van de robots gebeurt dikwijls door een bestemming en een rotatie op te geven, samen met enkele andere parameters zoals bijvoorbeeld een maximum snelheid tijdens het dribbelen. Meestal wordt gebruik gemaakt van Real-Time Randomized Path Planning for Robot ” Navigation” [5] om een veilig pad naar de bestemming te berekenen. Dit wordt gecombineerd met detectie van botsingen en vermijden van obstakels. Fysische simulatie Voor de simulatie wordt gebruik gemaakt van een fysische simulatie omgeving. Een veel gebruikte omgeving is ODE [27]. Deze zal de fysische eigenschappen van de robots simuleren, zoals locatie, snelheid en botsingen.
Hoofdstuk 3
Opbouw simulatie omgeving In dit hoofdstuk worden de belangrijke delen van de simulatie omgeving en hoe deze met elkaar communiceren besproken. Een eerste paragraaf behandelt het multi-agenten systeem en de agenten hierin. De tweede paragraaf behandelt de fysische omgeving en hoe het veld en de voetballers worden gesimuleerd. Voor beide delen wordt de keuze voor een bepaalde omgeving verantwoord. Vervolgens bespreken we de interface die deze twee omgevingen koppelt. Hiermee kunnen agenten de gegevens van hun robot en die van andere robots opvragen en commando’s terugsturen. In een laatste paragraaf, tot slot, bespreken we enkele belangrijke algemene regels gedefinieerd voor de Small Size League [31]. Met deze regels moet uiteraard rekening gehouden worden bij het implementeren van de simulatie omgeving en later het gedrag van de agenten.
3.1
Multi-agenten omgeving
Door te kiezen voor een multi-agenten aanpak kan een complexe strategie ge¨ımplementeerd worden met vrij eenvoudige regels voor elke agent. Door de individuele regels te volgen werken de agenten samen om de globale doelstellingen te bereiken. Men kan ervoor kiezen om zelf een multi-agenten omgeving te schrijven, maar er is ook een uitgebreid aanbod aan open-source omgevingen beschikbaar. Het komt er dan op neer een omgeving te kiezen die aan de eisen van dit project voldoet.
3.1.1
Keuze van de omgeving
Eerst wordt een overzicht gegeven van enkele interessante multi-agenten omgevingen samen met enkele van hun eigenschappen. Vervolgens wordt de keuze voor Repast verantwoord.
13
3 Opbouw simulatie omgeving
14
Overzicht enkele interessante multi-agenten systemen In deze paragraaf bespreken we enkele veel gebruikte multi-agenten omgevingen die geschikt zouden kunnen zijn. Voor de selectie van relevante omgevingen werd gebruik gemaakt van de Wikipedia pagina ”Comparison of agent-based modeling software” [9] en de lijst van andere simulators op de website van Mason [20]. • MASON(Multi-Agent Simulator Of Neighborhoods) [20] MASON is volledig in Java ge¨ımplementeerd en is dus platform onafhankelijk. Het ondersteunt zowel 2D als 3D werelden en ondersteunt continue co¨ordinaten. • Swarm [13] Swarm is origineel enkel in C ontwikkeld, maar via Java Swarm zijn de C-libraries nu ook beschikbaar in Java. Het is enkel beschikbaar voor Unix-gebaseerde besturingssystemen, maar ook in Windows te gebruiken met behulp van Cygwin [14]. De naam verwijst naar het idee waarop Swarm gebaseerd is, namelijk dat van groepen van dieren die samenwerken. • RePast(Recursive Porous Agent Simulation Toolkit) [17] Deze op Swarm gebaseerde omgeving bestaat zowel in Java als in C#. De Java versie is platform onafhankelijk en de C# versie bestaat voor de meeste hedendaagse besturingssystemen. De omgeving ondersteunt zowel 2D als 3D en zowel continue als discrete co¨ordinaten. • Ascape [22] Deze omgeving is platform onafhankelijk en geschreven in Java. Ze biedt enkel een 2D weergave van de wereld met discrete co¨ordinaten. • NetLogo [32] Deze omgeving is platform onafhankelijk en het gedrag van agenten wordt gedefinieerd in hun eigen taal, NetLogo. De omgeving ondersteunt zowel 2D als 3D en continue co¨ordinaten. Keuze voor Repast Voor de keuze uit de lijst uit vorige paragraaf hebben we dan volgende criteria gebruikt: • Mogelijkheid tot gebruik van continue waarden voor co¨ordinaten • Mogelijkheid tot een 3-dimensionale voorstelling van de positie van de agenten. Dit omdat de bal ook omhoog geschoten kan worden over andere robots. • Mogelijkheid om te koppelen aan een fysische omgeving. Doordat NetLogo geschreven wordt in een eigen taal zal het moeilijker zijn om dit te koppelen aan de fysische omgeving. Ascape voldoet niet aan de voorwaarde omtrent de
3 Opbouw simulatie omgeving
15
continue co¨ordinaten. Bij de keuze tussen Swarm en Repast werd voor Repast gekozen omdat deze recenter is en meer programmeer talen en besturingssystemen ondersteund. Er zijn vervolgens enkele voorbeelden ge¨ımplementeerd in beide overblijvende omgevingen om de mogelijkheden te bekijken en te vergelijken. Ook intern zijn de omgevingen vrij gelijkaardig, Mason vermeldt zelf op hun website dat hun software veel weg heeft van Repast en andere multi-agenten simulatoren. Bij het implementeren van de voorbeelden bleek Repast toch iets gemakkelijker te zijn om met te starten. Doordat ze op andere gebieden weinig doorwegende verschillen vertonen heeft deze factor de doorslag gegeven.
3.1.2
Configuratie van Repast
De spelers en de bal worden in Repast voorgesteld als agenten. Elke agent heeft een bepaalde locatie en vorm. Repast ondersteunt 3-dimensionale voorstellingen, maar voor de eenvoud beperken we ons voorlopig tot 2 dimensies. In Figuur 3.1 wordt de opbouw en voorstelling van de agenten in Repast schematisch weergegeven.
Figuur 3.1: UML Class Diagram voor de structuur van de agenten en hun weergave in Repast.
3 Opbouw simulatie omgeving
16
Definitie van de bal De bal wordt voorgesteld als een cirkelvormig voorwerp. In overeenstemming met de offici¨ele regels geven we de bal een oranje kleur. Definitie van de spelers De spelers worden onderverdeeld in 2 teams. Een speler wordt voorgesteld door een afbeelding die afhankelijk is van het team. Team 1 krijgt een rode kleur en team 2 een blauwe. Op die manier kunnen de teams gemakkelijk visueel uit elkaar gehouden worden. In de praktijk zal elke speler echter een verschillende afbeelding moeten krijgen in overeenstemming met de bovenkant van de robots. Op de bovenkant van elke robot staan een aantal bollen in verschillende kleuren. Deze zijn zo ontworpen opdat elke robot uniek kan ge¨ıdentificeerd worden en opdat eenvoudig de rotatie van de robot op het veld bepaald kan worden. Voorstelling van het veld Om de veldlijnen weer te geven in Repast cre¨eren we een agent met als afbeelding de lijnen. Dit is een mogelijke oplossing. Een andere mogelijkheid zou zijn door gebruik te maken van de GIS mogelijkheden ingebouwd in Repast [21]. Deze laatste mogelijkheid zou beter overeenkomen met de theorie van multi-agenten simulatie, maar is minder eenvoudig te implementeren.
3.1.3
GUI
In de gekozen multi-agenten omgeving, Repast, beschikt de gebruiker over de mogelijkheid om een eigen panel toe te voegen. Op deze manier kan men het wijzigen van instellingen mogelijk maken of bepaalde extra gegevens voorstellen. Door op dit paneel met verschillende tabbladen te werken kan een grote hoeveelheid instellingen en gegevens voorgesteld worden. Een eerste tab bevat de instellingen in verband met de snelheid en versnelling van de spelers. Hierop wordt dieper ingegaan in paragraaf 3.2.2. Een tweede tab geeft de signalen verzonden door de RefereeBox (zie paragraaf 3.3.2) weer. Hier wordt onder andere de score getoond. Een derde tab stelt de gebruiker in staat om de gemiddelde snelheid van een speler te meten over een bepaalde periode. Dit kan gebruikt worden om de snelheidseigenschappen van de spelers aan te passen aan de werkelijke eigenschappen (zie paragraaf 3.2.2). Op een vierde tabblad kan men dan de strategie van de spelers bekijken. Elke strategie heeft nog een eigen tabblad. In dat tabblad wordt de toestand van elke speler weergegeven en welke actie hij daardoor gekozen heeft. Op die manier kunnen fouten in de strategie opgespoord worden. Als men een nieuwe strategie toevoegt kan men ook een nieuw tabblad
3 Opbouw simulatie omgeving
17
aanmaken om deze strategie te bewerken. In paragraaf 4.3.3 wordt dieper in gegaan op het wijzigen van de strategie via de gui. De verschillende tabbladen zijn afgebeeld in Figuur 3.2.
3.2
Fysische omgeving
De software testen op de echte hardware brengt allerlei ongemakken met zich mee. Zo moet men steeds over voldoende werkende robotjes beschikken en men moet deze fysiek ter beschikking hebben. In het echt kan men niet versneld spelen en een volledige match spelen vereist minstens 10 robotjes. Omwille van deze redenen blijkt dus de nood aan goede simulatie software. De simulator zal de ontwikkelaar van de spelstrategie de mogelijkheid bieden om verschillende testen eenvoudiger uit te voeren.
3.2.1
Keuze van de omgeving
Omdat er verschillende fysische parameters moeten gemodelleerd worden is het aangewezen een reeds bestaande fysische omgeving te gebruiken. Er bestaat een grote verscheidenheid aan omgevingen ge¨ımplementeerd in verschillende talen. Om de koppeling aan een multi-agenten systeem mogelijk te maken is er nood aan een goed gedocumenteerde omgeving die gemakkelijk aan te passen is. We moeten de omgeving immers aanpassen voor gebruik voor voetbal simulatie en ze moet tevens samenwerken met de multi-agenten software. In de zoektocht naar een geschikte fysische simulatie omgeving hebben we onder andere volgende tools beschouwd: Newton Game Dynamics [15], Ogre [28], Open Dynamics Engine [27] en Java variant JOODE [2], Bullet [10] en JBullet [1] en Phys2D [12]. Hierbij lijkt de laatste het meest geschikt vanwege de eenvoud en de aanpasbaarheid. Phys2D is een volledig in Java geschreven omgeving, gebaseerd op de GDC1 presentatie in 2006 van Erin Catto [6]. Phys2D simuleert enkele basis fysische eigenschappen zoals botsen en contact, wrijving, stapelen en verbindingen. En het simuleert ook de voornaamste dynamische eigenschappen zoals snelheid, draaisnelheid, massa, luchtweerstand, krachten en momenten. Phys2D ondersteunt ook verschillende vormen zoals rechthoeken, cirkels, lijnen en willekeurige veelhoeken. Dit alles is ge¨ımplementeerd zodat het eenvoudig kan aangepast worden voor specifieke doeleinden.
3.2.2
Configuratie van Phys2D [12]
Voor de afbeelding naar het scherm wordt een verschaling toegepast zodat 1 cm wordt voorgesteld als 1 schermpixel. De voorstelling in de fysische simulator wordt afgebeeld in een apart venster. Een voorbeeld is te zien in Figuur 3.3. 1 GDC:
Game Developers Conference, www.gdconf.com
3 Opbouw simulatie omgeving
Figuur 3.2: Overzicht van de verschillende tabbladen van de GUI.
18
3 Opbouw simulatie omgeving
19
Figuur 3.3: Voorbeeld venster van Phys2D.
Er komen 3 soorten objecten voor in de simulatie. De bal en de spelers zijn speciale afgeleide objecten, de doelen worden voorgesteld door een standaard body object met een veelhoek als vorm. Dit wordt ook voorgesteld in het UML diagram in Figuur 3.4. De bal De bal wordt voorgesteld als een cirkelvormig voorwerp met een bepaalde massa en wrijvingsweerstand en hij is onderhevig aan een bepaalde demping bij botsen. Voor de grafische weergave wordt een oranje kleur aan de bal gegeven in overeenstemming met de offici¨ele regels besproken in paragraaf 3.4.4. Als een speler op de juiste manier in aanraking komt met de bal, zal hij hiermee kunnen dribbelen. De juiste manier wordt gedefinieerd als de juiste plaats op de omtrek van de speler en met een beperkt verschil in snelheid. Als het verschil in snelheid te groot is zal de bal gewoon afkaatsen. Het schoppen van een speler wordt gesimuleerd door de bal een zekere beginsnelheid mee te geven. Deze beginsnelheid wordt bepaald door de speler met een in te stellen maximumwaarde.
3 Opbouw simulatie omgeving
20
Figuur 3.4: UML Class Diagram voor de implementatie van Phys2D.
Spelers Een speler wordt eveneens voorgesteld als een cirkelvormig voorwerp met een diameter in overeenstemming met de offici¨ele regels zoals besproken in paragraaf 3.4.3. Spelers hebben een kleur afhankelijk van het team waartoe ze behoren. Om de rotatie aan te geven wordt een lijn getekend vanuit het midden van de speler naar de zijkant in de rotatierichting zoals voorgesteld in Figuur 3.5. Spelers kunnen in alle richtingen over het veld bewegen en gelijktijdig en onafhankelijk hun rotatie wijzigen.
Figuur 3.5: Voorstelling van een speler in Phys2D
3 Opbouw simulatie omgeving
21
De doelen De doelen worden gesimuleerd door een veelhoek te tekenen die in breedte, diepte en dikte van de palen overeenkomt met de offici¨ele specificaties zoals besproken in paragraaf 3.4.2. Zowel de spelers als de bal kunnen niet door de zijkanten van het doel bewegen. De veldlijnen en de rand Tot slot zijn er nog de veldlijnen en de buitenste rand van het veld. Om te maken dat robots niet van het veld kunnen rijden en de bal niet buiten kan rollen is een rechthoek rond de buitenkant van het veld voorzien. Als objecten toch buiten het veld zouden bewegen botsen ze als het ware terug op deze rand. Daarnaast zijn er ook nog de gewone lijnen zoals de middencirkel en de omtrek van het speelveld. Deze lijnen worden gewoon op het veld getekend en vormen uiteraard geen hindernis voor de spelers of de bal. Configuratie van de parameters Zowel de bal als de spelers hebben verschillende parameters die moeten worden afgesteld om de werkelijke situatie zo goed mogelijk te benaderen. Momenteel kunnen we hiervoor nog niet terugvallen op vergelijkingen met de eigen hardware omdat deze nog ontbreekt. Om toch zo waarheidsgetrouw mogelijk te werken is het gedrag van de spelers vergeleken met dat van robots van andere teams. Hiervoor werd uitgegaan van filmpjes die andere teams op hun website publiceren. Sommige parameters zoals de maximale versnelling en de maximale snelheid zijn waarschijnlijk ook afhankelijk van het speelveld. Deze parameters zullen dus eerst gemeten moeten worden in de huidige situatie. Vervolgens moeten ze kunnen worden ingesteld dat het gedrag hiermee rekening houdt. Daarvoor hebben we verschillende tools ontwikkeld. Via de gui kan de snelheid van een speler bepaald worden over een bepaalde periode. Er kan ook een grafiek actief gemaakt worden die voor een bepaalde speler de snelheid en de versnelling weergeeft in functie van de tijd. Vervolgens kan men dan ook via de gui de maximale snelheid, de maximale versnelling, de maximale rotatie snelheid en de maximale rotatieversnelling van de spelers instellen.
3.3
Interface tussen Repast en Phys2D
Voor de communicatie tussen het multi-agenten systeem en de fysische simulator voorzien we een interface die bestaat uit 3 grote delen: het WorldModel, de RefereeBox en de RobotCommander. Hun functionaliteit en plaats in het geheel wordt ook schematisch voorgesteld in Figuur 3.6. Door de communicatie te beperken tot deze 3 interfaces en door het aantal methoden van deze 3 interfaces zo sterk mogelijk te beperken, maken we het eenvoudig om de overstap te maken van simulatie naar het aansturen van echte robots.
Figuur 3.6: UML Class Diagram voor de interfaces tussen Repast en Phys2D.
3 Opbouw simulatie omgeving 22
3 Opbouw simulatie omgeving
3.3.1
23
WorldModel
Het WorldModel zal het mogelijk maken voor de spelers om de toestand van het veld te weten te komen. Zowel van de bal als van alle spelers kan de plaats en de snelheid opgevraagd worden. Elke speler heeft ook een bepaalde rotatie en rotatiesnelheid. Er kan ook opgevraagd worden welke speler de bal bezit en dus ook welk team de bal bezit. Er kan ook een lijst opgevraagd worden van alle spelers of van de spelers behorende tot een bepaald team. We geven hieronder enkele voorbeelden: • NdPoint getBallLoca tion() vraag de positie van de bal op • List
getP layerIds() vraag een lijst van alle spelers op • NdPoint getPlayerVe locity(PlayerId play vraag de snelheid van een speler op
erId)
• boolean ownsBall(Pl ayerId playerId) vraag of een bepaalde speler al dan niet de bal heeft
3.3.2
RefereeBox
Elke speler zal een RefereeBoxListener aan de RefereeBox hangen om de beslissingen van de scheidsrechter te ontvangen. Deze omvatten het starten en stoppen van de match en het maken van een doelpunt. Op basis hiervan kunnen de spelers bepalen of ze bepaalde handelingen op dit moment mogen doen. De spelers kunnen ook het aantal gemaakte doelpunten bijhouden en hun strategie aanpassen aan de scores. • startGame(Team team ) het spel wordt gestart of herstart door het gespecificeerde team. Als geen team wordt meegegeven begint het spel voor beide teams. • ballOut(Team team) de bal is buiten door toedoen van het aangeduide team. • goalScored(Team tea m,PlayerId player) er is een doelpunt gemaakt door de aangeduide speler in het doel van het aangeduide team. Zoals beschreven in de offici¨ele regels [31] en zoals ook aangehaald in paragraaf 3.4.5 wordt de RefereeBox bestuurd door e´ e´ n van de scheidsrechters.
3 Opbouw simulatie omgeving
3.3.3
24
RobotCommander
De RobotCommander zal instaan voor het aansturen van de robots. De agenten in het multi-agenten systeem sturen commando’s naar de robots in de vorm van versnellingen en het commando om de bal te schieten. De agenten zullen de versnelling van de robot en de rotatieversnelling kunnen regelen. Indien de robot in het bezit is van de bal, zullen de agenten de bal kunnen laten wegschieten met een bepaalde snelheid. We beschikken dus over volgende mogelijkheden: • setPlayerAccelerati on(PlayerId playerId , NdPoint accelerati wijzig de versnelling van de speler naar deze waarde
on)
• setPlayerRotationAc celeration(PlayerId playerId,double ra) wijzig de rotatie versnelling van de speler naar deze waarde • kickBall(PlayerId p layerId) schiet de bal met de maximale snelheid (om naar het doel te schieten) • kickBall(PlayerId p layerId, float kickS peed) schiet de bal met een aangepaste snelheid (om een pas te geven)
3.4
Algemene regels Robocup
In de simulatie omgeving moet ook rekening gehouden worden met enkele algemene regels zoals vastgelegd in Laws of the F180 League 2009”[31]. Deze regels bevatten onder ” andere afmetingen, aantal robots, kleurcodes en normaal geldende voetbal regels. We geven hieronder een kort overzicht van enkele belangrijke regels en eigenschappen die belangrijk zijn voor de fysische eigenschappen van de gesimuleerde realiteit. Voor een volledig overzicht van alle regels verwijzen we naar de offici¨ele regels [31].
3.4.1
Afmetingen van het veld
Het speelveld heeft een breedte van 6050 millimeter en een hoogte van 4050 millimeter. Daarbuiten is nog een extra strook voorzien zodat het totale veld 7400 millimeter breed is en 5400 millimeter hoog. Al deze afmetingen en enkele extra lijnen worden ook voorgesteld in Figuur 3.7.
3.4.2
Afmetingen van het doel
Een doel heeft een breedte van 700 millimeter en een diepte van 200 millimeter. De zijkanten van het doel zijn 20 millimeter dik. Deze afmetingen worden ook voorgesteld in Figuur 3.7 en Figuur 3.8.
3 Opbouw simulatie omgeving
Figuur 3.7: Afmetingen voetbalveld (Afbeelding overgenomen uit Laws of the F180 League 2009”[31]) ”
Figuur 3.8: Afmetingen doel (Afbeelding overgenomen uit Laws of the F180 League 2009”[31]) ”
25
3 Opbouw simulatie omgeving
3.4.3
26
De robots
Een team bestaat uit 5 robots waarvan e´ e´ n een vaste rol heeft, de keeper. Omdat het om de Small Size League gaat gelden uiteraard beperkingen voor de afmetingen van de robots. Een robot moet binnen een cilinder passen met een diameter van 180 mm en een hoogte van 150 mm. Dit is ook visueel voorgesteld in Figuur 3.9.
Figuur 3.9: Afmetingen robot (Afbeelding overgenomen uit Laws of the F180 League 2009”[31]) ”
Een robot mag het bovenaanzicht van de bal ook nooit meer als 20% bedekken. Deze regel moet ervoor zorgen dat de bal steeds door een andere robot kan afgenomen worden.
3.4.4
Afmetingen van de bal
De bal is een standaard oranje golfbal met een massa van ongeveer 46g en een diameter van ongeveer 43mm.
3.4.5
De RefereeBox
De scheidsrechter geeft signalen aan de robots via de RefereeBox. Deze zal speciale commando’s naar de teams sturen die informatie geven over de beslissingen van de scheidsrechter. De commando’s die verstuurd worden hebben vooral te maken met het stoppen en starten van de match. Naast een reden wordt bij elk commando ook de score van beide teams meegegeven.
3.5
Besluiten
Het resultaat is dan een simulatie omgeving die zowel de fysische eigenschappen als het gedrag van de robots simuleert. Door het gebruik van abstracte interfaces tussen de fysische simulator en het multi-agenten systeem is plaats gemaakt voor de overstap naar het aansturen van echte robots.
3 Opbouw simulatie omgeving
27
De fysische omgeving heeft verschillende parameters die kunnen aangepast worden. Als de hardware beschikbaar komt kunnen deze parameters aangepast worden om de realiteit zo goed mogelijk te benaderen. Wat we dan nog nodig hebben voor een goed team is een goede strategie. In het volgende hoofdstuk gaan we daarom dieper in op de strategie die de spelers hanteren. We cre¨eren zelf een strategie om de mogelijkheden van de simulatieomgeving te demonstreren.
Hoofdstuk 4
Testen in de simulatie omgeving In dit hoofdstuk komt aan bod hoe je in de ontwikkelde simulatietool een team van spelers kan maken en de strategie van de spelers kan bepalen. De strategie van een speler wordt verdeeld in enkele belangrijke delen. Een toestand waarin de speler zich bevind, de acties die de speler kan uitvoeren en de policy die bepaalt welke actie moet uitgevoerd worden. Uitgaande van een oneindig aantal combinaties van positie, rotatie en snelheid van de spelers en daarbij nog eens positie en snelheid van de bal kan de toestandsbeschrijving van een speler al snel heel complex worden. We moeten dus in eerste instantie een manier vinden om de toestand van een speler op een beknoptere manier voor te stellen. In een eerste paragraaf bespreken we daarom hoe een toestand gedefinieerd wordt. We bespreken uit welke delen deze bestaat en wat wordt meegenomen als relevante informatie om een toestand te bepalen. In een volgende paragraaf bespreken we vervolgens de mogelijke acties die een speler kan ondernemen en de vaardigheden die daar bij horen. Een speler zal steeds een bepaalde actie selecteren in zijn huidige toestand. Met die actie komen dan 3 vaardigheden overeen: Bewegen, draaien en schieten. In een derde paragraaf bespreken we dan de policy die zal bepalen welke actie ondernomen moet worden in een bepaalde toestand. Deze policy wordt voorgesteld door een verzameling regels die een actie selecteren in een bepaalde toestand. Door deze regels te wijzigen kunnen we het gedrag van de speler wijzigen. Dit kan in onze simulatieomgeving zelf real-time gebeuren. Op deze manier kan men eenvoudig strategie¨en samenstellen, evalueren en wijzigen.
4.1
Definitie van een toestand
De strategie van een voetbalspeler bestaat erin om in de huidige toestand de juiste actie te kiezen. Om dit te realiseren is het onder andere belangrijk om op een juiste manier de toestand van een speler te defini¨eren. Men moet bovendien niet enkel de toestand van die ene speler, maar ook die van de omgeving beschouwen om een juiste actie te
28
4 Testen in de simulatie omgeving
29
kunnen bepalen. In deze paragraaf bespreken we de delen die we hebben opgenomen in de toestandsbeschrijving van een speler.
4.1.1
Rollen en balbezit
Rollen Door het invoeren van rollen pogen we een betere verdeling op het veld te bekomen, samen met de zekerheid dat bepaalde functies steeds uitgevoerd worden. Dit concept kan ook gebruikt worden om er voor te zorgen dat de keeper functie steeds vast aan een bepaalde speler gekoppeld is. E´en van de offici¨ele regels[31] is namelijk dat de scheidsrechter verwittigd moet worden indien van keeper gewisseld wordt. Hieronder volgt een lijst van de gebruikte rollen, deze lijst kan uiteraard uitgebreid worden. KEEPER DEFENDER MIDFIELDER STRIKER OUT_BALLGETTER OUT_PASSRECEIVER OUT_DEFENDER START De rollen worden toegewezen aan de spelers in de RoleFactory. Dit wordt gedaan op basis van het PlayerId en de GameState. De speler met id 0 wordt bij normaal spel steeds een middenvelder omdat deze speler het beste in staat is om alleen te spelen. Vervolgens worden andere ondersteunende rollen toegekend. Als het spel nog niet gestart is wordt de start rol toegekend aan alle spelers, ze bewegen dan naar hun startpositie. De rollen die beginnen met OUT_ worden toegekend als he t spel hervat moet worden nadat de scheidsrechter het heeft stilgelegd. Het bezit van de bal Het bezit van de bal is uiteraard ook belangrijk. De bal kan in het bezit zijn van de speler zelf, van e´ e´ n van zijn teamgenoten of van de tegenstander. De bal kan ook vrij zijn op het veld. Volgende mogelijkheden komen dus voor. PLAYER TEAM OPPONENT FREE Dit kan vrij eenvoudig bepaald worden. Het PlayerId van de balbezitter kan opgevraagd worden via het WorldModel, hieruit kan dan eenvoudig het team afgeleid worden.
4 Testen in de simulatie omgeving
4.1.2
30
Bepalen van de toestand
Om de toestand van een speler te bepalen kunnen we rekening houden met onderstaande gegevens. In een eerste toestandsbeschrijving houden we steeds rekening met alle delen van de toestand, een tweede ontwikkelde toestandsbeschrijving houdt enkel rekening met relevante delen van de toestandsbeschrijving. Meer hierover in paragraaf 4.1.4. De positie op het veld De co¨ordinaten van de spelers zijn re¨ele getallen. Als we deze co¨ordinaten meenemen in de toestandsbeschrijving, bekomen we een oneindig aantal toestanden. Dit is niet gewenst, we moeten dit dus op een slimme manier discreet maken. Men zou dit kunnen doen door de breedte en de hoogte van het veld in een aantal delen te verdelen. Op deze manier moet men echter nog steeds voor elke speler een paar co¨ordinaten bijhouden. Bovendien moet het veld in voldoende delen worden opgedeeld. In combinatie met meerdere spelers op het veld zal dit echter ook snel een groot aantal toestanden opleveren. Een betere oplossing, die in deze thesis voorgesteld wordt, bestaat erin indices toe te kennen aan de spelers op basis van hun afstand tot bepaalde relevante plaatsen zoals omschreven in paragraaf 4.1.3. Deze plaatsen kunnen zijn: het eigen doel, het doel van de tegenstander, de plaats van de bal, ... De combinatie van deze verschillende indices vormt dan samen een voorstelling van de positie van de speler op het veld. Deze nemen we ook op in de toestand van de speler. De mogelijkheid om naar het doel te schieten We nemen in de toestand van de speler ook een voorstelling op die een indruk moet geven van de mogelijkheid om naar het doel te schieten. Deze toestand is eenvoudig bij te houden, er zijn namelijk twee mogelijkheden: de speler kan naar het doel schieten of de speler kan niet naar het doel schieten. De mogelijkheid om naar een teamgenoot te passen Hiervoor houden we een index bij die weergeeft naar welke speler er kan gepast worden. Men sorteert de teamgenoten op afstand tot het doel van de tegenstander en zoekt vervolgens de speler het dichtste bij het doel waarnaar vrij gepast kan worden. De index van deze speler waarnaar gepast kan worden wordt ook mee opgenomen in de toestand van de speler.
4.1.3
Implementatie
We belichten enkele interessante mechanismen die momenteel in de tool opgenomen zijn.
4 Testen in de simulatie omgeving
31
Sorteren van de spelers voor het bepalen van de positie op het veld Voor het voorstellen van de positie van de spelers op het veld maken we geen gebruik van co¨ordinaten, maar van indices. Voor het toekennen van deze indices bepalen we eerst voor elke speler van een team de afstand tot een bepaald doelwit. Daarna sorteren we de spelers zodat de dichtste speler eerst komt. Vervolgens kunnen we dan eenvoudig indices toekennen aan de spelers, waarbij de eerste speler index 0 krijgt. Op die manier heeft elke speler een indruk waar hij zich bevindt ten opzichte van zijn team. Als de bal bijvoorbeeld vrij is en als een bepaalde speler een index 0 heeft voor de afstand tot de bal, dan weet deze speler dat hij zich het dichtste bij de bal bevindt van zijn team en dat hij naar de bal moet gaan. Heeft de speler een grotere index, dan weet de speler dat hij beter andere taken vervult. Op deze manier wordt eenvoudig het werk verdeeld en de spelers verspreiden zich beter over het veld. Spelers worden ook gesorteerd op afstand tot het doel van de tegenstander. Als een speler in het bezit is van de bal kan hij dan bepalen of er teamgenoten zijn die zich dichter bij het doel bevinden. Is dit niet het geval dan zal hij zich beter zelf naar het doel begeven. Bepalen van een hoek om naar een bepaald object te schieten Om te bepalen of een speler naar een bepaald object kan schieten wordt eerst de hoek (AngularDomain) van dat object bepaald. Vervolgens worden ook alle hoeken bepaald van spelers die de hoek gedeeltelijk of volledig kunnen blokkeren. Daarna moet de hoek van het doel object gesplitst worden. Alle blokkerende hoeken zullen dus verwijderd moeten worden uit de oorspronkelijke doelhoek. Dit is echter niet zo eenvoudig doordat er verschillende mogelijkheden zijn. • een hoek kan geen enkel deel overlappen met een andere hoek • een hoek kan een andere hoek volledig overlappen • een hoek kan volledig binnen een andere hoek vallen • een hoek kan een eerste deel van de andere hoek overlappen • een hoek kan het laatste deel van de andere hoek overlappen Met al deze mogelijkheden moet rekening gehouden worden. Bovendien moet men er ook rekening mee houden dat bijvoorbeeld een hoek van 20◦ groter is dan een hoek van 370◦ . Telkens men een hoek splitst bekomt men dus geen, e´ e´ n of twee deelhoeken. Door de doelhoek te splitsen met alle mogelijke blokkerende hoeken bekomt men dan een lijst van vrije deelhoeken. Als er inderdaad nog deelhoeken overblijven in deze lijst kan de speler naar het doelwit schieten. Als de speler bovendien wil bepalen naar welke hoek hij best zou mikken, dan moet de lijst van hoeken nog eens gesorteerd worden op grootte. Het midden van de grootste hoek zal dan gekozen worden als beste doelhoek.
4 Testen in de simulatie omgeving
32
Figuur 4.1: Bepalen van de beste hoek om naar een doel te schieten.
We verduidelijken dit concept aan de hand van het mikken naar een doel zoals weergegeven in Figuur 4.1. De rode speler mikt naar het rechter doel, voorgesteld door de witte lijn. De blauwe spelers zijn andere spelers die de hoek naar het doel kunnen blokkeren, deze spelers kunnen van beide teams zijn. De hoek van deze spelers wordt voorgesteld in het rood. Nadat we de door spelers geblokkeerde hoeken hebben weggelaten blijven er nog twee deelhoeken naar het doel over, aangeduid in het geel en donker groen. Van deze twee is de donkergroene de breedste en dus de beste, hier zal naar gemikt worden.
4.1.4
Totale toestand versus gedeeltelijke toestand
Men zou ervoor kunnen kiezen om steeds alle factoren die een toestand bepalen mee in rekening te brengen. Dit vergt echter een voortdurende update van al deze toestanden, wat extra rekenwerk en dus ook extra rekentijd met zich meebrengt. Men kan overwegen een toestand bij te houden die niet steeds alles in rekening brengt maar zich beperkt tot de op dit moment relevante informatie. Zo zal de afstand tot de bal niet relevant zijn indien de speler in het bezit is van de bal, de afstand is dan toch 0. Om de meerwaarde van een gedeeltelijke toestandsbeschrijving te testen, onderscheiden we volgende 2 definities van een toestand: • totale toestand De totale toestand maakt geen gebruik van rollen en bestaat uit 3 delen. Een eerste deel is de BallOwningState. Vervolgens bevat deze ook een DistanceState, deze vormt een combinatie van indexen voor de afstand tot het eigen doel, de afstand tot het doel van de tegenstander en de afstand tot de bal. En een derde deel is dan de CanKickState, deze vormt een combinatie van de mogelijkheid om naar het doel te schieten en de index van de speler dichtst bij het doel van de tegenstander waarnaar deze speler kan passen. • gedeeltelijke toestand Bij de keuze voor een gedeeltelijke toestand is het belangrijk om juist te bepalen wat
4 Testen in de simulatie omgeving
33
relevante informatie is, en wat niet. Wij hebben op basis van de rol en het balbezit enkele relevante deeltoestanden bepaald. Bij een update van de toestand worden dan enkel deze ge¨updatet en in rekening gebracht. Op die manier kan een zekere hoeveelheid rekenwerk vermeden worden.
4.2
De acties
Voor de keuze van de acties kan men inspiratie halen bij het gewone voetbal, maar er zijn toch nog grote verschillen. Dit zijn de acties die momenteel beschikbaar zijn. WAIT TO_START GO_TO_BALL TURN_TO_BALL GO_TO_OPP_GOAL KEEP DEFEND_ON_GOAL DEFEND_ON_BALL DEFEND_ON_PLAYER AIM_TO_CTGTM KICK_TO_CTGTM RUN_CLEAR RUN_CLEAR_CENTER RUN_CLEAR_CENTERLINE KICK_BALL_OUT Voor elke actie zijn er 3 vaardigheden1 die uitgevoerd kunnen worden: verplaatsen, draaien en schieten. Voor de verplaatsing geeft men een bepaalde versnelling aan de robot aan de hand van een x- en y-waarde. Voor het draaien geeft men een hoekversnelling aan de robot en er kan ook steeds overwogen worden om de bal weg te schieten. Men zal dan een algoritme nodig hebben dat de geschikte vaardigheden selecteert om een bepaalde actie uit te voeren. Dit algoritme is ge¨ımplementeerd in de SkillFactory.
4.2.1
Van actie tot vaardigheid
Om een bepaalde actie uit te voeren wordt gebruik gemaakt van 3 soorten basisvaardigheden. Men dient dan te bepalen welke basisvaardigheden gebruikt moeten worden voor elke actie. Dit gebeurt op basis van een algoritme gedefinieerd in de SkillFactory. Om een gevarieerd spel te bekomen dient men een aantal combinaties van 3 vaardigheden te vormen om zo tot een uitgebreide verzameling praktische acties te komen waaruit een 1 Met
vaardigheid verwijzen we naar de klasse Skill in de code.
4 Testen in de simulatie omgeving
34
speler kan kiezen. In het UML diagram in Figuur 4.2 wordt een overzicht gegeven van alle vaardigheden. Dit diagram is ook vergroot terug te vinden in bijlage, zie Figuur A.4. In volgende paragrafen worden de 3 soorten vaardigheden verder toegelicht.
Figuur 4.2: Voorstelling mogelijke basisvaardigheden
4.2.2
Verplaatsen
Voor de verplaatsing beschikt de robot over 3 soorten basisvaardigheden. Een eerste brengt de robot zo snel mogelijk tot stilstand en heeft als doel op de huidige plaats te blijven staan. Een tweede beweegt de robot naar een bepaald doelwit, de MoveToBeOnTargetSkill. Hiervan zijn verschillende andere vaardigheden afgeleid. Ook de vaardigheid om naar de bal te bewegen kan hiertoe gerekend worden, deze heeft echter ook nog enkele extra’s. Een derde vaardigheid zal verschillende andere vaardigheden combineren om rond de bal te lopen, om hem daarna terug in het veld te schoppen. Bij het verplaatsen van de spelers naar een bepaald doelwit is het een uitdaging om de snelheid op nul te krijgen op het moment dat de speler de gewenste positie bereikt. Hiervoor moet op het juiste moment een tegengestelde versnelling aangelegd worden. Om snel te kunnen reageren is het belangrijk dat deze vertraging zo laat mogelijk wordt gestart. Op die manier kan zo lang mogelijk de maximale snelheid aangehouden worden. In Tabel 4.1 wordt een overzicht gegeven van de toewijzing van verplaats-vaardigheden aan PlayerActions. Vervolgens wordt een korte beschrijving gegeven van de vaardigheden. • DontMoveSkill Hier zal de robot een versnelling gegeven worden tegengesteld aan zijn huidige
4 Testen in de simulatie omgeving
PlayerAction TO START GO TO OPP GOAL AIM TO CTGTM KICK TO CTGTM GO TO BALL TURN TO BALL DEFEND ON BALL KEEP DEFEND ON GOAL DEFEND ON PLAYER RUN CLEAR RUN CLEAR CENTER RUN CLEAR CENTERLINE KICK BALL OUT WAIT default
35
Move MoveToStartSkill MoveToOppGoalSkill MoveToCTGPSkill MoveToCTGPSkill MoveToBallSkill DontMoveSkill MoveToDefendOnBallSkill MoveToKeeperPositionSkill MoveToDefenderPositionSkill MoveToDefendOnPlayerSkill RunClearSkill RunClearCenterSkill RunClearOnCenterLineSkill MoveToKickBallInSkill DontMoveSkill MoveToBallSkill
Tabel 4.1: De gebruikte toewijzing van verplaats-vaardigheden aan PlayerActions
snelheid. Om de stabiliteit te verbeteren verkleint de absolute waarde van de versnelling bij kleinere waardes voor de absolute waarde van de snelheid. • MoveToBallSkill De speler zal naar de bal bewegen. Eerst zal een versnelling gegenereerd worden in de richting van de bal. Als de speler dan de bal op een bepaalde afstand nadert moet de snelheid verminderen om de botssnelheid te beperken. Op dit moment moet dus een negatieve versnelling aan de robot gegeven worden. Er moet ook rekening gehouden worden met de snelheid van de bal. Zo zal een speler niet naar de huidige positie van de bal bewegen, maar naar de positie waar de bal waarschijnlijk zal zijn als de speler bij de bal is. • MoveToKickBallInSkill Deze vaardigheid wordt gehanteerd door de speler die de bal terug in het veld zal schieten nadat deze door de tegenstander is buiten geschopt. De speler zal eerst rond de bal lopen zodat hij in de richting van het veld mikt. Vervolgens zal hij naar de bal lopen en deze vast nemen. Als de speler vervolgens naar een medespeler schiet wordt het spel hervat. • MoveToBeOnTargetSkill Deze zal de robot verplaatsen in de richting van een bepaald doelwit. Dit is een abstracte vaardigheid waarbij het doelwit wordt ingevuld door een andere vaardigheid die overerft van deze vaardigheid.
4 Testen in de simulatie omgeving
36
• MoveToKeeperPositionSkill Als doelwit wordt een plaats vlak voor het doel bepaald, zodat zoveel mogelijk van het doel wordt afgeschermd. Deze vaardigheid zal een rechtstreeks schot naar het doel proberen verhinderen. • MoveToDefenderPositionSkill Deze vaardigheid heeft als doel de keeper te ondersteunen. De verdediger zal een plaats innemen ongeveer in het midden tussen de bal en het doel. • MoveToLineSkill De speler zal naar het dichtste punt op de gespecificeerde lijn bewegen. Als dit e´ e´ n van de twee eindpunten is, zal de speler naar een punt iets meer naar het midden van de lijn gaan. Dit om botsingen met het object op het eindpunt te vermijden. • MoveToDefendOnBallSkill Een speler die deze vaardigheid heeft gekozen zal eerst de kortste weg naar de lijn tussen de bal en het doel volgen. Als de speler zich op of dicht in de buurt van deze lijn bevindt zal hij vervolgens in de richting van de bal bewegen. • MoveToDefendOnPlayerSkill Eerst zal de speler bepaald worden van het andere team die het dichtst bij het doel staat en waarnaar de speler met de bal kan passen. De speler met deze vaardigheid zal dan bewegen zodat hij tussen de speler met de bal en de pasbare speler staat. • RunClearSkill Het doelwit is ergens op de helft van de tegenstander aan de kant met het minste tegenstanders. • RunClearCenterSkill De speler zal bewegen naar een positie in het midden tussen het doel van de tegenstander en het midden van de lijn tussen het eigen doel en de bal. Op die manier zal de speler zich dichter tegen het doel van de tegenstander bevinden als de bal op de eigen helft is. En als de bal dicht bij het doel van de tegenstander komt zal de speler iets verder van het doel gaan staan dan de bal. • MoveStraightToOppGoalSkill De speler zal rechtstreeks naar het doel van de tegenstander lopen. • MoveToOppGoalSkill De speler zal in een boog naar het doel van de tegenstander lopen en er een bepaalde afstand vandaan blijven. Er wordt gekozen om in een boog te lopen om zo aan de andere zijde plaats te cre¨eren. Als de speler niet kan scoren aan deze zijde is er zo meer kans dat hij kan passen naar een speler aan de andere zijde.
4 Testen in de simulatie omgeving
37
• MoveToCTGPSkill2 De speler beweegt naar de teamgenoot die zich het dichtste bij het doel van de tegenstander bevindt en waarnaar deze speler kan passen. • MoveToStartSkill Deze vaardigheid wordt gebruikt om de spelers naar hun startposities te bewegen. Deze positie is afhankelijk van het id van de speler.
4.2.3
Draaien
De rotatie van een robot kan apart gestuurd worden. Hier moet ook eerst een versnelling in de gewenste richting aangelegd worden en vervolgens een tegengestelde versnelling om te stoppen met draaien. De uitdaging is hier opnieuw om het juiste moment te vinden waarop de tegengestelde versnelling moet aangelegd worden. Een tweede uitdaging is ook opnieuw om de draaisnelheid exact op nul te krijgen. We geven eerst een overzicht van de toewijzing van draai-vaardigheden aan PlayerActions in Tabel 4.2 en bespreken daarna kort de verschillende vaardigheden. PlayerAction TO START GO TO OPP GOAL AIM TO CTGTM KICK TO CTGTM GO TO BALL TURN TO BALL DEFEND ON BALL KEEP DEFEND ON GOAL DEFEND ON PLAYER RUN CLEAR RUN CLEAR CENTER RUN CLEAR CENTERLINE KICK BALL OUT WAIT default
Turn TurnToOppGoalSkill TurnToOppGoalSkill TurnToPlayerSkill TurnToPlayerSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToBallSkill TurnToKickBallInSkill TurnToOppGoalSkill TurnToBallSkill
Tabel 4.2: De gebruikte toewijzing van draai-vaardigheden aan PlayerActions
• TurnToBallSkill Wijzigt de rotatie van de speler zodat deze klaar is om de bal te nemen. • TurnToOppGoalSkill Eerst wordt de hoek van het doel bepaald. Dit is een domein met een beginhoek 2 CTGP:
Closest To Goal Player, de teamgenoot het dichtst bij het doel van de tegenstander.
4 Testen in de simulatie omgeving
38
en een eindhoek. Vervolgens worden spelers gezocht die een deel van dit domein blokkeren. Men bepaalt ook hun hoeken en verdeelt het doeldomein in verschillende subdomeinen die niet worden geblokkeerd. Als er een deel van het domein van het doel overblijft wordt het grootste subdomein bepaald. De speler zal dan richten naar het midden van het grootste domein. Als het doel volledig wordt geblokkeerd zal de speler naar het midden van het doel mikken. • TurnToPlayerSkill Gelijkaardig als hierboven wordt een domein bepaald waarnaar gemikt moet morden. Het domein waarvan vertrokken wordt is de speler het dichtst bij het doel van de tegenstander waarnaar deze speler kan passen. • TurnToKickBallInSkill Deze vaardigheid maakt gebruik van de drie andere vaardigheden. Zolang de speler niet in de goede hoek staat mikt hij naar het doel van de tegenstander. Als hij naar de bal aan het gaan is, mikt de speler naar de bal. Als hij de bal heeft mikt hij naar een teamgenoot.
4.2.4
Schieten
Een speler kan de bal naar een teamgenoot passen of naar het doel schieten. In sommige gevallen mag de speler de bal niet bezitten, dan moet hij hem kunnen los laten. Om dit gedrag te kunnen realiseren beschikt hij over drie vaardigheden. Eerst geven we een overzicht van de toewijzing van deze vaardigheden aan de PlayerActions in Tabel 4.3 en vervolgens bespreken we kort deze vaardigheden. PlayerAction TO START GO TO OPP GOAL AIM TO CTGTM KICK TO CTGTM GO TO BALL DEFEND ON BALL KEEP DEFEND ON GOAL DEFEND ON PLAYER RUN CLEAR RUN CLEAR CENTER RUN CLEAR CENTERLINE KICK BALL OUT WAIT default
Kick null KickToGoalSkill null KickToTeamMateSkill null null null null null null null null KickToTeamMateSkill null DropBallSkill
Tabel 4.3: De gebruikte toewijzing van schiet-vaardigheden aan PlayerActions
4 Testen in de simulatie omgeving
39
• DropBallkill De bal wordt weggeschoten zonder snelheid. Dit komt dus neer op het loslaten van de bal. • KickToGoalSkill Als de weg naar het doel van de tegenstander vrij is en als de rotatie van de speler naar het doel gericht is, zal de bal weggeschoten worden met de maximale snelheid. Het controleren van de rotatie en het vrije pad is ook opgenomen in deze vaardigheid. • KickToTeamMateSkill Als de speler naar de teamgenoot het dichtst bij het doel van de tegenstander gedraaid is en als de weg naar deze speler vrij is, zal deze speler naar een teamgenoot passen. De snelheid wordt bepaald zodat de bal bijna stil ligt, maar toch nog een zekere snelheid heeft als hij bij de teamgenoot aankomt. Het wegschieten van de bal wordt gesimuleerd door de bal een zekere beginsnelheid te geven. De bal is onderhevig aan wrijving en zal na een bepaalde afstand tot stilstand komen. Op echte robotjes wordt het wegschieten van de bal gerealiseerd door met een plunjer tegen de bal te stoten. Men kan de kracht waarmee tegen de bal gestoten wordt regelen en zo dus ook de snelheid waarmee de bal vertrekt regelen.
4.3
Testen van strategie¨en
Om het gebruik van de simulatie omgeving te demonstreren hebben we twee strategie¨en ontwikkeld. E´en die gebruik maakt van de totale toestand die alle deeltoestanden in acht neemt en e´ e´ n strategie die met de gedeeltelijke toestand werkt. In de praktijk kunnen er verschillende toestanden met verschillende strategie¨en samenwerken. De beschreven strategie¨en worden in de UML-diagramma StaticStrategy en NewStaticStrategy genoemd. Dit zijn vrij eenvoudige strategie¨en die voor een bepaalde toestand een bepaalde actie selecteren. ’Static’ wijst hier op het feit dat de strategie niet automatisch gewijzigd wordt tijdens het spel. De strategie kan wel real-time door de gebruiker gewijzigd worden via de gui om deze scherp te stellen en te verbeteren.
4.3.1
Strategie 1
Een eerste strategie die ontwikkeld werd is een strategie die voor een totale toestand een actie bepaalt. Deze versie maakt gebruik van de totale toestand zoals beschreven in paragraaf 4.1.4. Deze houdt nog geen rekening met rollen en bepaalt dus een actie op basis van de combinatie van het balbezit, de plaats op het veld en de schiet- en pasmogelijkheden. Deze strategie is intern ge¨ımplementeerd als een driedubbele HashMap. De combinatie van de BallOwningState, de DistanceState en de CanKickState die deel uitmaken van die TotalState wordt gemapt op een PlayerAction.
4 Testen in de simulatie omgeving
40
De strategie kan live gewijzigd worden via de gui tijdens het spelen. Er is ook de mogelijkheid voorzien om deze strategie naar een bestand weg te schrijven zodat deze later opnieuw kan gebruikt worden. De strategie wordt in het bestand opgeslagen zodat deze ook gemakkelijk kan gelezen worden door de gebruiker. Hieronder ziet u enkele voorbeeld regeltjes voor een strategie. Deze strategie kan enkele duizenden regeltjes bevatten. PLAYER,DistanceState TEAM,DistanceState: FREE,DistanceState:
4.3.2
: [1/3/2],CanKickSta [0/0/1],CanKickState [1/1/2],CanKickState
te: [false|1],KICK_T : [true|3],KEEP : [false|2],DEFEND_O
O_CTGTM N_GOAL
Strategie 2
Deze strategie zal niet steeds de gehele toestand in rekening houden. Op basis van de rol en het balbezit wordt een selectie gemaakt welke delen van de totale toestand relevant zijn om een actie te kiezen. Zo is voor een aanvaller die in bezit is van de bal de afstand tot het eigen doel van geen enkel belang, alsook de afstand tot de bal, deze is toch vanzelfsprekend nul. Deze strategie is ge¨ımplementeerd als een HashMap die een NewTotalState op een PlayerAction mapt. Deze strategie kan ook gewijzigd worden via de GUI en kan ook opgeslagen worden. Doordat gebruik wordt gemaakt van delen van toestanden worden irrelevante toestanden vermeden en gelijkaardige toestanden samen genomen. Hierdoor wordt een strategie beperkt tot enkele honderden regels. Deze regels zijn wel ingewikkelder doordat ze kunnen verschillen van grootte. Hieronder worden enkele regels weergegeven als voorbeeld. KEEPER,PLAYER,[CKTMO MIDFIELDER,PLAYER,[C STRIKER,FREE,[BDS 0]
4.3.3
GDS 0],KICK_TO_CTGTM KTMOGDS 0/CAN_KICK_T ,GO_TO_BALL
O_GOAL/OPGDS 0],GO_T
O_OPP_GOAL
De strategie wijzigen via de GUI
Voor het testen, opstellen en wijzigen van strategie¨en is de mogelijkheid voorzien om deze te wijzigen via de GUI. Op die manier kan de gebruiker, live tijdens het spelen van een match, de strategie van de spelers wijzigen. De gebruiker kan voor elke toestand defini¨eren welke actie ondernomen moet worden. De gebruiker kan bovendien ook zien in welke toestand een bepaalde speler zich bevindt en welke actie hij daardoor gekozen heeft. In Figuur 3.2 ziet u in het onderste tabblad een voorbeeld van de GUI voor Strategie 2. Het wijzigen van de strategie gebeurt in 2 stappen. Eerst wordt de toestand geselecteerd. De gebruiker selecteert de Role, de BallOwningState en de andere deeltoestanden. Dan wordt automatisch de PlayerAction getoond volgens de huidige strategie. Dan kan de gebruiker een andere PlayerAction kiezen, hierdoor wordt de huidige strategie aangepast. Tot slot kan deze aangepaste strategie nog opgeslagen worden in een bestand met behulp van de export knop. Het wijzigen van een strategie wordt ook voorgesteld in Figuur 4.3
4 Testen in de simulatie omgeving
41
Figuur 4.3: Wijzigen van de strategie via de gui
De opgeslagen strategie¨en kunnen dan later opnieuw worden opgeroepen met de import knop of e´ e´ n van de automatische knoppen.
4.4
Lokale intelligentie
Zoals reeds eerder aangehaald kan men overwegen om bepaalde gedrag lokaal op de robot te regelen. Dit kan gesimuleerd worden door dit gedrag op de spelers in phys2D te implementeren. De spelers zullen over enkele vaardigheden beschikken die dit gedrag uitvoeren. Hieronder volgt een overzicht van de vaardigheden waarmee we reeds ge¨experimenteerd hebben.
4.4.1
Vermijden van botsingen
Bij internationale wedstrijden kunnen spelers bestraft worden die botsen met andere robots. De regels hieromtrent zijn terug te vinden in de offici¨ele regelgeving[31]. We proberen dit botsen te vermijden door de speler een versnelling te geven weg van de dichtste robot indien de speler te dicht komt bij deze robot. Robots in bezit van de bal worden niet in rekening gebracht bij het bepalen van de dichtste robot, op die manier ondervindt de robot geen problemen als hij de bal wil afnemen van een robot. Dit wordt enkel geactiveerd indien de snelheid van deze robot naar de andere robot is gericht. Indien deze robot zich in de buurt van de bal bevindt, zal de versnelling waarmee de robot weggaat van de andere robot verminderd worden.
4.4.2
Vermijden om buiten te lopen met de bal
Het normale gedrag probeert niet actief te voorkomen dat een speler die in het bezit is van de bal buiten het veld loopt. Daarom worden op de robot regels voorzien zodat deze weg zal lopen van de rand van het veld indien hij te dicht bij deze rand komt en naar de rand beweegt. De invoering van deze vaardigheid heeft voor grote verbeteringen gezorgd.
4 Testen in de simulatie omgeving
4.4.3
42
Afstand houden van de bal
Als het spel is stilgelegd door de scheidsrechter en als de bal zal uitgeschopt worden, moeten de andere spelers een bepaalde afstand van de bal blijven. Dit gedrag proberen we ook te realiseren op de robot zelf.
4.5
Besluiten
Uit bovenstaande voorbeelden is gebleken dat het geheel eenvoudig uit te breiden en aan te passen is. Alle delen van een strategie kunnen afzonderlijk vervangen, verbeterd en vernieuwd worden. De toestand kan uitgebreid worden door het toevoegen van extra deeltoestanden. Men moet dan in de factory horende bij die toestand de nieuwe deeltoestanden toevoegen in de gewenste gevallen. Men kan echter ook een totaal andere manier van voorstellen van de toestand introduceren. Men zal er enkel voor moeten zorgen dat de toestanden kunnen worden vergeleken en dat ze unieke hashwaarden genereren. Vervolgens kan men ook extra vaardigheden toevoegen en deze gebruiken door ze onder te brengen in nieuwe acties. Men kan dan eenvoudig via de gui de policy wijzigen zodat de nieuwe acties gebruikt worden. Tot slot kan men ook andere policies gebruiken. Men zou onder andere kunnen overwegen een policy te ontwikkelen die zijn regels aanpast tijdens het spelen tegen een ongekend team. Dit kan verwezenlijkt worden met een leermechanisme zoals bijvoorbeeld Reinforcement Learning [30]. Op die manier kan men de zwakheden van het andere team online leren en direct gebruiken.
Hoofdstuk 5
Besluiten 5.1
Resultaat
In deze thesis werd in het kader van het RoboCup.be project een simulatie en test omgeving voor gedistribueerde voetbal strategie¨en ontwikkeld. Hierbij wordt gebruik gemaakt van een multi-agenten systeem dat een gesimuleerde realiteit aanstuurt. Eerst werden andere teams bestudeerd en geanalyseerd aan de hand van hun ETDP. Hieruit hebben we een aantal concepten en veel gebruikte methodieken geleerd die bij de ontwikkeling van het Belgische team ook van pas kunnen komen. Vervolgens werd de simulatie omgeving ontwikkeld. De simulatie omgeving bestaat uit 2 delen. Een eerste deel zal de fysische realiteit simuleren. De plaats, de snelheid, de versnelling, de rotatie, de rotatie snelheid en de rotatie versnelling, al deze eigenschappen moeten worden gesimuleerd. Daarnaast zullen spelers botsen met elkaar en met de bal. Dit alles wordt zo goed mogelijk naar waarheid gesimuleerd door de fysische omgeving. Een tweede deel van de simulator is het multi-agenten systeem. Met elke robot komt een agent overeen die beslist welke actie moet uitgevoerd worden. Voor het maken van deze beslissing zal de agent een bepaalde strategie hanteren. Tot slot werd een geschikte strategie ge¨ımplementeerd in de ontwikkelde simulatie omgeving. Een strategie zal eerst de huidige toestand van de robot bepalen. Vervolgens bepaalt een policy een actie voor de huidige toestand. Deze actie komt dan overeen met 3 vaardigheden die de robot zullen verplaatsen, draaien en de bal doen wegschieten indien nodig. Enkele delen van het gedrag van de spelers werd ook in de fysische omgeving ge¨ımplementeerd. Op die manier proberen we het effect van lokale intelligentie te demonstreren. Gedrag op de robot zelf zal in staat zijn vlugger te reageren doordat de vertraging veroorzaakt tijdens de communicatie wordt vermeden. Het nadeel hierbij is echter dat de rekenkracht op de robot vrij beperkt is.
43
5 Besluiten
5.2
44
Uitbreidingen en verbeteringen
Deze thesis is de eerste die de (simulatie) software van het Belgische team behandelt. De software is dus zeker niet af, maar zal steeds blijven evolueren om de evolutie in de hardware te volgen en om de andere teams te kunnen verslaan. In deze paragraaf geven we een overzicht van enkele verbeteringen en uitbreidingen die zeker de moeite waard zijn om te bestuderen in de toekomst.
5.2.1
Overgang naar 3D
Aangezien de bal eigenlijk ook door de lucht kan vliegen is de overstap naar een 3 dimensionale weergave voor de hand liggend. Doordat de fysische simulator aan het agenten systeem is gekoppeld via een interface kan deze gemakkelijk vervangen worden door een 3 dimensionale fysische simulator zoals bijvoorbeeld JBullet [1]. Hierin kan dan ook het dribbelen en het afnemen van de bal beter naar waarheid gesimuleerd worden.
5.2.2
Uitbreiden van de toestand
Voor het bepalen van de juiste actie kan men de delen die de toestand bepalen uitbreiden met extra gegevens. We geven hieronder enkele mogelijke uitbreidingen, er zijn er uiteraard nog andere. • een index opnemen die de nabijheid van tegenstanders uitdrukt. • een voorstelling van de grootte van de hoek om naar het doel van de tegenstander te schieten. • een voorstelling die de mate waarin het eigen doel verdedigd wordt voorstelt.
5.2.3
Uitbreiden van de vaardigheden
Het aantal vaardigheden is sterk bepalend voor de variatie van het spel van de robots. Het is dus sterk aan te raden de set vaardigheden uit te breiden zodat om een bepaalde actie uit te voeren de juiste vaardigheden beschikbaar zijn. Samen met het toevoegen van vaardigheden zullen dus ook acties, die deze vaardigheden gebruiken, moeten toegevoegd worden. Ook zullen de vaardigheden uitgebreid moeten worden als de hardware evolueert. De hardware van de meeste hedendaagse teams is in staat om de bal ook in een boog door de lucht te schieten over andere spelers heen. Als deze mogelijkheid ook op onze robots voorzien wordt moeten vaardigheden ontwikkeld worden die hiervan gebruik maken.
5.2.4
Toevoegen van lerende strategie¨en
Een volgende uitbreiding die de moeite waard is om te proberen is het toevoegen van lerende strategie¨en. Deze zullen dan eventueel in staat zijn om tijdens het spelen hun gedrag aan te
5 Besluiten
45
passen om zo in te spelen op de strategie van de tegenstander. Een voor de hand liggende aanpak hierbij is het gebruik van reinforcement learning [30]. Hierbij hanteren agenten een wijzigende strategie. Door goede acties te belonen en slechte te bestraffen wordt gepoogd de strategie te verbeteren tijdens het spelen.
5.2.5
Verbeteren van de vaardigheden
Ook de implementatie van de huidige set vaardigheden kan verbeterd worden. Men moet wel steeds de overweging maken, het verbeteren van een vaardigheid betekent ook dikwijls meer rekenwerk, en dus meer rekentijd. Men zal dus snelheid moeten afwegen tegen nauwkeurigheid. Een vaardigheid die bijvoorbeeld nog kan verbeterd worden is de vaardigheid om het doel te verdedigen. Net zoals de aanvallers een hoek naar het doel berekenen kan de verdediger diezelfde hoek berekenen en deze zo veel mogelijk proberen verkleinen.
5.2.6
Beter vermijden van botsingen
Momenteel worden in de fysische simulator vaardigheden gebruikt die botsingen met andere robots proberen te voorkomen. Om te voldoen aan de offici¨ele regels moeten robots echter botsingen kunnen vermijden. Bij elke botsing zullen namelijk strafpunten worden toegekend. Om deze botsingen te vermijden zou men gebruik kunnen maken van path-planning [5] algoritmes die een weg omheen hindernissen bepalen. Maar ook de vaardigheden om botsingen te vermijden kunnen nog verbeterd worden.
5.2.7
Toepassen van het volledige reglement voor de Small-Size League
Ook op andere gebieden voldoen de robots en de simulator nog niet volledig aan de offici¨ele regels [31]. Bovendien worden deze regels regelmatig uitgebreid en aangepast. Men zal deze regels uitgebreid moeten bestuderen en toepassen vooraleer echt deel te kunnen nemen aan internationale wedstrijden.
Bibliografie [1] Jbullet - java port of bullet physics library. http://jbullet.adve [2] Joode. http://joode.source
l.cz/.
forge.net/, 2007.
[3] Hiroki Achiwa, Junya Maeno, Junya Tamaki, Saori Suzuki, Tatsuya Moribayasi, Kazuhito Murakami, and Tadashi Naruse. Robodragons 2009 extended team description. Technical report, Aichi Prefectural University, 2009. [4] Jan Audenaert, Katja Verbeeck, and Greet Vanden Berghe. Multi-agent based simulation for boarding. In Toon Calders, Karl Tuyls, and Mykola Pechenizkiy, editors, Proceedings of the 21st Benelux Conference on Artificial Intelligence. KaHo Sint-Lieven, Associatie K.U. Leuven, TU/e Printservice, October 2009. [5] James Bruce and Manuela Veloso. Real-time randomized path planning for robot navigation, 2002. [6] Erin Catto. Fast and simple physics using sequential impulses. PPT presentation, 2006. [7] Center for Complex Adaptive Agent Systems Simulation (CAS2) Decision & Information Sciences Division Argonne National Laboratory. TUTORIAL ON AGENT-BASED MODELING AND SIMULATION PART 2: HOW TO MODEL WITH AGENTS. Charles M. Macal and Michael J. North, 2006. [8] Chitchanok Chuengsatiansup, Thiraphat Charoensripongsa, Kanit Wongsuphasawat, Komsit Rattana, Pawawat Doungsodsri, Aphilux Buathongand Kittipat Wejwittayaklung, Manop Wongsaisuwan, and Wittaya Wannasuphoprasit. Plasmaz extended team description paper. Technical report, Department of Computer Engineering Department of Industrial Engineering Department of Mechanical Engineering Department of Electrical Engineering Chulalongkorn University, 2009. [9] Wikipedia contributors. Comparison of agent-based modeling software. http:// en.wikipedia.org/wik i/Comparison_of_agen t-based_modeling_sof tware, 2009. [10] Erwin Coumans. Bullet physics library. http://bulletphysic
46
s.org, 2009.
BIBLIOGRAFIE
47
[11] Jill Bigley Dunham. An agent-based spatially explicit epidemiological model in mason. Journal of Artificial Societies and Social Simulation, 9(1):3, 2005. [12] Kevin Glass and Gideon Smeding. Phys2d - the 2d game physics engine in java. http://www.cokeandco de.com/phys2d. [13] Swarm Development Group. Swarm. www.swarm.org, 1999. [14] Red Hat. Cygwin. http://www.cygwin.c
om.
[15] Julio Jerez and Alain Suero. Newton game dynamics physics engine. http://www. newtondynamics.com. [16] James J. Kuffner Jr. and Steven M. Lavalle. Rrt-connect: An efficient approach to single-query path planning. In Proc. IEEE Int l Conf. on Robotics and Automation, pages 995–1001, 2000. [17] Argonne National Laboratory. Repast - recursive porous agent simulation toolkit. http://repast.source forge.net/, 2008. [18] Tim Laue, Armin Burchardt, Sebastian Fritsch, Sven Hinz, Kamil Huhn, Teodosiy Kirilov, Alexander Martens, Markus Miezal, Ulfert Nehmiz, Malte Schwarting, and Andreas Seekircher. B-smart extended team description for robocup 2009. Technical report, Deutsches Forschungszentrum f¨ur K¨unstliche Intelligenz GmbH, Universit¨at Bremen, 2009. [19] Patrick Lester. A* pathfinding for beginners. http://www.policyal games/aStarTutorial. htm, 7 2005.
manac.org/
[20] Sean Luke, Gabriel Catalin Balan, Keith Sullivan, and Liviu Panait. Mason. http: //cs.gmu.edu/ ˜eclab/projects/mason /. [21] Nick Malleson. RepastCity - A demo virtual city. http://portal.ncess access/wiki/site/mas s/repastcity.html. [22] Miles T. Parker. What is ascape and why should you care? Societies and Social Simulation, vol. 4, no. 1, 2001.
.ac.uk/
Journal of Artificial
[23] Marco Raberto, Silvano Cincotti, Sergio M. Focardi, and Michele Marchesi. Agent-based simulation of a financial market. Quantitative finance papers, arXiv.org, 2001. [24] Craig W. Reynolds. Flocks, herds, and schools: A distributed behavioral model. Computer Graphics, 21(4):25–34, 1987. [25] Max Risler and Oskar von Stryk. Formal behavior specification of multi-robot systems using hierarchical state machines in XABSL. In AAMAS08-Workshop on Formal Models and Methods for Multi-Robot Systems, Estoril, Portugal, 2008.
BIBLIOGRAFIE
48
[26] Stuart Russell and Peter Norvig. Artificial Intelligence: a Modern Approach. Prentice Hall, 1995. [27] Russell Smith. Ode. http://www.ode.org. [28] Torus Knot Software. Ogre. http://www.ogre3d.o
rg, 2001.
[29] Jirat Srisabye, Piyamate Wasuntapichaikul, Chanon Onman, Kanjanapan Sukvichai, Supparat Damyot, Thitiwat Munintarawong, Phumin Phuangjaisri, and Yodyium Tipsuwan. Skuba 2009 extended team description. Technical report, Faculty of Engineering, Kasetsart University, 2009. [30] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: an introduction. Mit Pr, Mei 1998. [31] SSL TC. Laws of the f180 league 2009. 2009. [32] Wilensky Uri. Netlogo. http://ccl.northwes tern.edu/netlogo, 1999. Center for Connected Learning and Computer-Based Modeling. Northwestern University, Evanston. [33] Michael Wooldridge. An Introduction to MultiAgent Systems. John Wiley & Sons, March 2005. [34] Yonghai Wu, Xingzhong Qiu, Guo Yu, Jianjun Chen, Xuqing Rie, and Rong Xiong. Extended tdp of zjunlict 2009. Technical report, National Laboratory of Industrial Control Technology Zhejiang University, 2009. [35] Stefan Zickler, James Bruce, Joydeep Biswas, Michael Licitra, and Manuela Veloso. Cmdragons 2009 extended team description. Technical report, Carnegie Mellon University, 2009.
Bijlage A
UML In deze bijlage wordt een overzicht gegeven van de software aan de hand van enkele UML-diagrammen.
49
Figuur A.1: UML Class Diagram voor de interfaces tussen Repast en Phys2D.
A UML 50
Figuur A.2: UML Class Diagram voor de implementatie van Phys2D.
A UML 51
Figuur A.3: UML Class Diagram voor de structuur van de agenten en hun weergave in Repast.
A UML 52
Figuur A.4: Overzicht mogelijke basisvaardigheden
A UML 53
Figuur A.5: Overzicht opbouw spelers en hun strategie
A UML 54
Figuur A.6: Overzicht opbouw verschillende voorstellingen van de toestand
A UML 55
Figuur A.7: Sequentie Diagram dat de verschillende stappen bij het toepassen van een strategie weergeeft.
A UML 56
Figuur A.8: Sequentie Diagram dat de stappen weergeeft bij het updaten van een NewTotalState.
A UML 57
Bijlage B
Strategie voorbeeld Als voorbeeld geven we hieronder de regels die een strategie bepalen voor een StrategyPlayer met de NewTotalState en de NewStaticStrategy. Met ruim 220 regels is dit toch nog altijd vrij beperkt. 1
11
21
31
KEEPER , PLAYER , [ CKTMOGDS 0 ] , KICK TO CTGTM KEEPER , PLAYER , [ CKTMOGDS 1 ] , KICK TO CTGTM KEEPER , PLAYER , [ CKTMOGDS 2 ] , KICK TO CTGTM KEEPER , PLAYER , [ CKTMOGDS 3 ] , KICK TO CTGTM KEEPER , PLAYER , [ CKTMOGDS 4 ] , KICK TO CTGTM KEEPER , PLAYER , [ CKTMOGDS 5 ] , KICK TO CTGTM KEEPER , TEAM, ] , KEEP KEEPER , OPPONENT , [ BDS 0 ] , GO TO BALL KEEPER , OPPONENT , [ BDS 1 ] , KEEP KEEPER , OPPONENT , [ BDS 2 ] , KEEP KEEPER , OPPONENT , [ BDS 3 ] , KEEP KEEPER , OPPONENT , [ BDS 4 ] , KEEP KEEPER , FREE , [ BDS 0 /OWGDS 0 ] , GO TO BALL KEEPER , FREE , [ BDS 0 /OWGDS 1 ] , GO TO BALL KEEPER , FREE , [ BDS 0 /OWGDS 2 ] , KEEP KEEPER , FREE , [ BDS 0 /OWGDS 3 ] , KEEP KEEPER , FREE , [ BDS 0 /OWGDS 4 ] , KEEP KEEPER , FREE , [ BDS 1 /OWGDS 0 ] , KEEP KEEPER , FREE , [ BDS 1 /OWGDS 1 ] , KEEP KEEPER , FREE , [ BDS 1 /OWGDS 2 ] , KEEP KEEPER , FREE , [ BDS 1 /OWGDS 4 ] , KEEP KEEPER , FREE , [ BDS 1 /OWGDS 3 ] , KEEP KEEPER , FREE , [ BDS 2 /OWGDS 1 ] , KEEP KEEPER , FREE , [ BDS 2 /OWGDS 0 ] , KEEP KEEPER , FREE , [ BDS 2 /OWGDS 3 ] , KEEP KEEPER , FREE , [ BDS 2 /OWGDS 2 ] , KEEP KEEPER , FREE , [ BDS 2 /OWGDS 4 ] , KEEP KEEPER , FREE , [ BDS 3 /OWGDS 0 ] , KEEP KEEPER , FREE , [ BDS 3 /OWGDS 3 ] , KEEP KEEPER , FREE , [ BDS 3 /OWGDS 4 ] , KEEP KEEPER , FREE , [ BDS 3 /OWGDS 1 ] , KEEP KEEPER , FREE , [ BDS 3 /OWGDS 2 ] , KEEP KEEPER , FREE , [ BDS 4 /OWGDS 3 ] , KEEP KEEPER , FREE , [ BDS 4 /OWGDS 2 ] , KEEP KEEPER , FREE , [ BDS 4 /OWGDS 1 ] , KEEP KEEPER , FREE , [ BDS 4 /OWGDS 0 ] , KEEP KEEPER , FREE , [ BDS 4 /OWGDS 4 ] , KEEP DEFENDER, PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM
58
B Strategie voorbeeld
41
51
61
71
81
91
101
DEFENDER, PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL ] , KICK TO CTGTM DEFENDER, PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM DEFENDER, TEAM, ] , DEFEND ON GOAL DEFENDER, OPPONENT , [ BDS 0 ] , GO TO BALL DEFENDER, OPPONENT , [ BDS 1 ] , DEFEND ON GOAL DEFENDER, OPPONENT , [ BDS 2 ] , DEFEND ON GOAL DEFENDER, OPPONENT , [ BDS 3 ] , DEFEND ON GOAL DEFENDER, OPPONENT , [ BDS 4 ] , DEFEND ON PLAYER DEFENDER, FREE , [ BDS 0 /OPGDS 0 ] , GO TO BALL DEFENDER, FREE , [ BDS 0 /OPGDS 1 ] , GO TO BALL DEFENDER, FREE , [ BDS 0 /OPGDS 2 ] , GO TO BALL DEFENDER, FREE , [ BDS 0 /OPGDS 3 ] , DEFEND ON BALL DEFENDER, FREE , [ BDS 0 /OPGDS 4 ] , DEFEND ON BALL DEFENDER, FREE , [ BDS 1 /OPGDS 0 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 1 /OPGDS 1 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 1 /OPGDS 2 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 1 /OPGDS 4 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 1 /OPGDS 3 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 2 /OPGDS 1 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 2 /OPGDS 0 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 2 /OPGDS 3 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 2 /OPGDS 2 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 2 /OPGDS 4 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 3 /OPGDS 0 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 3 /OPGDS 3 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 3 /OPGDS 4 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 3 /OPGDS 1 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 3 /OPGDS 2 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 4 /OPGDS 3 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 4 /OPGDS 2 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 4 /OPGDS 1 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 4 /OPGDS 0 ] , DEFEND ON GOAL DEFENDER, FREE , [ BDS 4 /OPGDS 4 ] , DEFEND ON GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL
59
B Strategie voorbeeld
111
121
131
141
151
161
MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL / OPGDS 1 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL / OPGDS 2 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL / OPGDS 3 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL / OPGDS 4 ] , GO TO OPP GOAL MIDFIELDER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL / OPGDS 0 ] , GO TO OPP GOAL MIDFIELDER , TEAM, [ OPGDS 0 ] , RUN CLEAR MIDFIELDER , TEAM, [ OPGDS 1 ] , RUN CLEAR MIDFIELDER , TEAM, [ OPGDS 2 ] , RUN CLEAR MIDFIELDER , TEAM, [ OPGDS 3 ] , RUN CLEAR MIDFIELDER , TEAM, [ OPGDS 4 ] , RUN CLEAR MIDFIELDER , OPPONENT , [ BDS 0 ] , GO TO BALL MIDFIELDER , OPPONENT , [ BDS 1 ] , DEFEND ON BALL MIDFIELDER , OPPONENT , [ BDS 2 ] , DEFEND ON PLAYER MIDFIELDER , OPPONENT , [ BDS 3 ] , DEFEND ON PLAYER MIDFIELDER , OPPONENT , [ BDS 4 ] , DEFEND ON PLAYER MIDFIELDER , FREE , [ BDS 0 ] , GO TO BALL MIDFIELDER , FREE , [ BDS 1 ] , GO TO BALL MIDFIELDER , FREE , [ BDS 2 ] , GO TO BALL MIDFIELDER , FREE , [ BDS 3 ] , GO TO BALL MIDFIELDER , FREE , [ BDS 4 ] , GO TO BALL STRIKER , PLAYER , [ CKTMOGDS 0 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 0 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM STRIKER , PLAYER , [ CKTMOGDS 1 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 1 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM STRIKER , PLAYER , [ CKTMOGDS 2 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM STRIKER , PLAYER , [ CKTMOGDS 2 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 3 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 3 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM
60
B Strategie voorbeeld
171
181
191
201
211
221
STRIKER , PLAYER , [ CKTMOGDS 4 / CAN NOT KICK TO GOAL ] , KICK TO CTGTM STRIKER , PLAYER , [ CKTMOGDS 4 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 5 / CAN KICK TO GOAL ] , GO TO OPP GOAL STRIKER , PLAYER , [ CKTMOGDS 5 / CAN NOT KICK TO GOAL ] , RUN CLEAR CENTERLINE STRIKER , TEAM, ] , RUN CLEAR STRIKER , OPPONENT , [ BDS 0 ] , DEFEND ON BALL STRIKER , OPPONENT , [ BDS 1 ] , DEFEND ON PLAYER STRIKER , OPPONENT , [ BDS 2 ] , DEFEND ON BALL STRIKER , OPPONENT , [ BDS 3 ] , RUN CLEAR CENTER STRIKER , OPPONENT , [ BDS 4 ] , RUN CLEAR CENTER STRIKER , FREE , [ BDS 0 ] , GO TO BALL STRIKER , FREE , [ BDS 1 ] , RUN CLEAR STRIKER , FREE , [ BDS 2 ] , RUN CLEAR STRIKER , FREE , [ BDS 3 ] , RUN CLEAR STRIKER , FREE , [ BDS 4 ] , RUN CLEAR OUT BALLGETTER , PLAYER , [ CKTMOGDS 0 ] , KICK BALL OUT OUT BALLGETTER , PLAYER , [ CKTMOGDS 1 ] , KICK BALL OUT OUT BALLGETTER , PLAYER , [ CKTMOGDS 2 ] , KICK BALL OUT OUT BALLGETTER , PLAYER , [ CKTMOGDS 3 ] , KICK BALL OUT OUT BALLGETTER , PLAYER , [ CKTMOGDS 4 ] , KICK BALL OUT OUT BALLGETTER , PLAYER , [ CKTMOGDS 5 ] , AIM TO CTGTM OUT BALLGETTER , TEAM, ] , KICK BALL OUT OUT BALLGETTER , OPPONENT , [ BDS 0 ] , DEFEND ON BALL OUT BALLGETTER , OPPONENT , [ BDS 1 ] , DEFEND ON BALL OUT BALLGETTER , OPPONENT , [ BDS 2 ] , DEFEND ON BALL OUT BALLGETTER , OPPONENT , [ BDS 3 ] , DEFEND ON BALL OUT BALLGETTER , OPPONENT , [ BDS 4 ] , DEFEND ON BALL OUT BALLGETTER , FREE , [ BDS 0 ] , KICK BALL OUT OUT BALLGETTER , FREE , [ BDS 1 ] , KICK BALL OUT OUT BALLGETTER , FREE , [ BDS 2 ] , GO TO BALL OUT BALLGETTER , FREE , [ BDS 3 ] , GO TO BALL OUT BALLGETTER , FREE , [ BDS 4 ] , GO TO BALL OUT PASSRECEIVER , PLAYER , ] , GO TO OPP GOAL OUT PASSRECEIVER , TEAM, [ BDS 0 ] , RUN CLEAR CENTER OUT PASSRECEIVER , TEAM, [ BDS 1 ] , RUN CLEAR CENTER OUT PASSRECEIVER , TEAM, [ BDS 2 ] , RUN CLEAR CENTER OUT PASSRECEIVER , TEAM, [ BDS 3 ] , RUN CLEAR CENTER OUT PASSRECEIVER , TEAM, [ BDS 4 ] , RUN CLEAR CENTER OUT PASSRECEIVER , OPPONENT , ] , DEFEND ON BALL OUT PASSRECEIVER , FREE , ] , RUN CLEAR CENTER OUT DEFENDER , PLAYER , [ CKTMOGDS 0 ] , GO TO OPP GOAL OUT DEFENDER , PLAYER , [ CKTMOGDS 1 ] , GO TO OPP GOAL OUT DEFENDER , PLAYER , [ CKTMOGDS 2 ] , GO TO OPP GOAL OUT DEFENDER , PLAYER , [ CKTMOGDS 3 ] , GO TO OPP GOAL OUT DEFENDER , PLAYER , [ CKTMOGDS 4 ] , GO TO OPP GOAL OUT DEFENDER , PLAYER , [ CKTMOGDS 5 ] , GO TO OPP GOAL OUT DEFENDER , TEAM, ] , RUN CLEAR OUT DEFENDER , OPPONENT , [ BDS 0 ] , DEFEND ON BALL OUT DEFENDER , OPPONENT , [ BDS 1 ] , DEFEND ON GOAL OUT DEFENDER , OPPONENT , [ BDS 2 ] , DEFEND ON BALL OUT DEFENDER , OPPONENT , [ BDS 3 ] , DEFEND ON PLAYER OUT DEFENDER , OPPONENT , [ BDS 4 ] , DEFEND ON PLAYER OUT DEFENDER , FREE , [ BDS 0 ] , DEFEND ON GOAL OUT DEFENDER , FREE , [ BDS 1 ] , DEFEND ON GOAL OUT DEFENDER , FREE , [ BDS 2 ] , DEFEND ON GOAL OUT DEFENDER , FREE , [ BDS 3 ] , DEFEND ON PLAYER OUT DEFENDER , FREE , [ BDS 4 ] , DEFEND ON GOAL START , PLAYER , ] , TO START START , TEAM, ] , TO START START , OPPONENT , ] , TO START START , FREE , ] , TO START
61
Bijlage C
Beschrijving van deze masterproef in de vorm van een wetenschappelijk artikel
62
Simulation of distributed soccer strategies Tim Vermeulen
��
KaHo Sint-Lieven, Gebroeders Desmetstraat 1, 9000 Gent, [email protected], http://www.kahosl.be
Abstract. Robocup.be is part of an international project to encourage AI and robotic research. Guided by DSP Valley and in association with other colleges our school cooperates in a Belgian team of small, driving soccer robots to take part in international competitions in the future. Beside a good hardware design for the robot, the software which must control it is perhaps even more important. This thesis starts with studying and evaluating different strategies which are currently applied in the successful robot teams. The eventual aim is to develop a simulation tool that allows creating and testing different soccer strategies for the Belgian team. In a first step we create a physical simulation environment using a physical engine to model the reality. In a second step we extend this physical environment with a multi-agent system to get a simulator in which we can develop and test intelligent multi-agent soccer strategies. Using our created simulator we study some new strategies. Unlike the popular reactive strategies, we focus on agents with coordination and local intelligence.
1
Introduction
Robocup.be is part of an international project to encourage AI and robotic research. Guided by DSP Valley and in association with other colleges (Erasmus University College in Brussels, Lessius University College, Campus De Nayer in Sint-Katelijne Waver and Vrije Universiteit Brussel) our school cooperates in a Belgian team of small, driving soccer robots to take part in international RoboCup competitions in the future. The Belgian team aims for the Small Size League where the dimensions of the robots are limited. The robots have for instance a maximum height of 15 cm. In the future they want to join the international RoboCup Small Size League. In those annual soccer competitions teams from many different countries show what they can. In July 2009, 21 teams participated and the Thai team, Skuba, won the competition. One may find a complete overview of the results on the website of RoboCup 2009, www.robocup2009.org. ��
Supervisor: dr. Katja Verbeeck, Cosupervisors: ing. Tony Wauters, ing. Koen Vangheluwe, External supervisor: ing. lic. Filiep Vincent
2
The team is still in a development phase. This article will discuss the first steps in developing an environment to simulate and test strategies for the robots. We have chosen to develop the strategy as a multi-agent system because we believe the multi-agent approach has many benefits.
2 2.1
Background Multi-agent simulation
Multi-agent simulation is a pretty new approach. The system is implemented as a group of software agents, where every agent has its own behavior. Every agent’s behavior is specified so they cooperate and coordinate to achieve the goal. Multi-agent simulation is already present in many domains, like the simulation of financial markets [7], the study of the propagation of a virus [4] or the simulation of the boarding process for airplanes [1]. In this article we will use it to control the behavior of soccer robots. To define an agent there are many definitions. Some are very vague, but most of them agree on one point, an agent must have the ability to take decisions. This decisions can be taken based on very simple reactive rules or on complex self-learning structures. One can thus specify agents as active components with an own behavior. The agents live in a certain environment. Michael Wooldridge [11] refers to the work of Russel and Norvig [9] to distinguish some different types of environments based on following properties. – Accessible versus inaccessible. In an accessible environment the agent can have accurate, complete and up-to-date information about the environment, if not, it’s inaccessible, like most real-world environments. – Deterministic versus non-deterministic. In a deterministic environment every action has a single guaranteed effect. As a result, if an environment has other unknown agents, it’s non-deterministic. – Static versus dynamic. An environment is static if the only changes to the environment are a result of the actions of the robot. – Discrete versus continuous. A discrete environment has a fixed, finite number of actions and percepts. These properties have a big influence on the possibilities to define the behavior of the agents. The environment where we will deal with is partial accessible, non-deterministic, dynamic and continuous. One of the benefits of the multi-agent approach is the possibility to model a complex total behavior by specifying relative simple rules for a single agent. A typical example of this is the swarming behavior in the Boids simulation [8]. Also simulation has many benefits. Although we were forced to simulation because of the lack of hardware.
3
2.2
Study of ETDP of other teams
To get to know the principles of the strategies of the other teams, we started by studying their Extended Team Description Papers. Every team who wants to join the RoboCup competitions needs to submit a TDP. The ones who got in to the last rounds need to bring out an ETDP. Studying those we came to some conclusions. – Strategy Most teams use a strategy with a few steps. A first step determines an overall strategy, like will they play more defending or more offending or things like that. A next step will assign something like roles to the players: keeper, defender, midfielder, attacker, ... In a next step every player will choose an action, according to the assigned role. – Path-planning The moving of robots happens by calculating a target location. A pathplanning algorithm will then calculate a path to go to that target avoiding any obstacles in the way. Most teams use an algorithm based on ”Real-Time Randomized Path Planning for Robot Navigation” [2]. – Physical simulation Most teams have a simulation environment to test their software without the need of hardware. Most of the teams uses ODE [10] for the physical simulation.
3
Simulation environment
The created simulation environment exists of two parts and an interface layer between those two. One part is based on a physical engine while another part is the multi-agent environment. In between there is an interface layer to connect those two and to make the necessary conversions. 3.1
Physical engine
The robots, the field and the ball have many physical properties. To simulate the robots and the ball we specify them as bodies in a physical engine. The players have a position, a rotation, a velocity, a rotation speed, an acceleration and a rotation acceleration. The ball has a position and a velocity. Both bodies will also have a mass, friction and damping. All this is simulated by the physical engine. We have compared many engines and eventually chose for Phys2D [5] because it’s simple and easy to modify and adapt. Phys2D is completely written in Java and based on the GDC 1 presentation of Erin Catto in 2006 [3]. 1
GDC: Game Developers Conference, www.gdconf.com
4
3.2
Multi-agent environment
The controlling of the robots is done by a multi-agent system, like we have described in paragraph 2.1. First we need to select a multi-agent environment that meets our needs. We provide a list of some important criteria. Based on these criteria and some tests we have chosen Repast Symphony [6]. – continuous coordinates – a tree-dimensional space – possibilities to append the physical engine Next we need to define the agents. We will have two types of agents, the ball and the players. The ball is pretty easy and will change it’s location every step to the location of the ball in the physical world. The player will also first change it’s location, next it will use a strategy, like described in the next paragraph, to calculate the actions to take.
4
Strategies
Every player will use a strategy to determine what action to take. A strategy exists of three parts: a state representation, a set of actions the player can do and a policy with some rules to select an action in the current state. 4.1
The state representation
To define the state of a player one could use the coordinates of that player. Because the action of a player will also depend on the locations of the other players on the field and the location of the ball, those should also be included. Because all those coordinates are continuous, one will get a infinite number of states. Therefor we have created a new way of representing the state of a player. The total state of the player will be a dynamic set of partial player states. In paragraph 2.2 we have seen most teams are using something like roles, so we will use it too. We will also need to find a way of representing the location of the player. We will do this by specifying the distance to some targets relative to the distance of the teammates. Therefor all players of a team are sorted based on their distance to a target location. Than the closest will get index 0, the next index 1 and so on. We give a list of parts of the total state of a player. – Roles. Every player is assigned a role. Using roles we can guarantee some tasks are always performed, like defending the goal for instance. – Ball owning. An other part that is always important is the owning of the ball. There are 4 possibilities: the player itself has the ball, one of its teammates has the ball, the opponent has the ball or the ball is free.
5
– Distance to the own goal. This is an index representing the distance to the own goal. The index is calculated like described before. – Distance to the goal of the opponent. This is an index representing the distance to the goal of the opponent. The index is calculated like described before. – Distance to the ball. This is an index representing the distance to the ball. – The possibilities to shoot to the goal. Whether or not this player has a free path to kick the ball to the goal. – The possibility to pass to a teammate. This is the index, representing the distance to the goal of the opponent, of the teammate closest to the goal of the opponent where this player can give a pass to. In a first stage we considered always all those partial states. But some parts can sometimes be ignored and not calculated. This will cause a reduction of calculation time so the agent can spend more time on calculating other things. Thus we will first use an algorithm to select the relevant partial states, the combination of those partial states will then be used to represent the total state of the player. 4.2
The actions
To make a various play, one need an extensive set of actions a player can take. Actions can be things like ’go to the ball’, ’go to the goal of the opponent’, ’defend the own goal’ and so on. Each action will correspond with three skills, one of each type. The move skills will adjust the position of a player, the turn skills will adjust the rotation of a player and the kick skills will kick the ball. 4.3
The policy
The only thing left is getting from a state to an action to take. Therefore a strategy will have a policy. This is perhaps the most important part that specifies some rules to select an action in the current state. 4.4
Local intelligence
One may also consider to implement some parts of the behavior on the robot itself. For some parts of the behavior this can give better results because the reaction times are smaller. One should not forget that only limited calculation power is available on the robot.
5 5.1
Conclusions Result
In this article we described the different parts of a simulation environment for distributed soccer strategies. We have developed the simulation environment as a
6
part of the RoboCup.be project. The created simulation environment is based on a multi-agent system and a physical engine which we have modified to simulate the robot soccer game. First we have studied some other team’s Team Description Papers. With the commonly used techniques from there we started building our own simulation environment. The created simulation environment exists of two parts. One part is based on a physical engine to simulate the physical properties of the players and the ball as natural as possible. The second part is a multi-agent system with the ball and the players as the agents. The player agents will then use a strategy to calculate their next actions. A strategy exists of three parts, a state representation, a set of possible actions and a policy who defines the action to take in every state. One can also implement some parts of the behavior of the robots on the robot itself. This is simulated by implementing this behavior in the physical engine. One will add some skills to the player object in the physical engine. Only simple skills could be used however because the calculation power on the robots is limited. 5.2
Improvements and extensions
Like we have mentioned before, this is the first step, so there are still a lot of possibilities to improve and extend the simulation environment. We summarize some of them. – 3D environment It is also possible for the ball to fly trough the air. It’s clear that this behavior can not be simulated with a two-dimensional simulation environment. The transition to a three-dimensional physical simulation environment can solve this problem. – Extending the state representation By adding possible partial states one can better specify the state in certain circumstances. The more partial states are added, the better the best action can be chosen. – Extending the skills The more skills a player can use, the more varied the game will be. – Adding learning strategies By adding learning strategies the player can adapt his behavior to that of the opponent. – Improving the skills The skills can also be improved by making extra calculations. However, by doing this, the calculation times will increase and the update frequency will decrease. – Better collision avoidance To meet the official RoboCup Small Size League rules, the robots need to avoid all collisions. To approve the collision avoidance, a recommended solution would be a path-planning algorithm.
7
References 1. Jan Audenaert, Katja Verbeeck, and Greet Vanden Berghe. Multi-agent based simulation for boarding. In Toon Calders, Karl Tuyls, and Mykola Pechenizkiy, editors, Proceedings of the 21st Benelux Conference on Artificial Intelligence. KaHo Sint-Lieven, Associatie K.U. Leuven, TU/e Printservice, October 2009. 2. James Bruce and Manuela Veloso. Real-time randomized path planning for robot navigation, 2002. 3. Erin Catto. Fast and simple physics using sequential impulses. PPT presentation, 2006. 4. Jill Bigley Dunham. An agent-based spatially explicit epidemiological model in mason. Journal of Artificial Societies and Social Simulation, 9(1):3, 2005. 5. Kevin Glass and Gideon Smeding. Phys2d - the 2d game physics engine in java. http://www.cokeandcode.com/phys2d. 6. Argonne National Laboratory. Repast - recursive porous agent simulation toolkit. http://repast.sourceforge.net/, 2008. 7. Marco Raberto, Silvano Cincotti, Sergio M. Focardi, and Michele Marchesi. Agentbased simulation of a financial market. Quantitative finance papers, arXiv.org, 2001. 8. Craig W. Reynolds. Flocks, herds, and schools: A distributed behavioral model. Computer Graphics, 21(4):25–34, 1987. 9. Stuart Russell and Peter Norvig. Artificial Intelligence: a Modern Approach. Prentice Hall, 1995. 10. Russell Smith. Ode. http://www.ode.org. 11. Michael Wooldridge. An Introduction to MultiAgent Systems. John Wiley & Sons, March 2005.
Bijlage D
Poster
70
