More Like this

1. Probabilistic Robust Multi-Agent Finding

   Atzmon, S.; Stern, R.; Felner, A.; Sturtevant, N.; Koenig, S. (January 2020, International Conference on Automated Planning and Scheduling (ICAPS))

   In a multi-agent path finding (MAPF) problem, the task is to move a set of agents to their goal locations without conflicts. In the real world, unexpected events may delay some of the agents. In this paper, we therefore study the problem of finding a p-robust solution to a given MAPF problem, which is a solution that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that given solutions are p-robust. We also introduce an optimal CBS-based algorithm, called pR-CBS, and a fast suboptimal algorithm, called pR-GCBS, for finding such solutions. Our experiments show that a p-robust solution reduces the number of conflicts compared to optimal, non-robust solutions. 

   more » « less
2. Safe Multi-Agent Pathfinding with Time Uncertainty

   https://doi.org/10.1613/jair.1.12397  

   Shahar, Tomer; Shekhar, Shashank; Atzmon, Dor; Saffidine, Abdallah; Juba, Brendan; Stern, Roni (January 2021, 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. 

   more » « less
3. Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding

   https://doi.org/10.1609/icaps.v33i1.27214  

   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
4. CBSS: A New Approach for Multiagent Combinatorial Path Finding

   https://doi.org/10.1109/TRO.2023.3266993  

   Ren, Zhongqiang; Rathinam, Sivakumar; Choset, Howie (April 2023, IEEE Transactions on Robotics)

   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
5. Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids

   https://doi.org/10.1609/SOCS.V16I1.27279  

   Geft, Tzvika (July 2023, Proceedings of the International Symposium on Combinatorial Search)

   Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem arising in multi-agent systems with a wide range of applications.The problem's intractability has led to extensive research on improving the scalability of solvers for it.Since optimal solvers can struggle to scale, a major challenge that arises is understanding what makes MAPF hard.We tackle this challenge through a fine-grained complexity analysis of time-optimal MAPF on 2D grids, thereby closing two gaps and identifying a new tractability frontier.First, we show that 2-colored MAPF, i.e., where the agents are divided into two teams, each with its own set of targets, remains NP-hard.Second, for the flowtime objective (also called sum-of-costs), we show that it remains NP-hard to find a solution in which agents have an individually optimal cost, which we call an individually optimal solution.The previously tightest results for these MAPF variants are for (non-grid) planar graphs.We use a single hardness construction that replaces, strengthens, and unifies previous proofs.We believe that it is also simpler than previous proofs for the planar case as it employs minimal gadgets that enable its full visualization in one figure.Finally, for the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in.Namely, we complement our hardness result, which holds for three directions, with an efficient algorithm for finding an individually optimal solution if only two directions are allowed.This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem. 

   more » « less