Multi-Agent Reinforcement Learning for Markov Routing Games: A New Modeling Paradigm For Dynamic Traffic Assignment

Abstract

This paper aims to develop a paradigm that models the learning behavior of intelligent agents (including but not limited to autonomous vehicles, connected and automated vehicles, or human-driven vehicles with intelligent navigation systems where human drivers follow the navigation instructions completely) with a utility-optimizing goal and the system's equilibrating processes in a routing game among atomic selfish agents. Such a paradigm can assist policymakers in devising optimal operational and planning countermeasures under both normal and abnormal circumstances. To this end, we develop a Markov routing game (MRG) in which each agent learns and updates her own en-route path choice policy while interacting with others in transportation networks. To efficiently solve MRG, we formulate it as multi-agent reinforcement learning (MARL) and devise a mean field multi-agent deep Q learning (MF-MA-DQL) approach that captures the competition among agents. The linkage between the classical DUE paradigm and our proposed Markov routing game (MRG) is discussed. We show that the routing behavior of intelligent agents is shown to converge to the classical notion of predictive dynamic user equilibrium (DUE) when traffic environments are simulated using dynamic loading models (DNL). In other words, the MRG depicts DUEs assuming perfect information and deterministic environments propagated by DNL models. Four examples are solved to illustrate the algorithm efficiency and consistency between DUE and the MRG equilibrium, on a simple network without and with spillback, the Ortuzar Willumsen (OW) Network, and a real-world network near Columbia University's campus in Manhattan of New York City.

arXiv comment20 pages, 11 figures, published in Transportation Research Part C 137 (2022) 103560

References in corpus (7)

• Deep Reinforcement Learning for Multi-Agent Systems: A Review of Challenges, Solutions and Applications
• Mean Field Multi-Agent Reinforcement Learning
• Multi-agent Reinforcement Learning in Sequential Social Dilemmas
• Optimal Passenger-Seeking Policies on E-hailing Platforms Using Markov Decision Process and Imitation Learning
• Reward Design for Driver Repositioning Using Multi-Agent Reinforcement Learning
• Dynamic driving and routing games for autonomous vehicles on networks: A mean field game approach
• Learning Nash Equilibrium for General-Sum Markov Games from Batch Data

Cited by in corpus (2)

• AI-Driven Day-to-Day Route Choice
• Scalable and Reliable Multi-agent Reinforcement Learning for Traffic Assignment