前言

机器人导航就是如何引导机器人朝着某一目标前进的问题。许多机器人在完成任务时并不依赖任何地图，这种方法称为反应式导航。它们在导航时直接依据环境光的强度，或相对于自线的位置，或是否与墙接触而做出反应，沿着随机生成的路径工作，只有在探测到障碍物的时候才会改变路径。更先进的机器人则使用基于地图的类人导航方法。这种方法可以支持更复杂的机器人任务，但方法本身也更为复杂。而在本章中，将主要讨论基于反应式导航和基于地图导航这两种方法，并以在平面环境中运动的轮式机器人为主要对象。

反应式导航

1.Braitenberg车

Braitenberg车是一种非常简单的目标达成机器人，其特点是传感器与电机之间直接连接。小车自身既没有其作业环境的信息，也没有任何路径规划可言。

如图5.2 所示，它通过直接从传感器导出的转向信号来达到目标。

为了增加梯度，我们需要估计在当前位置的梯度方向，这至少需要对势场进行两次测量的值。本例中我们在机器人两侧各安装一个传感器，传感器建模由图5.2中的灰色模块所示， 并通过传感器相对于机器人的位置以及感知丽数进行参数化。在这个例子中，传感器是安装在小车的横向或y方向土2单位的位置。

被感知的势场由一个简单的平方反比函数定义：

该函数返回传感器值s(x, y)e[O, ]，它是一个在平面上传感器位置的函数。这个特殊函数在点(60, 90)有峰值。

小车的速度是:

其中，SR和SL分别是在右侧和左侧的传感器值的读数。在目标点有SR=SL=1，此时的速度变为零。

转向角由两个传感器读数的差值决定：

机器人的移动路径如图5.3 所示。它的初始位姿可以通过改变 Bycicle模块的参数来定义。我们看到机器人的速度随着与目标距离的减少而变慢，渐近地接近目标位置。

2.简单自动机

首先我们给机器人加载一个障碍场，它在工作区定义了一个100×100的矩阵变量 map。矩阵中的元素为0或1，分别表示自由空间和障碍，如图5.4所示。

在此我们先给定一些假设：首先，机器人在网格中活动，且只占一格；第二，机器人不具有任何非完整约束，可以移向任意相邻网格；第三，机器人可以确定自己在平面上的位置；最后，机器人仅可以感知它的下一个位置及目标位置。机器人本身并不使用地图——地图是给仿真器使用以给机器人提供传感器输入。

bug2 算法所用的策略非常简单，它先让机器人沿着一条直线向目标点运动。如果遇到障碍机器人就逆时针绕行，直到回到最初那条直线上的一点，这个点比之前遇到障碍时的点离目标更近。

基于地图的路径规划

从日常生活中我们知道，找到从 A 点到B点最佳路径的关键是要使用地图。一般来讲最佳意味着距离最短，但也应该考虑道路的可通过性带来的一些惩罚或代价。可通过性表示驶过某个区域的容易程度，有时走一条距离更远但路况更好的路反而会更快。一个更深思熟虑的规划者往往还会考虑车辆的运动学和动力学，会避开那些存在车辆无法完成的急转弯的路径。

1. 距离变换

考虑只有一个代表目标的非零元素的矩阵。此矩阵通过距离变换得到另一个大小相同的矩阵，但其中每个元素的值是它到最初非零目标元素的距离。在机器人路径规划中，我们使用默认的欧氏距离。

上述最艰难的工作完成后，从任意点找到一条到达目标的路径就变得十分简单了。无论机器人从什么地方开始，都会朝着距离目标最近的相邻网格移动，这种算法一直持续，直到抵达目的地为止。2.D*

D*是一种流行的机器人路径规划算法，有很多十分实用的特性。

D*是通过寻找一条路径使得运行的总成本最低。如果我们感兴趣的是最短时间到达目的地，那么成本就是穿过单元所需的时间，它和可遍历性成反比。如果我们感兴趣的是减小对车子的损伤或者最大化乘客的舒适度，那么成本可能就是单元地形的粗糙程度。单元分配的成本取决于车子的特性，一辆大型的四轮驱动车在穿越不平整的道路时可能仅需要有限的成本，但是对于一辆小汽车，成本可能是无限大的。
D*的关键特性是它支持增量式的重复规划，这是非常重要的。如果我们在移动过程中发现实际情况与地图不符合，或者是发现路线成本高于预期值或者完全被堵死了，我们就可以通过增量式重复规划找到一个更好的路线。增量式重复规划的计算成本比完全重复规划要低，前面讨论的距离转换法就属于完全重复规划。

