Can View Law-based Obstacle Avoidance Path Generation And Optimization

Obstacle avoidance path planning is a basic problem in mobile robot, virtual simulation, very large scale integrated circuit, geographic information system and many other fields. People explore a method to plan an optimal collision free path from start point to destination point in short time. The visibility graph method, artificial potential field method, genetic algorithm and many other kinds of obstacle avoidance path planning algorithm are proposed. Visibility graph method and convex point method are studied in this paper. Visibility graph method construct visibility graph with straight lines first. The straight lines combined by the vertices of obstacles, start point and destination point should not pass through the inside of obstacles, which means the straight lines are'visible'. Then plan an optimal path by a search strategy based on visibility graph.Convex point method is an obstacle avoidance path planning method which seeks for the shortest path by geometry method directly. First of all, original intersection point set is generated according to the obstacles in the line which from start point to destination point. Then the intersection point set is sorted and simplified to the intersection point pairs which divide each obstacle into the left and right side path. Choose side of the path according to the direction choice strategy and the initial path is complete. Finally optimize the initial path by searching and recording the convex points.Firstly, the basic principle of visibility graph method and convex point method are studied. Some basic algorithms such as bounding box testing, line intersected judgment and the node convexity judgment in which convex point method involved are discussed. The various special circumstances of program realization of the convex point method are analyzed and the solutions are provided.And then on the basis of theoretical analysis the convex point method is realized by programming. The environment expression of obstacles is the polygon data of shapefile. The obstacle avoidance path planning method and the visualization of obstacles and path are realized by using the Visual Basic.NET as program language combined with ArcGIS Engine.After test and analyze the realized program, it is easy to see that the convex point method is effective to the environment of concave and convex polygon, and it can simplify the complex problem of the nested or encircled obstacle polygons. The algorithm efficiency is high. But the convex point method does not take all the obstacles into account, so it cannot always get the global optimal solution. At the same time, the direction choice strategy lays particular stress on the direction of the first obstacle near the start point, which is easy to make the result deviate from the shortest path.Finally, base on the test results of the method defect, the improvement plan is put forward. The improved method chooses the short side path of each obstacle directly to generate the initial path. In order to get better path, after initial optimization, execute second optimization, which means make the node of the initial path to be the new start point and destination point sequentially to generate optimal path. The improved convex point method can find the shorter path, but take longer, and also can not always find the shortest path.