  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.
