A market-inspired approach to reservation-based urban road traffic management

ABSTRACT

Urban road traffic management is an example of a socially relevant problem that can be modelled as a large-scale, open, distributed system, composed of many autonomous interacting agents, which need to be controlled in a decentralized manner. Most models for urban road traffic management rely on control elements that act on traffic flows. Dresner and Stone have put forward the idea of an advanced urban road traffic infrastructure that allows for cars to individually reserve space and time at an intersection so as to be able to safely cross it.

In this paper we extend Dresner and Stone's approach to networks of intersections. For this purpose, we draw upon market-inspired control methods as a paradigm for urban road traffic management. We conceive the system as a computational economy, where driver agents trade with infrastructure agents in a virtual marketplace, purchasing reservations to cross intersections when commuting through the city. We show that in situations of similar traffic load, an increase of the infrastructure's monetary benefit usually implies a decrease of the drivers' average travel times.

REFERENCES

• 1: Gabriel Balan , Sean Luke, History-based traffic control, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160743]
• 2: A. Bazzan and F. Klügl Reducing the Effects of the Braess Paradox with Information Manipulation Application of Agent Technology in Traffic and Transportation, pp. 85--97, Birkhäuser, 2005.
• 3: Ana L. C. Bazzan , Robert Junges, Congestion tolls as utility alignment between agent and system optimum, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160653]
• 4: A. Bazzan and F. Klügl Multi-agent Architectures for Traffic and Transportation Engineering IGI-Global, forthcoming, 2008.
• 5: Ana L. Bazzan, Opportunities for multiagent systems and multiagent reinforcement learning in traffic control, Autonomous Agents and Multi-Agent Systems, v.18 n.3, p.342-375, June 2009 [doi>10.1007/s10458-008-9062-9]
• 6: Scott H. Clearwater, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 7: K. M. Dresner and P. Stone. A Multiagent Approach to Autonomous Intersection Management. Journal of Artificial Intelligence Research, 31:591--656, 2008.
• 8: Reference omitted for blind review
• 9: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 10: Robert Junges , Ana L. C. Bazzan, Evaluating the performance of DCOP algorithms in a real world, dynamic problem, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 11: Lior Kuyer , Shimon Whiteson , Bram Bakker , Nikos Vlassis, Multiagent Reinforcement Learning for Urban Traffic Control Using Coordination Graphs, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_61]
• 12: http://www.marketbasedcontrol.com/
• 13: M. Meyer and E. J. Miller. Urban Transportation Planning. McGraw-Hill, 1984.
• 14: K. Nagel and M. Schreckenberg. A Cellular Automaton Model for Freeway Traffic. J. Phys. I France 2, pp. 2221--2229, 1992.
• 15: R. Rossetti and S. Bampi and R. Liu and D. Van Vliet and H. Cybis. An Agent-based Framework for the Assessment of Drivers' Decision Making. Proceedings of the 3rd Annual IEEE Conference on Intelligent Transportation Systems, pp. 387--392, 2000.
• 16: T. Schwerdtfeger. DYNEMO: A Model for the Simulation of Traffic Flow in Motorway Networks. Proceedings of the 9th International Symposium on Transportation and Traffic Theory, pp. 65--87, 1984.
• 17: Kagan Tumer , Adrian Agogino, Distributed agent-based air traffic flow management, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329434]
• 18: C. Watkins. Learning from Delayed Rewards PhD Thesis, King's College, Cambridge, UK, 1989.
• 19: B. Wie and R. Tobin. Dynamic Congestion Pricing for General Traffic Networks Transportation Research Part B, Vol. 32 No. 5, pp. 313--327, 1998.
• 20: D. Wolpert and K. Tumer. Optimal Payoff Functions for Members of Collectives. Advances in Complex Systems, volume 04, issue 02, pp. 265--279, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents; Multiagent systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
market-based coordination mechanisms, reinforcement learning, traffic and transportation