Op biologie geïnspireerde coördinatie en controle van groot schalige en dynamische systemen

In literatuur over multi-agent systemen (MAS’en) wordt vaak aangenomen dat decentrale MAS’en erg geschikt zijn voor dynamische en grootschalige problemen. Deze aanname is gebaseerd op de decentrale eigenschappen van MAS’en die toelaten om problemen zodanig te splitsen dat agenten autonoom deelproblemen kunnen oplossen. Dit stelt agenten in staat om snel te reageren op veranderingen. Er is echter weinig wetenschappelijk bewijs voor deze aanname. Daarnaast zijn juist centrale algoritmen dominant in operationeel onderzoek.

Het voornaamste probleem dat wordt behandeld in deze dissertatie is het gebrek aan een systematische evaluatie van decentrale MAS’en en centrale algoritmen op dynamische en grootschalige logistieke problemen. Het logistieke probleem dat wordt bestudeerd is het dynamische pickup-and-delivery probleem met tijdvensters (dynamisch PDPTW). Er zijn vier vereisten voor een goede evaluatie. Ten eerste zijn er exacte definities van dynamiek en schaal vereist zodanig dat deze eigenschappen onafhankelijk gevarieerd kunnen worden. Ten tweede is er een dataset van dynamische PDPTW instanties met verschillende gradaties van dynamiek en schaal benodigd. De derde vereiste is een realistisch en onbevooroordeeld simulatie platform dat een dynamisch PDPTW in realtime kan simuleren en ondersteuning biedt voor zowel centrale als decentrale algoritmen. Ten vierde zijn er representatieve implementaties van centrale en decentrale algoritmes nodig.

Reproduceerbaarheid is een van de belangrijkste principes van de wetenschappelijke methode. Daarom moeten alle bovengenoemde componenten open source beschikbaar worden gemaakt. Een probleem dat ook wordt behandeld in deze dissertatie is het optimaliseren van MAS’en.

Deze dissertatie beschrijft vijf grote contributies. Dynamiek, urgentie, en schaal zijn formeel gedefinieerd in de context van dynamische PDPTW (contributie 1). Bestaande definities van dynamiek koppelen dynamiek vaak aan urgentie. Een empirische evaluatie van onze definities wijst uit dat de mate van dynamiek negatief gecorreleerd is met operationele kosten terwijl meer urgente scenario’s gecorreleerd zijn met significant hogere operationele kosten. Dit rechtvaardigt de conceptuele scheiding van dynamiek en urgentie. We definiëren schaal als een factor toegepast op het aantal voertuigen en bestellingen in een probleem. Deze drie definities maken het mogelijk om de effecten van één eigenschap op de operationele kosten te meten onafhankelijk van andere eigenschappen.

Gebaseerd op de formele definities van dynamiek, urgentie, en schaal is een dataset en probleem instantie generator van dynamische PDPTWs geconstrueerd (contributie 2). Deze benchmark dataset faciliteert systematische vergelijkingen van algoritmen onderhevig aan variërende probleem eigenschappen.

RinSim is een nieuwe open-source simulator specifiek ontwikkeld voor realtime logistieke experimenten (contributie 3). RinSim ondersteunt decentrale MAS’en, centrale algoritmen, en de dataset met verschillende gradaties van dynamiek, urgentie, en schaal. Zowel de centrale als de decentrale interface van RinSim hebben dezelfde soft- en hardware beperkingen. Op deze manier biedt RinSim een onbevooroordeelde omgeving voor het vergelijken van algoritme prestaties.

Een MAS, gebaseerd op het dynamisch contract-net protocol (DynCNET), en een gecentraliseerd taboe zoek algoritme, gebaseerd op de OptaPlanner optimalisatie bibliotheek, zijn geïmplementeerd. Met behulp van de formele definities, dataset, en RinSim zijn deze implementaties systematisch geëvalueerd (contributie 4). Dit evaluatie experiment is de eerste in zijn soort die de invloed van dynamiek, urgentie, en schaal, op de prestaties van twee categorieën algoritmen op een dusdanig systematische, grondige, en onbevooroordeelde manier vergelijkt. De resultaten van deze vergelijking tonen aan dat de kosten van de oplossingen die gevonden worden door het centrale algoritme gemiddeld genomen maar 94.2% beslaan ten opzichte van de operationele kosten die gevonden worden door het MAS. Dit geeft aan dat dit centrale algoritme over het algemeen beter presteert ten opzichte van het MAS. Maar, voor scenario’s die gemiddeld tot erg dynamisch zijn, erg urgent, en een gemiddelde tot grote schaal hebben, zijn de gemiddelde relatieve operationele kosten van het centrale algoritme 112.3%, het MAS werkt onder deze omstandigheden dus beter. Uit het beoordelen van de prestaties van de algoritmen per probleem eigenschap blijkt dat geen van de algoritmen in alle gevallen beter presteert dan de ander.

Om te onderzoeken of de prestaties van MAS’en kunnen worden geoptimaliseerd, bestuderen we hyper-heuristieken, meer specifiek genetisch programmeren (GP) (contributie 5). De heuristiek die wordt geëvolueerd door GP wordt gebruikt als biedingsfunctie in het veiling proces van CNET. De resultaten laten zien dat onze hyper-heuristiek in alle gevallen beter presteert dan het referentie algoritme dat is gebaseerd op OptaPlanner. De decentrale hyper-heuristiek presteert in de meeste gevallen zelfs beter dan het centrale referentie algoritme.