基于激光雷达的移动机器人定位与导航技术-硕士论文.doc

上海交通大学硕士学位论文
目 录
第一章 绪论 ……………………………………………………………………………………...3
1.1 引言…………………………………………………………………………………........3
1.2 移动机器人的定义与主要研究内容……………………………………………………3
1.2.1 移动机器人的定义……………………………………………………………3
1.2.2 移动机器人的主要研究内容…………………………………………………4
1.3 本文研究课题与内容安排………………………………………………………………5
1.3.1 研究课题………………………………………………………………………5
1.3.2 内容安排………………………………………………………………………6
第二章 移动机器人导航技术概述 ……………………………………………………………...8
2.1 移动机器人工作环境表示方法…………………………………………………………8
2.1.1 几何地图………………………………………………………………………8
2.1.2 拓扑地图……………………………………………………………………..10
2.2 移动机器人定位技术…………………………………………………………………..11
2.2.1 相对定位技术………………………………………………………………..11
2.2.2 绝对定位技术………………………………………………………………..12
2.3 移动机器人路径规划方法……………………………………………………………..13
2.3.1 Dijkstra和A*图搜索算法…………………………………………………..13
2.3.2 人工势场法…………………………………………………………………..13
2.3.3 调和函数势场法……………………………………………………………..14
2.3.4 回归神经网络法(RNN)……………………………………………………...15
第三章 基于线段关系的扫描匹配定位………………………………………………………...17
3.1 环境描述………………………………………………………………………………..17
3.2 定位传感器……………………………………………………………………………..19
3.3 直线段提取……………………………………………………………………… …….20
3.3.1 LRF数据点分段……………………………………………………………..20
3.3.2 直线拟合……………………………………………………………………..21
3.3.3 直线斜率计算………………………………………………………………..21
3.4 线段关系(LSR)匹配…………………………………………………………………....23
3.4.1 判据选取……………………………………………………………...……...23
3.4.2 递进式对应性计算…………………………………………………………..25
3.4.3 距离关系比较的分离与合并………………………………………………..26
3.4.4 最佳匹配搜索………………………………………………………………..28
3.4.5 位姿计算……………………………………………………………………..29
3.5 实验及结果分析………………………………………………………………………..29
第四章 基于已知地图的路径规划………………………………………………………...……32
4.1 基于A*算法的拓扑地图规划………………………………………………………....33
4.1.1 拓扑地图的表示……………………………………………………………..33
4.1.2 A*算法……………………………………………………………………….34
4.2 基于回归神经网络(RNN)的栅格规划算法………………………………………...…36
4.2.1 栅格环境的RNN表示………………………………………………………36
4.2.2 RNN动力学模型…………………………………………………………….37
4.2.3 RNN路径规划的基本机理………………………………………………….38
4.2.4 RNN安全路径设计………………………………………………………….39
4.2.5 RNN路径规划算法设计…………………………………………………….42
第五章 基于混合地图的移动机器人递阶导航系统的设计………………………...................47
5.1 导航系统体系结构……………………………………………………………………..48
5.2 混合地图模型…………………………………………………………………………..49
5.3 三级递阶规划结构……………………………………………………………………..50
5.3.1 全局规划层架构……………………………………………………………..50
5.3.2 局部规划层架构……………………………………………………………..51
5.3.3 基于Motor-schema的行为反应层………………………………………….53
5.4 地图匹配法和里程计相结合的自定位技术……………………………………..……55
5.4.1 里程计模型…………………………………………………………………..55
5.4.2 匹配定位方法………………………………………………………………..55
5.4.3 位姿融合……………………………………………………………………..58
5.4.3.1 里程计误差分析……………………………………………………………..58
5.4.3.2 匹配定位方法误差分析……………………………………………………..59
5.4.3.3 Kalman滤波………………………………………………………………….60
5.5 各功能间的统筹协调…………………………………………………………………..61
5.6 递阶导航软件SmartNavigator…………………………………………………………62
5.6.1 系统架构……………………………………………………………………..63
5.6.2 导航软件界面及使用介绍…………………………………………………..64
第六章 实验平台与实验设计…………………………………………………………...………69
6.1 多功能机器人“天骄-I”……………………………………………………………...…69
6.1.1 硬件系统……………………………………………………………………..69
6.1.2 运动控制系统………………………………………………………………..70
6.1.3 激光雷达……………………………………………………………………..71
6.2 基于混合地图的递阶导航实验………………………………………………………..73
6.2.1 实验设计与分析……………………………………………………………..73
6.2.2 地图描述……………………………………………………………………..74
6.2.3 实验过程……………………………………………………………...……...74
6.2.4 实验结果与分析……………………………………………………………..75
6.2.5 实验结论…………………………………………………..…………..….78
第七章 结论与展望……………………………………………………………………………...79
7.1 结论……………………………………………………………………………………..79
7.2 展望……………………………………………………………………………………..80
参考文献… ……………………………………………………………………………………….81
致 谢…………………………………………………………………………………………..84
攻读硕士学位期间发表的学术论文……………………………………………………………..86
作者在攻读硕士学位期间参加的科研工作……………………………………………………..86
第一章 绪论
1.1 引言
国际标准化组织（ISO）中的工业自动化系统委员会（TC184）所属工业机器人分会（SC2）对机器人的定义是：“A robot is a machine which can be programmed to perform some tasks which involve manipulative or locomotive actions under automatic control”，即“机器人是一种自动控制下通过编程可完成某些操作或移动作业的机器”。
机器人是在创造一个“与人一样思考、一样行动的机械装置”的构想下诞生的。随着机器人应用领域的不断拓展，机器人技术已经超出工业机器人范畴。早在七十年代中期，在计算机技术、传感器技术和人工智能理论的推动下，国际上广泛开展了对智能机器人的研究，其中以移动机器人[1]的研究最为广泛。近年来,移动机器人技术在工业、农业、医学及社会服务业等领域显示了越来越广泛的应用前景。在我国，移动机器人研究也蓬勃开展起来，神州系列载人飞船多次发射成功，表明国家加大在宇航领域的科学研究力度，在提出的“嫦娥计划”中，移动机器人是星际探索的重要工具，在即将到来的第十一个五年计划中，以服务机器人为代表的移动机器人将承担一个重要的角色，因此，移动机器人已经成为相关科技人员研究攻关重点。
1.2 移动机器人的定义与主要研究内容
1.2.1 移动机器人的定义
移动机器人是机器人学中的一个重要分支。所谓移动机器人就是指能够对复杂的环境进行自主的分析、判断和决策，并实现快捷、安全、自由移动的机器人
l 从工作环境来分，可分为室内移动机器人和室外移动机器人；
l 按移动方式来分，可分为轮式移动机器人、步行移动机器人、蠕动机器人、履带式移动机器人、爬行机器人和水下推进式机器人等；
l 按控制体系结构来分，可分为功能式(水平式)结构机器人、行为式(垂直式)结构机器人和混合式结构机器人；
l 按功能和用途来分，可分为医疗机器人、军用机器人、助残机器人、清洁机器人和管道检测机器人等；
l 按作业空间来分，可分为陆地移动机器人、水下机器人、无人飞机和空间机器人；
1.2.2 移动机器人的主要研究内容
与传统的工业机器人相比，移动机器人是一个组成结构非常复杂的系统，具有任务分析、信息感知、自主决策等类似人类智能行为的人工智能。换句话说，移动机器人可以看作是由知识库及传感器系统、行为控制器和机械装置组成的相互联系、相互作用的复杂动态系统。其研究涉及传感器、人工智能、机械控制等技术，尤其集中在若干关键技术的研究与突破。这些关键技术主要包括机器人体系结构、导航技术、运动控制技术和多传感器信息的集成与融合等[1,2]。
1) 多传感器信息融合
融合是针对一个系统中使用多传感器(多个或多类)这一特定问题而展开的一种信息处理的新的研究方向，它充分利用多源数据的互补性和计算机的高速运算与智能来提高结果信息的质量。多传感器融合[3]的常用方法有：加权平均法、贝叶斯估计、卡尔曼滤波等。其中加权平均法是最简单，也最直观的方法，一般用于对动态低水平的数据进行处理；贝叶斯估计是融合静态环境中多传感器低层数据的常用方法，适用于具有高斯白噪声的不确定性传感信息融合；对于系统噪声和观测噪声为高斯白噪声的线性系统模型采用卡尔曼滤波(KF)来融合动态低层次冗余传感信息。
2) 运动控制技术
由于移动机器人的执行机构种类众多，主要有车轮式，履带式，腿足式，蠕动式，蛇行式等机构形式。因此，运动控制技术的研究不可小觑。移动机器人的运动控制一般分两个层次：
l 移动控制：在导航模块给出具体的移动路径之后，求得合适的速度控制量和驾驶角，保持路径跟踪的鲁棒性。
l 执行：由机器人的移动机构完成移动控制命令。例如，对轮式机器人来说，即控制车轮的转角和转速。
3) 导航技术
这是移动机器人技术的核心研究部分，涉及到人工智能技术诸多问题：感知，执行，规划，结构，硬件，计算效率以及问题求解。所谓导航是指移动机器人通过传感器感知环境与自身状态，建立地图，实现在有障碍物的环境中搜索一条最优或近似最优的无碰路径，以到达目标的自主运动。导航技术需解决三方面的问题：1) 地图建模，2)自定位，3)路径规划。
4) 体系结构
移动机器人是一个自主式智能系统，其主要任务是如何把感知、规划、决策和行动等各种模块有机地结合起来。它的作用包括：把各个子系统连接成一个整体，包括各个部件的接口规范、通讯协议和数据流程；统一管理、调度各个子系统，控制它们功能的发挥，按总体工作模型进行协调工作，使各子系统步调一致地完成总体任务。可见，其设计的优劣直接关系到系统整体性能的发挥和智能水平的高低。
1.3 本文研究课题与内容安排
1.3.1 研究课题
由于导航技术涉及到移动机器人人工智能技术的每一个问题：感知，执行，规划，结构，硬件，计算效率以及问题求解。因此，导航技术目前仍是需要研究的最具有挑战性的问题之一[1]。导航技术涉及三个方面：
l 地图，映射移动机器人环境的信息数据结构，是路径规划的平台。
l 定位，确定移动机器人在二维工作环境中相对于全局坐标的位置及其本身的姿态,是确保导航质量的基本因素。
l 路径规划，指移动机器人按照某一性能指标，在地图中搜索一条从起始状态到目标状态的最优或次最优的无碰路径，是导航的核心技术。
关于地图建模、自定位方法和路径规划，分别有很多研究成果，但目前存在的问题是：
1. 研究者在理论上提出了很多地图建模方法，但囿于成本考虑，移动机器人板载计算机的计算和存储能力有限。因此，在实用的移动机器人导航软件系统中，如何选择合适的地图建模方法，成为难题。一些导航软件甚至不使用地图模型的概念，直接使用反应式行为的导航技术。
2. 自定位是保证导航质量的基础，目前常用的基于里程计的定位方法不能用于长时间的导航，需要采取更为有效的移动机器人自定位方法。
3. 路径规划算法的研究已取得很多理论成果，但多数仍停留在仿真研究层面上，对于实时性要求很高的实际机器人导航过程中，如何选择快速、有效的路径规划算法是导航系统设计的核心问题。
4. 如何整合导航技术的诸多研究成果，进行实用导航系统软件框架的设计，仍是目前较少涉及的研究领域。
综上所述，着眼于目前移动机器人导航研究中存在的问题，本文提出基于混合地图模型，里程计与地图匹配相结合的自定位方法和分层路径规划，来设计一个实用的移动机器人递阶导航系统软件。
1.3.2 内容安排
本文主要研究内容是在阅读大量文献和进行大量实验的基础上，针对地图建模，机器人自定位技术，路径规划方法，机器人运动控制，解决在真实环境下如何为移动机器人设计一个良好的导航系统，并在此基础上使用自主开发的移动机器人进行导航实验，检验导航系统的有效性。最后对导航系统的进一步研究做展望。
本文的内容将作如下安排：
第一章介绍移动机器人的发展状况，提出研究课题和全文的结构安排；
第二章对移动机器人导航技术进行了概述，介绍了导航技术研究的几大方向和已有研究成果。
第三章详细介绍了以线段关系为特征的地图扫描匹配方法。首先，对地图模型进行了描述，接着介绍了线段的获取，定义了在匹配中所用的线段关系，给出了完整的匹配方法，最后，用实验验证了方法的有效性。
导航的另一个重点是路径规划，第四章分别介绍了基于拓扑地图的规划和基于栅格地图的规划。对拓扑地图的规划采用的是A*算法，首先介绍了A*算法的基本原理，然后给出基于A*算法的规划步骤；对栅格地图的规划采用的是基于回归神经网络（RNN）的路径规划方法，首先讨论了RNN模型，基本机理和路径安全方法设计，接着描述如何在栅格地图上进行RNN路径搜索。
在此前研究基础上，第五章结合导航技术其他方面的研究，详细阐述了基于混合地图的移动机器人递阶导航系统。首先，对导航系统的体系框架和混合地图模型进行介绍。然后，分别针对基于拓扑地图的全局规划层，基于栅格地图的局部规划层和基于Motor Schema的反应式行为层，分三个层次阐述如何实现递阶路径规划与导航，并介绍基于线段关系的扫描匹配定位和里程计相结合的自定位模块设计。最后，介绍了自主设计开发的递阶导航软件SmartNavigator。
第六章介绍实验平台与实验设计，首先介绍实验所使用的移动机器人平台―“天骄-I”，然后运用上述导航软件设计了一个长距离导航实验，评估基于混合地图的递阶导航系统的性能，验证基于线段关系匹配扫描匹配定位方法的准确性和鲁棒性。
第七章是对整个研究的总结和展望，针对当前的方案提出了进一步改进研究的思路。
第二章 移动机器人导航技术概述
关于复杂环境下移动机器人自主推理和规划能力的诸多研究主题中，导航问题是研究核心和关键技术。实现导航的三要素是：1)“我在哪里”；2)“我要去哪”；3)“我该如何去”。因此，导航技术涉及三个方面：1）地图；2）定位；3）路径规划。
下面将从这三个方面概要介绍目前研究者所取得的成果。
2.1 移动机器人工作环境表示方法
环境表示指用何种描述方法来表示移动机器人的工作环境，对于机器人导航，通常有很多种方法，其中较为经典的可以分为两类。一类是几何地图，障碍物的位置信息直接以坐标的形式存储在地图中；另一类是拓扑地图，定义了机器人可达的一些区域，通常以相对关系来表示。
2.1.1 几何地图
在几何地图中，环境是一个二维空间，用物体的坐标形式表示。一方面，可以在导航过程中充分利用内部传感器和外部传感器信息，方便进行融合；另一方面，它类似于环境的缩略图，很直观，也方便多机器人之间信息共享。但是，几何地图难以创建，环境的稳定性难以保证，机器人在自己创建几何地图时常常利用内部传感器，它的估计本身不可避免地存在误差，以几何地图形式直接进行路径规划计算量较大。几何地图也有多种表现形式：
1) 特征地图
特征可以精确地存储在地图中，而这些特征易于被机器人所观测到，根据特征提取特级的差异，可以有很多特征表示。
点作为其中一种，可以定义为路标。然而，只观测到一个单独的点是不足以使机器人定位的，真正的应用中需要观测多个点信息。另外，点作为特征使用还需要与实际物体结合，因为通过激光雷达等传感器的感知，常常能获得物体表面上的多个点，作为路标记录的点也需要能够表现为物体表面。只有具有一定空间结构的一系列点才能表示特定的物体，才能作为有效特征信息存储与地图中。
为了使单独的一个特征就能提供足够的定位信息，可以采用拐角，认为它是一种带有了方向的点。两条相交的直线就能够构成一个拐角，而且颠倒能够提供方向信息。
在结构化的环境当中，直线可以用来直接表示障碍和其他物体的边界线，图2-1(b)即是以直线为特征来表示图2-1(a)中所示环境的特征地图。这些直线可以从声纳或者激光雷达测量所得的一系列点中提取出来。
其他例如柱面和曲面在一些场合也有所应用，还有人将曲面和直线结合来表示环境。

