Robust Multi-Agent Path Finding and Executing
Dor Atzmon, Roni Stern, Ariel Felner et al. · Journal of Artificial Intelligence Research · 2020
Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.
Cited by 69 works. doi:10.1613/jair.1.11734 Open-access PDF
Authors
References
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths
- Conflict-based search for optimal multi-agent pathfinding
- Cooperative Pathfinding
- Benchmarks for Grid-Based Pathfinding
- Coordinating Pebble Motion On Graphs, The Diameter Of Permutation Groups, And Applications
- Finding Optimal Solutions to Cooperative Pathfinding Problems
- Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
- The increasing cost tree search for optimal multi-agent pathfinding
- Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs
- Subdimensional expansion for multirobot path planning