Roadmap-based path planning - Using the Voronoi diagram for a clearance-based shortest path

One of the core problems in modern robotic applications is the path-planning. This problem is concerned with finding a good-quality path from a source point to a destination. In path-planning developments, the computational geometry plays a special role. The traditional computational geometry-based approaches to path planning can be classified into three basic categories, including the cell decomposition method, the roadmap method, and the potential field method. Some of the other popular roadmap-based approaches are based on computational geometry structures including the visibility graph for the shortest path and the Voronoi diagram for a maximum clearance path. The Voronoi diagram and its dual structure have used in a wide variety of applications such as collision detection, extraction of crust and skeleton, swarm intelligence optimization, and mobile robot agent network.