Multi-Train Path Finding revisited

Zhe Chen, Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Sven Koenig

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

Abstract

Multi-Train Path Finding (MTPF) is a coordination problem that asks us to plan collision-free paths for a team of moving agents, where each agent occupies a sequence of locations at any given time. MTPF is useful for planning a range of real-world vehicles, including rail trains and road convoys. MTPF is closely related to another coordination problem known as k-Robust Multi-Agent Path Finding (kR-MAPF). Although similar in principle, the performance of optimal MTPF algorithms in practice lags far behind that of optimal kR-MAPF algorithms. In this work, we revisit the connection between them and reduce the performance gap. First, we show that, in many cases, a valid kR-MAPF plan is also a valid MTPF plan, which leads to a new and faster approach for collision resolution. We also show that many recently introduced improvements for kR-MAPF, such as lower-bounding heuristics and symmetry reasoning, can be extended to MTPF. Finally, we explore a new type of pairwise symmetry specific to MTPF. Our experiments show that these improvements yield large efficiency gains for optimal MTPF.
Original languageEnglish
Title of host publicationProceedings of the International Symposium on Combinatorial Search
EditorsLukás Chrpa, Alessandro Saetti
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages38-46
Number of pages9
ISBN (Electronic)1577358732
Publication statusPublished - 2022
EventInternational Symposium on Combinatorial Search 2022 - Vienna, Austria
Duration: 21 Jul 202223 Jul 2022
Conference number: 15th
https://ojs.aaai.org/index.php/SOCS/issue/view/524 (Published Proceedings)
https://sites.google.com/unibs.it/socs2022 (Conference Website)

Publication series

NameFifteenth International Symposium on Combinatorial Search
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number1
Volume15

Conference

ConferenceInternational Symposium on Combinatorial Search 2022
Abbreviated titleSOCS 2022
Country/TerritoryAustria
CityVienna
Period21/07/2223/07/22
Internet address

Keywords

  • Constraint Search
  • Problem Solving Using Search
  • Model-based Search
  • Symmetry Handling

Cite this