A heuristic algorithm to optimize execution time of multi-robot path

Abstract

A common problem in the field of robotics is to coordinate motions of multiple robots to ensure the shortest possible execution time. The problem is known PSPACE-complete, thus, it is impossible to find the best solution in a reasonable time for large scale problems. For this reason, in this work we look for sub-optimal solutions by systematically improving a given one. We present a heuristic algorithm to reduce execution time of a path by changing robots' priorities in case of path overlap. The algorithm is applied to a solution computed by a decoupled method in a discrete event system context. It is shown that the proposed approach is effective in finding a solution with shorter execution time. Tests show that the proposed algorithm can achieve improvement up to 45%.