Obstacle avoidance shortest path planning method based on Voronoi diagram

Abstract

The invention discloses an obstacle avoidance shortest path planning method based on a Voronoi diagram, and the method comprises the steps: collecting the information of an obstacle, including the position of a starting point, the position of a destination point, the size of the obstacle, and the position of a central point of the obstacle; according to the positions of the center points of the obstacles, regarding the center points of the multiple obstacles as a point set S on a plane, constructing optimal triangulation for the point set S through adoption of a Delaunay triangulation method, and obtaining a triangulation straight line dual graph, namely a Voronoi graph corresponding to the point set S and the center points of the obstacles, through construction; expanding each edge of the Voronoi diagram in the direction in which the two obstacles determining the edge are located to obtain a simple polygon; and solving an Euclidean shortest path of two points in the simple polygon to obtain a final obstacle avoidance shortest path. The method is low in complexity, and has high self-adaptability and certain flexibility for obstacles with different threat degrees.

Description

technical field [0001] The invention relates to a Voronoi diagram-based shortest path planning method for obstacle avoidance, belonging to the technical field of path search. Background technique [0002] With the development of technologies such as transportation and image processing at this stage, it is possible for cars and robots to automatically avoid obstacles and complete specific tasks. In order to achieve these goals and improve the productivity of human society, it is necessary to increase research on obstacle avoidance algorithms and path planning. Finding a mature and stable obstacle avoidance path planning algorithm has become the focus of people's attention at this stage. [0003] At present, the popular path planning and obstacle avoidance algorithms mainly include A * Path planning algorithm, Dijkstra algorithm, RRT algorithm, artificial potential field method, etc. Although these classical algorithms can complete the task of path planning, it is difficult...

AI Technical Summary

Problems solved by technology

[0005] The technical problem to be solved by the present invention is to overcome the high complexity of path planning and obstacle avoidance algorithms in the prior art, and it is difficult to complete real-time path planning tasks under the condition of hardware performance limitations, and to provide a Voronoi diagram-based The shortest path planning method for obstacle avoidance, through the constructed Voronoi diagram and the information of obstacles, finds a safe area, which must be a simple polygon, and then finds the shortest path in this area, that is, complex obstacle avoidance path planning The problem is transformed into a simpler problem of finding the shortest path of Euclidean, so as to reduce the complexity of the algorithm

Images