Multi-Agent Systems: Project

Multi-Agent Systems: Project Dommicent Leendert Van Loock Jorn

Prof.: T. Holvoet Assistent: Robrecht Haesevoets

1

Inhoudsopgave 1 Probleemdomein

3

1.1

Domeinmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Non-functional requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.1

Robuustheid bij het uitvallen van vrachtwagens . . . . . . . . . . . . . . . . . . . .

4

1.2.2

Minimale rijafstand van de vrachtwagens . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.3

Minimale totale wachttijd van pakketten . . . . . . . . . . . . . . . . . . . . . . . .

4

2 Software ontwerp

4

2.1

Gedetailleerde beschrijving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Klassediagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3 Evaluatie 3.1

7

Experimenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.1.1

Robuustheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.1.2

Minimale rijafstand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2

Vergelijking met andere oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3

Kritische reflectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Taakverdeling

13

5 Conclusie

14

2

Samenvatting Dit verslag is gemaakt voor het vak multi-agent systems. Als opdracht wordt er een delegate mas oplossing bedacht voor het pick-up and delivery probleem. In de eerste sectie zullen we het probleem analyseren. Vervolgens zal de oplossing uitgelegd worden. Uiteindelijk wordt de oplossing dan ge¨evalueerd door onder andere vergeleken te worden met 2 andere oplossingen namelijk gradient field en contract net.

1

Probleemdomein

In dit deel van het verslag gaan we het probleem analyseren, hiervoor gebruiken we een domeinmodel. Ook gaan we de non-functional requirements vastleggen waaraan onze oplossing zou moeten voldoen. Bij een pick-up and delivery probleem ofwel PDP moeten vrachtwagens pakketten oppikken op bepaalde plaatsen en zo correct afleveren op de juiste locatie. We maken enkele vereenvoudigingen aan het probleem. We zullen geen rekening houden met eventuele prioriteiten van pakketten. Ook hebben ze geen deadline. Zoals verder in het verslag staat vermeld kan de oplossing wel makkelijk worden uitgebreid om dit in de toekomst wel te ondersteunen.

1.1

Domeinmodel

In figuur 1 vindt u het domeinmodel van het probleem. Het diagram is in het Engels om het makkelijk te kunnen vergelijken met het klasse diagram dat ook in het Engels is. Elke truck kan maar ´e´en package tegelijk vervoeren en elk pakket kan ook maar door ´e´en truck worden opgepakt. De trucks rijden op roads. Een road kan meerdere trucks bevatten. We gaan er dus ook van uit dat het inhalen van trucks geen probleem is. Alle roads komen uit op een crossroad. De locatie van een package is altijd op zo een crossroad. Een package kan dus niet midden op een road staan.

Figuur 1: Het domein

3

1.2

Non-functional requirements

In deze sectie leggen we twee non-functional requirements vast waaraan de oplossing moet voldoen. E´en gaat over de robuustheid van de oplossing. De andere gaat over de performantie dat de oplossing kan halen in verband met de rijafstand van de vrachtwagens. Als laatste toevoeging kan de wachttijd van pakketten geminimaliseerd worden. We proberen niet een volledige oplossing te bieden. We zullen onze oplossingen toespitsen op de bovenstaande eisen. Dit wil zeggen dat we momenteel geen rekening zullen houden met andere zaken zoals scalability of security.

1.2.1

Robuustheid bij het uitvallen van vrachtwagens

Bij een vervoersmaatschappij in de echte wereld kan het zijn dat er vrachtwagens in panne vallen. Dit kan door verschillende redenen zijn zoals een ongeval of mechanische fout. Als dit gebeurt kan de vrachtwagens dus geen pakketten meer ophalen. Het is noodzakelijk dat andere vrachtwagens de pakketten van de uitgevallen vrachtwagen overnemen zodat deze niet blijven staan. Dit kan vrij goed gerealiseerd worden met een multi-agent system. Praktisch gezien willen we er dus voor zorgen dat er geen pakketten blijven staan bij het uitvallen van trucks zoals waarschijnlijk wel het geval zal zijn bij bijvoorbeeld contract net. We stellen geen eisen aan de tijdsspanne waarin het systeem zich hersteld.

1.2.2

Minimale rijafstand van de vrachtwagens

