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
Bibliografie
[1] Yasushi Ando et al. “Performance of pheromone model for predicting traffic
congestion”. In: Proceedings of the fifth international joint conference on
Autonomous agents and multiagent systems AAMAS 06 (2006), p. 73.
[2] U.S. Department of Transportation Architecture Development Team. National
Intelligent Transportation System (ITS) Architecture - Theory of Operations.
Tech. rep. Washington D.C., USA: U.S. Department of Transportation, 1998.
[3] Maria Caridi and Sergio Cavalieri. “Multi-agent systems in production planning
and control: an overview”. In: Production Planning Control 15.2 (2004), pp. 106–
118.
[4] Bo Chen and H H Cheng. “A Review of the Applications of Agent Technology
in Traffic and Transportation Systems”. In: IEEE Transactions on Intelligent
Transportation Systems 11.2 (2010), pp. 485–497.
[5] Rutger Claes and Tom Holvoet. Ad hoc link traversal time prediction. 2011.
[6] Rutger Claes and Tom Holvoet. “Ant Colony Optimization applied to Route
Planning Using Link Travel Time Predictions”. In: 2011 IEEE International
Symposium on Parallel Distributed Processing Workshops. 2011, pp. 358–365.
[7] Rutger Claes and Tom Holvoet. “GRIDLOCK : A MICROSCOPIC TRAFFIC
SIMULATION PLATFORM”. In: 2nd International Conference on Models
and Technologies for ITS (2011).
[8] Rutger Claes and Tom Holvoet. Maintaining a distributed symbiotic relationship
using delegate MultiAgent systems. Ed. by J Montoya-Torres J Hugan
B Johansson S Jain and EEditors Yücesan. 2010.
[9] Rutger Claes, Tom Holvoet, and Danny Weyns. “A Decentralized Approach for
Anticipatory Vehicle Routing Using Delegate Multiagent Systems”. In: IEEE
Transactions on Intelligent Transportation Systems 12.2 (2011), pp. 364–373.
[10] Daniel Delling et al. “Engineering Route Planning Algorithms”. In: Algorithmics
of large and complex networks 2 (2009). Ed. by Jürgen Lerner, DorotheaWagner,
and Katharina AEditors Zweig, pp. 117–139.
[11] E W Dijkstra. “A note on two problems in connexion with graphs”. In: Numerische
Mathematik 1.1 (1959), pp. 269–271.
[12] Klaus Dorer and Monique Calisti. “An adaptive solution to dynamic transport
optimization”. In: Proceedings of the fourth international joint conference on
Autonomous agents and multiagent systems AAMAS 05 05 (2005), p. 45.
[13] M Dorigo, V Maniezzo, and A Colorni. “Ant system: optimization by a colony
of cooperating agents.” In: IEEE transactions on systems man and cybernetics
Part B Cybernetics a publication of the IEEE Systems Man and Cybernetics
Society 26.1 (1996). Ed. by VEditor Maniezzo, pp. 29–41.
[14] Kurt Dresner and Peter Stone. “Multiagent Traffic Management: A Reservation-
Based Intersection Control Mechanism”. In: The Third International Joint
Conference on Autonomous Agents and Multiagent Systems. 2004, pp. 530–537.
[15] Kurt Dresner and Peter Stone. “Multiagent Traffic Management: Opportunities
for Multiagent Learning”. In: LAMAS 2005. Ed. by K. Tuyls et al. Vol. 3898.
Lecture Notes in Artificial Intelligence. Berlin: Springer Verlag, 2006, pp. 129–
138.
[16] Kurt Dresner and Peter Stone. “Sharing the Road: Autonomous Vehicles meet
Human Drivers”. In: The 20th International Joint Conference on Artificial
Intelligence. 2007, pp. 1263–68.
[17] Burak Eksioglu, Arif Volkan Vural, and Arnold Reisman. “The vehicle routing
problem: A taxonomic review”. In: Computers & Industrial Engineering 57.4
(2009), pp. 1472–1483.
[18] Andrey Glaschenko et al. “Multi-Agent Real Time Scheduling System for Taxi
Companies”. In: Proc of 8th Int Conf on Autonomous Agents and MultiAgent
Systems AAMAS 2009 Budapest Hungary. Aamas. Citeseer, 2009, pp. 29–36.
[19] Google’s GSON Java library to convert Java Objects into the JSON datainterchange
format. url: http://code.google.com/p/google-gson/.
[20] Shaza Hanif et al. “Delegate MAS for large scale and dynamic PDP: A case
study”. In: Intelligent Distributed Computing V, 2011, pp. 23–33.
[21] P E Hart, N J Nilsson, and B Raphael. “A Formal Basis for the Heuristic
Determination of Minimum Cost Paths”. In: Ieee Transactions On Systems
Science And Cybernetics 4.2 (1968), pp. 100–107.
[22] Tom Holvoet and Paul Valckenaers. “Exploiting the Environment for Coordinating
Agent Intentions”. In: Environments for MultiAgent Systems III 4389.2
(2007), 51U66.
[23] Tom Holvoet, Danny Weyns, and Paul Valckenaers. “Patterns of Delegate
MAS”. In: 2009 Third IEEE International Conference on SelfAdaptive and
SelfOrganizing Systems 1 (2009), pp. 1–9.
[24] Soumia Ichoua, Michel Gendreau, and Jean-Yves Potvin. “Exploiting Knowledge
About Future Demands for Real-Time Vehicle Dispatching”. In: Transportation
Science 40.2 (2006), pp. 211–225.
[25] D E Kaufman, R L Smith, and K EWunderlich. An iterative routing/assignment
method for anticipatory real-time route guidance. 1991.
[26] Arne Kesting, Martin Treiber, and Dirk Helbing. “General Lane-Changing
Model MOBIL for Car-Following Models”. In: Transportation Research Record
1999.1 (2007), pp. 86–94.
[27] J K Kok, C J Warmer, and I G Kamphuis. “PowerMatcher: multiagent control
in the electricity infrastructure”. In: Expert Systems 48.3 (2005), pp. 75–82.
[28] Niels Lang, H Moonen, and Fj Srour. “Multi Agent Systems in Logistics: A
Literature and State-of-the-art Review”. In: papersssrncom (2008), p. 69.
[29] Osamu Masutani et al. “Pheromone Model: Application to Traffic Congestion
Prediction”. In: Traffic (2005), pp. 182–196.
[30] R Montemanni et al. “Ant Colony System for a Dynamic Vehicle Routing
Problem”. In: Journal of Combinatorial Optimization 10.4 (2005), pp. 327–343.
[31] Najem Moussa. “Car accidents in cellular automata models for one-lane traffic
flow.” In: Physical Review E - Statistical, Nonlinear and Soft Matter Physics
68.3 Pt 2 (2003), p. 036127.
[32] T Nagatani. “Dynamical jamming transition induced by a car accident in
traffic-flow model of a two-lane roadway”. In: Physica A: Statistical Mechanics
and its applications 202.3-4 (1994), pp. 449–458.
[33] T Nagatani. “Effect of traffic accident on jamming transition in traffic-flow
model”. In: Journal of Physics A: Mathematical and General 26.19 (1993).
[34] Neuroph, the Java Neural Network Framework. url: http://neuroph.sourceforge.
net/.
[35] OpenStreetMap project. url: http://www.openstreetmap.org/.
[36] Sophie N Parragh, Karl F Doerner, and Richard F Hartl. “A survey on pickup
and delivery problems”. In: Journal für Betriebswirtschaft 58.2 (2008), pp. 81–
117.
[37] H Parunak and S Brueckner. “Concurrent Modeling of Alternative Worlds with
Polyagents”. In: MultiAgentBased Simulation VII (2007), pp. 128–141.
[38] H V D Parunak et al. “E Pluribus Unum: Polyagent and Delegate MAS
Architectures”. In: MultiAgentBased Simulation VIII International Workshop
MABS 2007 Honolulu HI USA May 15 2007 Revised and Invited Papers. Ed.
by Luis Antunes, Mario Paolucci, and EmmaEditors Norling. Vol. 5003. May.
Springer, 2008, pp. 36–51.
[39] Victor Pillac et al. “A Review of Dynamic Vehicle Routing Problems”. In:
Industrial Engineering CIRRELT-2011-62 (2011), pp. 0–28.
[40] A E Rizzoli. “Ant colony optimization for real-world vehicle routing problems”.
In: Swarm Intelligence 133.1 (2007), pp. 87–151.
[41] John A Sauter et al. “Performance of digital pheromones for swarming vehicle
control”. In: Proceedings of the fourth international joint conference on
Autonomous agents and multiagent systems AAMAS 05 July (2005), p. 903.
[42] E.J. Schmitt and H. Jula. Vehicle Route Guidance Systems: Classification and
Comparison. 2006.
[43] Christos Stergiou and Dimitrios Siganos. Neural Networks. url: http://
www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#
Contents.
[44] Wang Tao Wang Tao and Zhang Jing Zhang Jing. Analysis of Multiple Velocity
Difference model in two-lane traffic flow with an accident. 2008.
[45] B Tatomir and L Rothkrantz. “Hierarchical Routing in Traffic Using Swarm-
Intelligence”. In: Intelligent Transportation Systems Conference 2006 ITSC 06
IEEE (2006), pp. 230–235.
[46] Barrett W Thomas and Chelsea C White III. “Anticipatory Route Selection”.
In: Transportation Science 38.4 (2004), pp. 473–487.
[47] Jordi Tielens. “Samen verkeer voorspellen”. MA thesis. Belgium: Faculteit
Ingenieurswetenschappen, Katholieke Universiteit Leuven, 2012.
[48] L M Tolbert and F Z Peng. “Scalable multi-agent system for real-time electric
power management”. In: 2001 Power Engineering Society Summer Meeting
Conference Proceedings Cat No01CH37262 3.C (2001), pp. 1676–1679.
[49] Martin Treiber, Ansgar Hennecke, and Dirk Helbing. “Congested Traffic States
in Empirical Observations and Microscopic Simulations”. In: Physical Review
E 62.2 (2000), pp. 1805–1824.
[50] JWahle et al. “Decision dynamics in a traffic scenario”. In: Physica A: Statistical
Mechanics and its Applications 287.3-4 (2000), pp. 669–681.
[51] Danny Weyns, Tom Holvoet, and Alexander Helleboogh. “Anticipatory Vehicle
Routing using Delegate Multi-Agent Systems”. In: Scenario (2007), pp. 87–93.
[52] M. Wooldridge. An Introduction to MultiAgent Systems. JOHN WILEY &
SONS, LTD, 2009.
[53] Qiu Zhifeng et al. “A Multi-Agent System Architecture for Electrical Energy
Matching in a Microgrid”. In: Proceedings of Fourth IEEE Young Researchers
Symposium in Electrical Power Engineering (2008), pp. 1–5.