图5.7显示了从任何一个初始点到达目标的路径： 可以看到，机器人又一次选择了障碍左边的较短的路径，这和采用距离转换方法得到的结果一样。

D*的真正威力在于它能在任务中有效地更改成本地图。这种能力在机器人领域非常需要，这是因为实际的机器人传感器量程有限，而且机器人在行进过程中会发现更多不可预知的情况。

如图5.8 所示。成本改变虽然比较小，但是我们注意到在这个区域中增加的通行成本通过单元的细微变亮体现了出来，从成本角度来说这些单元距离目标更远了。与图5.7 相比，机器人的路径移动到右边了，这样可以减小它穿过高成本区域的距离。D*允许机器人在移动过程中随时更新地图，当重新规划后，机器人仅仅移动到附近的最低成本的单元，这样可以保证在规划改变后仍然可以保证运动的连续性。

3 .沃罗诺伊路线图法

在路径规划的术语中，把生成一个计划称为“规划阶段”，而利用规划阶段的结果找到一条A到B的路径则称为“查询阶段”。前面介绍的两种算法，距离变换和D*在规划阶段都需要大量的计算，而在查询阶段都比较简单。但规划过程受目标位置的影响很大，一旦目标改变，之前耗时的规划计算都必须全部重来。虽然D*允许成本地图改变后重新计算路径，但它也不支持目标的改变。

规划和查询的计算成本差异导致了路线图方法的产生，这种方法查询的既有起始位置也
有目标位置。规划阶段提供的分析也支持不断变化的出发点和目标点。

4.概率路线图方法

前面介绍的距离变换和骨架化方法的计算量都很大，对于较大的地图不适用。为改善上述问题，于是产生了基于概率的方法。这些方法在全局地图上稀疏采样，其中最著名的方法就是概率路线图法，或称 PRM 法。

如图5.10(a)所示。图上的灰点就是随机选出的点，点之间的连线都不穿过障碍物。只有小于30单元长的路径被选出来，这也是PRM类的距离阈值。图上的每条边都有一个相关联的成本值，代表了其两端节点之间的距离。节点的颜色表示它属于哪一个组件，每个组件被分配一个特定的颜色。我们看到图的左边缘处有两个点与路线图其他部分没有连接。
查询阶段即找到一个从起点到终点的路线。这时只需要简单地从起点移动到离它最近的节点，然后就沿路线图走，最后再从离终点最近的节点离开。

为了提高运算效率，我们不得不做出一些重要的牺牲。首先，在自由空间中随机取样意味着每次运行该规划器都会产生一个不同的路线图，从而导致生成不同路径及路径长度。
它将产生如图5.10(b)所示的图，该图具有与图5.10(a)不同的节点和不同的边。

其次，如果创建的网络中包含未连接的元素，规划任务就算失败。在图5.10(a)的左侧就有两个未连接的节点，而在图5.10(b)中则有一个大的未连接组块。如果起点和终点位置没有通过路线图连在一起，即它们分属不同的组块，Path方法就会报告错误。该问题的唯一解决办法就是重新运行规划器。

本章总结

机器人导航问题是如何引导机器人朝着一个目标前进，本章已经介绍了多种方法。最简单的是纯反应式的 Braitenberg型车。然后我们通过增加有限的记忆创建了基于自动机的状态机器， 它可以躲避障碍，但是找出的路径并非最佳。随后我们介绍了几种不同的以地图为基础的规划算法。距离变换是一种计算密集型的方法，可以找到一个到达目标的最优路径。D*也可以找到一个最优路径，但它依赖于每个单元的可通过性，而不是把它们看作是自由空间或障碍物。PRM 方法通过随机采样减小了计算的负担，但代价是得到的路径不是最佳，尤其是它可能无法找出自由空间之间的狭窄路线。