Influence of participation rates and service level differentiation on community driven predictions

Hoe mieren files kunnen oplossen

Routeplanning is een vaak voorkomend probleem. De huidige routeplanningssystemen gebruiken 2 soorten data om de reistijd te voorspellen: historische data en real-time data. Onderzoekers hebben een nieuwe aanpak ontwikkeld, genaamd anticiperende routebepaling voor voertuigen. In deze aanpak worden de huidige intenties van alle chauffeurs (i.e. de route die ze op dat moment plannen te volgen) gedeeld met de wegeninfrastructuur. De bedoeling hiervan is om al deze informatie te bundelen en daaruit de verkeersdrukte en bijhorende reistijd in de nabije toekomst te voorspellen (“community driven predicties”). Maar deze techniek doet meer dan alleen de optimale route bepalen: ze slaagt er ook in om de reistijden van de voertuigen te verkorten, filevorming te verminderen en zo de doorvoer van het netwerk te verhogen.

Briljant!? Maar waarom is niemand daar eerder mee op de proppen gekomen?

Deze techniek werd al vaak gebruikt in wetenschappelijk onderzoek. Sommigen gebruikten hiervoor een gecentraliseerde architectuur, wat mogelijk problemen geeft op gebied van schaalbaarheid. Anderen verkiezen wel een gedecentraliseerde architectuur, maar veronderstellen dan dat alle chauffeurs hun routeplanningssysteem gebruiken. Dit is evenmin een realistische veronderstelling. Uit deze aanpakken willen we een verbeterde strategie distilleren. Twee belangrijke elementen nemen we daarom over: een heterogene bestuurders-populatie en een gedecentraliseerd systeem.

Hoe? Zo!

Heterogeniteit wordt verwezenlijkt door het verdelen van onze bestuurders in twee groepen: een groep die ons geavanceerd systeem gebruikt en een groep niet-gebruikers (de slimme versus de domme chauffeurs). Het percentage chauffeurs dat ons systeem gebruikt ten opzichte van het totaal noemen we de participatiegraad. Decentralisatie realiseren we door ons systeem te modelleren als een multi-agentsysteem. In dit systeem hebben we twee soorten agenten: wegagenten en voertuigagenten. Autowegen zijn uitgerust met wegagenten. Deze hebben als voornaamste taak om de intenties van de voertuigen te verzamelen en deze te beantwoorden met voorspellingen van de reistijd op hun weg. Deze voorspellingen zijn gebaseerd op een onderliggend artificieel neuraal netwerk dat de wegagenten onderhouden.

Een multi-agentsysteem is een volledig autonoom, gedecentraliseerd systeem dat zichzelf organiseert. De intelligente actoren in dit systeem, agenten genaamd, werken samen om een of andere systeemtaak te realiseren. Dergelijke gedistribueerde systemen worden gebruikt voor problemen die moeilijk gecentraliseerd op te lossen zijn omwille van de grote schaal. Toepassingen hiervan zijn logistiek, verkeer en transportsystemen, supply chain management, elektriciteitsbeheer (power grids), enzovoort…

Een tweede type agenten zijn de voertuigagenten. Elk voertuig heeft een dergelijke agent aan boord, maar de intelligentie ervan kan verschillen. “Domme” agenten nemen steeds het theoretisch snelste pad. Ze zijn niet in staat om hun intenties te delen met de wegeninfrastructuur en maken geen gebruik van de voorspellingen van wegagenten. “Slimme” agenten daarentegen kunnen hun intenties wel delen met de infrastructuur. Zij bepalen hun route door middel van een geavanceerd routeplanningsalgoritme dat gebaseerd is op het gedrag van mierenkolonies.

Een heer mier in het verkeer

Voertuigagenten zullen onder andere lichtgewicht agenten uitsturen (“mieren”) die voor hen mogelijke routes gaan zoeken met behulp van feromonen. Hieruit kiest de voertuigagent de beste route.

Een feromoon is een (vluchtige) chemische substantie die in de natuur afgescheiden wordt door een mier. Het dient als “wegwijzer” voor andere mieren om bijvoorbeeld de locatie van een voedselbron aan te duiden. In figuur 1 zie je een situatie waarin mieren met behulp van feromonen er ondanks een obstakel op hun huidige route toch in slagen de voedselbron te bereiken. Dit komt doordat enkele mieren op goed geluk van de route afwijken, het doel toch bereiken en nadien feromonen uitstrooien ter informatie van latere passanten. Het uitwisselen van deze stukjes informatie onderling noemen we stigmergie. De manier van organisatie binnen een mierenkolonie benoemen we dan met de term zwermintelligentie.

Deze mieren zullen onderweg communiceren met de wegagenten om prognoses te verkrijgen van de doorlooptijd van de corresponderende wegen. Deze manier van communiceren maakt van ons systeem een delegerend multi-agentsysteem. Behalve voor het zoeken van routes worden mieren ook gebruikt voor het delen van intenties met de wegagenten. Dit zorgt ervoor dat een gecentraliseerd communicatiesysteem overbodig wordt, een voordeel qua schaalbaarheid.

Allemaal mooi in theorie … Maar werkt dat wel?

We evalueren onze nieuwe aanpak door het uitvoeren van een aantal experimenten. We herhalen hierbij de experimenten honderden keren opdat we statistisch relevante uitspraken kunnen doen en we onderzoeken verschillende parameterwaarden. Om een uitspraak te kunnen doen over de prestaties van de auto’s in een experiment met domme en slimme chauffeurs (0% < participatiegraad < 100%), willen we voor zowel een domme als een slimme bestuurder zijn reistijd vergelijken met die in een experiment waarin niemand participeert (participatiegraad = 0%).

Als evaluatiemetriek kiezen we voor:

<begin_definitiekadertje>

Q-score(x) = (totale reistijd auto x in te evalueren experiment) / (totale reistijd auto x in basisexperiment)

<eind_definitiekadertje>

(met x een willekeurige auto).

Hiervan nemen we de gemiddelden voor zowel de slimme als de domme bestuurders, zodat we twee getallen bekomen. Op basis van deze getallen bepalen we dan of de domme/slimme bestuurders sneller hebben gereden, even snel of trager (respectievelijk <1, =1 en >1).

Wanneer we nu experimenten uitvoeren met voldoende file, krijgen we onder andere de resultaten uit figuur 2. We kunnen vaststellen dat de gebruikers van ons systeem een voordeel hebben door hun participatie vanaf een participatiegraad van 10%. Voor de groep van domme bestuurders ligt deze drempel op 70%. Vanaf deze waarden rijdt een auto uit de respectievelijke groep significant sneller dan in het basisexperiment. Verder zien we dat voor zowel de domme als de slimme bestuurders het voordeel dat ze ondervinden groter wordt. Ter vergelijking: in eerder onderzoek werd geclaimd dat de voordelen voor de slimme bestuurders daalden met stijgende participatiegraad.

Klaar! Probleem opgelost?!

Er blijft nog heel wat resterend werk over in dit researchdomein. Enkele voorbeelden zijn:

• Uitgebreider onderzoek naar goede/slechte parameterwaarden
• Vergroten van de schaal
• Introduceren van ongevallen als fileoorzaak