Scalable rail planning and replanning: winning the 2020 Flatland Challenge

Jiaoyang Li, Zhe Chen, Yi Zheng, Shao Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

32 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First International Conference on Automated Planning and Scheduling
EditorsSusanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages477-485
Number of pages9
ISBN (Electronic)9781713832317, 9781577358671
Publication statusPublished - 2021
EventInternational Conference on Automated Planning and Scheduling 2021 - Online, Guangzhou, China
Duration: 2 Aug 202113 Aug 2021
Conference number: 31st
https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume2021-August
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2021
Abbreviated titleICAPS 2021
Country/TerritoryChina
CityGuangzhou
Period2/08/2113/08/21
Internet address

Cite this