本文对移动机器人路径规划算法的研究状况进行了归纳总结,指出了各算法的性能差异和优缺点。全面阐述了路径规划中常用的启发式搜索算法,重点介绍了A*、D*、D*Lite和LRTA*这四种基本的启发式搜索算法。设计了启发式搜索算法仿真平台,并在此平台下对以上四种算法进行了分析,评价其搜索思想,比较其优缺点。 接着,本文阐述了基于限定Delaunay三角剖分的移动机器人路径规划算法。该算法首先用限定Delaunay三角剖分把环境三角化,然后将A*和D*Lite路径搜索算法扩展到了三角形环境中,分别用于静态和动态环境中搜索路径。为了克服三角形形状不规则所造成的非最优路径,充分考虑到了相邻三角形的几何位置关系和机器人当前位置和目标点的几何位置关系,设计了搜索节点构造规则,该方法能够保证搜索到一条最优或近似最优的无碰撞路径。本文还提出了一种动态三角剖分方法,该方法能够满足动态搜索算法的需要,保证大部分搜索节点可以重新利用,而且还可以快速重新剖分环境。与传统的栅格法相比,本文所述的算法属于精确单元分解法,能够完全表达外界环境,环境包含的搜索节点数要少,需要更少的存储数据空间。而且本文所述算法找到的是一条从起点到目标点的“通道”,便于应用运动控制算法。理论分析证明了本算法的正确性和完整性,仿真实验表明了本算法的有效性和最优性。 最后,本文将离散的三角形环境空间当作离散系统,机器人的速度的连续变化当作连续系统,构造一个统一框架,即混杂系统。路径规划算法用于在三角化的环境中找到一个最优的三角形序列,运动控制算法用于操纵机器人在最优的三角形序列中安全、最优、平滑地从起点运动到目标点,将两者结合组成三角仿射混杂系统。