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. Probabilistic Robust Multi-Agent Path Finding

   Atzmon, Dor; Li, Jiaoyang; Felner, Ariel; Nachmani, Eliran; Shperberg, Shahaf S.; Sturtevant, Nathan; Koenig, Sven (June 2020, Proceedings of the International Conference on Automated Planning and Scheduling)

   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
3. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

   Li, J.; Tinka, A.; Kiesel, S.; Durham, J.; Kumar, S.; Koenig, S. (January 2020, International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS))

   Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents from their start locations to their goal locations without collisions. We study the lifelong variant of MAPF where agents are constantly engaged with new goal locations, such as in warehouses. We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of agents only within a finite time horizon and ignores collisions beyond it. Our framework is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We evaluate our framework with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents, significantly outperforming existing methods. 

   more » « less
4. Scalable Mechanism Design for Multi-Agent Path Finding

   https://doi.org/10.24963/ijcai.2024/7  

   Friedrich, Paul; Zhang, Yulun; Curry, Michael; Dierks, Ludwig; McAleer, Stephen; Li, Jiaoyang; Sandholm, Tuomas; Seuken, Sven (August 2024, International Joint Conferences on Artificial Intelligence Organization)

   Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. This problem is computationally complex, especially when dealing with large numbers of agents, as is common in realistic applications like autonomous vehicle coordination. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. Adding to the complexity, agents might act in a self-interested and strategic way, possibly misrepresenting their goals to the MAPF algorithm if it benefits them. Although the field of mechanism design offers tools to align incentives, using these tools without careful consideration can fail when only having access to approximately optimal outcomes. In this work, we introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms. We test our mechanisms on realistic MAPF domains with problem sizes ranging from dozens to hundreds of agents. We find that they improve welfare beyond a simple baseline. 

   more » « less
5. Windowed MAPF with Completeness Guarantees

   https://doi.org/10.1609/aaai.v39i22.34499  

   Veerapaneni, Rishi; Saleem, Muhammad Suhail; Li, Jiaoyang; Likhachev, Maxim (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   Traditional multi-agent path finding (MAPF) methods try to compute entire collision free start-goal paths, with several algorithms offering completeness guarantees. However, computing partial paths offers significant advantages including faster planning, adaptability to changes, and enabling decentralized planning. Methods that compute partial paths employ a windowed approach and only try to find collision free paths for a limited timestep horizon. While this improves flexibility, this adaptation introduces incompleteness; all existing windowed approaches can become stuck in deadlock or livelock. Our main contribution is to introduce our framework, WinC-MAPF, for Windowed MAPF that enables completeness. Our framework leverages heuristic update insights from single-agent real-time heuristic search algorithms and agent independence ideas from MAPF algorithms. We also develop Single-Step Conflict Based Search (SS-CBS), an instantiation of this framework using a novel modification to CBS. We show how SS-CBS, which only plans a single step and updates heuristics, can effectively solve tough scenarios where existing windowed approaches fail. 

   more » « less