Roadmap-Based Path Planning - Using the Voronoi Diagram for a Clearance-Based Shortest Path

Abstract

Path planning still remains one of the core problems in modern robotic applications, such as the design of autonomous vehicles and perceptive systems. The basic path-planning problem is concerned with finding a good-quality path from a source point to a destination point that does not result in collision with any obstacles. In this article, we chose the roadmap approach and utilized the Voronoi diagram to obtain a path that is a close approximation of the shortest path satisfying the required clearance value set by the user. The advantage of the proposed technique versus alternative path-planning methods is in its simplicity, versatility, and efficiency.