Projects per year
Abstract
Current approaches for real-world Multi-Agent Path Finding (MAPF) usually start with a simplified MAPF model and modify the resulting plans so they are kinematically feasible. We investigate one such problem, called MAPF with turn actions (MAPFT), and show that ignoring the kinematic constraints significantly increases solution cost. A first modification of the popular Conflict-Based Search algorithm to MAPFT yields significantly better plans but comes at the cost of substantial decreases in scalability. We then introduce several techniques that can improve the performance of CBS for MAPFT, including stronger and generalised versions of existing symmetry-breaking constraints and a novel pruning technique that eliminates redundant branches in the CBS constraint tree. Experimental results on six popular MAPF domains show convincing improvements for CBS success rate and substantial reductions in node expansions and runtime.
Original language | English |
---|---|
Title of host publication | Sixteenth International Symposium on Combinatorial Search 2023 |
Editors | Roman Barták, Wheeler Ruml, Oren Salzman |
Place of Publication | Washington DC USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 119-127 |
Number of pages | 9 |
ISBN (Electronic) | 139781577358824 |
DOIs | |
Publication status | Published - 2023 |
Event | International Symposium on Combinatorial Search 2023 - Prague, Czechia Duration: 14 Jul 2023 → 16 Jul 2023 Conference number: 16th https://ojs.aaai.org/index.php/SOCS/issue/view/565 (Proceedings) https://socs23.search-conference.org/ (Website) |
Publication series
Name | The International Symposium on Combinatorial Search |
---|---|
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Number | 1 |
Volume | 16 |
ISSN (Print) | 2832-9171 |
ISSN (Electronic) | 2832-9163 |
Conference
Conference | International Symposium on Combinatorial Search 2023 |
---|---|
Abbreviated title | SoCS 2023 |
Country/Territory | Czechia |
City | Prague |
Period | 14/07/23 → 16/07/23 |
Internet address |
|
Keywords
- Bounding And Pruning Techniques
- Constraint Search
- Symmetry Handling
- Search In Robotics
Projects
- 1 Finished
-
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