Fault-Tolerant Offline Multi-Agent Path Planning
This addresses the need for reliable multi-robot systems by enabling fault tolerance in path planning, though it appears incremental as it builds on existing multi-agent planning with added crash-handling mechanisms.
The paper tackles the problem of offline multi-agent path planning where agents may crash and block parts of the workspace, proposing a method to prepare paths and switching rules so that all correct agents reach their destinations without collisions or deadlocks despite unforeseen crashes.
We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace. In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks, despite unforeseen crashes of other agents. Such planning is attractive to build reliable multi-robot systems. We present problem formalization, theoretical analysis such as computational complexities, and how to solve this offline planning problem.