AlphaRoute: Large-Scale Coordinated Route Planning via Monte Carlo Tree Search
Authors:
Open Access
- 26 June 2023
- journal article
- research article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 37 (10) , 12058-12067
Abstract
This paper proposes AlphaRoute, an AlphaGo inspired algorithm for coordinating large-scale routes, built upon graph attention reinforcement learning and Monte Carlo Tree Search (MCTS). We first partition the road network into regions and model large-scale coordinated route planning as a Markov game, where each partitioned region is treated as a player instead of each driver. Then, AlphaRoute applies a bilevel optimization framework, consisting of several region planners and a global planner, where the region planner coordinates the route choices for vehicles located in the region and generates several strategies, and the global planner evaluates the combination of strategies. AlphaRoute is built on graph attention network for evaluating each state and MCTS algorithm for dynamically visiting and simulating the future state for narrowing down the search space. AlphaRoute is capable of 1) bridging user fairness and system efficiency, 2) achieving higher search efficiency by alleviating the curse of dimensionality problems, and 3) making an effective and informed route planning by simulating over the future to capture traffic dynamics. Comprehensive experiments are conducted on two real-world road networks as compared with several baselines to evaluate the performance, and results show that AlphaRoute achieves the lowest travel time, and is efficient and effective for coordinating large-scale routes and alleviating the traffic congestion problem. The code will be publicly available.Keywords
This publication has 19 references indexed in Scilit:
- Artificial Intelligence Powered Mobile Networks: From Cognition to DecisionIEEE Network, 2022
- Task Selection and Collision-Free Route Planning for Mobile Crowdsensing Using Multi-Population Mean-Field GamesIEEE Transactions on Green Communications and Networking, 2021
- A microsimulation based analysis of the price of anarchy in traffic routing: The enhanced Braess network caseJournal of Intelligent Transportation Systems, 2021
- Real-time deep reinforcement learning based vehicle navigationApplied Soft Computing, 2020
- Online Vehicle Routing With Neural Combinatorial Optimization and Deep Reinforcement LearningIEEE Transactions on Intelligent Transportation Systems, 2019
- Cooperative vehicular content distribution in edge computing assisted 5G-VANETChina Communications, 2018
- An agent-based model of the emergence of cooperation and a fair and stable system optimum using ATIS on a simple road networkTransportation Research Part C: Emerging Technologies, 2018
- Toward 5G Spectrum Sharing for Immersive-Experience-Driven Vehicular CommunicationsIEEE Wireless Communications, 2017
- Mastering the game of Go with deep neural networks and tree searchNature, 2016
- On the spatial partitioning of urban transportation networksTransportation Research Part B: Methodological, 2012