【作者】 杜安红；

【导师】 戴光明；

【作者基本信息】 中国地质大学 ， 计算机应用技术， 2004， 硕士

【摘要】 避障路径规划问题是在具有障碍物的环境中,按照某个评价标准(如最短路径长度、最短行进时间、最小能量消耗等),规划一条从起始点位置到达目标点位置最优(或次优)的无碰撞路径。在机器人学、VLSI、地理信息系统等众多领域有着广泛的应用,其主要内容涉及环境表达、规划方法、路径搜索以及人工智能等多个学科。关于避障路径规划高效算法的研究长期以来一直受到人们的关注和重视。人们从多方面进行了探索和研究,虽取得了一些成果,但仍存在许多问题有待深入研究。为了降低避障路径规划的算法复杂度,一方面研究新的高效算法,另一种有效途径是在保证规划路径精度的前提下,有效降低障碍环境复杂度。本文首先对避障环境进行适当抽象和一定程度的简化,把环境中的障碍物简化为其垂直投影在平面上的区域边界的包围盒,从而建立起障碍环境模型:E=(O,R,S,D),其中O={Oi| i=1,2,3,…,n} 表示n个障碍物的包围盒集合,Oi={Vij| j=1,2,3,…,mi} 是障碍投影边界的多边形包围盒,Vij=(xij,yij) 表示第i个包围盒的第j个顶点坐标,要求Oi∩Oj=φ(i≠j且i,j=1,2,3,…,n);R代表障碍环境中的运动对象,S代表路径规划的起点,D代表路径规划的终点。在该模型基础上,经过适当预处理,本文分别应用Dijkstra算法,遗传算法和二级动态规划算法等方法从理论和应用两个层面研究避障路径规划算法。取得的结果不仅可直接应用于避障路径规划算法的设计与实现,而且还可应用于计算几何中相关问题的求解。因此,本项研究具有重要理论意义和实际应用价值。经典Dijkstra算法是解决带权图中的单源点最短路径问题的,不能直接求解平面障碍环境中的最短路径规划问题。本文给出了一种构造算法,把障碍环境模型转换成熟悉的带权图,同时构造出了图中各顶点间的邻接矩阵。在对经典Dijkstra算法进行必要的改进后,利用改进的Dijkstra算法解决障碍环境模型中的避障路径规划问题。经理论证明和实验证实,本文给出的利用改进Dijkstra算法解决该问题的正确性,效率高,并且该方法始终能得到障碍环境中的指定两点间的最优路径。遗传算法与传统的算法有很多不同之处,智能性和本质并行性是其最主要的特点。由于遗传算法在寻求全局最优解方面具有高效性,因此遗传算法被广泛地应用于避障路径规划中。但现有成果由于设计上的不足,并没能很好地解决复杂环境下的路径规划问题,本文针对上述不足,加强各种遗传算子和编码设计,通过合理选择初始种群规模和初始染色体等一系列措施提高了进化的效率。实验表明本文方法的可行性,并有很高的寻优率。对障碍物环境下求任意两点间的最短路径问题进行了剖析。与传统的Floyd算法不同,本文提出了一种不破坏障碍物整体信息,被称作“两级动态规划求最短避障路径”的算法。该算法从本质上反映了在这种较为复杂的环境下全局优化与局部优化的统一。此外在求解<WP=7>图的成本矩阵方面,构造了一种新的算法,算法过程更直观和易于理解。经理论证明和实验计算表明结论正确。设计的算法虽然其时间复杂度是(是包含起始点、目标点和各障碍物顶点的顶点总数),和Floyd算法相同。但本文所设计的算法在思路上是一种创新。论文最后概述了三维场景中避障路径规划的现状,并分析了一些代表性算法,指出了路径规划领域中存在的问题及今后努力方向。更多还原

【Abstract】 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, <WP=9>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更多还原