Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
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
AbstractMulti-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.
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
Novel Applications Track