Een ander belangrijk punt voor vervoersmaatschappijen is de afstanden dat de trucks afleggen. Hoe langer de afstanden zijn hoe meer brandstof er moet aangekocht worden en dus hoe meer kosten er moeten worden gemaakt. In onze oplossing gaan we dus proberen om de afstand te minimaliseren. Het doel is om de gereden afstand 15% korter te maken dan de bestaande oplossingen met gradient field en contract net. Tijdens de evaluatie gaan we controleren of dit doel gehaald is of niet.

1.2.3

Minimale totale wachttijd van pakketten

De wachttijd van de pakketten moet ook minimaal zijn. Hoe sneller pakketten worden behandeld hoe beter de service tegenover de klant. In onze oplossing gaan we proberen om de totale wachttijd te minimaliseren. We zullen echter geen rekening houden met individuele wachttijden maar het probleem alleen globaal bekijken. Dit heeft als consequentie dat eventuele starvation niet wordt uitgesloten in deze oplossing. Ook hier zullen we proberen om de wachttijd te verminderen met 25% tegenover de andere oplossingen met gradient fields en contract net.

2

Software ontwerp

De oplossing wordt geschreven in de simulator RinSim. Deze simulator is ge¨ımplementeerd in Java. Onze oplossing is dus bijgevolg ook in Java geschreven. Om deze sectie overzichtelijk te houden leggen we enkel delen van de oplossing uit die we zelf geschreven hebben. In het klasse diagram zullen dus geen klassen staan van de simulator zelf.

4

2.1

Gedetailleerde beschrijving

Voor onze oplossing gaan we gebruik maken van zogenaamde ants. Deze ants zijn eigenlijk zelf agenten die de hoofd agenten zoals vrachtwagens en pakketten helpen om hun taak te volbrengen. Van dit systeem komt ook de naam delegate MAS omdat de hoofdagenten het werk delegeren naar de zogenaamde ants. In onze oplossing gaan we gebruik maken van drie soorten ants namelijk feasibility, exploration en intention ants. In de volgende paragrafen ga ik het nut voor elk van de ants in onze oplossing bespreken. De feasibility ants worden gebruikt door de pakketten. Ze gaan informatie verspreiden over de pakketten op de kruispunten van het wegennet. Deze informatie bevat de positie van het pakket en of er door een truck al een intentie is gemaakt op dit pakket. De ants gaan deze informatie verspreiden door middel van flooding. We hebben geen gebruik gemaakt van selective flooding omdat het minimaliseren van eventuele overhead geen doelstelling op zich was. Dit kan in de toekomst echter nog wel worden toegevoegd. De flooding gebeurt wel maar tot op een bepaalde diepte, ook worden er vanaf elk kruispunt maar ´e´en keer ants verstuurd als er ´e´en aankomt. Deze maatregelen werden genomen om te verzekeren dat het flooding proces uiteindelijk zou eindigen. Wat belangrijk is om te verzekeren dat het systeem blijft werken als er vrachtwagens of pakketten wegvallen is het feit dat de gegevens van de pakketten op de kruispunten vervagen na een tijd en uiteindelijk verdwijnen. Dit geldt zowel voor de intentie als de algemene informatie afzonderlijk. De pakketten moeten dus om een bepaald tijdsinterval de kruispunten updaten met behulp van hetzelfde systeem om te verzekeren dat de informatie op de kruispunten blijft staan. De exploration ants worden gebruikt door de vrachtwagens. Als de vrachtwagens een pad hebben afgewerkt gaan ze op zoek naar een nieuw pad. Merk op dat de vrachtwagens in ons systeem dus geen alternatieve paden gaan onderzoeken wanneer hij een pad aan het afwerken is omdat dit niet ´e´en van de doelen was van de oplossing en om dus geen onnodige overhead te hebben. Ook dit kan uiteindelijk relatief simpel worden toegevoegd aan de oplossing. Bij het zoeken naar een nieuw pad zendt de vrachtwagen de exploration ants uit. Deze gaan dan opnieuw door middel van flooding aan de omliggende kruispunten informatie van de pakketten opvragen dat daar door feasibility ants zijn neergelegd. Ook dit flooding mechanisme is beperkt tot een bepaalde diepte en zendt per kruispunt maar ´e´en keer nieuwe ants uit als er ´e´en toekomt. Dit gebeurt om dezelfde reden als hierboven namelijk de eindigheid verzekeren. Na de flooding rapporteren al de ants dan terug naar de vrachtwagen. Vervolgens stuurt de vrachtwagen exploration ants naar de afleverlocaties van de gevonden pakketten waar dan opnieuw gezocht wordt naar omliggende pakketten op dezelfde manier. Hij doet dit enkel voor pakketten die ofwel geen intentie hebben ofwel indien hij een beduidend betere intentie heeft. Met beduidend beter bedoelen we dat de tijd waarin de huidige truck het pakket kan ophalen maal een correctie co¨effici¨ent nog steeds kleiner is als de tijd van de vrachtwagen met de huidige intentie. Op die manier worden er dus paden gevonden met een vooraf ingesteld aantal pakketten. Als er geen paden meer worden gevonden van de bepaalde lengte gaat hij het opnieuw proberen voor paden met ´e´en pakket minder. Hij blijft dit doen zolang er geen paden gevonden worden tot en met paden van ´e´en pakket. Van al deze paden neemt de vrachtwagen dan de kortste. Als de vrachtwagen een pad heeft uitgekozen moet hij dit kenbaar maken aan de pakketten op dit pad. Hij doet dit door intention ants uit te sturen naar deze pakketten. Deze ant weet wanneer de vrachtwagen het pakket kan oppikken en gaat dit dus ook meedelen aan het pakket. De pakketten onthouden deze intentie en gaan deze ook mee uitsturen bij de volgende update van de kruispunten door de feasibility ants. De intention ants rapporteren dan terug of de intentie succesvol is gezet op het pakket. Tijdens het afwerken van het pad moet de vrachtwagen ook om een bepaald tijdsinterval de intenties opnieuw uitsturen met nieuwe informatie naar de pakketten die nog moeten worden afgehandeld. Indien het zetten van de intentie bij ´e´en pakket op het pad mislukt, omdat een andere vrachtwagen een betere intentie had, wordt het pad van de huidige vrachtwagen verwijderd en wordt er naar een nieuw pad gezocht. Door het vervagen van de intenties worden de oude intenties van deze vrachtwagen na een tijd automatisch verwijderd. De intenties vervagen immers niet alleen op de kruispunten maar ook in het pakket zelf.

