Abstract
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 goal of the research problem that has been tackled in [2] is to find complete solutions for multi-robot path-planning problem, the theoretical analyses already demonstrated the completeness of Push and Spin (PASp) algorithm. However, the PASp algorithm does not guarantee the optimality of the solution.
In this work, some decisions are found within the complete solution that may optimize PASp performance. Two pluggable methods are proposed for this purpose; smooth operation, that aims to reduce the redundant moves in the generated paths, and heuristic search, that evaluates different alternative paths according to its occupancy by other robots. The improved version of PASp algorithm is referred to as PASp+ algorithm. The experimental results showed that, compared to PASp, Push and Swap (PAS), Push and Rotate (PAR), Bibox and the tractable multi-robot path-planning (MAPP) algorithms, adding heuristic search and smooth operation in PASp+ resulted a significant improvement shown in reducing the number of moves for all problem instances with high percentage reaches to 47.8%. However, in higher computation time.