Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge

(Winner of the NeurIPS’20 Flatland Challenge).
Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma and Sven Koenig.
International Conference on Automated Planning and Scheduling (ICAPS), pages 477-485, 2021.
A short version appeared at the International Symposium on Combinatorial Search (SoCS), pages 179-181, 2021.
[bibtex] [code] [demo] [media] [pdf] [publisher] [talk]

@inproceedings{LiICAPS21,
  author    = {Jiaoyang Li and Zhe Chen and Yi Zheng and Shao-Hung Chan and Daniel Harabor and Peter J. Stuckey and Hang Ma and Sven Koenig},
  title     = {Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge},
  booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)},
  pages     = {477--485},
  year      = {2021}
}

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.