  An important capability of autonomous multi-robot systems is to prevent
collision among the individual robots. One approach to this problem is to plan
conflict-free trajectories and let each of the robots follow its pre-planned
trajectory. A widely used practical method for multi-robot trajectory planning
is prioritized planning, which has been shown to be effective in practice, but
is in general incomplete. Formal analysis of instances that are provably
solvable by prioritized planning is still missing. Moreover, prioritized
planning is a centralized algorithm, which may be in many situations
undesirable.
  In this paper we a) propose a revised version of prioritized planning and
characterize the class of instances that are provably solvable by the algorithm
and b) propose an asynchronous decentralized variant of prioritized planning,
which maintains the desirable properties of the centralized version and in the
same time exploits the distributed computational power of the individual
robots, which in most situations allows to find the joint trajectories faster.
  The experimental evaluation performed on real-world indoor maps shows that a)
the revised version of prioritized planning reliably solves a wide class of
instances on which both classical prioritized planning and popular reactive
technique ORCA fail and b) the asynchronous decentralized algorithm provides
solution faster than the previously proposed synchronized decentralized
algorithm.
