11 导航-拓扑路径规划

上一章节《人工智能机器人学导论》-10 多智能体

《人工智能机器人学导论》-11 导航-拓扑路径规划

概述
导航是目前仍需研究的最具有挑战性的问题之一。当然，当前已经可以找到很多现成的算法库和例子，例如ROS或MRPT，但是基本的算法思路我们还是可以了解一下的。

两种不同的导航算法：拓扑导航和度量导航（metric navigation），也分别称为定性导航和定量导航。
另外一个重要的问题是如何制图。

导航功能可以由以下四个机器人面临的问题表述：
我将去何处？
这个问题通常由人或任务规划器完成。

最佳的路径是什么？
这是关于路径规划的问题，是导航问题中最受关注的地方。

我到过什么地方？当机器人进入一个新环境绘制新环境的地图是一个重要的部分。就算机器人只在同一个环境，因为环境内的物体会改变，也需要重新制图更新地图。
卡内基.梅隆大学的 Xavier机器人通过不同时间的制图，发现某些时候的走廊比较拥堵，从而可以让自己考虑某个时间段不走这些区域。

我现在在哪里？
为了能跟踪路径或者构建一幅地图，机器人就必须知道自己在哪里，即所谓定位。

路径规划器的评价标准
1、算法复杂度：算法是不是太复杂或占用太多存储空间，以至于机器人不能执行或存储空间不够。

2、地形表示的充分性：许多研究用的机器人是基于室内平坦的地面。但是实际应用场合可能存在粗糙的地面，陡峭的坡。如果路径规划算法产生的路径只能针对室内平坦路面，那么在实际的环境运行，机器人将陷入困境。

3、机器人平台物理限制表示的充分性：机器人有物理限制，研究用的机器人一般转弯半径为零，它就能在狭小的地方原地转身，这时路径规划算法不需要考虑机器人转动半径。但是实际场合使用的机器人有可能转弯半径不为零，而非圆形机器人会引起更多的复杂性。

4、与反应层的兼容性：路径规划是慎思式，而在混合型结构中，反应层负责实现该路径，因此需要有从路径规划器到反应层进行转换的技术。

5、能支持地图的修正和重新规划：路径规划需要一个基础地图，这个地图可能有错误。机器人根据这个地图出发，然后发现地图的错误，通过更新地图实现重新规划。

传感器不确定性的影响
实际的传感器都存在不确定性，机器人开发人员需要使用数学的方法来平滑传感器的噪声。

导航和机器人范式
规划、制图、定位都属于慎思部分。如果规划好路径，如何运动到那里，这将使用反应式行为。在混合结构中如何将慎思与反应进行集成来用于导航仍然是需要广泛研究的问题。

空间存储
环境的表示称为机器人空间存储。它应能提供处理和存储当前感知输出数据的方法和数据结构。

拓扑路径规划
对于基于行为的机器人来说，拓扑图、路线或定性导航的方法更为简单和自然。人们经常为别人指路，自然也希望机器人能理解诸如 “沿着走廊往前走，在尽头向前左转，然后进入右手的第二个房间”这样的指令。 即使没有完整的地图，只要机器人知道 “走廊”，“尽头”，“房间”的含义，就足以完成导航的任务。
路线的表示方法有两种：
1、关系法：机器人建立的简单的，以及点连接的环境空间存储。
2、关联法：关系技术侧重于环境空间图描述，而关联技术着眼于将感知和定位相联系。它相应于在反射式行为中感知与动作紧密联系的方式。

关系技术是一种直接表示法，因此可以用于路径规划，而关联技术则更适于重新检视己知路线。

路标和路口
拓扑导航依赖于路标的存在。它是可被机器人感知的一些显著特征。大多数的导航技术中都可能用到路标。如果机器人在环境中找到一个地图上标注过的路标，那么它就可以根据地图进行定位。如果机器人规划一条分段的路径，它就需要根据路标判断一段路径何时结束，同时开始下一段路径。如果机器人发现了新的路标，可以将这些路标添加到它的记忆空间中，重建或扩展原图。

路口是一种特殊的路标，是机器人改变其全局导航方向的一个时机。识别路口是局部定位、路径规划和地图绘制的关键要素。

路标可以是人工的或者是自然的，必须满足下面的三个标准：
1、易于识别：如果机器人不能发现它就没有用了。

2、能够满足任务活动的需求：如果任务仅是简单的方向提示（如过了麦当劳在第二个路口向右转），那么该路标能够被确认就足够了。而如果打算让一个路标为航天飞机和空间站对接提供位置指引，则路标还应当具备便于获取相对距离信息的功能。

3、能从不同的视角感知：如果不能再较大的范围内看到路标，机器人可能永远找不到它。

关系法
关系法是用图或由边和节点组成的网络来描述环境的。节点表示路口、路标或目标点，边表示两节点之间的一条可通行的路线，表示两节点间存在一种空间关系。边还附有其他信息，如方向、大致距离、地形种类或者通过这条路径所需的动作。两点之间的路径可以通过标准图算法计算出来，例如Dijskstra的单源最短路径算法。

但是如果使用航位推算对机器人进行导航会由于误差不断累积，机器人很快就不能达到任何一个节点了。

