On completeness of scalable path planning for multiple robots using graph with cycles

Abstract

This paper presents a problem of finding collision-free paths for multiple robots in the complex environment. Many existing results for the problem cannot guarantee to find a solution or to reduce the computational complexity as the number of robots increases. In this paper, using a graph with cycles, we show that multiple robots can determine collision-free paths. Specifically, we propose an algorithm, which guarantees completeness and scalability even though the empty space is small due to a crowd of robots.