Robust Multi-Agent Path Finding
Dor Atzmon, Roni Stern, Ariel Felner et al. · Adaptive Agents and Multi-Agents Systems · 2018
In the multi-agent path-finding (MAPF) problem, the task is to find 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. We explore the notion of k -robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. 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 show the benefit of using a k -robust plan during execution, and for finding plans that are likely to succeed.
Cited by 30 works. doi:10.65109/foxs6890
Authors
References
- Conflict-based search for optimal multi-agent pathfinding
- Cooperative Pathfinding
- Benchmarks for Grid-Based Pathfinding
- Finding Optimal Solutions to Cooperative Pathfinding Problems
- Subdimensional expansion for multirobot path planning
- Planning optimal paths for multiple robots on graphs
- A General Formal Framework for Pathfinding Problems with Multiple Agents
- Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges
- Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving
- Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective