Bachelor Project AI The pull of the Unknown. 1 juli 2005

Bachelor Project AI The pull of the Unknown Sjoerd Kerkstra 1 juli 2005

S J Preeker

Inhoudsopgave 1 inleiding 1.1 inleiding en aanverwant werk . . . . . . . . . . . . . . . . . . 1.2 onderzoeksvraag . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 6

2 theorie 2.1 Uitleg hoofd artikel . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Vertex-Ant-Walk; definitie . . . . . . . . . . . . . . . . . . . . 2.3 Vertex-Ant-Walk; resultaten . . . . . . . . . . . . . . . . . . . 2.3.1 bewijs voor convergentie van Vertex-Ant-Walk . . . . 2.3.2 Upper bound voor convergentie tijd Vertex-Ant-Walk 2.4 doel van ons project . . . . . . . . . . . . . . . . . . . . . . . 2.5 evaluatiemethoden . . . . . . . . . . . . . . . . . . . . . . . .

6 6 6 7 7 8 8 10

3 theoretische aanpak 11 3.1 Diffunderende geur modelleren als gauss verdeling . . . . . . 12 3.1.1 De modellering van gas verspreiding in de tijd . . . . . 12 3.1.2 modellering van geur-diffusie binnen het framework van Vertex-Ant-Walk . . . . . . . . . . . . . . . . . . . 13 3.1.3 modellering van geur-diffusie als convolutie . . . . . . 13 3.1.4 implementatie: discrete versus continue convolutie . . 14 3.1.5 implementatie van discrete convolutie . . . . . . . . . 14 3.1.6 muren . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.7 verschillende schalen . . . . . . . . . . . . . . . . . . . 16 3.2 Convergentie/total coverage van ons algoritme . . . . . . . . 17 3.2.1 De bovengrens aan de convergentiegarantie van ons algoritme . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.2 quantitatieve analyse van de grootte van σ en de convergentie garantie . . . . . . . . . . . . . . . . . . . . 18 3.2.3 muren en de convergentie garantie grens . . . . . . . . 19 3.3 convergentie garantie voor een n aantal stappen . . . . . . . . 21 3.3.1 de relatie tussen theorie en implementatie aangaande geurdiffusie . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2 De standaard deviatie van een gauss verdeling na n convoluties met een kernel . . . . . . . . . . . . . . . . 22 3.3.3 Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4 Convergentie garantie voor een arbitraire graaf . . . . . . . . 24 3.4.1 Kan convergentie u ¨berhoubt gegarandeerd worden met diffusie? . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4

Software, het simulatie platform. 25 4.1 Ontwerp beslissingen . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Het uiteindelijke ontwerp . . . . . . . . . . . . . . . . . . . . 27

2

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

27 29 29 29 29 30 30 31 31 31

5 resultaten 5.1 Resultaten voor een leeg level . . . . . . . . . . . . . . 5.1.1 het effect van veel muren, gangen en kamertjes 5.1.2 Het effect van het aantal mieren . . . . . . . . 5.1.3 de variatie in spreiding met en zonder diffusie .

. . . .

. . . .

. . . .

. . . .

32 32 32 34 34

4.3 4.4 4.5 4.6

4.2.1 potu . . . . . . . . . . . . . 4.2.2 smellGrid . . . . . . . . . . 4.2.3 levelGrid . . . . . . . . . . 4.2.4 opbouw grafische weergave 4.2.5 control . . . . . . . . . . . . 4.2.6 levels . . . . . . . . . . . . moeilijkheden . . . . . . . . . . . Handleiding . . . . . . . . . . . . TODO . . . . . . . . . . . . . . . Ide¨en . . . . . . . . . . . . . . . .

6 conclusie 7 Vervolg onderzoek 7.1 patroontjes kijken

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

36 36 . . . . . . . . . . . . . . . . . . . . . . . . 39

8 Bibliography

43

3

Lijst van figuren 1

2

3

4 5

6

7

8

9

10

11

12

Een typische percentage verkend grafiek. in dit geval heeft de groene lijn een lagere rate of covering dan de blouwe lijn. Door tijdgebrek staat er langs de y as geen percentage maar absolute waarden. Het totaal aantal tiles is 1600. . . . . . . . 2 grafen waarbij de rode vertices bezocht zijn. de verspreidings score is er onder aangegeven. Het is duidelijk te zien dat goed verspreide bezochte vertices een lagere score halen dan het zelfde aantal slecht verspreidde vertices. . . . . . . . Een typische mean distance grafiek, waarin de gemiddelde afstand van alle vertices tot verkende vertices is uitgezet tegen de tijd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diffunderende geur wordt gemodelleerd als een gaussverdeling die steeds verder ¨ınzakt¨ın de tijd. . . . . . . . . . . . . . . . . Het verschil tussen het effect van discrete convolutie en continue convolutie is bij een laag aantal convoluties duidelijk zichtbaar. Dit verschil convergeert echter naar 0 bij een toenemend aantal convoluties . . . . . . . . . . . . . . . . . . . . De twee overwogen methoden. Het verschil tussen de twee is nog niet geheel duidelijk. Uiteindelijk is de rechter methode gekozen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Gauss verdelingen en de som van die twee gauss Verdelingen. de zwarte punten geven vertices aan. Merk op dat de middelste vertex hier een hogere geurwaarde heeft dan de twee vertices waar de geur oorspronkelijk vandaan komt. . . . In dit figuur is te zien hoe de eerste en tweede afgeleides van een gauss verdeling er uit zien. Merk op dat in de tweede afgeleide de snijpunten met de x as precies op afstand sigma(de standaard deviatie van een gauss) van het middelpunt van de gaussverdeling liggen. . . . . . . . . . . . . . . . . . . . . . . Een gauss verdeling met zijn virtuele gespiegelde tegenhanger. Dit spiegeleffect is een gevolg van onze modellering van geur bij muren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theoretisch wordt geurverspreiding opgevat als convolutie met een continue gauss kernel. In onze implementatie wordt echter voor elke vertix een percentage geur aan de buren af gestaan. In een open veld zonder muren is deze aanpak gelijk aan convolutie met een discrete kernel met sigma = 1 − a. . . Prestaties in een level zonder muren. De snellere daling bij diff = 0.01,0.10 geeft een snellere verspreiding door het level weer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prestaties in een level zonder muren. Opvallend is de afbuiging van de lijn met hoge diffusie . . . . . . . . . . . . . . . . 4

10

11

12 13

15

16

17

19

20

21

33 33

13 14

15 16 17 18 19 20 21 22 23 24

25

Prestatie in een gecompliceerd level. Hier is een hoge diffusie iets beter in staat snel tot een hoge spreiding te komen. . . . Prestatie in een gecompliceerd level. Nog steeds zit er een knik in de lijn met hoge diffusie maar dit gebeurt na een groter aantal iteraties . . . . . . . . . . . . . . . . . . . . . . level6 leeg varAnts Diff000 . . . . . . . . . . . . . . . . . . . . level6 leeg varAnts Diff001 . . . . . . . . . . . . . . . . . . . . Zonder diffusie er er veel spreiding in de resultaten van verschillende test runs. . . . . . . . . . . . . . . . . . . . . . . . Met diffusie is er veel minder spreiding in de resultaten van verschillende testruns. . . . . . . . . . . . . . . . . . . . . . . 4 way walk en diffusie, met 2 diffusie stappen voor 1 ant walk 4 wayWalk en 8 way Diffusion . . . . . . . . . . . . . . . . . 4 way Walk and Diffusion in maze level . . . . . . . . . . . . 8way walk and diffusion . . . . . . . . . . . . . . . . . . . . . 4way walk, 8 way diffusion, emptyLevel . . . . . . . . . . . . Dit plaatje is verkregen met een random ruis in de gemeten intensiteiten. De ruis is maximaal 20% van de eigen intensiteit. Op deze manier hebben we sensorvervuiling nagebootst. No diffusion, level maze, 8 way Walk . . . . . . . . . . . . . .

5

34

35 35 36 37 37 39 40 40 41 41

