移动机器人路径规划属于机器人控制系统的重要应用基础问题,也是机器人研究领域一个关键的研究课题。机器人路径规划是指在有障碍物的空间中找到一条最短或者低代价的无碰撞路径。动态环境即时变环境,指障碍物和目标点的位置随时间变化而变化。本文针对三维动态环境下,机器人路径规划的鲁棒性问题,提出了一个基于宽度优先搜索(BFS,Breadth-First Search)算法的路径规划。该算法通过对角线原则和前向链确定先行值,先行值是指从起始点到目标点的合适的时间步长。然后推算障碍物和目标点到先行值时的位置,并计算空间中所有位置在所有时刻的位势值。机器人从起点出发,沿着位势值降低的方向朝目标点行进,安全到达目标点。本文主要进行了以下几项工作:一、建立机器人三维工作环境模型。该环境模型是一种数据结构,该结构反映的是机器人在某个位置随机行进一步与障碍物发生碰撞的可能性大小。二、给出机器人路径规划数学支持,本文提出的算法基于人工势场法和调和函数。并根据对角线原则和前向链确定先行值LA(Lookahead value)。对角线原则是指将四个起始点位于三维空间的底面,四个目标点位于三维空间的顶面,在同样环境大小和同样障碍物密度下相距最远,则从起始点行进到目标点的时间步长相对最大。前向链的提出基于宽度优先搜索(BFS)。BFS根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点。如果目标结点存在于解答树的有限层上,宽度优先搜索算法一定能保证找到一条通向它的最佳路径。三、计算空间每个位置在每个时间步长时的位势值。位势值是时间函数,反映了机器人在某个位置随机行进一步与障碍物发生碰撞的可能性大小。机器人从起点出发,每一步沿着最小位势值的方向朝目标点行进,安全到达目标点。四、运用MATLAB7.0对本文提出的算法进行仿真,结果表明该算法能使机器人安全避障并行进到目标点。并比较工作条件变化对结果的影响。