Projects per year
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 language | English |
---|---|
Title of host publication | Proceedings of the International Symposium on Combinatorial Search |
Editors | Lukás Chrpa, Alessandro Saetti |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 38-46 |
Number of pages | 9 |
ISBN (Electronic) | 1577358732 |
Publication status | Published - 2022 |
Event | International Symposium on Combinatorial Search 2022 - Vienna, Austria Duration: 21 Jul 2022 → 23 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
Name | Fifteenth International Symposium on Combinatorial Search |
---|---|
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Number | 1 |
Volume | 15 |
Conference
Conference | International Symposium on Combinatorial Search 2022 |
---|---|
Abbreviated title | SOCS 2022 |
Country/Territory | Austria |
City | Vienna |
Period | 21/07/22 → 23/07/22 |
Internet address |
|
Keywords
- Constraint Search
- Problem Solving Using Search
- Model-based Search
- Symmetry Handling
-
Personalised Public Transport
Harabor, D. (Primary Chief Investigator (PCI)), Moser, I. (Chief Investigator (CI)) & Ronald, N. (Chief Investigator (CI))
24/06/19 → 31/12/25
Project: Research
-
Improved Constraint Reasoning for Robust Multi-agent Path Planning
Stuckey, P. (Primary Chief Investigator (PCI)), Harabor, D. (Chief Investigator (CI)), Le Bodic, P. (Chief Investigator (CI)), Gange, G. (Chief Investigator (CI)) & Koenig, S. (Partner Investigator (PI))
1/01/20 → 31/12/24
Project: Research