42 42

1 1.1

inleiding inleiding en aanverwant werk

Dit bachelor project gaat over het effici¨ent verkennen van een onbekende ruimte. Het enorme scala aan methoden dat op dit probleem toegepast kan worden is snel terug gebracht tot multi-agent exploratie. Ook over dit subonderdeel van verkennen wordt enorm veel gepubliceerd, vanuit verschillende invalshoeken. Centraal staat het Artikel van I.A Wagner, M. Lindenbaum en A.M.Bruckstein [9]. Dit bleek erg interessant en een goed aanknopingspunt voor verder onderzoek. Aangezien dit paper een belangrijke plaats in neemt in ons project, zal de inhoud er van in het volgende hoofdstuk nader worden besproken.

1.2

onderzoeksvraag

In dit verslag proberen we antwoord te geven op de volgende onderzoeks vraag: Is de werking van Vertex-Ant-Walk verbeteren door het implementeren van diffunderende geursporen?

2 2.1

theorie Uitleg hoofd artikel

Zoals eerder genoemd is er ´e´en paper waar ons project zich grotendeels op baseert. Dit is het paper ’DISTRIBUTED COVERING BY ANT-ROBOTS USING EVAPORATING TRACES’ Van I.A Wagner, M. Lindenbaum en A.M.Bruckstein. In dit artikel worden de eigenschappen onderzocht van een groep robots die alleen communiceren door middel van het achterlaten van geursporen, en tot doel hebben een onbekend gebied te doorkruisen. Nauwkeuriger gesteld: de ant-robots manoeuvreren over een een arbitrair verbonden graaf en geven elke tijdstap geur af op hun positie. De enige informatie waar de ant-robots over kunnen beschikken zijn de geurwaarden in hun directe omgeving. Deze geurwaarden nemen af in de tijd zodat een mier kan achterhalen in welke richting er voor het laatst een mier is langs gekomen.Voor het gedrag van de ant-robots worden in het paper 3 vergelijkbare algoritmen tegen elkaar afgezet. Het laatste algoritme is de basis van ons simulatieplatform. In de volgende paragrafen worden de werkingen eigenschappen van dit algoritme verder verduidelijkt

2.2

Vertex-Ant-Walk; definitie

In hoofd artikel worden 3 ant-walk algoritmen vergeleken. Bij 2 hiervan wordt geur afgegeven aan de connectie tussen 2 vertices van een graaf. Bij het derde algoritme wordt geur afgegeven op de vertex zelf. Dit laatste 6

algoritme wordt Vertex-Ant-Walk genoemd. Formeel ziet het er als volgt uit: def Vertex-Ant-Walk(u vertex;) A t := t − 1 B vind een vertex v in N (u) zodat s(v) = minω∈N (u) {s(ω)}; (als er meer dan 1 v voldoet moet er een heuristische keuze gemaakt worden) C /*leg geur neer op de plek waar je staat*/ set s(v) := t; D go to v; end Vertex-Ant-Walk met u ∈ V (G) de de vertex waar de mier zich bevind op tijd t, en V (G) de verzameling vertices in de graaf. N (u) is de verzameling aangrenzende vertices in u.

2.3

Vertex-Ant-Walk; resultaten

Er wordt door Wagner, Lindenbaum en Bruckstein een belangrijke eigenschap van het algoritme bewezen; dat in eindige tijd altijd alle verbonden vertices bezocht worden(van nu af aan convergentie genoemd). Ook wordt er een bovengrens gesteld aan het aantal tijdstappen dat nodig is om dit te bereiken. Het bewijs voor- en de boven grens aan totale coverage van een graaf komen later weer terug in dit verslag. Daarom wordt er hier meer uitleg gegeven over deze twee eigenschappen.

2.3.1

bewijs voor convergentie van Vertex-Ant-Walk

Er zijn een aantal begrippen die voor het bewijs van belang zijn: flow Het bewijs dat in het paper gegeven wordt voor het convergeren naar een situatie waarin alle vertices bezocht zijn steunt op het begrip flow. Hierbij is f (u, v) de flow van van vertex u naar v, met (u, v) ∈ V . Flow is gedefinieerd als het aantal bezoeken van een mier aan een vertex. Pu Pu is gedefinieerd als de volgorde waarin de buur vertices van vertex u bezocht worden. als een ant-robot bijvoorbeeld vanuit u naar v gaat, wordt v toegevoegd aan Pu . Het bewijs zelf gaat als volgt:

7

lemma 1 Voor elke vertex u ∈ V , is Pu periodiek met gu , waarbij gu de graad van vertex u is. De graad is het aantal buren dat u heeft. bewijs: het algoritme kiest altijd de vertex met de laagste geurwaarde. Als vanuit vertex u v gekozen word. zal er in v geur neergelegd worden, waardoor v bij een volgende keuze in u niet gekozen zal worden. Omdat geur langzaam vervliegt zal de laatst bezochte buur vertex van u altijd het minst aantrekkelijk zijn om nogmaals te bezoeken vanuit u. Pas nadat alle buren van s bezocht zijn, zal v weer de meest aantrekkelijke vertex zijn om heen te bewegen. omdat u gu buren heeft, is gu de periode van Pu . 1. lemma 2 Laat vertices v en w allebei buren zijn van u. Dan is op basis van lemma 1 te stellen dat f (u, v) niet veel zal verschillen van f (u, w). Oftewel: het kan, doordat Pu cyclisch is, niet zo zijn dat |f (u, v)f (u, w)| > 1. Hierdoor worden alle buren van u uiteindelijk bezocht. Aangezien u alle vertices in een graaf kan zijn, worden uiteindelijk alle vertices in een graaf bezocht. 2.3.2

Upper bound voor convergentie tijd Vertex-Ant-Walk

in het hoofd artikel wordt een upper bound gegeven voor het aantal tijdstappen waarin totale coverage plaats zal vinden. Deze wordt gegeven door

tk ≤

n∆d k

met tk het aantal stappen tot totale coverage , n het aantal vertices in de graaf, ∆ de maximum graad van een vertex in de graaf, d de diameter van de graaf en k het aantal robots. Het bewijs voor deze formule is te vinden in het hoofd artikel.

2.4

doel van ons project

Tot nu toe is alleen het paper besproken dat de basis is van ons project. In deze paragraaf wordt duidelijk gemaakt wat we zelf gaan doen. In het paper van Wagner, Lindenbaum en Bruckstein worden, in verband met hun bevindingen, een aantal zaken genoemd die interessant zouden kunnen zijn voor vervolgonderzoek. Een van deze zaken is het aspect van rate of covering van de algoritmen. er staat letterlijk: Rate of covering: The amount of covering per unit of time is not at all constant during execution . . . . . . In some applications(e.g. surveillance) it maybe better to choose a ’quick and dirty’ algorithm that covers a significant part of the area in a short time, rather than one wit a shorter time of total covering. 8

Het doel van ons project is om zo’n ”quick and dirty”methode te maken. Specifieker: om een algoritme te maken dat sneller een groter percentage van de graaf heeft doorlopen dan Vertex-Ant-Walk. Dit mag ten koste gaan van eventuele slechtere prestaties bij het doorlopen van de laatste paar overgebleven vertices.

9

Figuur 1: Een typische percentage verkend grafiek. in dit geval heeft de groene lijn een lagere rate of covering dan de blouwe lijn. Door tijdgebrek staat er langs de y as geen percentage maar absolute waarden. Het totaal aantal tiles is 1600.

2.5

evaluatiemethoden

