Redundant Voronoi Roadmap Graph Using Imaginary Obstacles for Multi-Robot Path Planning

Abstract

Roadmap-based path planning is a well-established method for multi-robot systems, where the free space of the environment is represented as a roadmap graph. The Voronoi diagram is known for its efficiency in creating roadmaps for single-robot systems due to its ability to generate paths with high clearance from obstacles. However, the design of the Voronoi diagram does not allow for redundant paths, as only one path is obtained between each pair of obstacles. In contrast, multi-robot path planning requires multiple path options for efficient solutions. Therefore, we propose redundant Voronoi roadmap graph, which incorporates multiple paths computed from the Voronoi diagram. In this approach, we introduce imaginary obstacles to modify the costmap and obtain a roadmap with more paths. Our proposed roadmap retains the high clearance feature of the Voronoi diagram and is suitable for multi-robot systems due to the availability of alternative route options. We demonstrate that our method can generate roadmaps in various simulated environments with different levels of redundancy. Additionally, we verify the efficiency of our proposed roadmap graph through graph analysis and multi-robot path planning experiments. Comparative analysis shows that the use of the proposed roadmap increases the success rate and solution quality compared to the roadmap obtained directly from the conventional Voronoi diagram.