Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, T. K. Satish Kumar |
PosterID:
31
PDF
Poster
BibTeX
|
| Mutex propagation is a form of efficient constraint propagation popularly used in automated planning to tightly approximate the reachable states from a given state. We investigate the use of this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF problems, mutex propagation gives us a strong branching rule for Conflict-Based Search (CBS), a popular framework for solving MAPF optimally. This is derived from the strong ability of mutex propagation to identify and reason with symmetries in MAPF instances. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows us to design symmetry-breaking constraints automatically. Our experimental results show a significant advantage of mutex propagation over CBSH with rectangle reasoning, a state-of-the-art optimal MAPF solver. | |
| Canb | 10/28/2020, 04:00 – 05:00 |
| 10/31/2020, 11:00 – 12:00 |
| Paris | 10/27/2020, 18:00 – 19:00 |
| 10/31/2020, 01:00 – 02:00 |
| NYC | 10/27/2020, 13:00 – 14:00 |
| 10/30/2020, 20:00 – 21:00 |
| LA | 10/27/2020, 10:00 – 11:00 |
| 10/30/2020, 17:00 – 18:00 |
Efficient Robot Planning for Achieving Multiple Independent Partially Observable Tasks That Evolve over Time
Anahita Mohseni-Kabir, Manuela Veloso, Maxim Likhachev
Adaptive Informative Path Planning with Multimodal Sensing
Shushman Choudhury, Nate Gruver, Mykel J. Kochenderfer
Multi-Agent Path Finding with Mutex Propagation
Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, T. K. Satish Kumar
Real Time Crowd Navigation from First Principles of Probability Theory
Peter Trautman, Karankumar Patel