skip to main content
10.5555/1402298.1402315acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Aligning social welfare and agent preferences to alleviate traffic congestion

Published: 12 May 2008 Publication History

Abstract

Multiagent coordination algorithms provide unique insights into the challenging problem of alleviating traffic congestion. What is particularly interesting in this class of problem is that no individual action (e.g., leave at a given time) is intrinsically "bad" but that combinations of actions among agents lead to undesirable outcomes. As a consequence, agents need to learn how to coordinate their actions with those of other agents, rather than learn a particular set of "good" actions. In general, the traffic problem can be approached from two distinct perspectives: (i) from a city manager's point of view, where the aim is to optimize a city wide objective function (e.g., minimize total city wide delays), and (ii) from the individual driver's point of view, where each driver is aiming to optimize a personal objective function (e.g., a "timeliness" function that minimizes the difference desired and actual arrival times at a destination). In many cases, these two objective functions are at odds with one another, where drivers aiming to optimize their own objectives yield to congestion and poor values of city objective functions.
In this paper we present an objective shaping approach to both types of problems and study the system behavior that arises from the drivers' choices. We first show a topdown approach that provides incentives to drivers and leads to good values of the city manager's objective function. We then present a bottom-up approach that shows that drivers aiming to optimize their own personal timeliness objective lead to poor performance with respect to a city manager's objective function. Finally, we present the intriguing result that drivers that aim to optimize a modified version of their own timeliness function not only perform well in terms of the city manager's objective function, but also perform better with respect to their own original timeliness functions.

References

[1]
A. Agogino and K. Tumer. Efficient evaluation functions for multi-rover systems. In The Genetic and Evolutionary Computation Conference, pages 1--12, Seatle, WA, June 2004.
[2]
M. Balmer, N. Cetin, K. Nagel, and B. Raney. Towards truly agent-based traffic and mobility simulations. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 60--67, New York, NY, July 2004.
[3]
M. Bando, K. Hasebe, A. Nakayama, A. Shibata, and Y. Sugiyama. Dynamical model of traffic congestion and numerical simulation. Physical Review E, 51(2):1035--1042, 1995.
[4]
A. L. Bazzan and F. Klügl. Case studies on the Braess paradox: simulating route recommendation and learning in abstract and microscopic models. Transportation Research C, 13(4):299--319, 2005.
[5]
A. L. Bazzan, J. Wahle, and F. Klügl. Agents in traffic modelling -- from reactive to social behaviour. In KI - Kunstliche Intelligenz, pages 303--306, 1999.
[6]
C. Boutilier. Planning, learning and coordination in multiagent decision processes. In Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, Holland, 1996.
[7]
B. Burmeister, A. Haddadi, and G. Matylis. Application of multi-agent systems in traffic and transportation. IEEE Proceedings in Software Engineering, 144(1):51--60, 1997.
[8]
C. R. Carter and N. R. Jennings. Social responsibility and supply chain relashipships. Transportation Research Part E, 38:37--52, 2002.
[9]
D. Challet and Y. C. Zhang. On the minority game: Analytical and numerical studies. Physica A, 256:514, 1998.
[10]
K. Dresner and P. Stone. Multiagent traffic management: A reservation-based intersection control mechanism. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 530--537, New York, NY, July 2004.
[11]
S. Hall and B. C. Draa. Collaborative driving system using teamwork for platoon formations. In The third workshop on Agents in Traffic and Transportation, 2004.
[12]
B. A. Huberman and T. Hogg. The behavior of computational ecologies. In The Ecology of Computation, pages 77--115. North-Holland, 1988.
[13]
P. Jefferies, M. L. Hart, and N. F. Johnson. Deterministic dynamics in the minority game. Physical Review E, 65 (016105), 2002.
[14]
N. R. Jennings, K. Sycara, and M. Wooldridge. A roadmap of agent research and development. Autonomous Agents and Multi-Agent Systems, 1:7--38, 1998.
[15]
B. S. Kerner and H. Rehborn. Experimental properties of complexity in traffic flow. Physical Review E, 53(5):R4275--4278, 1996.
[16]
F. Klügl, A. Bazzan, and S. Ossowski, editors. Applications of Agent Technology in Traffic and Transportation. Springer, 2005.
[17]
A. A. Lazar, A. Orda, and D. E. Pendarakis. Capacity allocation under noncooperative routing. IEEE Transactions on Networking, 5(6):861--871, 1997.
[18]
M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the 11th International Conference on Machine Learning, pages 157--163, 1994.
[19]
K. Nagel. Multi-modal traffic in TRANSIMS. In Pedestrian and Evacuation Dynamics, pages 161--172. Springer, Berlin, 2001.
[20]
D. C. Parkes. Iterative Combinatorial Auctions: Theory and Practice. PhD thesis, University of Pennsylvania, 2001.
[21]
T. Sandholm and R. Crites. Multiagent reinforcement learning in the iterated prisoner's dilemma. Biosystems, 37:147--166, 1995.
[22]
P. Stone and M. Veloso. Multiagent systems: A survey from a machine learning perspective. Autonomous Robots, 8(3):345--383, July 2000.
[23]
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998.
[24]
K. Tumer and D. Wolpert. A survey of collectives. In Collectives and the Design of Complex Systems, pages 1, 42. Springer, 2004.
[25]
K. Tumer and D. H. Wolpert. Collective intelligence and Braess' paradox. In Proceedings of the Seventeenth National Conference on Artificial Intelligence, pages 104--109, Austin, TX, 2000.

Cited By

View all
  • (2024)Influence-Focused Asymmetric Island ModelProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663127(2261-2263)Online publication date: 6-May-2024
  • (2024)Informed Diversity Search for Learning in Asymmetric Multiagent SystemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654206(313-321)Online publication date: 14-Jul-2024
  • (2024)Influence Based Fitness Shaping for Coevolutionary AgentsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654175(322-330)Online publication date: 14-Jul-2024
  • Show More Cited By

Index Terms

  1. Aligning social welfare and agent preferences to alleviate traffic congestion

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
    May 2008
    673 pages
    ISBN:9780981738116

    Sponsors

    In-Cooperation

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 12 May 2008

    Check for updates

    Author Tags

    1. multiagent systems
    2. optimization
    3. reinforcement learning
    4. traffic management
    5. transportation

    Qualifiers

    • Research-article

    Conference

    AAMAS08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Influence-Focused Asymmetric Island ModelProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663127(2261-2263)Online publication date: 6-May-2024
    • (2024)Informed Diversity Search for Learning in Asymmetric Multiagent SystemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654206(313-321)Online publication date: 14-Jul-2024
    • (2024)Influence Based Fitness Shaping for Coevolutionary AgentsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654175(322-330)Online publication date: 14-Jul-2024
    • (2023)Learning Synergies for Multi-Objective Optimization in Asymmetric Multiagent SystemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590524(447-455)Online publication date: 15-Jul-2023
    • (2023)Novelty Seeking Multiagent Evolutionary Reinforcement LearningProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590428(402-410)Online publication date: 15-Jul-2023
    • (2019)Runtime Revision of Norms and Sanctions based on Agent PreferencesProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331881(1609-1617)Online publication date: 8-May-2019

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media