移动机器人路径规划：局部路径规划，全局路径规划

移动机器人的运动规划研究开始于20世纪60年代。1978年Wesley 和Lozano 第 一 次把位形空间(Configuration Space)的概念引入到运动规划器的设计中。在C 空间中，每 一个位姿代表机器人在空间中的方位和位置。而机器人则被看做是一个质点，那么运动 规划问题就可以被看做是在位形空间中，寻找一条起始点到终点之间的路径问题。所谓 的路径，就是位形空间中机器人位形的一个特定序列，但是不考虑机器人位形的时间因 数。轨迹指的是何时到达路径中的每个地点，强调了时间的相关性[130]。机器人的运动 规划就是对轨迹的规划，按照环境认知的不同，我们可以把移动机器人的运动规划分成局 部路径规划和全局路径规划。

(1)局部路径规划

局部路径规划指的是机器人在全局信息位置的情况下，依靠传感器信息进行的局部路径规划，主要可以分为人工势场法(Artificial Potential Field)、遗传算法、模糊逻辑算 法、神经网络算法等。人工势场法Z初由Khatib 提出，其基本思想是引入一个称为势场 的数值函数来描述机器人空间的几何结构，通过搜索势场的下降方向来完成运动规划。 这种方法由于它的简单性和优美性而被广泛采用。但是也存在着一些缺点，如存在陷阱 区、在相近的障碍物前不能发现路径、在障碍物前产生振荡以及在狭窄通道中摆动等。针 对人工势场法的缺点，国内外许多专家学者不断寻找新的途径，以克服该方法所存在的弊 端，文献[131]采用预测与势场法相结合的算法解决移动机器人的导航问题，取得了良好效果。文献[132]通过引入虚拟障碍物使搜索过程跳出局部Z优的陷阱，但引入虚拟障 碍物可能会产生新的局部极小点，同时也增加了算法的复杂度。

遗传算法是一种多点搜索算法，因此能够更有效地搜索到全局Z优解，这也是为什么 遗传算法可以用来解决机器人路径规划中的局部极值问题的原因。但是遗传算法的运算 速度不够快，在复杂环境问题规划过程中需要占用大量的存储空间和运算的时间。

模糊逻辑算法可以通过查表得到信息，完成路径的局部规划，克服了人工势场法所带 来的陷人局部极小值的缺点。用于时变位置环境下的路径规划，实时效果较好。

孙增圻等在假设检验方法中引入了罚函数项，依靠优化罚函数的方法来寻求机器人 运动的Z优路径，同时利用神经网络模拟退火算法使其避免陷入局部Z小值。他把移动 物体的碰撞罚函数定义为各种障碍物与移动物体上的各个测试点之间的碰撞罚函数之 和。路径的碰撞罚函数则为所有在路径点上的碰撞罚函数和路径总长之和[133。谢宏斌 提出了一种基于模糊概念的动态环境模型，并在该模型基础上结合模糊神经网络进行机 器人的路径规划，他使用动态环境中物体的信息调整模糊神经网络权值的方式来加快算 法的收敛速度，从而达到动态控制机器人下一步运动的目的[134]。

(2)全局路径规划

机器人的全局路径规划方法可以分为可视图法(Visibility Graph)、结构空间法 (Configuration Space)、栅格法、拓扑法、随机路径规划法等。

可视图法是将移动机器人看做一点，把目标点、机器人和具有多边形的障碍物的各个 D点进行连接，要求机器人和障碍物各D点之间、目标点和障碍物各D点之间以及各障碍 物D点与D点之间的连线，都不能穿越障碍物，这样形成的图称之为可视图。该方法的优 点是可以求得Z短路径，但缺乏灵活性，并且随着障碍物的D点个数的增多存在组合爆炸 问题[135]。

结构空间法是一种数据结构方法。移动机器人通过该数据结构来确定物体或自身的 位姿。结构空间表示法有许多种，Z具代表性的是Voronoi 图法和四叉树(Quadtree) 及 其扩展算法。Voronoi图法的基本思想是：先产生与环境障碍物中所有边界点等距离的 Voronoi边 ，Voronoi边之间的交点称之为 Voronoi D点。然后，移动机器人沿着这些 Voronoi边行走，不仅不会与障碍物相碰撞，而且一定在任意两个障碍物的中间。四叉树 是一种递归网格，先在移动机器人所处环境上建立一个二维直角坐标网格，然后用大的 网格单元对机器人所处环境进行划分。倘若障碍物占用了网格单元的一个元素，则就把 这部分分成四个小格子(四叉树)。如果这四个小格子中还有被占据的单元，则递归地对 该单元再分割成更小的四个子网格[136]。

栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元，多采用二维 笛卡儿矩阵栅格表示工作环境。每一个矩形栅格都有一个累积值CV, 表示在此方位中存 在障碍物的可信度，CV值越高，表征存在障碍物的可能性越高。用栅格法表示格子环境 模型中存在障碍物可能性的方法起源于美国的CMU大学，通过优化算法在单元中搜索Z 优路径。由于该方法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅 格。因为栅格的大小直接影响着环境信息存储量的大小以及路径搜索的时间，所以在实 用上具有一定的局限性[137]。

拓扑法是根据环境信息和运动物体的几何特点，将组成空间划分成若干具有拓扑特 征一致的自由空间。根据彼此间的连通性建立拓扑网，从该网中搜索一条拓扑路径，即完 成了路径规划的任务。该方法的优点在于因为利用了拓扑特征而大大缩小了搜索空间， 其算法复杂性只与障碍物的数目有关，在理论上是完备的。但是，建立拓扑网的过程是相 当复杂而费时的，特别是当增加或减少障碍物时如何有效地修正已经存在的拓扑网络以 及如何提高图形搜索速度是目前亟待解决的问题。但是针对一种环境，拓扑网只需建立 一次，因而在其上进行多次路径规划就可期望获得较高的效率[138]。

以上几种方法都是基于自由空间几何构造的规划，而快速随机搜索树算法 RRT(Rapidly Exploring Random Tree) 则是近年兴起的一种以解决高维姿态空间和复杂 环境中运动规划为目的的基于随机采样的运动规划。1998年美国伊利诺伊大学(UIUC) 的科学家S.M.La Valle 在Z优控制理论、非完整规划和随机路径规划的基础上提出了一 种单一查询RRT。路径产生阶段，从目标状态点出发，找到父亲节点，依此直至到达起始 状态点，即树根，就规划出从起始状态点到达目标状态点满足全局和微分约束的路径以及 在每一时刻的控制输人参数。因为在搜索树的生成过程中充分考虑了机器人客观存在的 微分约束(如非完整约束、动力学约束、运动动力学约束等),因而算法规划出来的轨迹合 理性非常好，但算法的随机性导致其只能概率完备。