移动机器人导航路径规划

众所周知，移动机器人是工厂物料运输的优质解决方案，是提高生产效率，降低生产成本，增强生产稳定性的不二之选。为了满足工业生产需求，一款优秀的移动机器人产品首先需要解决三大问题：
 

小蓝（杭州蓝芯科技有限公司简称）就是专ye解决导航规划问题滴，接下来就和大家好好唠唠怎么实现一次走位。

轨迹计划

世界上*遥远的距离不是生与死，而是明明出口就在眼前，而我却要去远远的兜一圈才能到。移动机器人在面对复(luan)杂(dui)环(luan)境(fang)时，也需要完成走迷宫般的绝望任务。
 

图 1

为了应付复杂的人类以及胖胖的自己，我们机智的机器人，拥有了自己的轨迹规划方法。那就是把你们变胖，把自己变瘦（美丽）！于是提出了两个重要假设（敲黑板）：
机器人是一个点，障碍物按机器人半径进行膨胀；
机器人是完整的，忽略非完整约束对姿态的限制；
于是，工作空间就完美的降为了二维物理空间（姿态空间），如图2

图 2

于是路径规划问题就变成了姿态空间的搜索问题：在自由姿态空间中为机器人寻找一条路径，使其从初始姿态发展到目标姿态。将姿态空间离散化以后，就能进行啦。

快速扩展随机树法（RRT）

快速扩展随机树法可以看作一种树形算法，它从一个起始构型（对于二维图，就是一个点）出发，不断延伸树型数据，*终与目标点相连。具体做法就是以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域，便可以在随机树中找到一条由从初始点到目标点的路径。

图 3

RRT算法也有一些缺点，它是一种纯粹的随机搜索算法对环境类型不敏感，当C-空间中包含大量障碍物或狭窄通道约束时，算法的收敛速度慢，效率会大幅下降。同时，RRT 的一个弱点是难以在有狭窄通道的环境找到路径。因为狭窄通道面积小，被碰到的概率低。

因此有学者提出了RRTConnect算法，基本的RRT每次搜索都只有从初始状态点生长的快速扩展随机树来搜索整个状态空间，如果从初始状态点和目标状态点同时生长两棵快速扩展随机树来搜索状态空间，效率会更高。

该算法与原始RRT相比，在目标点区域建立第二棵树进行扩展。每一次迭代中，开始步骤与原始的RRT算法一样，都是采样随机点然后进行扩展。然后扩展完第yi棵树的新节点qnew后，以这个新的目标点作为第二棵树扩展的方向。
 

图 4

这种双向的RRT技术具有良好的搜索特性，比原始RRT算法的搜索速度、搜索效率有了显著提高，被广泛应用。首先，Connect算法较之前的算法在扩展的步长上更长，使得树的生长更快；其次，两棵树不断朝向对方交替扩展，而不是采用随机扩展的方式，特别当起始位姿和目标位姿处于约束区域时，两棵树可以通过朝向对方快速扩展而逃离各自的约束区域。这种带有启发性的扩展使得树的扩展更加贪婪和明确，使得双树RRT算法较之单树RRT算法更加有效。

单元分解法

单元分解法的基本思想是将姿态空间中的自由空间分隔成几个小区域，将每个区域当成一个单元。以单元为顶点，以单元之间的相邻关系为边构成一张连通图。然后在连通图中搜索初始姿态和目标姿态所在的单元，然后搜索连接初始单元和目标单元的路径。*后就能按照所得路径的单元序列生成单元内部的路径了。

图 5

单元分解法的有点在于，机器人不需要考虑它在每个空闲单元中的具体位置，只需要考虑如何从一个单元移动到相邻的空闲单元，同时单元数和环境大小无关。

但是计算效率会极da地依赖于环境中的物体的复杂度，为了解决这方面的问题，又提出了新的单元分解法，也就是栅格表示法：将环境分解成若干个大小相同的栅格。这样其实就是对地图的一种近似，就不用考虑环境的疏密和物体形状的复杂度。

图 6

人工势场法

人工势场法利用磁场的特性来解决路径规划的问题。假设目标点对机器人产生吸引力，障碍物对机器人产生排斥力。这样就能根据力的合成构成机器人的控制方法了。

图 7

引力场（attraction）随机器人与目标点的距离增加而单调递增，且方向指向目标点；斥力场（repulsion）在机器人处在障碍物位置时有一极da值，并随机器人与障碍物距离的增大而单调减小，方向指向远离障碍物方向。如图8就是引力场和斥力场同时作用下的势场图。

图 8

人工势场法通过构建人工势场，进行势场力计算，受力分析进而计算合力，得到*终加速度。

图 9

人工势场法结构简单，便于底层的实时控制，在实时避障和平滑的轨迹控制方面得到广泛的应用。但是由于斥力作用范围较小的问题，势场法只能解决局部空间的避障问题，它缺乏全局信息，这样，它就很容易陷入局部*小值。当机器人位于局部*小点的时候，机器人容易产生振荡或者停滞不前。障碍物越多，产生局部*小点的可能性就越大，产生局部*小点的数量也就越多，这是具体实现过程中需要注意的。

通过上述介绍，想必大家存在一个疑惑，构建了很多单元和路径（拓扑图），那么如何去搜索路径呢，又怎么去判断哪条路径更加优秀呢。下期论点，让我们讨论路径规划算法中的路径所搜法，一起学习A*算法，遗传算法以及粒子滤波算法是如何为我们服务的。