A Comparison of Two Decoupled Methods for Simultaneous Multiple Robots Path Planning

Two path planning algorithms dedicated to multiple robots driving simultaneously in a cluttered workspace are defined and compared in this paper. Each robot is assigned an initial position, a goal position and a constant reference speed, and has to drive without colliding with its teammates and the environment. Both approaches are based on an implementation of the widely known A* algorithm and belong to the family of decoupled path planning methods, since robots are considered sequentially and with a predefined priority ranking. The first algorithm is called Prioritized Planning (PP), where the path of each robot is computed sequentially while taking into account static obstacles as well as the previously-planned robot positions. The second algorithm, called Fixed-Path Coordination (FPC), follows a two-step approach: (i) obtaining A* paths of all robots taking into account static obstacles only; (ii) applying a velocity-tuning procedure so that lower-priority robots can stop and restart along their paths to let the higher-priority robots move freely. Both algorithms have been applied on a variety of test-cases through a Monte Carlo setup to evaluate and compare their performances.