A complete multi-robot path-planning algorithm

摘要

In the domain of multi-robot path-planning problems, robots must move from their start locations to their goal locations while avoiding collisions with each other. The research problem that we addressed is to find a complete solution for the multi-robot path-planning problem. Our first contribution is to recognize the solvable instances of the problem with our solvability test; the theoretical analysis has already been provided to show the validity of this test. Our second contribution is to solve this problem completely, in polynomial time, with the Push and Spin (PASp) algorithm. Once the problem was solved, we found decisions within the complete solution that may improve the performance of the complete algorithm. Hence, our third contribution is to improve the performance by selecting the best path from the set of complete paths. We refer to the improved version of our algorithm as the improved PASp algorithm. In terms of the completeness evaluation, the mathematical proofs demonstrate that the PASp is a complete algorithm for a wider class of problem instances than the classes solved by the Push and Swap (PAS), Push and Rotate (PAR), Bibox or the tractable multi-robot path-planning (MAPP) algorithms. Moreover, PASp solves any graph recognized to be solvable without any assumptions. In addition, the theoretical proof of the PASp algorithm showed completive polynomial performance in terms of total-path-lengths and execution time. In our performance evaluation, the experimental results showed that the PASp performs competitively, in reasonable execution time, in terms of number of moves compared to the PAS, PAR, Bibox and MAPP algorithms on a set of benchmark problems from the video-game industry. In addition, the results showed the scalability and robustness of PASp in problems that can be solved only by PASp. Such problems require high levels of coordination with an efficient number of moves and short execution time. In grid and bi-connected graphs with too many cycles, PASp required more moves and more time than the PAS, PAR and Bibox algorithms. However, PASp is the only algorithm capable of solving such instances with only one unoccupied vertex. Furthermore, adding heuristic search and smooth operation to the improved PASp showed significant further improvement by reducing the number of moves for all problem instances. PASp produced the best plans in a bit higher time. Finally, the PASp algorithm solves a wider class of problems and performs more completely in very complex/crowded environments than other state-of-art algorithms. Additionally, the Spin operation introduces a novel swapping technique to exchange two items and restore others in a graph for industrial applications.