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 Search with Optimal Task Assignment
We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees.
more »
« less
- Award ID(s):
- 1724392
- NSF-PAR ID:
- 10073417
- Date Published:
- Journal Name:
- Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems
- ISSN:
- 1548-8403
- 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
-
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.more » « less
-
more » « less
Abstract We consider the problem of multi-robot path planning in a complex, cluttered environment with the aim of reducing overall congestion in the environment, while avoiding any inter-robot communication or coordination. Such limitations may exist due to lack of communication or due to privacy restrictions (for example, autonomous vehicles may not want to share their locations or intents with other vehicles or even to a central server). The key insight that allows us to solve this problem is to stochastically distribute the robots across different routes in the environment by assigning them paths in different topologically distinct classes, so as to lower congestion and the overall travel time for all robots in the environment. We outline the computation of topologically distinct paths in a spatio-temporal configuration space and propose methods for the stochastic assignment of paths to the robots. A fast replanning algorithm and a potential field based controller allow robots to avoid collision with nearby agents while following the assigned path. Our simulation and experiment results show a significant advantage over shortest path following under such a coordination-free setup.
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
