ECBS-based Suboptimal Multi-robots Path Planning Algorithm

摘要

This paper focuses on the multi-robot path planning problem. Traditional algorithms add path constraints to robots by "exhaustive method" until all robots’ conflicts are eliminated, which has high completeness but low efficiency when dealing with large space and high complexity problems, and usually cannot find the target path within the specified time. To solve these problems, two ECBS-based suboptimal path planning algorithms for multiple robots are proposed in this paper. One classifies conflicts according to their characteristics, and different categories are equipped with different conflict resolution approaches, thus improving the search efficiency. The other one is based on the first scheme to establish a set of real-time updated dynamic priority assignment criteria to give priority to low-priority robots for path planning, thus giving way to high-priority robots and reducing the search time. Finally, it is experimentally verified that both optimization algorithms can retain the completeness of the traditional algorithm while reducing the size of the constraint tree. Only a small increase in path length boosts the experimental success rate increase and significantly reduces the computation time, improving the overall search efficiency. And as the number of robots increases, the optimization effect becomes more obvious.