.png){kind=icon}
.png){kind=icon}
Return
Multi-agent path finding with mutex propagation
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2022.103766.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Mutex propagation is a form of efficient constraint propagation popularly used in AI plan-ning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex prop-agation provides stronger constraints for conflict resolution in CBS, a popular optimal search-based MAPF algorithm, as well as in MDD-SAT, an optimal satisfiability-based MAPF algorithm. Mutex propagation provides CBS with the ability to break symmetries in MAPF and provides MDD-SAT with the ability to make stronger inferences than unit propagation. While existing work identifies a limited form of symmetries and requires the manual de-sign of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH-RCT, a state-of-the-art variant of CBS, with respect to the success rate. We also show that MDD-SAT with mutex propagation often performs better than MDD-SAT with respect to the success rate. (C) 2022 Elsevier B.V. All rights reserved.
Keywords:
Heuristic search
Multi-agent path finding
Satisfiability solving
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W