避障路径规划问题是在具有障碍物的环境中,按照某个评价标准(如最短路径长度、最短行进时间、最小能量消耗等),规划一条从起始点位置到达目标点位置最优(或次优)的无碰(避障)路径。避障路径规规划问题在机器人学、VLSI、地理信息系统等众多领域有着广泛的应用,其主要内容涉及环境表达、规划方法、路径搜索以及人工智能等多个学科。关于避障路径规划高效算法的研究长期以来一直受到人们的关注和重视,人们从多方面进行了探索和研究,虽取得了一些成果,但仍存在许多问题有待深入研究。以“可视图”模型为基础,应用“智能计算”、“两级动态规划”以及“最小任意四边形包围盒”等方法从理论和应用两个层面研究避障路径规划算法。取得的结果不仅可直接应用于避障路径规划算法的设计与实现,而且还可应用于计算几何中相关问题的求解。因此,研究工作具有重要理论意义和实际应用价值。采用“可视图”表达环境、建立环境模型,将避障路径规划中最优路径问题转化成为从起始点到目标点经过可视直线的最短路径问题,使之成为研究工作的基础。在对求解TSP问题的GT算法进行了细致分析和对比了TSP问题与避障路径规划问题的异同点之后,引入了“基因库”概念,对GT算法进行了改造,成功地将其用于求解避障路径规划问题。此外,给出了一个问题规模和初始种群规模关系的数学公式,通过问题规模来确定种群规模;在初始染色体选择时,利用“凸点法”的结论,避免了无效和盲目地选择。这一系列措施提高了演化的效率。对在障碍物环境下求任意两点间的最短路径问题进行了剖析。提出了一种与传统Floyed算法不同的不破坏障碍物整体信息的“两级动态规划求最短避障路径”的算法。该算法从本质上反映了在这种较为复杂的环境下全局优化与局化优化的统一。此外,在求解图的成本矩阵方面,构造了一种新的算法,算法过程更直观和易于理解。经理论证明和实验计算表明结论正确。算法的时间复杂度O(n3)(n是可视图的顶点数)虽和Floyed算法相同,但本算法新颖的设计思路是一种创新。为了降低避障路径规划的算法复杂度,除研究新的高效算法外,另一种有效途径是在保证规划路径精度的前提下,减小构成障碍物边界的点数。障碍物常表达成封闭轮廓线(凸多边形),构造包围封闭轮廓最小面积包围盒就是解决这个问题的有效方<WP=5>法。包围盒是计算几何中的基本问题之一。除在路径规划方面的应用之外,包围盒问题在碰撞检测、实时漫游及视区裁剪等研究中也有着广泛的应用。在分析现有算法(1975年由New York大学的两位学者H.Freeman、P.Shapira提出的方法)的基础上,对求封闭轮廓线的最小矩形包围盒的算法进行了研究。提出了封闭轮廓线最小矩形包围盒的数学分析方法。在解的搜索域上也进行了研究并根据所得到的结论对现行算法进行了改进。凸多边形最小面积任意四边形包围盒问题在计算几何中是有更广泛意义的论题。经过严格的数学推理演绎,较为系统地得到了包括“凸多边形的最小面积四边形包围盒的四边都是多共点边,或三边是多共点边而另一边(单共点边)中点与凸多边形的一顶点重合”等一系列重要结论。依据此结论设计了时间复杂性为O(m4)(m是问题规模,凸多边形的顶点数)的算法,解决了“凸多边形最小面积任意四边形包围盒”这个在理论上和实际应用中都具有重要意义的问题。相关各类算法都经过了程序运行结果的验证,达到了预期的效果。