避障路径规划问题是在具有障碍物的环境中,按照某个评价标准(如最短路径长度、最短行进时间、最小能量消耗等),规划一条从起始点位置到达目标点位置最优(或次优)的无碰撞路径。在机器人学、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算法相同。但本文所设计的算法在思路上是一种创新。论文最后概述了三维场景中避障路径规划的现状,并分析了一些代表性算法,指出了路径规划领域中存在的问题及今后努力方向。