Robot Local Path Planning Based On Voronoi Diagram

Path planning is one of important topics in robotics,which can be classified into global and local path planning.The traditional path planning based on Voronoi diagram is used for global path planning, which belongs to geometric method based on configuration space. In this paper, local path planning based on Voronoi digram is studied, which adopts sensor-based information to build map incrementally so as to be applicable to local path planning.Much current work in sensor-based planning is heuristic and applies to two-dimensional spaces. None of these methods possesses proofs of correctness guaranteeing that a path can be found, so their completeness can't be well solved. The algorithm described in this paper uses generalized Voronoi diagram (GVD). Firstly, the robot accesses to an equidistant edge in the GVD, and then traces the edge until it reaches a node in the GVD, at which point it branches to explore all edges emanating from that node. When all nodes have no unexplored directions, the algorithm ends. This termination property differentiates this algorithm from other local path planning techniques: it is complete.The incremental construction procedure in this paper can be extended into three-dimensional spaces, and the base component of the map system is generalized Voronoi graph (GVG) in three-dimensional. The situation in three-dimensional spaces is more complex than two-dimensional because of the existing of disconnected GVG. High order GVG edges in High order Generalized Voronoi Graph (HGVG) are introduced to solve this problem. Corresponding experiment results are given out in this paper.