5

2.2

Klassediagram

Figuur 2: Het klassediagram van de oplossing

6

In figuur 2 vindt u het klassendiagram van de implementatie van onze oplossing. De twee belangrijkste klassen zijn PackageAgent en TruckAgent die de agenten voorstellen van respectievelijk de pakketten en de vrachtwagens. De klasse Truck en Package stellen dan deze eigenlijke vrachtwagens en pakketten voor. Voor de zogenaamde ants zijn er geen aparte klassen voorzien. Deze bewerkingen gebeuren gewoon in methodes in de klasse van de agenten. Ook is er een EnvironmentAgent aanwezig, deze zorgt ervoor dat de waarden op de kruispunten devalueren zoals staat beschreven in onze oplossing. De EnvironmentMgr houdt dan weer alle kruispunten ofwel Intersection objecten bij. Deze kruispunten hebben IntersectionPackageProps, dit zijn de gegevens van de pakketten die op dat kruispunt zijn achtergelaten. Aangezien het dus aparte objecten zijn kan de informatie op de kruispunten van deze simulatie dus ook vertraging hebben zoals in de echte wereld. De gegevens bevatten ook een Intention object. Dit object stelt een intentie voor van een truck voor het pakket. In elke IntersectionPackageProp zit dus een kopie van deze intentie. Deze informatie kan dus ook achterlopen op de echte huidige intentie naar gelang de laatste update die door de feasibility ants werd doorgevoerd. De path klasse tenslotte stelt een pad voor dat de vrachtwagen kan afleggen.

3

Evaluatie

In deze sectie zullen we een evaluatie maken van het uiteindelijke resultaat. We beginnen hiervoor met experimenten te doen om te kijken of de gekozen non-functional requirements gevolgd werden. We zullen verschillende parameters laten varieren en uiteindelijk de beste eruit kiezen. Tijdens deze zoektoch wordt er al continu vergeleken met andere oplossingen. Als laatste puntje wordt een kristische reflectie gegeven over het uiteindelijk resultaat.

3.1

Experimenten

