Reinforcement learning for route choice in an abstract traffic scenario

• Anderson Rocha Tavares UFRGS
• Ana Lucia Cetertich Bazzan UFRGS

DOI: https://doi.org/10.5753/wesaac.2012.33142

Resumo

Traffic movement in a commuting scenario is a phenomena that results from individual and uncoordinated route choice by drivers. Every driver wishes to achieve reasonable travel times from his origin to his destination and, from a global point of view, it is desirable that the load gets distributed proportionally to the roads capacity on the network. This work presents a reinforcement learning algorithm for route choice which relies solely on drivers experience to guide their decisions. Experimental results demonstrate that reasonable travel times can be achieved and vehicles distribute themselves over the road network avoiding congestion. The proposed algorithm makes use of no coordinated learning mechanism, making this work a case of use of independent learners concept.

Referências

Bazzan, A. L. C., Bordini, R. H., Andriotti, G. K., Viccari, R., and Wahle, J. (2000). Wayward agents in a commuting scenario (personalities in the minority game). In Proc. of the Int. Conf. on Multi-Agent Systems (ICMAS), pages 55–62. IEEE Computer Science.

Bazzan, A. L. C. and Klügl, F. (2008). Re-routing agents in an abstract traffic scenario. In Zaverucha, G. and da Costa, A. L., editors, Advances in artificial intelligence, number 5249 in Lecture Notes in Artificial Intelligence, pages 63–72, Berlin. Springer-Verlag.

Buşoniu, L., Babuska, R., and De Schutter, B. (2008). A comprehensive survey of multiagent reinforcement learning. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 38(2):156–172.

Chmura, T. and Pitz, T. (2007). An extended reinforcement algorithm for estimation of human behavior in congestion games. Journal of Artificial Societies and Social Simulation, 10(2).

Claus, C. and Boutilier, C. (1998). The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pages 746–752.

Galib, S. M. and Moser, I. (2011). Road traffic optimisation using an evolutionary game. In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, GECCO ’11, pages 519–526, New York, NY, USA. ACM.

Kaelbling, L. P., Littman, M., and Moore, A. (1996). Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237–285.

Klügl, F. and Bazzan, A. L. C. (2004). Simulated route decision behaviour: Simple heuristics and adaptation. In Selten, R. and Schreckenberg, M., editors, Human Behaviour and Traffic Networks, pages 285–304. Springer.

Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the 11th International Conference on Machine Learning, ML, pages 157–163, New Brunswick, NJ. Morgan Kaufmann.

Ortúzar, J. and Willumsen, L. G. (2001). Modelling Transport. John Wiley & Sons, 3rd edition.

Sen, S., Sekaran, M., and Hale, J. (1994). Learning to coordinate without sharing information. In Proceedings of the National Conference on Artificial Intelligence, pages 426–426. JOHN WILEY & SONS LTD.

Tan, M. (1993). Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the Tenth International Conference on Machine Learning (ICML 1993), pages 330–337. Morgan Kaufmann.

Wardrop, J. G. (1952). Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, volume 2, pages 325–378.

Watkins, C. J. C. H. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3):279–292.