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

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

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

45 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 language	English
Title of host publication	Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling
Editors	Susanne Biundo, Minh Do, Robert Goldman, Michael Katz, Qiang Yang, Hankz Hankui Zhuo
Place of Publication	Palo Alto CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	477-485
Number of pages	9
ISBN (Electronic)	9781713832317, 9781577358671
Publication status	Published - 2021
Event	International Conference on Automated Planning and Scheduling 2021 - Online, Guangzhou, China Duration: 2 Aug 2021 → 13 Aug 2021 Conference number: 31st https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings)

Publication series

Name	Proceedings International Conference on Automated Planning and Scheduling, ICAPS
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Volume	2021-August
ISSN (Print)	2334-0835
ISSN (Electronic)	2334-0843

Conference

Conference	International Conference on Automated Planning and Scheduling 2021
Abbreviated title	ICAPS 2021
Country/Territory	China
City	Guangzhou
Period	2/08/21 → 13/08/21
Internet address	https://ojs.aaai.org/index.php/ICAPS/issue/view/380 (Proceedings)

Access to Document

373564393-oaFinal published version, 8.39 MB

https://ojs.aaai.org/index.php/ICAPS/article/view/15994

Cite this

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. In S. Biundo, M. Do, R. Goldman, M. Katz, Q. Yang, & H. H. Zhuo (Eds.), Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (pp. 477-485). (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 2021-August). Association for the Advancement of Artificial Intelligence (AAAI). https://ojs.aaai.org/index.php/ICAPS/article/view/15994

Li, Jiaoyang ; Chen, Zhe ; Zheng, Yi et al. / Scalable rail planning and replanning : winning the 2020 Flatland Challenge. Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling. editor / Susanne Biundo ; Minh Do ; Robert Goldman ; Michael Katz ; Qiang Yang ; Hankz Hankui Zhuo. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2021. pp. 477-485 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

@inproceedings{2cf33203b2d14182b64985464de9c40f,

title = "Scalable rail planning and replanning: winning the 2020 Flatland Challenge",

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.",

author = "Jiaoyang Li and Zhe Chen and Yi Zheng and Chan, \{Shao Hung\} and Daniel Harabor and Stuckey, \{Peter J.\} and Hang Ma and Sven Koenig",

note = "Funding Information: The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1409987, 1724392, 1817189, 1837779, and 1935712 as well as a gift from Amazon. The Research at Monash University was partially supported by the Australian Research Council (ARC) under grant numbers DP190100013 and DP200100025 as well as a gift from Amazon. The research at Simon Fraser University was supported by the Natural Sciences and Engineering Research Council (NSERC) under grant number RGPIN-2020-06540. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government. Publisher Copyright: Copyright {\textcopyright} 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; International Conference on Automated Planning and Scheduling 2021, ICAPS 2021 ; Conference date: 02-08-2021 Through 13-08-2021",

year = "2021",

language = "English",

series = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

pages = "477--485",

editor = "Susanne Biundo and Minh Do and Robert Goldman and Michael Katz and Qiang Yang and Zhuo, \{Hankz Hankui\}",

booktitle = "Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling",

address = "United States of America",

url = "https://ojs.aaai.org/index.php/ICAPS/issue/view/380",

}

Li, J, Chen, Z, Zheng, Y, Chan, SH, Harabor, D , Stuckey, PJ, Ma, H & Koenig, S 2021, Scalable rail planning and replanning: winning the 2020 Flatland Challenge. in S Biundo, M Do, R Goldman, M Katz, Q Yang & HH Zhuo (eds), Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling. Proceedings International Conference on Automated Planning and Scheduling, ICAPS, vol. 2021-August, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 477-485, International Conference on Automated Planning and Scheduling 2021, Guangzhou, China, 2/08/21. <https://ojs.aaai.org/index.php/ICAPS/article/view/15994>

Scalable rail planning and replanning: winning the 2020 Flatland Challenge. / Li, Jiaoyang; Chen, Zhe; Zheng, Yi et al.
Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling. ed. / Susanne Biundo; Minh Do; Robert Goldman; Michael Katz; Qiang Yang; Hankz Hankui Zhuo. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2021. p. 477-485 (Proceedings International Conference on Automated Planning and Scheduling, ICAPS; Vol. 2021-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Scalable rail planning and replanning

T2 - International Conference on Automated Planning and Scheduling 2021

AU - Li, Jiaoyang

AU - Chen, Zhe

AU - Zheng, Yi

AU - Chan, Shao Hung

AU - Harabor, Daniel

AU - Stuckey, Peter J.

AU - Ma, Hang

AU - Koenig, Sven

N1 - Conference code: 31st

PY - 2021

Y1 - 2021

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

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

UR - https://www.scopus.com/pages/publications/85105819190

M3 - Conference Paper

AN - SCOPUS:85105819190

T3 - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

SP - 477

EP - 485

BT - Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling

A2 - Biundo, Susanne

A2 - Do, Minh

A2 - Goldman, Robert

A2 - Katz, Michael

A2 - Yang, Qiang

A2 - Zhuo, Hankz Hankui

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

Y2 - 2 August 2021 through 13 August 2021

ER -

Li J, Chen Z, Zheng Y, Chan SH, Harabor D , Stuckey PJ et al. Scalable rail planning and replanning: winning the 2020 Flatland Challenge. In Biundo S, Do M, Goldman R, Katz M, Yang Q, Zhuo HH, editors, Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2021. p. 477-485. (Proceedings International Conference on Automated Planning and Scheduling, ICAPS).

Scalable rail planning and replanning: winning the 2020 Flatland Challenge

Abstract

Publication series

Conference

Access to Document

Other files and links

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this

Scalable rail planning and replanning: winning the 2020 Flatland Challenge

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Improved Constraint Reasoning for Robust Multi-agent Path Planning

Personalised Public Transport

Cite this