In deze sectie hebben we een selectie gemaakt van experimenten die we gedaan hebben om de functionaliteit, werking enz. van het systeem te testen. De resultaten die hier staan beschreven zijn de resultaten toegepast op het stratenplan van Leuven. Tijdens het schrijven van het systeem werd er ook veel getest op een kleiner stratenplan m.n. het stratenplan van Rumst. Dit stratenplan was veel kleiner waardoor we fouten in het systeem veel sneller konden ontdekken. Met dit kleiner stratenplan was het voor ons gemakkelijker te voorspellen wat er ging gebeuren.

3.1.1

Robuustheid

De eerste non-functional requirement is robuustheid. Het wegvallen van vrachtwagens is in onze oplossing geen enkel probleem. Om dit mooi te kunnen testen is het eenvoudig om 3 pakketten en 3 vrachtwagens in omloop te brengen waarbij de exploration ants 2 pakketten ver kijken. We hadden een situatie waarbij 1 vrachtwagen 2 pakketten zou behandelen, 1 vrachtwagen die 1 pakket zou behandelen en een vrachtwagen die bleef staan. Wanneer 1 van de twee werkende vrachtwagens uitviel kwam de 3e in actie. Dit experiment werd nadien herhaald met meerdere pakketten en meerdere vrachtwagens. Telkens werden pakketten die voorzien waren voor een vrachtwagen die later uitvalt, nadien overgenomen door een andere vrachtwagen.

3.1.2

Minimale rijafstand

Het uiteindelijk resultaat omvat verschillende parameters waarvan de waarde het uiteindelijk resultaat positief of negatief beinvloedt afhankelijk van het stratenplan, het aantal pakketten in omloop, het aantal 7

vrachtwagens enz. Voorbeelden van deze parameters zijn de diepte van de zoekboom van de exploration ants en ook hoe ver in het stratenplan de feasability ants gaan. Omdat we met het stratenplan van Leuven toch een relatief compact stratenplan hebben waarbij veel wegen onderling geconnecteerd zijn moeten deze waardes niet al te hoog staan opdat vrachtwagens pakketten zouden vinden. We gaan op deze parameters dan ook niet verder in. In het geval van andere stratenplannen moet hier zeker naar gekeken worden en een afweging worden gemaakt van hoeveel berichten er worden rondgestuurd ten op zichte van het vinden van pakketten. Belangrijke parameters die zeker te maken hebben met de tweede non-functional requirement zijn het aantal op elkaar volgende pakketten dat een exploration ant zoekt. Stel deze gelijk aan 1 en samen met bijvoorbeeld 1 vrachtwagen en 2 pakketten in het systeem. Het kan dan zijn dat minder afstand wordt afgelegd door eerst het verste pakket ten opzichte van de vrachtwagen te halen en dan het andere. Hiervoor moet er dus meer dan 1 pakket ver gekeken worden door de exploration ants. Een andere belangrijke parameter heeft te maken met wanneer een vrachtwagen een pakket kan afnemen van een andere. We kunnen stellen dat een vrachtwagen eenvoudig kan overnemen wanneer hij sneller bij een pakket kan zijn. Er kan echter snel een voorbeeld gevonden waarbij dit niet altijd resulteert in zo weinig mogelijk afstand afleggen. Daarom kunnen we een parameter invoeren die stelt dat een vrachtwagen een pakket kan overnemen wanneer hij bijvoorbeeld 20% beter doet doet in pickuptime in plaats van absoluut beter.

