Influence of participation rates and service level differentiation on community driven predictions
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
[1] Yasushi Ando et al. “Performance of pheromone model for predicting trafficcongestion”. In: Proceedings of the fifth international joint conference onAutonomous agents and multiagent systems AAMAS 06 (2006), p. 73.[2] U.S. Department of Transportation Architecture Development Team. NationalIntelligent 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 planningand 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 Technologyin Traffic and Transportation Systems”. In: IEEE Transactions on IntelligentTransportation 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 RoutePlanning Using Link Travel Time Predictions”. In: 2011 IEEE InternationalSymposium on Parallel Distributed Processing Workshops. 2011, pp. 358–365.[7] Rutger Claes and Tom Holvoet. “GRIDLOCK : A MICROSCOPIC TRAFFICSIMULATION PLATFORM”. In: 2nd International Conference on Modelsand Technologies for ITS (2011).[8] Rutger Claes and Tom Holvoet. Maintaining a distributed symbiotic relationshipusing delegate MultiAgent systems. Ed. by J Montoya-Torres J HuganB Johansson S Jain and EEditors Yücesan. 2010.[9] Rutger Claes, Tom Holvoet, and Danny Weyns. “A Decentralized Approach forAnticipatory Vehicle Routing Using Delegate Multiagent Systems”. In: IEEETransactions on Intelligent Transportation Systems 12.2 (2011), pp. 364–373.[10] Daniel Delling et al. “Engineering Route Planning Algorithms”. In: Algorithmicsof 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: NumerischeMathematik 1.1 (1959), pp. 269–271.[12] Klaus Dorer and Monique Calisti. “An adaptive solution to dynamic transportoptimization”. In: Proceedings of the fourth international joint conference onAutonomous agents and multiagent systems AAMAS 05 05 (2005), p. 45.[13] M Dorigo, V Maniezzo, and A Colorni. “Ant system: optimization by a colonyof cooperating agents.” In: IEEE transactions on systems man and cyberneticsPart B Cybernetics a publication of the IEEE Systems Man and CyberneticsSociety 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 JointConference on Autonomous Agents and Multiagent Systems. 2004, pp. 530–537.[15] Kurt Dresner and Peter Stone. “Multiagent Traffic Management: Opportunitiesfor 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 meetHuman Drivers”. In: The 20th International Joint Conference on ArtificialIntelligence. 2007, pp. 1263–68.[17] Burak Eksioglu, Arif Volkan Vural, and Arnold Reisman. “The vehicle routingproblem: 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 TaxiCompanies”. In: Proc of 8th Int Conf on Autonomous Agents and MultiAgentSystems AAMAS 2009 Budapest Hungary. Aamas. Citeseer, 2009, pp. 29–36.[19] Google’s GSON Java library to convert Java Objects into the JSON datainterchangeformat. url: http://code.google.com/p/google-gson/.[20] Shaza Hanif et al. “Delegate MAS for large scale and dynamic PDP: A casestudy”. In: Intelligent Distributed Computing V, 2011, pp. 23–33.[21] P E Hart, N J Nilsson, and B Raphael. “A Formal Basis for the HeuristicDetermination of Minimum Cost Paths”. In: Ieee Transactions On SystemsScience And Cybernetics 4.2 (1968), pp. 100–107.[22] Tom Holvoet and Paul Valckenaers. “Exploiting the Environment for CoordinatingAgent Intentions”. In: Environments for MultiAgent Systems III 4389.2(2007), 51U66.[23] Tom Holvoet, Danny Weyns, and Paul Valckenaers. “Patterns of DelegateMAS”. In: 2009 Third IEEE International Conference on SelfAdaptive andSelfOrganizing Systems 1 (2009), pp. 1–9.[24] Soumia Ichoua, Michel Gendreau, and Jean-Yves Potvin. “Exploiting KnowledgeAbout Future Demands for Real-Time Vehicle Dispatching”. In: TransportationScience 40.2 (2006), pp. 211–225.[25] D E Kaufman, R L Smith, and K EWunderlich. An iterative routing/assignmentmethod for anticipatory real-time route guidance. 1991.[26] Arne Kesting, Martin Treiber, and Dirk Helbing. “General Lane-ChangingModel MOBIL for Car-Following Models”. In: Transportation Research Record1999.1 (2007), pp. 86–94.[27] J K Kok, C J Warmer, and I G Kamphuis. “PowerMatcher: multiagent controlin 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: ALiterature and State-of-the-art Review”. In: papersssrncom (2008), p. 69.[29] Osamu Masutani et al. “Pheromone Model: Application to Traffic CongestionPrediction”. In: Traffic (2005), pp. 182–196.[30] R Montemanni et al. “Ant Colony System for a Dynamic Vehicle RoutingProblem”. In: Journal of Combinatorial Optimization 10.4 (2005), pp. 327–343.[31] Najem Moussa. “Car accidents in cellular automata models for one-lane trafficflow.” In: Physical Review E - Statistical, Nonlinear and Soft Matter Physics68.3 Pt 2 (2003), p. 036127.[32] T Nagatani. “Dynamical jamming transition induced by a car accident intraffic-flow model of a two-lane roadway”. In: Physica A: Statistical Mechanicsand its applications 202.3-4 (1994), pp. 449–458.[33] T Nagatani. “Effect of traffic accident on jamming transition in traffic-flowmodel”. 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 pickupand delivery problems”. In: Journal für Betriebswirtschaft 58.2 (2008), pp. 81–117.[37] H Parunak and S Brueckner. “Concurrent Modeling of Alternative Worlds withPolyagents”. In: MultiAgentBased Simulation VII (2007), pp. 128–141.[38] H V D Parunak et al. “E Pluribus Unum: Polyagent and Delegate MASArchitectures”. In: MultiAgentBased Simulation VIII International WorkshopMABS 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 vehiclecontrol”. In: Proceedings of the fourth international joint conference onAutonomous agents and multiagent systems AAMAS 05 July (2005), p. 903.[42] E.J. Schmitt and H. Jula. Vehicle Route Guidance Systems: Classification andComparison. 2006.[43] Christos Stergiou and Dimitrios Siganos. Neural Networks. url: http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html#C…] Wang Tao Wang Tao and Zhang Jing Zhang Jing. Analysis of Multiple VelocityDifference 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 06IEEE (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: FaculteitIngenieurswetenschappen, Katholieke Universiteit Leuven, 2012.[48] L M Tolbert and F Z Peng. “Scalable multi-agent system for real-time electricpower management”. In: 2001 Power Engineering Society Summer MeetingConference Proceedings Cat No01CH37262 3.C (2001), pp. 1676–1679.[49] Martin Treiber, Ansgar Hennecke, and Dirk Helbing. “Congested Traffic Statesin Empirical Observations and Microscopic Simulations”. In: Physical ReviewE 62.2 (2000), pp. 1805–1824.[50] JWahle et al. “Decision dynamics in a traffic scenario”. In: Physica A: StatisticalMechanics and its Applications 287.3-4 (2000), pp. 669–681.[51] Danny Weyns, Tom Holvoet, and Alexander Helleboogh. “Anticipatory VehicleRouting 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 EnergyMatching in a Microgrid”. In: Proceedings of Fourth IEEE Young ResearchersSymposium in Electrical Power Engineering (2008), pp. 1–5.