Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
DOI:
https://doi.org/10.1609/socs.v12i1.18576Keywords:
Meta Reasoning And SearchAbstract
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.Downloads
Published
2021-07-21
Issue
Section
Extended Abstracts