Title: Multi-Agent Path Finding with Mutex Propagation
Mutex propagation is a form of efficient constraint propagation popularly used in AI planning 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 propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. 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 for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate. more »« less
Walker, Thayne T.; Sturtevant, Nathan R.; Felner, Ariel; Zhang, Han; Li, Jiaoyang; Kumar, T. K.(
, Proceedings of the International Conference on Automated Planning and Scheduling)
null
(Ed.)
Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.
Ren, Zhongqiang; Rathinam, Sivakumar; Choset, Howie(
, Proceedings of Robotics: Science and Systems)
NA
(Ed.)
Conventional Multi-Agent Path Finding (MAPF)
problems aim to compute an ensemble of collision-free paths
for multiple agents from their respective starting locations to
pre-allocated destinations. This work considers a generalized
version of MAPF called Multi-Agent Combinatorial Path Finding
(MCPF) where agents must collectively visit a large number of
intermediate target locations along their paths before arriving at
destinations. This problem involves not only planning collisionfree
paths for multiple agents but also assigning targets and
specifying the visiting order for each agent (i.e. multi-target
sequencing). To solve the problem, we leverage the well-known
Conflict-Based Search (CBS) for MAPF and propose a novel
framework called Conflict-Based Steiner Search (CBSS). CBSS
interleaves (1) the conflict resolving strategy in CBS to bypass
the curse of dimensionality in MAPF and (2) multiple traveling
salesman algorithms to handle the combinatorics in multi-target
sequencing, to compute optimal or bounded sub-optimal paths
for agents while visiting all the targets. Our extensive tests verify
the advantage of CBSS over baseline approaches in terms of
computing shorter paths and improving success rates within a
runtime limit for up to 20 agents and 50 targets. We also evaluate
CBSS with several MCPF variants, which demonstrates the
generality of our problem formulation and the CBSS framework.
Li, Jiaoyang; Ruml, Wheeler Ruml; Koenig, Sven(
, Proceedings of the AAAI Conference on Artificial Intelligence)
null
(Ed.)
Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a lead- ing two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.
Shahar, Tomer; Shekhar, Shashank; Atzmon, Dor; Saffidine, Abdallah; Juba, Brendan; Stern, Roni(
, Journal of Artificial Intelligence Research)
null
(Ed.)
In many real-world scenarios, the time it takes for a mobile agent, e.g., a robot, to move from one location to another may vary due to exogenous events and be difficult to predict accurately. Planning in such scenarios is challenging, especially in the context of Multi-Agent Pathfinding (MAPF), where the goal is to find paths to multiple agents and temporal coordination is necessary to avoid collisions. In this work, we consider a MAPF problem with this form of time uncertainty, where we are only given upper and lower bounds on the time it takes each agent to move. The objective is to find a safe solution, which is a solution that can be executed by all agents and is guaranteed to avoid collisions. We propose two complete and optimal algorithms for finding safe solutions based on well-known MAPF algorithms, namely, A* with Operator Decomposition (A* + OD) and Conflict-Based Search (CBS). Experimentally, we observe that on several standard MAPF grids the CBS-based algorithm performs better. We also explore the option of online replanning in this context, i.e., modifying the agents' plans during execution, to reduce the overall execution cost. We consider two online settings: (a) when an agent can sense the current time and its current location, and (b) when the agents can also communicate seamlessly during execution. For each setting, we propose a replanning algorithm and analyze its behavior theoretically and empirically. Our experimental evaluation confirms that indeed online replanning in both settings can significantly reduce solution cost.
Conventional Multi-Agent Path Finding (MAPF)
problems aim to compute an ensemble of collision-free paths
for multiple agents from their respective starting locations to
pre-allocated destinations. This work considers a generalized
version of MAPF called Multi-Agent Combinatorial Path Finding
(MCPF) where agents must collectively visit a large number
of intermediate target locations along their paths before arriving
at destinations. This problem involves not only planning
collision-free paths for multiple agents but also assigning targets
and specifying the visiting order for each agent (i.e., target
sequencing). To solve the problem, we leverage Conflict-Based
Search (CBS) for MAPF and propose a novel approach called
Conflict-Based Steiner Search (CBSS). CBSS interleaves (1) the
collision resolution strategy in CBS to bypass the curse of
dimensionality in MAPF and (2) multiple traveling salesman
algorithms to handle the combinatorics in target sequencing, to
compute optimal or bounded sub-optimal paths for agents while
visiting all the targets. We also develop two variants of CBSS that
trade off runtime against solution optimality. Our test results
verify the advantage of CBSS over the baselines in terms of
computing cheaper paths and improving success rates within a
runtime limit for up to 20 agents and 50 targets. Finally, we run
both Gazebo simulation and physical robot tests to validate that
the planned paths are executable
Zhang, H., Li, J., Surynek, P, Koenig, S., and Kumar, S. Multi-Agent Path Finding with Mutex Propagation. Retrieved from https://par.nsf.gov/biblio/10193991. Proceedings of the International Conference on Automated Planning and Scheduling 30.
Zhang, H., Li, J., Surynek, P, Koenig, S., & Kumar, S. Multi-Agent Path Finding with Mutex Propagation. Proceedings of the International Conference on Automated Planning and Scheduling, 30 (). Retrieved from https://par.nsf.gov/biblio/10193991.
Zhang, H., Li, J., Surynek, P, Koenig, S., and Kumar, S.
"Multi-Agent Path Finding with Mutex Propagation". Proceedings of the International Conference on Automated Planning and Scheduling 30 (). Country unknown/Code not available. https://par.nsf.gov/biblio/10193991.
@article{osti_10193991,
place = {Country unknown/Code not available},
title = {Multi-Agent Path Finding with Mutex Propagation},
url = {https://par.nsf.gov/biblio/10193991},
abstractNote = {Mutex propagation is a form of efficient constraint propagation popularly used in AI planning 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 propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. 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 for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
volume = {30},
author = {Zhang, H. and Li, J. and Surynek, P and Koenig, S. and Kumar, S.},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