De prestaties van Vertex-Ant-Walk en het nieuwe algoritme zullen op 2 manieren worden beoordeeld. Rate of covering Het concept ”rate of covering” wordt inzichtelijk gemaakt door het gebruik van een grafiek die het percentage verkende vertices afzet tegen het aantal tijdstappen(zie figuur 1). In zo’n grafiek is aan de helling op het punt t te zien hoe snel er nieuwe vertices verkend worden. Deze grafiek vorm is overgenomen uit de scriptie ”Gericht ronddolen”van Paul R. Laan. Spreiding van verkende vertices in de graaf De ”percentage verkend”grafiek geeft direct informatie over de snelheid waarmee nieuwe vertices ontdekt worden. Een nadeel van deze grafiek is echter dat er geen enkele spati¨ele informatie uit af te lezen is. Dat wil zeggen: Het wordt niet duidelijk hoe de verkende vertices verdeeld zijn in de graaf. Deze informatie is, met name aangaande ”surveillance¨applicaties, misschien wel belangrijker dan de rate of covering. Het is bij dat soort applicaties immers veel belangrijker alle plekken een ongeveer gezien te hebben dan om ´e´en plek zeer zorgvuldig terwijl de rest onderkend blijft. Om het concept ”spreiding van verkende vertices” inzichtelijk te maken is er gekozen voor de maat ”gemiddelde afstand tot een verkende

10

vertex”. Wiskundig ziet dit er als volgt uit: spreiding =

1 X minv∈B(G) {d(u, v)} n u∈V (G)

met n het aantal vertices in graaf G, V (G) de verzameling vertices in G, B(G) de verzameling bezochte vertices in G en d(u, v) de afstand tussen u en v Dit houdt in dat van alle vertices in een graaf het minimaal aantal stappen bepaald word dat gedaan moet worden om bij een verkende vertex te komen. Merk op dat als V (G) = B(G) (alle vertices zijn verkende vertices), d(u, v) = 0 voor alle u, v. hierdoor wordt de spreiding ook 0. Bij hetzelfde aantal verkende tiles geeft deze maat een hoge waarde aan een graaf waar alle verkende vertices op ´e´en hoop zitten, en een lage waarde aan een graaf waar de verkende vertices egaal verspreid zijn(zie figuur 2).