Zoektocht naar de parameter voor een significant beter pad door 2 pakketten ver te kijken We starten de experimenten met het zoeken naar een gewicht voor wanneer een vrachtwagen het pakket van een andere mag overnemen. We beginnen met lage aantallen: twee vrachtwagens laten vechten om twee pakketten. Om deze inderdaad te laten vechten en niet richting contract net te gaan zetten we de parameter voor het aantal opeenvolgende pakketten voor de exploration ants op 2. Ons gevoel zegt dat iedere vrachtwagen 1 pakket moet doen. Dit hangt natuurlijk ook af van de positie van de pakketten en de afleverlocaties. We verwachten ook wanneer we de parameter voor een significant beter pad te hoog zetten dat het systeem onstabiel wordt omdat we een te grote eis opleggen. Bijvoorbeeld als de tweede vrachtwagen 90% beter moet doen dan de eerste dan zal de eerste zowel pakket 1 als pakket 2 gaan halen omdat de tweede vrachtwagen nooit beter kan doen. Het resultaat hiervan is te zien in figuur 3. We vergelijken 3 afhankelijke veranderlijken met elkaar: de tijd dat een pakket moet wachten totdat het opgepikt wordt, de tijd dat het moet wachten totdat het afgeleverd wordt en de totale afstand dat door vrachtwagens gereden wordt. We focussen ons op de laatste omdat deze net het tweede non-functional requirement is. In al onze grafieken is een lagere waarde dus een betere waarde. Figuur 3 en de volgende figuren bevatten zowel onze oplossing (in de legende als Delegate) als andere oplossingen (Gradient Field en Contract Net) om te vergelijken. De weight in de legende van de grafieken is het percentage dat bij de lengte van het nieuwe pad wordt bijgeteld. Is deze parameter dus gelijk aan nul dan geldt eenvoudig dat de vrachtwagen die er het snelst is wint. Is de parameter gelijk aan 1 dan wordt bij een aanvraag van een andere vrachtwagen zijn afstand tot het pakket verdubbeld. De afstand wordt dan vergeleken met de verwijderde afstand van de vrachtwagen die het pakket zou komen halen. (De vrachtwagen stuurt deze nog verwijderde afstand in iedere intentie om een pakket te komen halen) Zo kunnen we eisen dat een vrachtwagen beduidend beter moet doen. In figuur 3 ziet u geen weight 0.2. Dit komt omdat dit hetzelfde resultaat gaf als weight 0. Deze manier van werken wordt doorgezet doorheen het verslag. We zien dat een gewicht van 0 tot en met een gewicht van 0.5 (dit komt overeen met anderhalf keer het pad) voor de gereden afstand het beste resultaat geeft. We doen ongeveer 60% beter dan Gradient Field en 30% beter dan Contract Net. Dit resulteerde ook in het feit dat iedere vrachtwagen 1 pakket deed. Ook in vergelijking met de andere oplossingen is dit het beste resultaat. Vanaf 0.6 kon de tweede

8

2 Trucks - 2 Packages Comparison: 3 Trucks - 10 Packages (For Delegate MAS : 2 Consecutive packages)

MAS – weight 0.4 Delegate – 3 consecutive – weight 0 MAS – weight 0.1 Delegate – 2 consecutive – weight 0.6 Gradient Field Gradient Field Contract Net Contract Net

PICKUP WAIT PICKUP WAIT

DELIVER WAIT

DRIVEN

DELIVER WAIT

DRIVEN

Figuur 3: Experiment 1 vrachtwagen nooit beter doen dan de eerste vrachtwagen. Dit komt doordat de eerste vrachtwagen zowel naar het eerste pakket als naar het tweede pakket als eerste een intentie heeft gestuurd om het te komen halen. De straf op de tweede vrachtwagen was gewoon te groot en hij kon niet beter doen, zelfs niet om alleen het tweede pakket te halen. Het effect van deze parameter heeft bij twee pakketten en twee vrachtwagens maar twee uitwegen. Of 1 vrachtwagen doet beide pakketten of ze doen er allebei 1. Daarom moeten we het effect van deze parameter bekijken bij meerdere pakketten. Het resultaat hiervan is te vinden in figuur 4 waar we 3 vrachtwagens gebruiken voor 20 pakketten. Ook in figuur 4 zien we dat onze Delegate MAS oplossing het zeer goed doet. Alle parameters (getest tot 1) doen het op alle vlakken beter dan Gradient Field en Contract Net. Voor de gereden afstand doen we hier ongeveer 35% beter dan Gradient Field en 10% dan Contract Net. Onderling is er tussen de parameters relatief weinig variatie waardoor we niet echt een stap verder zijn in het vinden naar de juiste parameter.

