Research On Algorithm For Avoidance Obstacle Path Planning

Avoidance obstacle path planning is aimed at planning an optimal(or sub-optimal)collision free path from start point to target point,which is based on a certain evaluation criterion(such as the shortest length of path,the shortest time of moving,the minimum consumption of energy).This technique is widely used in many fields,such as moving robot technology,industry design,city pipe network design,transportation industry.It has attracted a lot of attention from many researchers,and fruitful research results have been achieved.This technique mainly involves two technical problems: constructing the model of obstacle environment and path searching algorithm.One of the most widely used methods of constructing obstacle environment is the visibility graph.But it is difficult and inefficient to use it to construct the obstacle environment which has boundaries.Aiming at this problem,a strategy called Segmentation Modeling has been put forward in this paper.The strategy goes like this: Fist we search the shortest path of the obstacle environment without considering all the obstacles inside to get an initial path,then we modify the initial path by stages with visibility graph.Based on this strategy,two algorithms are proposed and introduced in this paper to search the initial path,then the final shortest path are searched by stages on the original line.The typical Dijkstra algorithm is one of the most effective and widely used algorithms.It is used to search the shortest path of single source point in weighted graph,but it does not apply to searching the shortest path in obstacle environment for it will over search.This paper improves the typical Dijkstra algorithm and compensates to remedy the defects above.This paper also proposes a weighted graph based algorithm which apply to search all the paths from start point to target point.It can be used to search the shortest path in obstacle environment with a little improvement.All the key algorithms have been programmed with Myeclipse programming software,and works well.