Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
| Multi-agent path finding Rail planning Robust planning under uncertainty |
PaperID: 165
pdf
poster
|
| 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. | |
Session 6: Search
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 and Sven Koenig
Keywords:
Multi-agent path findingRail planningRobust planning under uncertainty
A Competitive Analysis of Online Multi-Agent Path Finding
Authors: Hang Ma
Keywords:
multi-agent path findingcompetitive analysisonline algorithms
Conflict-Based Increasing Cost Search
Authors: Thayne T. Walker, Nathan Sturtevant, Han Zhang, Jiaoyang Li, Sven Koenig, Ariel Felner and T. K. Satish Kumar
Keywords:
multi-agentsearchheuristic searchplanning
Speeding Up Search-Based Motion Planning using Expansion Delay Heuristics
Authors: Jasmeet Kaur, Ishani Chatterjee and Maxim Likhachev
Keywords:
Learning HeuristicsMotion PlanningHeuristic Search