Research Of The Algorithms For Path Planning In Obstacles Environment

Avoidance obstacle path planning problem is able to be stated as follows: in obstacles environment, based on a certain evaluation criterion(such as the shortest length of path, the shortest time of moving, the minimal consuming of energy, and so on), from start point to destination point, plans a optimal ( or sub-optimal ) collision free path. It has universal applications in many fields, such as robotics, VLSI's design, GIS, etc. The main contents relate to many subjects, for example environment representing, planning method, path searching and artificial intelligence. Researchers are always caring for and thinking much of the study of high-powered algorithm for avoidance obstacle path planning. Through exploration and research in many aspects, some fruits are obtained, but there are plenty of problems needed to lucubrate.In order to reduce algorithm's time complexity of avoidance obstacle path planning, one way is to study new more effective algorithm, another effective way is to reduce complexity of obstacle environment on the premise of guaranteeing the precision of path planning. In this paper, obstacle environment is properly simplified, obstacles are simplified as encasing boxes of their upright reflection planar boundaries, then model E=(O,R,S,D)is constructed, where O={Oi| i=1,2,3,…,n} stands for encasing box set of n obstacles, Oi={Vij| j=1,2,3,…,mi} is the very polygonal encasing box of reflection boundary of obstacle, Vij=(xij,yij) is coordinates of no. j vertex of no. i encasing box, and Oi∩Oj=φ(i≠j and i,j=1,2,3,…,n)is necessary; M represents a moving object in obstacles environment, S represents the start point(or current position of M), D represents the destination point. Based on the above model, through properly transforming, This paper uses the methods of Dijkstra algorithm, genetic algorithm and two level dynamic planning, etc., studies the algorithm for planning path of avoidance obstacle at two levels of theory and application. The obtained results can not only been applied to the design and implementation of algorithm for avoidance obstacle path planning, but also been used to solve the problems of computational geometry. So, this study has the important theory significance and the practical application value.The typical Dijkstra algorithm is used to solve the shortest path of single source point in weighted graph, and is not able to solve the above model directly. An algorithm is presented, uses the algorithm to transform the model into the weighted graph, and constructs the linking matrix. Then using the improved Dijkstra algorithm to solve the path planning in model of obstacles environment. Both theory proving and experiment testifying indicate the method is correct and effective, and can always obtain the optimal result.Genetic algorithm has many aspects different from traditional algorithm, intelligence and parallel in essence are uppermost characteristics of genetic algorithm. Because genetic algorithm is high-powered to search global optimal solution, GA is widely applied in avoidance obstacle path planning. Though some results have been gotten, path planning problem of complex environment has not been solved very well. Aiming at the above scarcities of using genetic algorithm to plan path, this paper enhances to design corresponding aspects, and selects proper size of population and initial chromosome, shoots at advancing the efficiency of evolving. Experiments indicate method in this paper is feasible, and has high optimization of searching.Analyzing the shortest path problem between two arbitrary points in the obstacles environment. This paper presents an algorithm entitled as "A Two-level Dynamic Shortest Path Planning Algorithm for Obstacle Avoidance", which does not destroy the integrity information of obstacle, and is different from the traditional Floyd Algorithm. The algorithm essentially reflects unification of global optimization and local optimization in this very complex environment. In addition, a new algorithm is constructed to solve cost matrix...