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
more »
« less
Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding.
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.
more »
« less
- Award ID(s):
- 2120529
- NSF-PAR ID:
- 10354016
- Editor(s):
- NA
- Date Published:
- Journal Name:
- Proceedings of Robotics: Science and Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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.more » « less
-
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.more » « less
-
Andrei Ciortea ; Mehdi Dastani ; Jieting Luo (Ed.)The Multi-Agent Path Finding (MAPF) is a problem of finding a plan for agents to reach their desired locations without colliding. Distributed Multi-Agent Path Finder (DMAPF) solves the MAPF problem by decomposing a given MAPF problem instance into smaller subproblems and solve them in parallel. DMAPF works in rounds. Between two consecutive rounds, agents may migrate between two adjacent subproblems following their abstract plans, which are pre-computed, until all of them reach the areas that contain their desired locations. Previous works on DMAPF compute an abstract plan for each agent without the knowledge of other agents’ abstract plans, resulting in high congestion in some areas, especially those that act as corridors. The congestion negatively impacts the runtime of DMAPF and prevents it from being able to solve dense MAPF problems. In this paper, we (i) investigate the use of Uniform-Cost Search to mitigate the congestion. Additionally, we explore the use of several other techniques including (ii) using timeout estimation to preemptively stop solving and relax a subproblem when it is likely to get stuck; (iii) allowing a solving process to manage multiple subproblems – aimed to increase concurrency; and (iv) integrating with MAPF solvers from the Conflict-Based Search family. Experimental results show that our new system is several times faster than the previous ones; can solve larger and denser problems that were unsolvable before; and has better runtime than PBS and EECBS, which are state-of-the-art centralized suboptimal MAPF solvers, in problems with a large number of agents.more » « less
-
Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Paretooptimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
