Jiaoyang Li, Graeme Gange, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig |
PosterID:
51
PDF
Slides
Poster
BibTeX
|
| We consider two new types 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 but in opposite directions. The second, target symmetry, arises when the individually optimal path of one agent requires the target location of a second agent after the second agent has already arrived. Undetected, these symmetries can produce an exponential blowup in the space of possible conflict resolutions, leading to timeout failure even for state-of-the-art algorithms such as Conflict-Based Search. We propose to break symmetries using new reasoning techniques that: (1) detects each type of situation and; (2) resolves them by introducing specialized constraints. We implement our ideas in the context of Conflict-Based Search where, in a range of experiments, we report up to an order-of-magnitude improvement in runtime performance and, in some cases, more than a doubling in success rate. | |
| Canb | 10/28/2020, 20:00 – 21:00 |
| 10/30/2020, 13:00 – 14:00 |
| Paris | 10/28/2020, 10:00 – 11:00 |
| 10/30/2020, 03:00 – 04:00 |
| NYC | 10/28/2020, 05:00 – 06:00 |
| 10/29/2020, 22:00 – 23:00 |
| LA | 10/28/2020, 02:00 – 03:00 |
| 10/29/2020, 19:00 – 20:00 |
Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search
Ryo Kuroiwa, Alex Fukunaga
New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding
Jiaoyang Li, Graeme Gange, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig
Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks
Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt
Contention-Aware Mapping and Scheduling Optimization for NoC-Based MPSoCs
Rongjie Yan, Yupeng Zhou, Anyu Cai, Changwen Li, Yige Yan, Minghao Yin