Zoektocht naar de parameter voor een significant beter pad door 3 pakketten ver te kijken In de twee experimenten tot nu toe keken de exploration ants slechts 2 pakketen ver. We zullen dit nu ophogen naar 3. We beginnen opnieuw met lage waarden: 3 vrachtwagens en 3 pakketten waarbij de exploration ants nu 3 pakketten ver kijken. Het resultaat is te vinden in figuur 5. We zien dat Contract Net het net iets beter doet op elk vlak dan onze Delegate MAS oplossing. Toch moet onze oplossing zeker niet onderdoen omdat het verschil zeer klein is. De beste Delegate MAS oplossing - een weight van 0.8 - doet voor de gereden afstand meer dan 25% beter dan Gradient Field en minder dan 1% slechter dan Contract Net. Zoals daarnet zal nu ook het aantal pakketten opgehoogd worden. 20 pakketten is te hoog omdat dit een explosie aan paden geeft dat door de computer moet berekend worden. We stellen daarom het aantal pakketten voor dit experiment gelijk aan 10. Het resultaat hiervan ziet u in figuur 6.

9

32Trucks Trucks --20 2 Packages Packages Comparison: 3 Trucks - 10 Packages (For Delegate MAS : 2 Consecutive packages)

Delegate – weight Delegate – weight MAS – weight 0.4 Delegate – 3 consecutive – weight MAS – weight 0.1 Delegate – 2 consecutive – weight Gradient Field Gradient Field Delegate – weight Contract Net Contract Net Delegate – weight Gradient Field Contract Net

PICKUP WAIT PICKUP WAIT

DELIVER WAIT

0.0 0.2 0 0.5 0.6 0.8 0.9

DRIVEN

DELIVER WAIT

DRIVEN

Figuur 4: Experiment 2 33 2Trucks Trucks --20 2 Packages 3 Packages Comparison: 3 Trucks - 10 Packages (For Delegate MAS :2 3 Consecutive packages)

Delegate – weight Delegate – weight Delegate – weight Delegate – weight MAS – weight 0.4 Delegate – 3 consecutive – weight Delegate – weight MAS – weight 0.1 Delegate – 2 consecutive – weight Delegate – weight Gradient Field Gradient Field Delegate – weight Delegate – weight Contract Net Contract Net Delegate – weight Gradient Field Gradient Field Contract Net Contract Net

PICKUP WAIT PICKUP WAIT

DELIVER WAIT

0.0 0.0 0.2 0.1 0 0.5 0.3 0.6 0.6 0.8 0.8 0.9

DRIVEN

DELIVER WAIT

DRIVEN

Figuur 5: Experiment 3 We zien dat onze Delegate MAS oplossing het nu minstens even goed doet als de Contract Net oplossing. Hetzelfde in gereden afstand maar wel beter op andere gebieden. We doen op elk gebied veel beter dan de Gradient Field oplossing. Voor de gereden afstand doen we 13% beter dan de Gradient Field oplossing. We zien ook dat de parameter verschillende waardes kan aannemen die leiden tot hetzelfde resultaat in uiteindelijk gereden afstand. Ze zijn bijna allemaal gelijkwaardig op het gebied van afgelegde weg. Dus we gaan verder kijken welke van deze parameters ook goed scoort op de andere domeinen. Hierbij zien

10

33 2Trucks Trucks --20 2 Packages 3 Packages 10 Comparison: 3 Trucks - 10 Packages 2 Consecutive packages) (For Delegate MAS :3 Packages)

Delegate – weight Delegate – weight Delegate – weight Delegate – weight MAS – weight 0.4 Delegate – 3 consecutive – weight Delegate – weight MAS – weight 0.1 Delegate – 2 consecutive – weight Delegate – weight Gradient Field Gradient Field Delegate – weight Delegate – weight Contract Net Contract Net Delegate – weight Gradient Field Gradient Field Gradient Net Field Contract Contract Net Contract Net

PICKUP WAIT PICKUP WAIT

DELIVER WAIT

0.0 0.0 0.2 0.0 0.1 0 0.5 0.4 0.3 0.6 0.6 0.8 0.8 0.9

DRIVEN

DELIVER WAIT

DRIVEN

Figuur 6: Experiment 4 we dat een gewicht van 0.4 in deze situatie de beste optie zal zijn. (Moeilijk te zien op de grafieken)

