Today I read a paper titled “Asynchronous Decentralized Algorithm for Space-Time Cooperative Pathfinding”
The abstract is:
Cooperative pathfinding is a multi-agent path planning problem where a group of vehicles searches for a corresponding set of non-conflicting space-time trajectories
Many of the practical methods for centralized solving of cooperative pathfinding problems are based on the prioritized planning strategy
However, in some domains (e.g., multi-robot teams of unmanned aerial vehicles, autonomous underwater vehicles, or unmanned ground vehicles) a decentralized approach may be more desirable than a centralized one due to communication limitations imposed by the domain and/or privacy concerns
In this paper we present an asynchronous decentralized variant of prioritized planning ADPP and its interruptible version IADPP
The algorithm exploits the inherent parallelism of distributed systems and allows for a speed up of the computation process
Unlike the synchronized planning approaches, the algorithm allows an agent to react to updates about other agents’ paths immediately and invoke its local spatio-temporal path planner to find the best trajectory, as response to the other agents’ choices
We provide a proof of correctness of the algorithms and experimentally evaluate them on synthetic domains