Abstract
We describe a new way of reasoning about symmetric collisions for Multi-Agent Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking constraint to resolve these conflicts. This specialized technique allows us to identify and eliminate, in a single step, all permutations of two currently assigned but incompatible paths. Each such permutation has exactly the same cost as a current path, and each one results in a new collision between the same two agents. We show that the addition of symmetry-breaking techniques can significantly speed up Conflict-Based Search (CBS), a popular framework for MAPF.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twelfth International Symposium on Combinatorial Search |
| Editors | Pavel Surynek, William Yeoh |
| Place of Publication | Palo Alto CA USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 184-185 |
| Number of pages | 2 |
| ISBN (Electronic) | 9781577358084 |
| Publication status | Published - 2019 |
| Event | International Symposium on Combinatorial Search 2019 - Napa, United States of America Duration: 16 Jul 2019 → 17 Jul 2019 Conference number: 12th https://ojs.aaai.org/index.php/SOCS/issue/view/439 (Proceedings) http://users.fit.cvut.cz/surynpav/socs2019/main.php?page=introduction (Website) |
Conference
| Conference | International Symposium on Combinatorial Search 2019 |
|---|---|
| Abbreviated title | SoCS 2019 |
| Country/Territory | United States of America |
| City | Napa |
| Period | 16/07/19 → 17/07/19 |
| Internet address |