特定位置
可通过特定位置将关系图和机器人此前的观测结果连接起来。例如检测 墙角，机器人检测到距离每堵墙的距离都是1米，代表是一个地图中的墙角，从而做一次定位。特殊位置定位可以消除累计误差，可自行校正。特定位置方法支持机器人在探索未知环境时发现新的路标。机器人发现能够通过可靠定位特殊物体或区域，并将之添加到地图上，然后重复的移向它，从而构造出一个更完整的度量图。

关联法
拓扑路径导航关联法的重点是建立一个行为，它将感知的观测信息转化为到达特定路标的运动方向。它的前提假设是，对于导航有用的位置或路径需要具备以下两个属性：
1、感知稳定性：观测位置相近时所感知到的应该相似。

2、感知可区分性：观测位置相距较远时所感知到的应该不同。

关联法采用非常粗糙的计算机视觉，视觉导引主要依赖图像特征。它是通过对图像进行区域划分来实现的，如下这个图像被分成了16份，对每个部分进行检验并对该部分属性进行度量。度量内容包括边缘密度（边缘上像素数目初一该区域像素总数）、边的主要方向（边的大部分指向角）和平均强度等。

顺时针一次为原始图像、分割为16个区的图像、用交叉阴影线表示的分区赋值


上图机器人在不同的视点得到不同的结果，根据度量出来的数据可以判断是直行还是向右运动。

具有混合结构的拓扑导航实例学习
本例子针对办公室环境导航问题，机器人随机的放进一个房间，然后必须在15分钟之内走出来并进入另一个房间，每个机器人都被输入一幅拓扑结构图，但不允许测量房间和走廊的布局。利用这个实例说明拓扑图如何输入，如何构造图形，如何应用脚本简化行为管理和已学到的东西。

路径规划
将拓扑图以Backus-Naur格式输入为ASCII文件，下图为地图样本，分别为办公场地的度量图、图拓扑描述、机器人从R3移动到R7所做的修正图（其中去掉了无用的节点）
输入图包括三种类型的节点：房间（R）、走廊（H）、门厅（F），假设环境时正交的，节点之间的边只能是四个方向之一，所以可以方便的用东（E）、南（S）、西（W）、北（N）来表示，这里N在地图中是任意设置的。开始个出了机器人的其实节点，但作为特别挑战，机器人在地图中的初始方向未给定。拓扑图在结构上是正确的，但并没有说明走廊或门是否是阻塞的，这些阻塞可能随时发生或撤除。另外假设每个房间外边都有一个路标，例如房间号或房间名。

制图器负责构造路径，它把拓扑图的路口类型、起始节点和目标节点作为输入，并产生一个从起始点到目标点最佳路径的节点链。制图器的操作分两步：对地图进行预处理来为路径规划打基础，然后进行路径规划。预处理步骤首先在输入地图中建立一个节点数据库，并对走廊节点进行再分类，将走廊与门之间连接的走廊节点用Hd表示。一旦知道了起始节点和目标节点，制图器就会消除多余的路口。例如R1和R6是不必访问的房间，这种房间不是起始点，也不是终点，而且只有一个门。

可以使用Dijkstra单源最短路径算法计算最优路径。（Dijkstra算法（单源最短路径）算法实现）
算法通过考虑每个相连接节点对的代价产生最短路径，代价用图中边的长度或权重表示。拓扑表示中节点之间的连接可反应路径中各路径的优先权，优先权可表示层边的权重。在这个例子中，通过门厅的路径计算代价非常大而且不可靠，因此我们将起始于门厅的子路径段边权重设置为3，同时为了不鼓励机器人不礼貌行为，例如穿过人们的办公室，从一个房间到另外一个房间的权重设置为2，其他的连接权重设置为1。
当前节点到下一节点类型需要的行为：

	到达下一节点	到达下一节点	到达下一节点	到达下一节点
从当前节点	走廊（H）	大厅（F）	房间（R）	房门（Hd）
走廊（H）	走廊导航	走廊导航	未定义	走廊导航
大厅（F）	走廊导航	大厅导航	门导航	走廊导航
房间（R）	未定义	门导航	门导航	门导航
房门（Hd）	走廊导航	走廊导航	门导航	走廊导航

上表格看出，并不是所有的节点组合都是允许的，机器人不可能在不通过Hd节点的情况下，从走廊节点H移向一个房间节点R。


上面的图是一个起始节点R7目标节点R2的导航例子。
制图器计算的路径是R7-H1-H2-H5-R2，由于H3和H4与该任务无关，被删除。

首先 任务管理器选择门导航策略使机器人从R7移动到H1，机器人首先寻找门的位置，通过检查数据库发现门在南边，机器人向南运动。当机器人找到门以后，抽象行为的初始化过程就结束了，接着执行门导航标准任务，机器人一旦通过了门，该标准任务就结束了，整个抽象行为也就完成了。

接下来导航任务是从H1到H2也是指向南方，任务管理器选择走廊导航行为。
从H2移动到H5，因为H5是通向感兴趣房间的路口，需要通过视觉方式来识别这个房间作为到达H5的条件。
H5到R2使用门导航行为，通过沿墙行走和超声波检测门是否打开，如果门是打开的标准任务被激活，机器人进入房间R2，成功完成任务。


第二个例子，任务是从R1-H1-F1-H8-H0-R0，但其中H8-H0是堵塞的，机器人探测到路径被堵塞，于是采用走向目标的行为策略回到H8，制图器更新拓扑图并重新计算新的路径。
此时的路径编程了H8-F1-H5-H6-H7-H0-R0




下一章节：《人工智能机器人学导论》-12 度量路径规划