Bepalen van de juiste parameters Voor het bepalen van de juiste parameters werken we verder op de 10 pakketten in omloop omdat we hierbij ook 3 pakketten ver kunnen kijken, in tegenstelling tot 20 pakketten. We moeten dus nog een experiment voor onze oplossing doen waarbij we 2 pakketten ver kijken en 10 pakketten in omloop hebben. Dit ziet u in figuur 7. Hierbij zien we dat een gewicht van 0.1 tot en met 0.9 voor onze tweede non-functional requirement, bij 2 pakketten ver kijken, het beste resultaat geeft. 10 pakketten in omloop en 3 pakketten ver kijken werd al gedaan in het 4e experiment (zie figuur 6). De beste parameter in die situatie was 0.4. In figuur 8 zetten we alles nog eens op een rijtje voor 3 vrachtwagens en 10 pakketten. U ziet onze beste oplossing door 3 pakketten ver te kijken en door 2 pakketten ver te kijken. We besluiten hieruit standaard 2 pakketten ver te kijken omdat dit voor de afgelegde weg beter is dan 3 pakketten ver te kijken. De parameter voor een beduidend beter pad zetten we standaard op 0.2. Dit omdat de parameter van het resultaat in figuur 8 voor 2 pakketten ver te kijken slaat op 0.1 tot en met 0.9 (experiment 5 in figuur 7). Zodus kunnen we in deze range nog eens de beste parameter zoeken. Deze moet gezocht worden binnen de experimenten dat twee pakketten ver kijken. Het tweede experiment (figuur 4) geeft voor de parameter 0.2 een lagere waarde voor de 2e non-functional requirement dan voor 0.1.

3.2

Vergelijking met andere oplossingen

Voor de vergelijking met de andere oplossingen verwijzen we opnieuw naar figuur 8 evenals de andere figuren bij de experimenten. Ons finaal resultaat is dus 2 pakketten ver kijken en de waarde van de parameter om een pakket van een andere vrachtwagen te mogen overnemen staat op 0.2. (Dit is in figuur 8 hetzelfde als de waarde 0.1) Hoe we hiertoe kwamen staat beschreven in Experimenten. We zien dat

11

33 2Trucks Trucks --20 10 2 Packages 3 Packages Comparison: 3 Trucks - 10 Packages 2 Consecutive 2 Consecutive Packages packages) (For Delegate MAS :3 Packages)

Delegate – weight Delegate – weight Delegate – weight Delegate – weight MAS – weight 0.4 Delegate – 3 consecutive – weight Delegate – weight MAS – weight 0.1 Delegate – 2 consecutive – weight Delegate – weight Gradient Field Gradient Field Delegate – weight Delegate – weight Contract Net Contract Net Delegate – weight Gradient Field Gradient Field Gradient Net Field Contract Contract Net Contract Net

PICKUP WAIT PICKUP WAIT

DELIVER WAIT

0.0 0.0 0.2 0.0 0.1 0 0.5 0.4 0.3 0.0 0.6 0.6 0.1 0.8 1 0.8 0.9

DRIVEN

DELIVER WAIT

DRIVEN

Figuur 7: Experiment 5 Comparison: 33 2Trucks Trucks 3 Trucks --20 10 2 Packages 3 Packages - 10 Packages Comparison: 3 Trucks - 10 Packages 2 Consecutive 2 Consecutive Packages packages) (For Delegate MAS :3 Packages)

Delegate – weight 0.0 Delegate – weight 0.0 0.2 Delegate – weight 0.0 Delegate – weight 0.1 MAS Delegate – weight – weight 0.4 Delegate – 30.4 consecutive – 3 –consecutive 0 0.5 weight 0.4 Delegate – weight 0.0 0.3 MAS Delegate – weight – weight 0.1 Delegate – 20.1 consecutive – 2 –consecutive weight 0.6 Delegate – weight 0.1 0.6 Gradient Gradient Field Field Delegate Gradient Field – weight 0.8 Delegate – weight 1 0.8 Contract Contract Net Net Contract Net Delegate – weight 0.9 Gradient Field Gradient Field Gradient Net Field Contract Contract Net Contract Net

PICKUP WAIT PICKUP PICKUP WAIT WAIT

DELIVER WAIT DELIVER DELIVER WAIT WAIT

DRIVEN DRIVEN

DRIVEN

Figuur 8: Experiment 6 we in deze situatie op ieder vlak beter doen dan Gradient Field en Contract Net. Ook in andere situaties (zie experimenten) doen we quasi minimum even goed als Contract Net. In de situatie van figuur 8 doen we voor de afgelegde weg ongeveer 20% beter dan Gradient Field en 6% beter dan Contract Net.

12