(a) 地图原形
(a) Real map

(e) 拓扑地图
(e) Topo map

(b) 特征地图
(b) Feature map

(c) 栅格地图
(c) Grid map

(d) Voronoi图
(d) Voronoi map
图2-1 地图示例
Fig. 2-1 Examples of map

2) 栅格地图
除了使用一些特征来表示物体，还可以用机器人是否可达来表示环境信息。最常见的就是栅格地图，环境分解成规则地具有分辨率的栅格单元，每个栅格单元用一个概率值来表明它是否被障碍物所占居，如图2-1(c)所示。以这种方式来表示环境，不需要知道物体的形状，无需进行特征提取。但是，在表征大范围环境时，栅格地图通常占用较多的存储，计算量也较大。
栅格地图较多地用在路径规划中，对环境采用正方形栅格进行分解，然后可按栅格间4－连通或8－连通关系进行最短路径搜索[4]；其他的栅格形状还有正六边形和正三角形等，分别可按6－连通和3－连通关系进行路径搜索。栅格表示法的优点之一是在于无需对不同栅格之间的可行路径进行预处理，所有的可行路径都是隐式形成的。此外，栅格法易于建立、表示和维护，物体位置表示在栅格地图中是精确的，易于识别。
3) Voronoi图
Voronoi图[2]可以认为是非障碍物空间（自由空间）的中轴线（如图2-1(d)所示）。由于Voronoi图的维数比机器人所在的环境维数低，因此Voronoi图用于路径规划搜索时通常搜索空间也较小。Voronoi图上形成的路径长度要长于最短路径长度，故而Voronoi图上路径的最优性较差。但在实际应用中，由于要考虑到机器人运动的安全性，通常沿着Voronoi图运动时具有较宽阔的通道。不过当采用路径长度作为优化目标时，Voronoi图不能完全保证所规划路径的安全性。计算Voronoi图的算法较多，如Aggarwahl[6]给出了一种N个节点环境中，串行计算复杂度为O(Nlog2N)的算法。
2.1.2 拓扑地图
拓扑地图[7]高度抽象了环境的几何特征描述，采用拓扑节点表示具有相同或相近特征的环境，不同节点间的连接权值表示相应的距离代价（如图2-1(e)所示）。拓扑节点可以人为定义也可以由机器人自主定义，走廊、门、路口常常被选作拓扑节点；拓扑节点间的连接可以用节点间的距离和角度表示，也可以用它们在不同方向上距离的差值表示，还可以直接以坐标形式表示拓扑节点，只是需要附加信息来表示节点间的连通性。
拓扑地图表示忽视对物体形态的认知，即不需要通过传感器去感知观测到的具体是何种物体，它要做的是拓扑节点的定义以及根据传感器信息对节点的确认。离散的拓扑地图可以应用与更高层次的决策，例如在较大范围的环境里，在具有较少存储空间的拓扑地图上的规划显然要比直接在几何地图上的规划要简单得多。这样做，对于人类使用者来说也更为熟悉，我们更习惯指使机器人去某个房间而不是叫它去某个坐标位置。尽管拓扑地图表现出种种优越性，但它仍存在其不利的方面。它需要较精确的位置估计，也要求拓扑节点方便被观测到；对拓扑节点的定义是拓扑地图的一大难点，如果传感器本身不稳定或环境动态性较大，将更加困难；规则化的环境常常有很多地方很相近，观测上的相似性将陷入对拓扑节点确认的混淆。
2.2 移动机器人定位技术
定位是确定移动机器人在二维工作环境中相对于全局坐标的位置及其本身的姿态,是移动机器人导航的最基本环节。定位方法主要有两大类，一类是局部定位或者叫跟踪定位，它基于机器人之前的位置，根据内部和外部传感器估计当前位置，这种方法需要设定机器人的起始位姿，并且要求机器人的位置的估计与真实值之间的差异不能太大；另一类是定位方法是全局定位，它不利用以前的位置信息，完全根据传感器的观测确定当前位置，也无需知道机器人的初始位置，对于机器人位置丢失后位置的恢复非常有用。这两种方法各有其特点，跟踪定位是一个连续的过程，也符合机器人的移动规律，它可以根据观测精确地较正机器人的位置，是一种较好的定量方法；与之对应的全局定位不连续，能较好地解决定性的问题，即根据观测确定物体形态或是当前所处的区域。在较大范围的环境里，也许有很多相似的物体和环境，传感器的观测差异很小，怎样区分是一个难题。跟踪定位只需要区分较少的差异使得它比全局定位也更容易实现，
定位技术可分为绝对定位技术和相对定位技术。
2.2.1 相对定位技术
相对定位技术[8]主要有测距法和惯性导航法。测距法常采用的传感器有光电编码器、里程计和航向陀螺仪。其优点是具有良好的短期精度、低廉的价格以及较高的采样速率。 惯性导航法采用陀螺仪和加速度计实现定位,陀螺仪测量回转速度,加速度计测量加速度。 根据测量值的一次积分和二次积分可分别求出角度和位置参量。相对定位技术的基本思路都是基于测量值的累积, 因而无法避免时间漂移问题,随着路径的增长,任何小的误差经过累积都会无限增加。 因此,相对定位不适于长距离和长时间的准确定位, 通常将它们与绝对位置测量技术相结合,以获得更可靠的位置估计。
2.2.2 绝对定位技术
绝对定位技术[9]中比较成熟的有全球定位系统、路标定位和地图匹配定位。全球定位系统(Global Positioning System) 简称GPS[10] ，它是一种以空间卫星为基础的高精度导航与定位系统。 GPS 定位系统用于移动机器人定位时存在近距离定位精度低等问题。 路标定位是一种常见的定位技术。路标是具有明显特征的能被机器人传感器识别的特殊物体。根据路标的不同，分为基于自然路标定位和基于人工路标定位。其中，人工路标定位技术[11]应用得最为成熟。人工路标定位是在移动机器人的工作环境里，人为地设置一些坐标已知的路标，如超声波发射器、特定颜色色块和激光反射板等，机器人通过对路标的探测来确定自身的位置。 基于已知地图的定位系统称为地图匹配定位技术，移动机器人通过自身的传感器探测周围环境，并利用感知到的局部信息进行局部地图构造，然后将这个局部地图与预先存储的完整地图进行比较，如两地图相互匹配，就能计算出机器人在工作环境中的位置与方向。 地图匹配定位的两个关键技术是地图模型的建立和匹配算法。
在很多应用中，这两种定位技术常常是相互配合的，相对定位中产生的累积误差不能适用于大范围的导航需求，而绝对定位中，为了缩小地图的范围，可以利用相对定位对当前机器人的位置进行估计。
根据这些定位技术和要求，有三种定位策略是最常用的。
1) 直接位置计算，它只利用外部传感器信息，直接根据观测和地图的匹配计算机器人的位置，一方面要求传感器能够提供足够多的准确信息，另一方面，环境中不存在观测的混淆，否则机器人不能确定自己的位置。
2) 基于单假设的位置跟踪，需要同时利用内部和外部传感器信息。首先，通过基于内部传感器相对定位技术，根据机器人前一位置对当前位置进行估计，再利用外部传感器的观测信息进行校正，就能得到准确可靠的机器人位置。当然，如果对位置的估计偏差较大，观测信息将不能对错误估计进行校正，机器人迷失了自己。对位置的估计，限制了地图的范围，有效地减少了混淆现象，而且即使发生了混淆也能准确区分。
3) 基于多假设的位置跟踪，同样同时使用内部和外部传感器信息。与基于单假设的位置跟踪只对最可能的位置跟踪不同，它同时跟踪所有的可能位置，并且都进行更新。这样的做法使得位置切换成为可能，即使对最可能位置的跟踪丢失，也可能很快恢复。它能够完成具有观测混淆环境中全局定位。
2.3 移动机器人路径规划方法
路径规划是指移动机器人按照某一性能指标搜索一条从起始状态到目标状态的最优或次最优的无碰路径。目前常用的路径规划方法有图搜索算法，人工势场算法和神经网络算法。下面将介绍其中几个典型的路径规划方法。
2.3.1 Dijkstra和A*图搜索算法
生成移动机器人环境的图表示后，可在图上按一定的性能指标进行路径规划。多数路径规划研究都以路径长度作为代价指标来求解最短路径。Dijkstra算法和A*算法是两种典型的图搜索算法[12]，前者搜索出图中所有节点到目标节点的最小代价路径；后者通过辅助的启发式信息来搜索出图中指定节点对之间的最小代价路径。当图中多数节点之间存在直接连通性时（即是稠密图），采用节点优先扫描的Dijkstra算法是典型的节点之间最小代价路径搜索算法，此时对N节点稠密图搜索复杂度为O(N2)。如果对稠密图采用边扫描优先的Dijkstra算法，由于图中有O(N2)条边，计算复杂度将增加到O(N2logN)，高于节点优先扫描时的Dijkstra算法。如果当机器人起始位置节点被扩展到后就停止搜索，此时的Dijkstra算法就成了启发式信息为0的A*算法。即A*算法可以看作一种有启发式信息的边优先扫描Dijkstra算法。可见，启发式搜索由于在路径规划中引入了启发信息，使得在搜索中能够优先考虑更有希望的顶点，无疑有助于减少算法的搜索空间，从而提高搜索效率。因此，如果规划任务要求找到一条从起始节点到目标节点的最优或次最优的无碰路径即可，而无需确定所有节点到目标节点的最小代价路径，应考虑采用A*启发式搜索算法[13]。
需要补充的是，栅格表示的环境中同样可用图搜索方法进行路径规划。多数研究者在栅格表示的环境中路径规划时通常也都以路径长度作为优化指标，例如4-连通二维环境中通常最好得到的是最短4-连通路径。具有启发式信息的A*算法适用于这里的4-连通环境路径搜索，所需平均计算复杂度为O(NlogN)。
2.3.2 人工势场法
势场法在机器人的环境上给定一个标量函数，这个函数通常在路径规划的目标点处具有最小值，而在障碍物附近可能有较大的值，然后机器人沿着势场的最速梯度方向运动[4,5,6]。
Khatib[14]的人工势场法（Artificial Potential Field, APF）是一个典型的势场法路径规划例子。APF方法中目标节点对环境上任何一点都有吸引力，而环境中的障碍物仅对其周围局部范围内具有排斥力，吸引力势场和排斥力势场的叠加矢量构成机器人在当前位姿点的运动方向。APF的排斥力势场是局部的，计算比较简单。由于APF方法中通常选择障碍物边缘上势场值为+∞，因此在障碍物附近的路径通常具有较好的安全性。
势场法由于其数学上优雅性和简洁性而引起了很多研究者注意。但是Borenstein等[15,16]分析指出通常的人工势场法具有几个明显的缺点：1) APF方法有可能存在非期望的局部吸引点（当目标处为最小势场值时，非期望的局部吸引点是非期望的最小值处；当目标处为最大势场值时，非期望的局部吸引点是非期望的最大值处），使得机器人陷入到某个局部环境中，而不能到达目标点。即APF方法不能保证路径规划的完整性。2) 在密集障碍物环境下，通常的APF方法容易会裁减掉比较狭窄的通道，破坏了路径规划的完整性。3) 在某些局部环境中探测到新障碍物后势场可能发生振荡。4) 狭窄通道中由于机器人传感器探测范围有限性，也会发生路径振荡。
2.3.3 调和函数势场法
在环境上用Laplace方程建模时，选择合适的边界条件可以保证方程的解，即调和函数(Harmoinc函数) [17]，所形成的势场中所有非期望的局部吸引点约束在障碍物内部，而自由位姿空间中只有目标节点是唯一的局部吸引点。这样，用调和函数解形成的势场也可以进行路径规划。相比普通的人工势场法，调和函数法的最大优点在于合适的边界条件可以避免非期望局部吸引点的出现，保证了路径规划的完整性。调和函数路径规划方法便于进行理论分析，但Koditschek[18]指出调和函数路径规划存在一个严重的缺点：通常任意形状环境上的调和函数方程不存在代数解析解。这约束了必须通过数值方法对调和函数进行数值求解。Zelek[19]则指出了调和函数路径规划中数值求解时存在地一个严重缺点：有效数字的快速衰减性，不能高解析度地表示大环境。因此已有的调和函数路径规划方法虽然在理论上有其完整性，但在实际应用中是有限的。
2.3.4 回归神经网络法（RNN）
RNN（Recurrent Neural Network）是Hopfield神经网络的推广，具有高度并行性和更丰富的动力学性质。RNN路径规划中每个神经元和离散化环境节点相对应，并且神经元之间的局部连通关系表示环境的连通性，通过施加合适的外部激励使RNN形成最速上升势场[20,21,22]。由于研究者对RNN路径规划的出发点差异，目前对RNN路径规划尚且缺乏统一的名称，这些名称包括波前扩散法的细胞自动机路径规划[22]、波动扩散神经网络[21]（Wave Expansion networks,WENN）、Shunting Model神经网络[20]（SMNN）等。虽然方法名称各有差异，但这些方法中每个处理单元都可看作一个动态回归神经元，而每个神经元都对周围相邻神经元采样并向传播势场。因此可统一称为RNN路径规划。
波前扩散法用栅格将环境离散化表示后，采用细胞自动机来表示栅格空间，通过波前扩散法来建立势场。波前扩散法中从目标节点出发的一束波沿着非障碍物细胞节点进行运动，按每个细胞节点被扩散到的先后顺序进行编号。当机器人当前位置对应的细胞节点被波前扩展到后，通过回溯获得一条最短路径。
Kassim[21]的WENN路径规划神经元模型比较接近于波前扩散法的细胞模型，同样采用波前扩散机理来构建势场。Kassim提出采用WENN来构建环境的Voronoi骨架图来降低路径规划搜索空间。Kassim提出对环境中的障碍物进行分割，然后每个障碍物分别传出自己的波，进行同步扩散，当多束波在某个栅格相遇时，表明该栅格一定在Voronoi图上。但该方法仅适用于环境中障碍物都为凸型的情况。
Glasius[23]构建了一种连续状态的RNN模型，由于该RNN中每个神经元都具有波动扩散衰减性质，因此也能形成最快上升路径。但其模型是根据微分方程和差分方程近似变换关系求得的，每个神经元的负反馈系数较小，故神经元收敛速度慢，动态特性较差。为此在Glasius模型基础上，Yang[20]等受生物神经元细胞模型出发，给出一种扩展的RNN模型――SMNN来进行路径规划，SMNN的神经元模型具有更好的生物化学解释机理，同时神经元的负反馈系数可以调整，具有较快的收敛速度。
第三章 基于线段关系的扫描匹配定位
移动机器人的自定位能力是实现自主导航的关键。在结构化或半结构化的环境里，如走廊、办公室等，如果环境地图已知，自定位主要采用基于扫描匹配[31,32,33,34,35,36,38]和基于概率论[35,37]两类方法。根据对传感器数据的再加工与否，扫描匹配又可以分为特征匹配[31,32,33,34,35,36]和原始数据匹配[38]。
基于几何特征的匹配寻找观测地图和参考地图的特征的对应关系，能够实现迅速、高效、可靠的定位。APR [31]寻找的是两个地图中的定位点的对应关系，它不受初始估计的影响；M.Altermatt [32] and Xu Zezhong [33]根据拐角间的不变量对他们进行匹配；Cox [34] and J. Gutmann [35] 将扫描数据直接跟地图中的线段进行匹配。如果不能探测到足够的定位点，APR [31]很容易发生混淆。匹配拐角[32,33]对特征提取的要求很高，一旦有遮挡很容易丢失位置。原始数据匹配[34,35]因为需要经过多次迭代，计算量很大。
本章提出了一种以线段关系（LSR，Line Segment Relationship）为特征的匹配方法。同APR[31]方法类似，也需要建立一个对应关系矩阵来记录地图的对应关系，有所不同的是，增加了更多的关系，比如角度、点到直线的距离等，而不仅仅是点到点的距离。这些被匹配的关系有不同的优先级，只有在高优先级的关系一致的情况下，才去比较低优先级的关系。通过计算两条线段的对应程度，得出对应性矩阵，从中搜索最佳匹配，估计机器人的位姿。对应关系的最大值，即我们要找的最佳匹配用来计算机器人的位姿。因为关系产生于同一个地图中，匹配的过程无需用到坐标变换，将不受估计位姿的影响。它能够在有遮挡的情况下成功地匹配，且计算量较小。
下文介绍了作为特征的线段的定义，以及通过激光雷达获取直线的方法，在此基础上提出了以线段为特征的地图扫描匹配方法，并根据匹配的结果定位，最后的实验对该方法进行了检验。
3.1 环境描述
如前文所述，对环境的描述主要有两种方法，几何地图和拓扑地图。为了实
图3-1 地图示例
Fig. 3-1 Example of a metric map
现机器人的自主定位，详细表述了环境的几何地图要优于拓扑地图，而考虑