Accelerating route choice learning with experience sharing in a commuting scenario: : An agent-based approach
Abstract
Navigation apps have become more and more popular, as they give information about the current traffic state to drivers who then adapt their route choice. In commuting scenarios, where people repeatedly travel between a particular origin and destination, people tend to learn and adapt to different situations. What if the experience gained from such a learning task is shared via an app? In this paper, we analyse the effects that adaptive driver agents cause on the overall network, when those agents share their aggregated experience about route choice in a reinforcement learning setup. In particular, in this investigation, Q-learning is used and drivers share what they have learnt about the system, not just information about their current travel times. Using a classical commuting scenario, we show that experience sharing can improve convergence times that underlie a typical learning task. Further, we analyse individual learning dynamics to get an impression how aggregate and individual dynamics are related to each other. Based on that interesting pattern of individual learning dynamics can be observed that would otherwise be hidden in an only aggregate analysis.
References
[1]
A.L.C. Bazzan, Aligning individual and collective welfare in complex socio-technical systems by combining metaheuristics and reinforcement learning, Eng. Appl. of AI 79 (2019), 23–33.
[2]
A.L.C. Bazzan and C. Chira, Hybrid evolutionary and reinforcement learning approach to accelerate traffic assignment (extended abstract), in: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), R. Bordini, E. Elkind, G. Weiss and P. Yolum, eds, IFAAMAS, 2015, pp. 1723–1724, http://www.aamas2015.com/en/AAMAS_2015_USB/aamas/p1723.pdf.
[3]
A.L.C. Bazzan, M. Fehler and F. Klügl, Learning to coordinate in a network of social drivers: The role of information, in: Proceedings of the International Workshop on Learning and Adaptation in MAS (LAMAS 2005), K. Tuyls, P.J. Hoen, K. Verbeeck and S. Sen, eds, Lecture Notes in Artificial Intelligence, 2006, pp. 115–128, www.inf.ufrgs.br/~bazzan/downloads/lamas38980115.pdf.gz.
[4]
A.L.C. Bazzan and R. Grunitzki, A multiagent reinforcement learning approach to en-route trip building, in: 2016 International Joint Conference on Neural Networks (IJCNN), 2016, pp. 5288–5295. ISSN.
[5]
A.L.C. Bazzan and F. Klügl, Experience sharing in a traffic scenario, in: Proc. of the 11th Int. Workshop on Agents in Traffic and Transportation, Santiago de Compostella, Spain, 4 Sept. 2020, 2020.
[6]
L.S. Buriol, M.J. Hirsh, P.M. Pardalos, T. Querido, M.G.C. Resende and M. Ritt, A biased random-key genetic algorithm for road congestion minimization, Optimization Letters 4 (2010), 619–633.
[7]
D. Cagara, B. Scheuermann and A.L.C. Bazzan, Traffic optimization on islands, in: 7th IEEE Vehicular Networking Conference (VNC 2015), IEEE, Kyoto, Japan, 2015, pp. 175–182.
[8]
C. Claus and C. Boutilier, The dynamics of reinforcement learning in cooperative multiagent systems, in: Proceedings of the Fifteenth National Conference on Artificial Intelligence, AAAI’98/IAAI’98, American Association for Artificial Intelligence, Menlo Park, CA, USA, 1998, pp. 746–752.
[9]
L. D’Acierno, B. Montella and F. De Lucia, A stochastic traffic assignment algorithm based on ant colony optimisation, in: Ant Colony Optimization and Swarm Intelligence, 5th International Workshop, ANTS 2006, M. Dorigo, L.M. Gambardella, M. Birattari, A. Martinoli, R. Poli and T. Stützle, eds, Lecture Notes in Computer Science, Vol. 4150, Springer-Verlag, Berlin, 2006, pp. 25–36.
[10]
H. Dia and S. Panwai, Intelligent Transport Systems: Neural Agent (Neugent) Models of Driver Behaviour, LAP Lambert Academic Publishing, 2014, http://books.google.com.br/books?id=fPXpoAEACAAJ. ISBN 9783659528682.
[11]
J.C. Dias, P. Machado, D.C. Silva and P.H. Abreu, An inverted ant colony optimization approach to traffic, Engineering Applications of Artificial Intelligence 36(0) (2014), 122–133.
[12]
A. Fachantidis, M.E. Taylor and I.P. Vlahavas, Learning to teach reinforcement learning agents, Machine Learning and Knowledge Extraction 1(1) (2019), 21–42.
[13]
S.M. Galib and I. Moser, Road traffic optimisation using an evolutionary game, in: Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO’11, ACM, New York, NY, USA, 2011, pp. 519–526. ISBN 978-1-4503-0690-4.
[14]
R. Grunitzki and A.L.C. Bazzan, Combining car-to-infrastructure communication and multi-agent reinforcement learning in route choice, in: Proceedings of the Ninth Workshop on Agents in Traffic and Transportation (ATT-2016), A.L.C. Bazzan, F. Klügl, S. Ossowski and G. Vizzari, eds, CEUR-WS.org, New York, 2016, http://ceur-ws.org/Vol-1678/paper12.pdf. ISSN.
[15]
F. Klügl and A.L.C. Bazzan, Simulation studies on adaptative route decision and the influence of information on commuter scenarios, Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 8(4) (2004), 223–232, taylorandfrancis.metapress.com/(rtuskx45aqmlhkysft50mq55)/app/home/contribution.asp?referrer.
[16]
J.R. Kok and N. Vlassis, Sparse cooperative Q-learning, in: Proceedings of the 21st. International Conference on Machine Learning (ICML), ACM Press, New York, USA, 2004, pp. 481–488.
[17]
A. Koster, A. Tettamanzi, A.L.C. Bazzan and C.d.C. Pereira, Using trust and possibilistic reasoning to deal with untrustworthy communication in VANETs, in: Proceedings of the 16th IEEE Annual Conference on Intelligent Transport Systems (IEEE-ITSC), IEEE, The Hague, The Netherlands, 2013, pp. 2355–2360.
[18]
L.J. LeBlanc, E.K. Morlok and W.P. Pierskalla, An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research 9(5) (1975), 309–318.
[19]
H. Lin, T. Roughgarden, É. Tardos and A. Walkover, Braess’s paradox, Fibonacci numbers, and exponential inapproximability, in: Automata, Languages and Programming, 32nd International Colloquium, ICALP, Springer, 2005, pp. 497–512.
[20]
K.S. Narendra and M.A.L. Thathachar, Learning Automata: An Introduction, Prentice-Hall, Upper Saddle River, NJ, USA, 1989. ISBN 0-13-485558-2.
[21]
D. Oliveira and A.L.C. Bazzan, Multiagent learning on traffic lights control: Effects of using shared information, in: Multi-Agent Systems for Traffic and Transportation, A.L.C. Bazzan and F. Klügl, eds, IGI Global, Hershey, PA, 2009, pp. 307–321. ISBN 978-160566226-8.
[22]
J. Ortúzar and L.G. Willumsen, Modelling Transport, 3rd edn, John Wiley & Sons, 2001.
[23]
G.d.O. Ramos, B.C. Da Silva, R. Rǎdulescu, A.L.C. Bazzan and A. Nowé, Toll-based reinforcement learning for efficient equilibria in route choice, The Knowledge Engineering Review 35 (2020).
[24]
G.d.O. Ramos, A.L.C. Bazzan and B.C. da Silva, Analysing the impact of travel information for minimising the regret of route choice, Transportation Research Part C: Emerging Technologies 88 (2018), 257–271.
[25]
G.d.O. Ramos, B.C. da Silva and A.L.C. Bazzan, Learning to minimise regret in route choice, in: Proc. of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), S. Das, E. Durfee, K. Larson and M. Winikoff, eds, IFAAMAS, São Paulo, 2017, pp. 846–855, http://ifaamas.org/Proceedings/aamas2017/pdfs/p846.pdf.
[26]
G.d.O. Ramos and R. Grunitzki, An improved learning automata approach for the route choice problem, in: Agent Technology for Intelligent Mobile Services and Smart Societies, F. Koch, F. Meneguzzi and K. Lakkaraju, eds, Communications in Computer and Information Science, Vol. 498, Springer, Berlin, Heidelberg, 2015, pp. 56–67. ISBN 978-3-662-46240-9.
[27]
S. Seele, R. Herpers and C. Bauckhage, Cognitive agents for microscopic traffic simulations in virtual environments, in: Proc. of ICEC 2012, M. Herrlich, R. Malaka and M. Masuch, eds, LNCS, Vol. 7522, 2012, pp. 318–325.
[28]
G. Sharon, J.P. Hanna, T. Rambha, M.W. Levin, M. Albert, S.D. Boyles and P. Stone, Real-time adaptive tolling scheme for optimized social welfare in traffic networks, in: Proc. of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), S. Das, E. Durfee, K. Larson and M. Winikoff, eds, IFAAMAS, São Paulo, 2017, pp. 828–836.
[29]
M. Tan, Multi-agent reinforcement learning: Independent vs. cooperative agents, in: Proceedings of the Tenth International Conference on Machine Learning (ICML 1993), Morgan Kaufmann, 1993, pp. 330–337. ISBN 1-55860-307-7.
[30]
A. Taylor, I. Dusparic, E.G. López, S. Clarke and V. Cahill, Accelerating learning in multi-objective systems through transfer learning, in: 2014 International Joint Conference on Neural Networks (IJCNN), IEEE, Beijing, China, 2014, pp. 2298–2305.
[31]
L. Torrey and M.E. Taylor, Teaching on a budget: Agents advising agents in reinforcement learning, in: Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, IFAAMAS, St. Paul, MN, USA, 2013, https://dl.acm.org/doi/10.5555/2484920.2485086.
[32]
J.G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, Part II 1(3) (1952), 325–362.
[33]
C.J.C.H. Watkins and P. Dayan, Q-learning, Machine Learning 8(3) (1992), 279–292.
[34]
M. Witt, K. Kompaß, L. Wang, R. Kates, M. Mai and G. Prokop, Driver profiling – data-based identification of driver behavior dimensions and affecting driver characteristics for multi-agent traffic simulation, Transportation Research Part F: Traffic Psychology and Behaviour 64 (2019), 361–376.
[35]
T. Yamashita, K. Izumi and K. Kurumatani, Analysis of the effect of route information sharing on reduction of traffic congestion, in: Application of Agent Technology in Traffic and Transportation, F. Klügl, A.L.C. Bazzan and S. Ossowski, eds, Birkhäuser, 2004, pp. 99–112.
[36]
J.Y. Yen, Finding the K shortest loopless paths in a network, Management Science 17(11) (1971), 712–716.
[37]
M. Zimmer, P. Viappiani and P. Weng, Teacher–student framework: A reinforcement learning approach, in: AAMAS Workshop Autonomous Robots and Multirobot Systems, Paris, France, 2014, https://hal.archives-ouvertes.fr/hal-01215273.
Index Terms
- Accelerating route choice learning with experience sharing in a commuting scenario: An agent-based approach
Index terms have been assigned to the content through auto-classification.
Recommendations
A multi-agent reinforcement learning with weighted experience sharing
ICIC'11: Proceedings of the 7th international conference on Advanced Intelligent Computing Theories and Applications: with aspects of artificial intelligenceReinforcement Learning, also sometimes called learning by rewards and punishments is the problem faced by an agent that must learn behavior through trial-and-error interactions with a dynamic environment [1]. With repeated trials however, it is expected ...
Comparing paradigms for strategy learning of route choice with traffic information under uncertainty
Travellers route choice dynamics with endogenous reliability of ATIS are modelled.Joint strategy fictitious play model best describes route choice learning process.In case of low accuracy of information, choice behaviour tends towards randomness. This ...
Is Reinforcement Learning the Choice of Human Learners?: A Case Study of Taxi Drivers
SIGSPATIAL '20: Proceedings of the 28th International Conference on Advances in Geographic Information SystemsLearning to make optimal decisions is a common yet complicated task. While computer agents can learn to make decisions by running reinforcement learning (RL), it remains unclear how human beings learn. In this paper, we perform the first data-driven ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2021 – IOS Press. All rights reserved.
Publisher
IOS Press
Netherlands
Publication History
Published: 01 January 2021
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Jan 2025