Abstract
We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling |
Editors | J. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 193-201 |
Number of pages | 9 |
ISBN (Electronic) | 9781577358244 |
Publication status | Published - 1 Jun 2020 |
Event | International Conference on Automated Planning and Scheduling 2020 - Nancy, France Duration: 26 Oct 2020 → 30 Oct 2020 Conference number: 30th https://aaai.org/ojs/index.php/ICAPS/issue/view/263 (Proceedings) https://icaps20.icaps-conference.org (Website) |
Publication series
Name | Proceedings International Conference on Automated Planning and Scheduling, ICAPS |
---|---|
Publisher | The AAAI Press |
Volume | 30 |
ISSN (Print) | 2334-0835 |
ISSN (Electronic) | 2334-0843 |
Conference
Conference | International Conference on Automated Planning and Scheduling 2020 |
---|---|
Abbreviated title | ICAPS 2020 |
Country/Territory | France |
City | Nancy |
Period | 26/10/20 → 30/10/20 |
Internet address |
|