More Like this

1. Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding

   Ren, Zhongqiang ; Li, Jiaoyang ; Zhang, Han ; Koenig, Sven ; Rathinam, Sivakumar ; Choset, Howie ( July 2023 , International Conference on Automated Planning and Scheduling)

   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
2. Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding.

   Ren, Zhongqiang ; Rathinam, Sivakumar ; Choset, Howie ( January 2022 , 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. 

   more » « less
3. Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding

   https://doi.org/10.1109/ICRA48891.2023.10160864  

   Ren, Zhongqiang ; Zhang, Chaoran ; Rathinam, Sivakumar ; Choset, Howie ( May 2023 , IEEE)

   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
4. Conflict-Based Search with Optimal Task Assignment

   Hoenig, W. ; Kiesel, S. ; Tinka, A. ; Durham, J. ; Ayanian, N. ( January 2018 , Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems)

   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
5. EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

   Li, Jiaoyang ; Ruml, Wheeler Ruml ; Koenig, Sven ( January 2021 , 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. 

   more » « less