  Planning collision-free paths for multi-robot systems (MRS) is a challenging
problem because of the safety and efficiency constraints required for
real-world solutions. Even though coupled path planning approaches provide
optimal collision-free paths for each agent of the MRS, they search the
composite space of all the agents and therefore, suffer from exponential
increase in computation with the number of robots. On the other hand,
prioritized approaches provide a practical solution to applications with large
number of robots, especially when path computation time and collision avoidance
take precedence over guaranteed globally optimal solution. While most
centrally-planned algorithms use static prioritization, a dynamic
prioritization algorithm, PD*, is proposed that employs a novel metric, called
freedom index, to decide the priority order of the robots at each time step.
This allows the PD* algorithm to simultaneously plan the next step for all
robots while ensuring collision-free operation in obstacle ridden environments.
Extensive simulations were performed to test and compare the performance of the
proposed PD* scheme with other state-of-the-art algorithms. It was found that
PD* improves upon the computational time by 25% while providing solutions of
similar path lengths. Increase in efficiency was particularly prominent in
scenarios with large number of robots and/or higher obstacle densities, where
the probability of collisions is higher, suggesting the suitability of PD* in
solving such problems.