Figuur 2: 2 grafen waarbij de rode vertices bezocht zijn. de verspreidings score is er onder aangegeven. Het is duidelijk te zien dat goed verspreide bezochte vertices een lagere score halen dan het zelfde aantal slecht verspreidde vertices. Uitgezet tegen de tijd ontstaat er typisch een zelfde vorm grafiek als voor de rate of covering,alleen omgedraaid(zie figuur 3.

3

theoretische aanpak

Zoals eerder vermeld is het doel van ons project om een algoritme te maken dat sneller een groter percentage van de graaf heeft doorlopen dan VertexAnt-Walk. oftewel: het ontwerpen van een algoritme dat een hogere ”rate of covering” heeft dan Vertex-Ant-Walk.

11

Figuur 3: Een typische mean distance grafiek, waarin de gemiddelde afstand van alle vertices tot verkende vertices is uitgezet tegen de tijd.

het Vertex-Ant-Walk algoritme maakt gebruik van geursporen die in de tijd vervliegen. Deze geur vervliegt echter in het niets, het verdwijnt. In dit project wordt er een aanpassing gemaakt op die regel; In plaats van te verdwijnen met de tijd, diffundeert de geur met de tijd. Dit betekent dat er geen geur verdwijnt maar alleen geur verspreid over de graaf. Geur wordt in ons algoritme als gas gezien, en wordt als zodanig opgevat als verdeeld volgens een gauss(/normaal)verdeling(zie figuur 4 op pagina 13). In de volgende paragraaf wordt dit idee verder uitgewerkt.

3.1

Diffunderende geur modelleren als gauss verdeling

Zoals gezegd wordt geur in ons algoritme opgevat als gas, dat zich met de tijd gauss-verdeeld verspreidt door de omgeving. Voordat deze opvatting gebruikt kan worden in het algoritme, is er een aantal zaken dat aandacht vraagt: 3.1.1

De modellering van gas verspreiding in de tijd

Een gas(of vloeistof) zal zich, afhankelijk van de eigenschappen van de omgeving en het gas zelf, snel of langzaam verdelen in de omgeving. De verspreiding van de gasdeeltjes zal toenemen met de tijd maar zal altijd gaussisch verdeeld zijn. Wat er gebeurt met de gauss verdeling in de tijd is dat de parameter standaard deviatie (van nu af aan sigma genoemd) toeneemt. Een verspreidend gas is te modelleren als gauss verdeling met toenemende sigma.

12

Figuur 4: Diffunderende geur wordt gemodelleerd als een gaussverdeling die steeds verder ¨ınzakt¨ın de tijd.

3.1.2

modellering van geur-diffusie binnen het framework van Vertex-Ant-Walk

De meest voor de hand liggende methode om geur-diffusie te modelleren in Vertex-Ant-Walk is om op elk punt in de graaf waar zich geur bevindt een gauss(sigma) te sampelen en per tijdstap alle sigma’s te verhogen. Deze aanpak vereist echter dat voor elke vertex m samples moeten worden berekend. Hierdoor moet bij n met geur gevulde vertices de gauss formule −(x−µ)2

f (x, σ) = σ√12π e 2σ2 per tijdstap m ∗ N keer berekend worden. Hier komt nog bij dat als een meerdere malen van geur wordt voorzien, er voor elke geur apart een gauss sampling moet worden gemaakt. Dit is computationeel niet erg aantrekkelijk. Er is een betere manier. 3.1.3

modellering van geur-diffusie als convolutie

De convolutie van 2 gaussverdelingen levert een nieuwe gaussverdeling op. De sigma’s van deze gauss verdelingen verhouden zich als volgt: q

gauss(σo ) ? gauss(σk ) = gauss( σo2 + σk2 ) Als een geur verdeling herhaaldelijk geconvolueerd wordt met de zelfde gaussverdeling zal de geurverdeling steeds verder ¨ınzakken”(zie figuur 4).

13

De gaussverdeling waarmee herhaaldelijk geconvolueerd wordt wordt vanaf nu de kernel genoemd. De sigma van de kernel (σk ) heeft direct invloed op de snelheid waarmee de geur inzakt; Een grote σk zorgt per tijdstap voor grote toename van de sigma van de geurverdeling en dus een grotere inzakking van de geur, en vica versa voor een kleine σk . Met σk is dus de diffusie snelheid van de geur te regelen. Computationeel is convolutie veel aantrekkelijker; alle vertices in de graaf hoeven maar 1 keer met een kernel geconvolueerd te worden. Convolutie vraagt slechts een beperkt aantal vermenigvuldigingen en optellingen per vertix, significant minder dan het sampelen van een gauss op elke vertix. Ten minste: discrete convolutie vergt significant minder rekenwerk. En dit is wat ons algoritme implementeert. In de volgende sectie wordt dit uit gelegd. 3.1.4

implementatie: discrete versus continue convolutie

Ons algoritme, net als Vertex-Ant-Walk, gebruikt een discrete basis. Namelijk de vertices van de graaf waarover de ANT-ROBOTS bewegen. hierdoor is het practisch om ook de geur op dezelfde schaal te sampelen(zie 3.4: verschillende schalen), en geur te laten inzakken door discrete convolutie op die schaal. Een belangrijk punt bij de keuze voor discrete convolutie, is de verhouding tussen discrete en continue convolutie. In relatie tot ons algoritme is het vooral van belang te weten of convolutie van een gauss(geur) verdeling met een discrete kernel hetzelfde effect heeft als convolutie met een continue kernel. Gelukkig blijkt dit in grote lijnen het geval. het blijkt dat: limn→∞ kD(σ0 , n) - C(σ0 , n)k = 0 met σ0 de standaard deviatie van de originele gauss verdeling, D(σ0 , n) de grootte van σ0 na n discrete convoluties en C(σ0 , n) de grootte van σ0 na n continue convoluties. deze convergentie naar 0 gaat snel: Zie figuur 5 op basis van deze gegevens wordt de aanname gemaakt dat discrete- en continue convolutie equivalent zijn. Hierdoor is het mogelijk het gedrag van elementen van ons (discrete)algoritme te voorspellen op basis van continue wiskunde(zie sectie 3.3.3 op pagina 23). 3.1.5

implementatie van discrete convolutie

Er is gekozen om convolutie met een discrete kernel te gebruiken om geur diffusie te modelleren. De implementatie van deze convolutie wijkt echter lichtelijk af van het gebruikelijke 14

Figuur 5: Het verschil tussen het effect van discrete convolutie en continue convolutie is bij een laag aantal convoluties duidelijk zichtbaar. Dit verschil convergeert echter naar 0 bij een toenemend aantal convoluties

3.1.6

muren

Het grootste deel van de problemen bij het modelleren van diffunderende geur in een graaf is nu besproken. Er blijft echter een belangrijk punt dat vooral te maken heeft met de de practische applicatie van ons algoritme: Muren. Althans: er kan van ”muren”gesproken worden in het geval van het ontbreken van een verbonding in een regelmatig verbonden graaf die een 2d of 3d raster voorstelt (hetgeen bij onze simulaties gebeurt). In het meer algemene geval kan het probleem als volgt gedefinieerd worden: hoe verhoudt de geurverdeling zich tussen twee vertices met afwijkende connectieviteit? Om enigzins realistische geurverdeling te modelleren moet het zo zijn dat een vertix met een groot aantal verbindingen veel geur afstaat, en een vertix met weinig verbindingen weinig. Er zijn twee methoden overwogen(zie figuur 6 op pagina 16). Uiteindelijk is de tweede methode gekozen, omdat deze methode een ”gauss spiegeling¨ımplementeert(zie figuur 9 op pagina 20) implementeert. Aangenomen wordt dat dit een goede benadering is van realistisch gedrag van gassen. Dit is echter een redelijk ongefundeerde aanname. Dit is echter geen groot probleem omdat ook aangenomen wordt dat een perfecte modellering van het gedrag van gassen niet noodzakelijk is voor het functioneren van ons algoritme. Door deze aanpassing aan het gedrag van geurdiffusie is deze in ons

15

Figuur 6: De twee overwogen methoden. Het verschil tussen de twee is nog niet geheel duidelijk. Uiteindelijk is de rechter methode gekozen.

project niet meer compleet op te vatten als convolutie. Dit is alleen mogelijk zo lang er geen geen muur (afwijkende connectieviteit) in de graaf aanwezig is. Voor de theoretische resultaten die in dit verslag naar voren komen is de aanwezigheid van muren echter geen probleem(zie sectie 3.2.3 op pagina 19) 3.1.7

verschillende schalen

Een laatste punt aangaande het modelleren van geur in een discrete omgeving is de verhouding tussen de schalen van stapgroote en geurdiffusie. Het is mogelijk om geur zeer nauwkeurig te laten verspreiden door geur per vertix op meerdere plekken te sampelen. Ook is het mogelijk een zeer grof geurgrid te definieren waardoor meerdere vertices dezelfde geurwaarde krijgen. Er is uiteindelijk gekozen om de samplegroote voor de geur en voor de stappen van de ANT-ROBOTS samen te laten vallen. een reden hiervoor is dat vooronderzoek en simulaties uitwijzen dat het gedrag van het algoritme niet significant beter of slechter wordt van variaties in de schalen. De andere reden voor deze keuze is een practische: gelijke geurgrid zijn conseptueel eenvoudiger en er is niet genoeg tijd om diep op dit onderwerp in te gaan.

16

3.2

Convergentie/total coverage van ons algoritme

Een van de belangrijkste theoretische resultaten aangaande in het hoofd artiekel is het bewijzen van de convergentie van Vertex-Ant-Walk. Dat wil zeggen: de eigenschap dat gegeven genoeg tijd, alle vertices in een graaf gegarandeerd bezocht zullen worden. Juist deze eigenschap geldt niet altijd voor ons algoritme. Deze eigenschap geldt alleen binnen bepaalde grenzen, die in de volgende secties gegeven zullen worden. 3.2.1

De bovengrens aan de convergentiegarantie van ons algoritme

Voor het Vertex-Ant-Walk algoritme is convergentie bewezen op basis van de periodiciteit in de bezoeken aan neighbours van een vertex u (zie 2.3.1). Deze periodiciteit is bij diffusie van geur niet oneindig lang gegarandeerd. Hierdoor kan er een groot verschil in flow optreden tussen de buren van u. Anders gezegd: bij diffunderende geur is het mogelijk dat er na een tijd een vertex is die nog nooit bezocht is, maar wel een hogere geurwaarde heeft dan zijn buur-vertices. Hierdoor wordt deze vertix vervolgens nooit bezocht. Dit fenomeen heeft te maken met de vorm van de gauss verdeling. 2 gauss verdelingen kunnen namelijk optellen tot een convexe functie(zie figuur 7) Wanneer dit precies gebeurt wordt in de volgende sectie uitgelegd

Figuur 7: 2 Gauss verdelingen en de som van die twee gauss Verdelingen. de zwarte punten geven vertices aan. Merk op dat de middelste vertex hier een hogere geurwaarde heeft dan de twee vertices waar de geur oorspronkelijk vandaan komt.

17

3.2.2

quantitatieve analyse van de grootte van σ en de convergentie garantie

Zoals gezegd kan een niet bezochte vertex u ’onbereikbaar’ worden wanneer 2 buren van u, v en w, een gauss(geur) verdeling hebben met een voldoende grote verspreiding. Oftwel met een voldoende grote σv , σw (zie figuur 7 op pagina 17). Met ’onbereikbaar’ wordt bedoeld dat een vertex u een hogere geurwaarde krijgt dan zijn buren, terwijl u zelf niet direct geur ontvangen heeft. In verband hiermee blijkt de volgende regel te gelden: Stelling In een graaf G is het alleen mogelijk dat een vertex u ’onbereikbaar’ wordt wanneer er twee Gauss verdelingen Gauss(σv ),Gauss(σw ) bestaan, waarvoor geldt: σv = σw ≥ 1 Dit resultaat is verkregen op de volgende manier: stap 1 stel een vertex u ∈ V (G), met buur-vertices v, w ∈ V (G). v en w zijn beide bezocht, u niet. de enige geur die u dus ontvangt is diffusie van v en w. Over de 3 vertices ligt dus een geurverdeling die op elke plaats x de som is van de twee gauss verdelingen op v en w, genoemd g(σv , σw , x) . u wordt ’onbereikbaar’ wanneer de top van die geur verdeling boven u komt te liggen. Dit gebeurt wanneer op g(σv , σw , x) het dal overgaat in een piek. Oftwel; als g(σv , σw )00 (de tweede afgeleide boven u) negatief wordt. stap 2 Zoals te zien in figuur 7 geldt g(σv , σw )00 = 0 wanneer de buigpunten van gaussv (σv ) en gaussw (σw ) elkaar raken. Gelukkigerwijs ligt het buigpunt van een gauss(σ) verdeling precies op afstand σ van het middelpunt van die gauss. stap 3 de afstand tussen de middelpunten van gaussv (σv ) en gaussw (σw ) is 2 (zie figuur 7 op pagina 17). de twee buigpunten van gaussv (σv ) en gaussw (σw ) raken elkaar dus als σv = σw = 1. Als σv en σw kleiner worden, wordt g(σv , σw )00 = 0 daar positief (zie weer plaatje). Er komt dan op dat punt een dal te liggen. Als dat gebeurt, is g(σv , σw , u) niet meer het hoogste punt, en zal u gewoon bereikbaar zijn vanuit u en w omdat u een lagere geurwaarde heeft. stap 4 Aangenomen dat de sample grootte voor geur gelijk is aan de stapgrootte, is dit resultaat inderdaad worst-case. Met andere woorden: de afstand 2 is de minimale afstand tussen 2 gauss verdelingen waar nog 1 vertix tussen is die mogelijk onbezocht is. Als de twee nog dichter bij elkaar zouden liggen zouden ze buren zijn. Hierdoor kan het volgende gesteld worden. Als er in een graaf geen 2 geurverdelingen Gauss(σv ),Gauss(σw ) zijn met σv = σw ≥ 1, dan zijn alle vertices nog op een of andere manier bereikbaar.

18

Figuur 8: In dit figuur is te zien hoe de eerste en tweede afgeleides van een gauss verdeling er uit zien. Merk op dat in de tweede afgeleide de snijpunten met de x as precies op afstand sigma(de standaard deviatie van een gauss) van het middelpunt van de gaussverdeling liggen.

3.2.3

muren en de convergentie garantie grens

Een belangrijk punt van aandacht met betrekking tot de convergentie grens van σv = σw ≥ 1, is het volgende. Kan het zo zijn dat door reflectie van een gauss verdeling op een muur, een vertex onbereikbaar wordt bij een lagere waarde dan 1? Dit blijkt gelukkig niet het geval. Gelukkig, omdat hierdoor niet op de specifieke structuur van de graaf gelet hoeft te worden bij het geven van grenzen aan de convergentie. De redenering voor dit resultaat gaat als volgt: stap 1 De methode die gebruikt wordt om om te gaan met geurverdeling bij muren implementeert een reflectie van die geurverdeling(zie hoofdstuk daarover). Beschouw figuur 9 op pagina 20.Stel a als de afstand 19

Figuur 9: Een gauss verdeling met zijn virtuele gespiegelde tegenhanger. Dit spiegeleffect is een gevolg van onze modellering van geur bij muren.

tussen het middelpunt van de orginele gauss Go en een muur, kan de spiegeling van Go in een muur gezien worden als een andere, virtuele gespiegelde gaussverdeling Gs op afstand 2a. stap 2 Stel vervolgens x = de afstand van een meetpunt tot het middelpunt van een Go . De afstand van x tot de middelpunten van Go en Gs (d(x, Go ) en d(x, Gs ) respectievelijk), kan dan als volgt gedefinieerd worden. d(x, Go ) = x d(x, Gs ) = 2a − x Hieruit kan worden afgelezen dat d(x, Go ) > d(x, Gs ) wanneer x > 2a − x oftewel wanneer a > x. Hier staat dat de afstand van een punt x tot de orginele gauss verdeling Go alleen kleiner is dan de afstand tot de gespiegelde gaussverdeling Gs wanneer a > x oftwel wanneer x voorbij de grens van de muur ligt. Aangezien er aangenomen wordt dat er geen geur kan zijn in een muur, kan er gesteld worden dat de orginele gaussverdeling altijd dichter bij een punt x ligt dan de gespiegelde gaussverdeling, of even ver. stap 3 Uit de vorige stap valt te concluderen dat de invloed van een gaussverdeling Go op een punt x altijd groter of gelijk is aan de invloed van de spiegeling Gs van Go . Met het oog op de convergentiegarantie zal bij toenemende σ het buigpunt van Go (op afstand σ) ook altijd eerder of gelijk aankomen op een punt x. Als er op punt x dus 2 buigpunten samenkomen waardoor er mogelijk vertices onbereikbaar worden, zal dit altijd zijn op basis van de orginele buigpunten van Go . De aanwezigheid van muren heeft hierdoor geen invloed op convergentie garantie.

20

3.3

convergentie garantie voor een n aantal stappen

In (sectie 3.1.3 op pagina 13) is aangegeven hoe de standaard deviatie (σ) van een gauss verdeling verandert door convolutie met een kernel. In (sectie 3.2 op pagina 17)is aangetoond dat het mogelijk is dat er vertices onbereikbaar worden wanneer er 2 gauss verdelingen zijn met σ ≥ 1. In deze sectie worden deze twee zaken met elkaar verbonden, om te komen tot een voorspelling van het aantal geurdiffusie stappen dat gedaan kan worden voor dat er mogelijk vertices onbereikbaar worden. 3.3.1

de relatie tussen theorie en implementatie aangaande geurdiffusie

Theoretisch wordt geur in ons project gemodelleerd als continue gauss verdeling, waarbij geur diffusie een convolutie is met een kernel. In onze implementatie wordt dit echter een discreet gesampelde gauss verdeling en wordt diffusie op de volgende manier geimplementeerd(zie ook hoofstuk 4 over software implementatie): geef op elke vertex een percentage van de geur van die vertex aan de buren van die vertex(zie figuur 10 op pagina 21).

Figuur 10: Theoretisch wordt geurverspreiding opgevat als convolutie met een continue gauss kernel. In onze implementatie wordt echter voor elke vertix een percentage geur aan de buren af gestaan. In een open veld zonder muren is deze aanpak gelijk aan convolutie met een discrete kernel met sigma = 1 − a. In een open veld (oneindige graaf) implementeert onze methode precies 21

discrete convolutie met een kernel. In een veld met muren (eindige graaf) zorgt de omgang met die muren er voor dat de geurdiffusie lichtelijk afwijkt van discrete convolutie. maar deze afwijking heeft geen invloed op de theoretische resultaten (zie sectie 3.2.3 op pagina 19). Hier volgt een lijst met elementen uit de implementatie en hun relatie tot de theorie. Geurdiffusie door geur af te geven aan buur-vertices Beschouw figuur 10 op pagina 21 de standaard deviatie σk van de kernel is gelijk aan 1 − a waarbij a het deel van de geur is dat overblijft in een vertex na een convolutie met de kernel. Een discrete convolutie met een kernel met standaard deviatie σk is (afgezien van muren) gelijk aan het afgeven van een σk deel van de geur aan de buur-vertices Het neerleggen van geur door een ant-robot Elke tijdstap wordt er door een ant-robot een geur neer gelegd op de vertex waar deze zich op dat moment bevindt. Dit moet een compleet geconcentreerde geur zijn. In onze implementatie wordt dit gerepresenteerd door alle geurwaardes op vertices waar zich Ant-Robots op te hogen met een vaste waarde ∆ (zie hoofdstuk 4 over software implementatie). Theoretisch wordt deze geur opgevat als een (continue) gauss verdeling met σ = 0 (of als een deltapuls wanneer ∆ = 1) 3.3.2

De standaard deviatie van een gauss verdeling na n convoluties met een kernel

Zoals eerder vermeld geldt er voor ´e´en convolutie van een gauss verdeling gauss(σo ) met een gauss kernel gauss(σk ) het volgende: q

gauss(σo ) ? gauss(σk ) = gauss( σo2 + σk2 ) Voor 2 convoluties van gauss(σo ) met gauss(σk ) geldt dan: rq

(gauss(σo ) ? gauss(σk )) ? gauss(σk ) = gauss(

2

σo2 + σk2 + σk2 )

q

= gauss( σo2 + σk2 + σk2 ) q

= gauss( σo2 + 2(σk2 )) Op de zelfde manier geldt voor n convoluties van gauss(σo ) met gauss(σk ): q

gauss(σ0 n ? gauss(σk )) = gauss( σo2 + n(σk2 ))

22

3.3.3

Conclusie

- In de vorige sectie is aan gegeven wat het verband is tussen n convoluties van een gauss verdeling met een kernel en de σ van de resulterende gauss verdeling. - Eerder is vastgesteld dat er, gegeven een gelijke discrete sampeling voor geur en stapgrootte, mogelijk vertices onbereikbaar worden als er 2 gauss verdelingen zijn met σ ≥ 1 (zie sectie 3.2.2 op pagina 18). in deze sectie worden deze 2 feiten gecombineerd om aan te kunnen geven hoeveel diffusiestappen(convoluties) er gedaan kunnen worden voordat er mogelijk vertices onberijkbaar worden. Er blijkt het volgende verband te gelden: Dov ≤

1 σk2

met Dov (σk ) het aantal diffusiestappen dat gedaan kan worden met kernel Gauss(σk ) met garantie van convergentie De redenatie hier achter gaat als volgt: stap 1 gauss(σo ), n keer geconvolueerd met kernel gauss(σk ) geeft gauss q met een standaarddeviatie van σo2 + n(σk2 ) (zie sectie 3.3.2 op pagina 22) stap 2 Als er 2 gaussverdelingen zijn met σ ≥ 1, kan het zo zijn dat er vertices onbereikbaar zijn. om de uiteindelijk formule eenvoudiger te maken, Wordt convergentie gegarandeerd todat er ´e´en gaussverdeling is met σ ≥ 1, in plaats van twee. Dit zorgt ervoor dat de convergentie grens iets lager wordt. aangezien de grens een ondergrens is, is dit toegestaan. Het lager worden van de convergentie grens heeft te maken met het uitzonderingsgeval waarbij er slechts ´e´en Ant-Robot aanwezig is in een graaf; Deze Ant-robot heeft dan namelijk 1 tijdstap nodig om er voor te zorgen dat er u ¨berhoubt 2 gaussverdelingen zijn in de graaf. Omdat dit een klein verschil is ten opzichte van een gemiddeld aantal tijdstappen wordt het ten behoeve van de duidelijkheid van de formule verwaarloosd. Nu is er te stellen dat er pas onbereikbare vertices kunnen zijn wanneer er ´e´en geur verdeling in de graaf voorkomt met σ ≥ 1 stap 3 op basis van stap 1 en 2 is de volgende formule op te stellen dat er pas onbereikbare vertices kunnen zijn wanneer q

σo2 + n(σk2 ) = 1 ⇒ σo2 + n(σk2 ) = 1 ⇒ n(σk2 = 1 − σo2 ⇒ n = 23

1−σo2 σk2

stap 4 Aangezien een Ant-robot geur neerlegt als gauss(σ) met σ = 0, hebben alle geurverdelingen in de eerste tijdstap(n = 0) maximaal de waarde 0. Hierdoor geldt σo2 = 0. Het aantal convolutiestappen Dov (σk ) dat gedaan kan worden met kernel Gauss(σk ) met behoudt van convergentie garantie, kan hierdoor beschreven worden met de formule Dov ≥ σ12 k

3.4

Convergentie garantie voor een arbitraire graaf

Nu het duidelijk is hoeveel (tijd/diffusie)stappen er gedaan kunnen worden met de garantie dat er geen vertices onbereikbaar worden(zie sectie 3.3.3 op 23), is het eenvoudig om de diffusiesnelheid zo te kiezen dat convergentie gegarandeerd wordt. Er is namelijk eerder een bovengrens gesteld aan het aantal stappen dat nodig is om een arbitraire graaf te doorlopen met Vertex-Ant-Walk(zie 2.3.2 op 8). Convergentie/totale coverage is gegarandeerd wanneer d 1 ≥ n∆ k σ2 k

3.4.1

Kan convergentie u ¨ berhoubt gegarandeerd worden met diffusie?

Een punt van aandacht is dat er bij de vorige sectie gebruik wordt gemaakt van een convergentie garantie op basis van het Vertex-Ant-Walk algoritme, dat geen geurdiffusie toepast. Het is niet van zelf sprekend dat deze argumentatie ook gebruikt kan worden voor ons algoritme. Dit blijkt uiteindelijk echter wel te kunnen. De argumentatie die gebruikt wordt om convergentie te garanderen maakt namelijk gebruik van de volgorde waarin de buren van een vertex u bezocht worden(zie 2.3.1 op 7). Zo lang een onbezochte vertex niet een hogere geurwaarde krijgt dan een bezochte vertex, zal er geen verandering in die volgorde optreden. gelukkig gebeurt dit niet voor dat er 1 stappen zijn gedaan. Hierdoor kan totale coverage gegarandeerd worden σ2 k

tot die

1 σk2

stappen.

24

4

Software, het simulatie platform.

We werden geacht een omgeving te vinden, op voorhand hadden we gekozen om te programmeren in python, dit omdat we daarin veruit het snelst in kunnen ontwikkelen. De volgende extra python libaries zijn we gaan gebruiken. • pygame : Deze libarie bevat functies voor het werken met graphics. hiermee is het heel makkelijk om met grote hoeveelheden verschillende graphics objecten snel te werken. Dit alles is zeer geoptimaliseerd,draait op alle grote platforms en gebruikt hardware versnelling waar mogelijk. • pylab : Een onderdeel van matplotlib, met deze uitbeiding kan makkelijk uit lijsten grafieken worden gemaakt en opgeslagen, het werken hiermee lijkt heel erg op matlab. We hebben scripts gemaakt die tests uitvoeren en vervolgens wegschrijven, en deze resultaten kunnen in een anders script ingelezen worden, waarna er grafieken verschijnen. • wxPython is een GUI toolkit deze wrapt het wxWidget cross platform GUI libary. Hierin is een klein controle programmatje gemaakt waarmee snel levels gekozen kunnen worden, de meest gebruikte instellingen kunnen worden verandert en daarna getest. Zodat niet elke keer variabelen in het script zelf opgezocht en handmatig verandert hoeven worden Ook is gebruik gemaakt van matlab. Dit is vooral gebruikt voor het testen en maken van grafieken voor de wiskundige onderbouwing.

4.1

Ontwerp beslissingen

In het begin waren we nog al ambitieus en met die gedachte is ons programma ook ontwikkelt. Het diffusie gedeelte is losgekoppeld van het level gedeelte dit omdat we eventueel met verschillende resoluties wouden werken. Hier is het niet van gekomen en hiervoor zijn een aantal redenen: 1. de proccesorbelasting voor het uitrekenen van de diffusie is zo dermate hoog is dat het fijner maken van het geur grid het geheel ondoenlijk langzaam zal maken. 2. De mooiere en precisere plaatjes die bij een fijnere Geur resolutie horen zijn ook te krijgen door middel van een Gauss Convolutie 1 van elke pixel. Het figuur op de voorkant van dit verslag is op die manier verkregen. 1

smoothen, betere resultaten krijgt men met een selectieve gauss algoritme

25

3. Een ander idee was het meer bewegings vrijheid geven van de antrobots, hier is ook geen dichte resolutie geur grid voor nodig. Om een meer vrije richting te bepalen zou er met behulp van de omliggende vakjes een vlak uitgerekend kunnen worden waarop de mier de richting van de helling kiest (omlaag). 4. Voor de ondezoeksvraags waren deze functies niet nodig,en de 4 weken die we hebben worden zijn te kort voor al onze idee¨en. Om deze redenen hebben we het idee van een fijner geurgrid laten vallen. Desondanks hebben de diffusie functies een eigen classe gehouden. Het hele programma is door dit modulaire design makkelijk aan te passen en uit te breiden. Het onderzoeksdoel is het verbeteren van de coverage van een onbekende wereld door ant-robots door het toe voegen van diffusie. Om deze verbetering te kunnen aantonen is het nodig onze implementatie te kunnen vergelijken met de in de paper gebruikte simulatie. Alle variabelen die er toe doen zijn op een plekverzamelt, waarmee het aanpassen van het model naar dat van de in de papergebruikte versie een kleine moeite is. Om beter te begrijpen hoe ant-robots zicht gedragen, het debuggen makkelijk te maken en om te kunnen ontdekken of ants zich gedragen zoals verwacht, is het nodig een grafische omgeving te hebben. Dit is zo gedaan dat het testen ook zonder grafische weergave werkt. Aan het scheiden hebben we veel gehad er zijn namelijk veel tests gedaan op OW computers in de practicumzaal en ook voor het debuggen is het grafisch maken van ons simulatie programma onmisbaar gebleken.

26

4.2

Het uiteindelijke ontwerp

Hieronder staat de globale uml-diagram met de belangrijkste functies en attributen waarna een globale uitleg van de classen en hun functies volgt. De classen en attributen voor het grafische gedeelte en de test scripts zijn niet weergegeven.

4.2.1

potu

De ’test omgeving’, hierin staan alle variabelen die van belang zijn voor de experimenten. Er kan een test object aangemaakt worden waarvan de variabelen ingestelt kunnen worden en met de de functie run() kan het geheel getest worden, met of zonder grafische weergave. Omdat python een taal is die net geschreven moet zijn,door het verplicht indenten en het ontbreken van allerlei regels met haken, is het erg leesbaar en verschilt het niet veel 27

van pseudo code. Nu volgt hier een verkort gedeelte van de main loop in potu.run() het hart van ons simulatie platform: while self.Notdone: if display: self.handleEvents() if level.coverd() and not self.pauze: print ’Finished in %d Steps’ % (steps) self.pauze = 1 #1 update smellfield (if swithed on) #2 for each ant calculate new position. #3 drop new smellbomb # ! it must be in this order otherwise ants will join up. if not self.pauze : newAntPosList = [] for Antx in antList: # for each ant find a new position newAntPosList.append(Antx.update(smell)) level.update(Antx.position) smell.dropBomb(Antx.position,self.intensity) # drop stinkbomb # on new position if self.smellUpdate : for i in range(self.smellUpdates): smell.update() # Calculate diffusion # # # # if

1 update all the visual sprites with their new values. 2 draw changes to screen 3 update ant positions 4 draw ant to screen self.displaySmell and display and not self.pauze: """ display smell field """ smellMapSprites.update(smell,level,self.trace) pygame.display.update(smellMapSprites.draw(screen)) antSprites.update(newAntPosList) pygame.display.update(antSprites.draw(screen))

if not steps % self.sampleRate and not self.pauze: self.samples.append(level.meanDistance()) self.discoverdSample.append(level.discovered) if not self.pauze: steps += 1 if self.maxSteps < steps: break 28

4.2.2

smellGrid

module smellGrid.py Deze class is verantwoordelijk voor het diffunderen van geur, en het uitlezen van geurwaarden voor de ant-robot. 4.2.3

levelGrid

Deze classe bevat alle gegevens over de status van het level, heeft functies voor het inladen van een level uit een bestand en heeft functies voor het verzamelen van statistiek zoals het het bepalen van de gemidelde afstand van de velden tot het pad van de mier. levelGrid houd precies bij waar mieren zijn geweest. Voor het bepalen van de afstand zoeken we eerst de vakjes op waar de mier geweest is en maken dat pad elke keer 1 breeder. De vakjes waarvan de afstand is bepaalt breidt zich als een olie vlek uit. 4.2.4

opbouw grafische weergave

Het veld is onderverdeeld in 40 bij 60 vakken van 10 bij 10 pixels, voor elk vakje is apart een object aangemaakt. Elke ronde voeren al deze blokjes een update functie uit welke de nieuwe intensiteit bepaalt en aan de hand daarvan de intensiteit aanpast. De intensiteiten verschillen enorm daarom worden deze met een logaritmische schaal weergegeven. Na wat onderzoek en testen: s 1 −ln(intensity) + 1 Dit bleek dit veruit het beste te werken Hier is ook een redelijk een goede verklaring voor: deze functie maakt een normaal verdeling ongedaan, welke een e macht is. De intensiteiten worden genormalizeerd zodat het meest “stinkende” vakje altijd wit zal zijn. Hierdoor zal als een mier een paar keer over hetzelfde vakje heen gaat het hele scherm donkerder worden. De “mieren” zijn aparte objecten, welke elke beurt een update() uitvoeren die zal de nieuwe positie bepalen en dan zichzelf die nieuwe positie toekennen. De grafische objecten van de mieren zoeken op welke keuze gemaakt is en updaten dan de positie op het scherm. die 4.2.5

control

29

Gebouwd met wxPython, een python wrapper voor een multiplatform gui builder. Hiermee kunnen de meeste relevanten variabelen : level,aantal mieren,diffusie, en de manier van lopen en diffunderen mee verandert worden. 4.2.6

levels

Levels kunnen eenvoudig gemaakt worden, ze bestaan uit een tekst bestanden van 40 regels en 60 tekens met 1 en 0 of m. 1 staat voor muur en 0 voor open ruimte en m staat voor mier. Zodra er een mier in het level staat gedefinieert kan niet meer zelf bepaald worden hoeveel mieren er in een veld worden gezet.

4.3

moeilijkheden

Het grootste obstakel was het snelhouden van het model, er zijn voor een veld van 40 bij 60, 2400 - objecten * 4 of 8 operaties nodig per diffusie update. Dit alles gebeurt met een hele grote nauwkeurigheid van floats in python.In ons geval is de minumale waarde : 1e-323. De gebruikte machine architectuur of de C of java implementaie, is verantwoordelijk voor het uiteindelijke gedrag van floats in python. Voor de verschillende operaties zijn er verschillende datastructuren, veel gebruitk zijn dictionaries met als ’key’ een positie (x,y). Er worden veel lookups gedaan, vooral om een naastliggend veld te updates, mits die geldig is. Er zijn verschillende datastrucuren geprobeert maar het verschil in performance is minimaal,daarom is voor dictionaries gekozen, hiermee is de code schoner korter en makkelijker te begrijpen. Om het geheel te snel te houden hebben is geprobeert het heen en weer gooien van geheugen en het gebruik van loops zo efficient mogelijk te laten zijn. Er word regelmatig gebruik gemaakt van try,catch blokken waarmee een groot aantal controles overboord konden. Een grote perfomance boost kregen we door de psyco module te gebruiken. Dit is een JIT 2 compiler, welke de performance van het geheel minimaal 2x heeft versneld is onze ervaring.3 . 2 3

Just In Time. Compileert versies van de zelfde code en kiest de snelste Als psyco is geinstalleerd is word het gebruikt maar het werkt prima zonder

30

Een moeilijkheid was het goed weergeven van kleuren en gradienten, dit is eerder behandelt.

4.4

Handleiding

Om het model te draaien is python 2.3 of hoger nodig en pygame. Deze zijn goed te installeren op linux en windows en te downloaden van pygame.org en python.org. Na uitpakken kan het geheel gestart worden met: python potu.py Variabelen zijn in potu.py handimatig te veranderen. Het makkelijks is het echter om control.py te starten, hiervoor zal echter ook wxPython 4 geinstalleerd moeten zijn. Als u control.py start met python zult u een schermpje te zien krijgen waarin u gemakkelijk de meeste gebruikte instellingen kunt doen doen en vervolgens het een experiment kan starten.

4.5

TODO

Practische Verbeteringen aan het programma : potu.py Meer informatie in het opgekomen venter, zou niet heel moeilijk moeten zijn met de pygame libarie. Nu word bijvoorbeeld (wanneer op een vakje geklikt word de intensiteit van een vakje in de console weergegeven. smellgrid.py Hier zou verdere snelheids verbeteringen gedaan kunnen worden. control.py Dit kan uitgebeid worden met meer instellings variablen. Maar word dan misschien wel onoverzichtelijk. Ook de mogelijkheid om grafieken te genereren moet nog geimplementeerd worden, dit kan heel makkelijk met de pylab modules.

4.6

Ide¨ en

Een idee zou zijn het path planning van mieren te emuleren. Mieren lopen na een tijdje in een vast spoor van voedsel naar nest. Mieren lijken altijd een redelijk optimale route te vinden. Door gebruik te maken van 2 smellGrids/ 2 geuren zou het mogelijk moeten zijn om dit na te bootsen. In punt A volgen ze de geur van B en zodra ze punt B hebben gevonden volgen ze Geur A. 4

wxpython.org

31

5

resultaten

In deze sectie worden de prestaties besproken van Vertex-Ant-Walk met en zonder diffusie. Dit gebeurt op basis van de evalutiemethoden uit sectie 2.5 op pagina 10. De termen in de legenda zijn: gemiddelde Als deze term voor een legenda item staat, is de corresponderende een gemiddelde van 15 testRuns. diff = X De diffusie constante is in het simulatieplatform gesteld op X. Belangrijk: deze constante geeft het deel geur aan, dat per tijdstap aan ´e´en buurvakje wordt afgegeven. Aangezien alle tests zijn gedaan op een 4-connected grid heeft elk vakje in een muurloos veld 4 buren. Hierdoor geldt voor de standaard deviatie σk van de gauss-kernel σk = 4X. ants Het aantal mieren. noise de error parameter in het simulatieplatform.

5.1

Resultaten voor een leeg level

In figuur 11 vallen een aantal dingen op: Het is duidelijk dat de grafiek m´et diffusie veel sneller valt. Dit betekend dat de verkenningspaden met diffusie veel sneller goed verdeeld zijn door de omgeving. Bij diffusie 0.10 is te zien dat de grafiek net iets hoger afvlakt, maar verder is weinig verschil te zien tussen diff = 0.01 of 0.10. Dat er echter wel degelijk verschillen zijn tussen zwakkere en sterkere diffusie, is te zien in figuur 12. Een opvallend aspect is hier het afbuigen van de lijn met diff = 0.10 na 275 iteraties. Dit effect wordt veroorzaakt door het onbereikbaar worden van vakjes(vertices) door optellende gaussen. In de simulaties is ook goed te zien dat ant robots bij een hoge diffusie na een tijd actief gebaande paden gaan volgen in plaats van nieuwe vakjes te verkennen. Dit gebeurt echter alleen nadat het hele veld min of meer verkend is. Dit is goed te zien aan het samenvallen van het afbuigen in figuur 12 en het bereiken van een minimum in figuur 12) 5.1.1

het effect van veel muren, gangen en kamertjes

De resultaten voor een gecompliceerd level met veel muren en gangen, zijn gegeven in de figuren 13 en 14. Deze zijn grotendeels vergelijkbaar met de resultaten voor een leeg level. Er zijn een aantal opvallende punten: Hoge diffusie(rode lijn) is in een gecompliceerd beter in staat om tot een hoge verdeling in het level te komen.(de afbuiging in de verspreidingsgrafiek vlakt pas later af). Het lijkt bij gecompliceerde omgevingen dus wel nu te hebben om grotere diffusie te gebruiken. 32

Figuur 11: Prestaties in een level zonder muren. De snellere daling bij diff = 0.01,0.10 geeft een snellere verspreiding door het level weer

Figuur 12: Prestaties in een level zonder muren. Opvallend is de afbuiging van de lijn met hoge diffusie

33

Figuur 13: Prestatie in een gecompliceerd level. Hier is een hoge diffusie iets beter in staat snel tot een hoge spreiding te komen.

Verder is in de andere grafiek te zien dat er nog steeds een redelijk abrubte knik zit in het aantal verkende tiles bij hoge diffusie. Dit gebeurt wel pas na een grooter aantal iteraties. Een mogelijke verklaring hiervoor is dat vakjes/vertices die tegen een rand aan liggen bijna altijd verkend worden (deze zijn gegarandeerd begaanbaar tot σ22 , 2 keer zo lang als andere vertices). k Aangezien een gecompliceerd veld erg veel vertices tegen muren aan heeft, kan dit de tijd tot afbuiging vergroten. 5.1.2

Het effect van het aantal mieren

Het Vermoeden bestond, dat meerdere mieren beter samen gingen werken door diffusie. Dit blijkt niet het geval.Uit de figuren 15 en 16 blijkt, dat het effect van het toevoegen van extra mieren met of zonder diffusie is vergelijkbaar is. 5.1.3

de variatie in spreiding met en zonder diffusie

In de figuren 17 en 18 zijn de prestaties weergegeven met en zonder diffusie. In deze grafieken zijn alle test runs apart weergegeven met daar doorheen het gemiddelde. Er is duidelijk te zien dat er zonder diffusie veel meer variatie is in de snelheid waarmee de spreiding toeneemt. Het level waar op getest is bevat 4 kamers die slechts door een nauwe opening met elkaar in verbinding staan. In figuur 17 zijn deze kamers terug te zien in de platteaus die in de

34

Figuur 14: Prestatie in een gecompliceerd level. Nog steeds zit er een knik in de lijn met hoge diffusie maar dit gebeurt na een groter aantal iteraties

Figuur 15: level6 leeg varAnts Diff000

35

Figuur 16: level6 leeg varAnts Diff001

grafiek te zien zijn. Op die plekken zaten de mieren vast in een kamer.

6

conclusie

Het antwoord op de onderzoeksvraag ’Is de werking van Vertex-Ant-Walk verbeteren door het implementeren van diffunderende geursporen?’ is ja. De snelheid waarmee een graaf doorlopen wordt en vooral de spreiding van de verkenningspaden binnen die graaf wordt veel beter van het gebruik van geurdiffusie(zie 5. De garantie dat alle vertices uiteindelijk bezocht zullen worden is echter alleen te geven tot n stappen, waarbij n = σ12 (zie 3.2.2). k

7

Vervolg onderzoek

Geurdiffusie in Ant Walk algoritmen blijkt een vruchtbaar concept. Er zijn dan ook nog veel zaken die interessant zouden zijn om verder te onderzoeken. bewegende objecten misschien heeft diffusie wel een positief effect op het omgaan met dynamische omstandigheden. Geur inzakking Door het inzakken van de gauss/geur-verdeling op een vertex, worden er uiteindelijk vertices onbereikbaar. Als er verdijnt en de geur voor dat dat gebeurt weg is, kan totale coverage wel gegarandeerd worden, met mogelijk behoud van de goede eigenschappen van diffusie. Misschien zijn er wel andere functies dan gauss functies om 36

Figuur 17: Zonder diffusie er er veel spreiding in de resultaten van verschillende test runs.

Figuur 18: Met diffusie is er veel minder spreiding in de resultaten van verschillende testruns.

37

het inzakken te modelleren.Zodat de som van 2 functies in het midden nooit hoger wordt dan op de plek van de orginele top. verschillende schalen voor diffusie en stapgrootte Het kost best veel rekenkracht om diffusie te modelleren. Mogelijk is het niet nodig om voor elke vertex een geurwaarde bij te houden. Misschien is een meer globale geur waarbij Ant-Robots hun richting bepalen op basis van een gradient efficienter. andere domeinen Om generaliteit te testen zou het leuk zijn om ant walk met geurdiffusie op andere domeinen te testen, zoals het in kaart brengen van sites binnen een bepaald webdomein.

38

7.1

Verkregen patronen

Om dat ze te mooi zijn om achter te houden: Tot slot nog een aantal karakteristieke paden door een level en de instellingen waarbij deze voorkomen.

Figuur 19: 4 way walk en diffusie, met 2 diffusie stappen voor 1 ant walk

39

Figuur 20: 4 wayWalk en 8 way Diffusion

Figuur 21: 4 way Walk and Diffusion in maze level

40

Figuur 22: 8way walk and diffusion

Figuur 23: 4way walk, 8 way diffusion, emptyLevel

41

Figuur 24: Dit plaatje is verkregen met een random ruis in de gemeten intensiteiten. De ruis is maximaal 20% van de eigen intensiteit. Op deze manier hebben we sensorvervuiling nagebootst.

Figuur 25: No diffusion, level maze, 8 way Walk

42

8

Bibliography

Referenties [1] On Multiagent Exploration. Ioannis M. Rekleitis Gregory Dudek Evangelos E. Milios [2] Coverage, Exploration and Deployment by a Mobile Robot and Communication Network Maxim A. Batalin and Gaurav S. Sukhatme [3] Reducing the Odometry Error. Ioannis M. Rekleitis,Gregory Dudek and Evangelos E. Milios , biologisch getinte studies naar cooperatief gedrag bij insecten [4] Self-organized patterns and traffic ow organisms: from bacteria and social insects to vertebrates Debashish Chowdhury , Katsuhiro Nishinari , and Andreas Schadschneider [5] generating qualitative Equations about Macro-behaviors of Foraging in Ant Colony. Koichi Kurumatani en Mari Nakamura En meer quantitative onderzoeken naar virtuele robots op een meer abstract niveau. [6] Wagner I.A., Lindenbaum, M. and Bruckstein, A.M., ”EFFICIENTLY SEARCHING A GRAPH BY A SMELL-ORIENTED VERTEX PROCESS” [7] Wagner I. and Bruckstein, A.M., ”COOPERATIVE CLEANERS: A STUDY IN ANT ROBOTICS” [8] Terrain Coverage with Ant Robots: A Simulation Study. Sven Koenig & Yaxin Liu [9] Wagner I.A., Lindenbaum, M. and Bruckstein, A.M.,”DISTRIBUTED COVERING BY ANT-ROBOTS USING EVAPORATING TRACES”

43