Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

Authors

  • Jiaoyang Li University of Southern California
  • Zhe Chen Monash University
  • Yi Zheng University of Southern California
  • Shao-Hung Chan University of Southern California
  • Daniel Harabor Monash University
  • Peter J. Stuckey Monash University
  • Hang Ma Simon Fraser University
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/icaps.v31i1.15994

Keywords:

Integration Of Multiple Planning And Scheduling Techniques, Or Of Planning And Scheduling Techniques With Techniques From Other Areas Or Disciplines, Experiences In Development, Deployment, And Maintenance Of Planning And Scheduling Applications, Industry / Application Challenge Problems, Engineering Issues In Using Planning And Scheduling Techniques

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 rail 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.
ICAPS-21 Proceedings Cover

Downloads

Published

2021-05-17

How to Cite

Li, J., Chen, Z., Zheng, Y., Chan, S.-H., Harabor, D., Stuckey, P. J., Ma, H., & Koenig, S. (2021). Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 477-485. https://doi.org/10.1609/icaps.v31i1.15994

Issue

Vol. 31 (2021): Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling

Section

Novel Applications Track