Completeness of Scalable Path Planning for Multiple Robots using a Graph of Shared Cycles

Gwang Tae Kim, Hyun-Wook Jo, Chung-Woon Park, and Jong-Tae Lim


Multiple robots, Path planning, Graph, Shared Cycle, Rotation


Many path planning methods have been studied to find collision-free paths for multiple robots in complex environment. However, the previous methods cannot guarantee completeness or scalability in the finding the paths. In this paper, we propose the method transforming a roadmap to the graph of cycles having more than one shared edge with other cycles. Then, we show that all multiple robots can be moved to their goal positions without collision using the graph. The proposed algorithm guarantees not only the completeness, but also the scalability. Especially, we show that the proposed algorithm provides efficient paths of all robots than existing methods and can be available for the roadmap having extremely many robots.

Important Links:

Go Back