Push and spin: A complete multi robot path planning algorithm
In multi robot path planning problem domain, robots must move from their start locations to their goal locations avoiding collisions with each other. There are various cooperative algorithms in this domain with their specialized strengths. Notable amongst them are Push and Swap (PAS) Push and Rotate (PAR) which appear as most favorable for such problems. This can be attributed to the reason that they don't impose as many restrictions on the graph topology. Our analysis, however, shows that a wider class of solvable instances is excluded from PAS and PAR domain. In this paper, we have proposed Push and Spin (PASp) algorithm, as a new complete cooperative algorithm for Multi robot Path Planning problem with rotation (MPPr) for any instance recognized by the solvability test as solvable without any assumption. The algorithm employed two operations i.e. a "push" operation where robots move towards their goals up to the point that no progress can be made, and "spin" operation that allows two robots to swap positions without altering the configuration of other robots. The experimental results show that the PASp performs competitively in terms of number of moves compared to PAS, PAR and tractable multi robot path planning (MAPP) algorithms, on a set of benchmark problems from the video game industry, in reasonable execution time. In addition, results show 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, in short execution time. In bi connected graphs, with too many cycles, PASp produces a higher number of moves than PAS, PAR and Bibox algorithms in a higher time. However, PASp is the only one capable of solving such instances with only one empty vertex.
2016 14th International Conference on Control, Automation, Robotics and Vision (ICARCV)