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

Keywords:

Meta Reasoning And Search

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 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