Daar waar onze oplossing de nodige robuustheid heeft, heeft Contract Net dit niet. Vrachtwagens en pakketten kunnen in onze oplossing zonder problemen wegvallen. We zien tijdens simulaties duidelijk dat er bij Contract Net pakketten blijven staan als er vrachtwagens uitvallen.

3.3

Kritische reflectie

In deze sectie zullen we het finaal resultaat nog eens overlopen. De sterke en zwakke punten worden op een rijtje gezet. Het resultaat doet het in de meeste situaties beter dan zowel Gradient Field als Contract Net op gebied van afgelegde afstand maar ook op de andere gebieden. We kunnen zeggen dat de gevraagde 15% verbetering op Gradient Field wel is gehaald. Algemeen was het verschil met Contract Net kleiner. Als we verder kijken dan enkel deze requirement, zien we dat onze oplossing ook als de betere naar voor komt bij andere maatstaven. (Zie Experimenten) Onze oplossingen heeft een zekere robuustheid waarbij het wegvallen van vrachtwagens of pakketten geen probleem mag geven. Daar waar we een kleiner verschil hadden in afgelegde weg met Contract Net dan met Gradient Field hebben we hiermee wel een groot voordeel ten opzichte van Contract Net. Dit werkt in het finale resultaat maar nog niet op de meest efficiente manier: Zoals voordien is uitgelegd zoekt onze vrachtwagen tijdens het afwerken van een pad niet continu naar andere paden. Hij blijft echter wel intenties sturen naar de pakketten op zijn af te werken pad. Wanneer een pakket dus is weggevallen zal de vrachtwagen een ander pad zoeken omdat zijn intentie naar dat pakket niet bevestigd werd door het pakket. Zijn pad werd geannuleerd. Het wegvallen van pakketten wordt dus wel optimaal behandeld. Het wegvallen van vrachtwagens of het bijkomen van pakketten op verschillende tijdstippen wordt daarentegen niet op de meest efficiente manier behandeld: Stel dat zowel een eerste als een tweede vrachtwagen een pad aan het afwerken zijn. 1 van de twee vrachtwagens valt vervolgens weg. De andere vrachtwagen zal eerst zijn eigen pad afwerken voordat hij opnieuw nieuwe paden zal zoeken. Een betere situatie zou zijn waarbij hij dus wel continu naar nieuwe paden zoekt. Dan is het mogelijk dat hij een pakket moet oppikken dat voor de weggevallen vrachtwagen bedoeld was. Een analoge situatie gebeurt wanneer een pakket op een later tijdstip opduikt op een pad dat een vrachtwagen aan het afwerken is. Hij zal in deze situatie gewoon voorbij het pakket rijden. Voordien werd ook gezegd dat dit heel snel aan te passen is in onze oplossing. We moeten hiervoor slechts de voorwaarde in 1 if-test aanpassen. Dit hebben we standaard niet gedaan om geen extra overhead in de meer normale situaties te hebben.

4

Taakverdeling

Aangezien we samen op kot zitten is het meeste werk voor dit project samen gedaan. De twee referentieoplossingen werden in de oefenzitting gemaakt en achteraf is er door ons beide nog aan gesleuteld om ze werkende te krijgen. Voor onze eigenlijke Delegate MAS oplossing zijn we samen rond te tafel gaan zitten om te brainstormen over hoe we het probleem het best konden aanpakken en welke doelen we wilde stellen. Vervolgens hebben we een eigen git repository aangemaakt met daarop een nieuwe module voor de oplossing. De grootste delen van deze oplossing zijn ook samen geschreven en gedebugd. In een later stadium heeft iedereen individueel nog wat functionaliteit toegevoegd en vooral nog veel bugs opgelost. Het uiteindelijke verslag werd ook op deze repository geplaatst zodat we beide eraan konden werken. We hebben dus individueel stukken toegevoegd en stukken van de ander verbeterd tot het resultaat dat u nu leest.

13

5

Conclusie

We hebben een mooie oplossingen weten te implementeren voor het probleem. In vergelijking met de andere oplossingen presteren we minstens even goed en vaak zelfs beter. Door de beperkte tijd dat er voor handen was voor dit project hebben we met bepaalde dingen geen rekening kunnen houden. We hebben de oplossing echter ruim proberen te houden zodat deze zaken in een later stadium eventueel nog konden worden toegevoegd.

14