AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

Authors

Jiaoyang Li,Zhe Chen,Yi Zheng,Shao-Hung Chan,Daniel Harabor,Peter J. Stuckey,Hang Ma,Sven Koenig

University of Southern California,Monash University,University of Southern California,University of Southern California,Monash University,Monash University,Simon Fraser University,University of Southern California


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale railway networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF, or in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

DOI:

10.1609/socs.v12i1.18576


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search