Clearance-Based Performance-Efficient Path Planning Using Generalized Voronoi Diagram
JunTak Lee, Tae-Won Kang, Yong-Sik Choi, Jin-Woo Jung · International Journal of Fuzzy Logic and Intelligent Systems · 2023
The Voronoi diagram is one of the most well-known methods in clearance-based pathfinding.The generalized Voronoi diagram, which is derived from the Voronoi diagram, accepts a polygon as input.This study proposes a method for generating and simplifying a generalized Voronoi diagram.A generalized Voronoi diagram is generated by creating a Voronoi diagram with points representing polygons.The Douglas-Peucker line simplification algorithm is used to simplify the diagram, and the A-star algorithm is used to determine the optimal path.By comparing the simplified and non-simplified versions, we determine that the simplifying process decreases the run time while preserving most of the clearance; however, the distance inefficiency of the Voronoi diagram is not overcome.Additional research is required to determine a more distance-efficient path.