动态环境下多移动机器人路径规划研究

1、（申请工学硕士学位论文）动态环境下多移动机器人路径规划研究摘 要对多移动机器人系统而言，如何产生各个机器人的协调无碰运动路径是对它的一项基本要求。因此，近年来多机器人路径规划逐渐成为机器人研究的一个热点问题。本文通过对多机器人编队问题的研究，从协调和协作两个方面来研究多机器人路径规划问题。编队控制是指多个机器人在到达目的地的过程中，保持某种队形同时又要适应环境约束的控制技术。多机器人研究中的主要问题是机器人间的协调和合作，通常协调是为了解决机器人之间的冲突和矛盾，而合作指机器人通过一种机制合作完成一项任务。 对于自主移动机器人编队问题来说，协调主要就是使机器人避免和障碍物以及机器人之间发生碰撞

2、；合作就是保持队形。通过本课题的研究，得到如下的成果与结论：综合国内外相关研究文献，阐述了移动机器人研究现状和主要内容。同时，详细介绍了多机器人系统、路径规划及机器人编队问题的研究现状。介绍了几种移动机器人路径规划的理论和算法，主要包括全局路径规划和局部路径规划。提出了一种基于模糊逻辑的行为融合路径规划方法。通过对多移动机器人编队问题的研究，来阐述多机器人路径规划中的路径冲突协调和协作问题，提出了一种在未知环境中基于观察者的多机器人编队控制方法。通过一种新的开源机器人仿真平台Player/Stage建立仿真实验环境，然后在Eclipse下利用java编程语言编写客户端算法，控制程序通过TCP

3、socket连接到Player机器人设备服务器端，实现对仿真机器人的控制。关键词：路径规划，多机器人系统，机器人编队，Playe/StageAbstractFor multiple mobile robots system，how to find a safe path without collosion for each robot is a basic requirement. Therefore，the multi-robots path planning approach is emerging as a key technology in the study of multiple

4、mobile robotics over recent years. Through the study of formation control of multi-robots，this thesis studies the problem of multiple mobile robots path planning from two aspects of coordination and cooperation.The formation problem in multi-robots systems is defined as the coordination of a group o

5、f robots to maintain a formation with a desired shape and reach a particular destination without collisions. The key problem of multiple robots system is the coordination and cooperation with each robot. Usually，coordination is used to resolve the conflicts and collosions among each robot and cooper

6、ation means that some robots collaborate to complete a task according to a mechanism. As for the formation of multi-robots，the coordination is the avoidance of obstacle and the resolvement of collsion with other robots，and the cooperation is used to maintain a formation with a desired shape. The mai

7、n contents of this thesis are as follows:1. Investigated the current research status and main contents of mobile robots，according to the domestic and foreign relevant references. At the same time，gave the detailed introduction of current research status of multi-robots system，path planning and forma

8、tion control.2. Introduced some kinds of theories and algorithms of path planning，mainly including the global path planning and the local path planning and presented a behavior fusion path planning method for mobile robots based on fuzzy logic.3. Through the study of formation control of multi-robot

9、s，explained the problem of coordination and cooperation in multi-robots path planning. Presented an observer based formation control algorithm for multi-robots. 4. Built the simulated environment for multi-robots formation control with the Player/Stage software and compiled java program to control t

10、he simulated robots through TCP Socket in the Eclipse.Keyword: Path Planning，Multi-Robots System，Formation Control，Player/Stage目 录 TOC o 1-3 h z u HYPERLINK l _Toc134780208 第1章 绪论 PAGEREF _Toc134780208 h 1 HYPERLINK l _Toc134780209 1.1 课题研究背景及意义 PAGEREF _Toc134780209 h 1 HYPERLINK l _Toc134780210 1.

11、2 国内外研究历史及现状 PAGEREF _Toc134780210 h 2 HYPERLINK l _Toc134780211 1.3 本文内容与结构 PAGEREF _Toc134780211 h 6 HYPERLINK l _Toc134780212 第2章 移动机器人路径规划理论及算法 PAGEREF _Toc134780212 h 7 HYPERLINK l _Toc134780213 2.1 路径规划问题概述 PAGEREF _Toc134780213 h 7 HYPERLINK l _Toc134780214 2.2 常用路径规划算法 PAGEREF _Toc134780214

12、h 7 HYPERLINK l _Toc134780215 2.2.1 模糊逻辑法 PAGEREF _Toc134780215 h 7 HYPERLINK l _Toc134780216 2.2.2基于栅格法的自主机器人实时路径规划 PAGEREF _Toc134780216 h 9 HYPERLINK l _Toc134780217 2.2.3 人工势场法 PAGEREF _Toc134780217 h 11 HYPERLINK l _Toc134780218 2.2.4 VFH方法 PAGEREF _Toc134780218 h 12 HYPERLINK l _Toc134780219 2

13、.3 基于模糊逻辑的行为融合路径规划方法 PAGEREF _Toc134780219 h 13 HYPERLINK l _Toc134780220 2.3.1 方法概述 PAGEREF _Toc134780220 h 13 HYPERLINK l _Toc134780221 2.3.2 移动机器人模型 PAGEREF _Toc134780221 h 13 HYPERLINK l _Toc134780222 2.3.3 坐标系和控制变量 PAGEREF _Toc134780222 h 14 HYPERLINK l _Toc134780223 2.3.4 路径规划器结构 PAGEREF _Toc1

14、34780223 h 15 HYPERLINK l _Toc134780224 2.4 本章小结 PAGEREF _Toc134780224 h 20 HYPERLINK l _Toc134780225 第3章 多机器人编队问题研究 PAGEREF _Toc134780225 h 21 HYPERLINK l _Toc134780226 3.1 多机器人编队概述 PAGEREF _Toc134780226 h 21 HYPERLINK l _Toc134780227 3.2 常见的多机器人编队方法 PAGEREF _Toc134780227 h 21 HYPERLINK l _Toc13478

15、0228 3.2.1跟随领航者法 PAGEREF _Toc134780228 h 21 HYPERLINK l _Toc134780229 3.2.2基于行为法 PAGEREF _Toc134780229 h 22 HYPERLINK l _Toc134780230 3.2.3虚拟结构法 PAGEREF _Toc134780230 h 22 HYPERLINK l _Toc134780231 3.3 基于观察者的多机器人编队方法 PAGEREF _Toc134780231 h 23 HYPERLINK l _Toc134780232 3.3.1 l- 编队控制法 PAGEREF _Toc134

16、780232 h 23 HYPERLINK l _Toc134780233 3.3.2 编队方法基本思想 PAGEREF _Toc134780233 h 25 HYPERLINK l _Toc134780234 3.3.3 编队方法结构 PAGEREF _Toc134780234 h 25 HYPERLINK l _Toc134780235 3.4 本章小结 PAGEREF _Toc134780235 h 27 HYPERLINK l _Toc134780236 第4章 开源机器人项目Player/Stage PAGEREF _Toc134780236 h 28 HYPERLINK l _To

17、c134780237 4.1 Player介绍 PAGEREF _Toc134780237 h 28 HYPERLINK l _Toc134780238 4.1.1 描述 PAGEREF _Toc134780238 h 28 HYPERLINK l _Toc134780239 4.1.2 Player的运行方式 PAGEREF _Toc134780239 h 29 HYPERLINK l _Toc134780240 4.1.3 系统平台要求 PAGEREF _Toc134780240 h 29 HYPERLINK l _Toc134780241 4.1.4 总体框架的设计特点 PAGEREF

18、_Toc134780241 h 30 HYPERLINK l _Toc134780242 4.2 Stage介绍 PAGEREF _Toc134780242 h 35 HYPERLINK l _Toc134780243 4.3 本章小结 PAGEREF _Toc134780243 h 35 HYPERLINK l _Toc134780244 第5章 仿真实验 PAGEREF _Toc134780244 h 36 HYPERLINK l _Toc134780245 5.1 仿真实验的硬件和软件 PAGEREF _Toc134780245 h 36 HYPERLINK l _Toc13478024

19、6 5.1.1 world文件 PAGEREF _Toc134780246 h 36 HYPERLINK l _Toc134780247 5.1.2 cfg文件 PAGEREF _Toc134780247 h 37 HYPERLINK l _Toc134780248 5.1.3 客户端开发工具介绍 PAGEREF _Toc134780248 h 39 HYPERLINK l _Toc134780249 5.2 传感器参数分析及设置 PAGEREF _Toc134780249 h 41 HYPERLINK l _Toc134780250 5.3 客户端与机器人服务器Player的通信 PAGER

20、EF _Toc134780250 h 44 HYPERLINK l _Toc134780251 5.4 基于模糊逻辑的行为融合路径规划方法仿真 PAGEREF _Toc134780251 h 46 HYPERLINK l _Toc134780252 5.5 基于观察者的多机器人编队方法仿真 PAGEREF _Toc134780252 h 48 HYPERLINK l _Toc134780253 5.5.1 编写多机器人仿真world文件 PAGEREF _Toc134780253 h 48 HYPERLINK l _Toc134780254 5.5.2 编写多机器人仿真cfg文件 PAGERE

21、F _Toc134780254 h 49 HYPERLINK l _Toc134780255 5.5.3 多机器人编队控制算法 PAGEREF _Toc134780255 h 51 HYPERLINK l _Toc134780256 5.5.4 仿真实验结果与分析 PAGEREF _Toc134780256 h 52 HYPERLINK l _Toc134780257 5.6 本章小结 PAGEREF _Toc134780257 h 53 HYPERLINK l _Toc134780258 第6章 工作总结和展望 PAGEREF _Toc134780258 h 54 HYPERLINK l _

22、Toc134780259 6.1 工作总结 PAGEREF _Toc134780259 h 54 HYPERLINK l _Toc134780260 6.2 论文创新点 PAGEREF _Toc134780260 h 54 HYPERLINK l _Toc134780261 6.3 工作展望 PAGEREF _Toc134780261 h 55 HYPERLINK l _Toc134780262 参考文献 PAGEREF _Toc134780262 h 56 HYPERLINK l _Toc134780263 致 谢 PAGEREF _Toc134780263 h 60 HYPERLINK l

23、 _Toc134780264 攻读硕士期间参加的科研项目和发表的论文 PAGEREF _Toc134780264 h 61第1章 绪论中国工程院院长宋健指出：“机器人学的进步和应用是20世纪自动控制最有说服力的成就，是当代最高意义上的自动化”。机器人技术综合了多学科的发展成果，代表了高技术的发展前沿，它在人类生活应用领域的不断扩大，正引起国际上重新认识机器人技术的作用和影响1-9。1.1 课题研究背景及意义本课题来源于国家自然科学基金(60475031)：“传感器网络环境中移动机器人动态特征与可重构控制框架”和湖北省青年杰出人才基金项目(2005ABB021)：“自治体系统的分布式智能传感、控

24、制与协作”。机器人作为人类20世纪最伟大的发明之一，在短短的40年内发生了日新月异的变化。发展机器人技术己成为高技术领域中具有代表性的战略目标之一。机器人技术的出现和发展，不但使传统的工业生产面貌发生了根本性变化，而且将对人类的社会产生深远的影响。就目前的机器人技术水平而言，单机器人在信息的获取、处理及控制能力等方面都是有限的，对于复杂的工作任务及多变的工作环境，单机器人的能力尤显不足。于是人们考虑由多个机器人组成的群体系统通过协调、协作来完成单机器人无法或难以完成的工作。进行多机器人系统的研究是机器人技术发展的必然趋势，必将对机器人技术的发展起着重要作用。今后随着科技的发展，多机器人系统的应

25、用领域将逐渐向工业、军事领域发展，它的应用将越来越广。在工业中，多机器人系统的柔性可极大地加快企业的转产速度，实现柔性加工；在国防中，它可以实现无人飞机和无人坦克代替军队进行作战，最大限度地减少人员伤亡。可以预见多机器人系统的应用将会对社会带来巨大变革，能极大地提高人们的生活质量以及工农业和国防现代化程度。在多机器人系统的许多应用领域中，要求多机器人在作业和运动过程中保持一定的队形，尤其是在完成军事任务的过程中，保持队形显得更为重要。多移动机器人保持一定的队形至少有以下几点好处:充分获取当前环境信息。单个机器人的传感器获取信息的能力是有限的，如果多个机器人保持一定的队形，而每个机器人的传感器负

26、责获取自己周围的环境信息，这样就可以保证比较完整地获得机器人群体当前活动区域的环境信息，对于实现侦察、搜寻、排雷及安全巡逻等任务是有利的。可以增强抵御外界入侵的能力。作战过程中，机器人士兵通过保持队形，可以抵抗多方向的入侵，增加自身安全性，群居动物按一定队形行进可以有效抵抗掠食者的现象就是一例。可以提高工作效率，如果选择的队形适当，可以加快任务的完成。例如，多个机器人推箱子，机器人与箱子之间必须保持一定的几何关系才能够将箱子推向期望的方向，类似的任务还有农作物收割、播种等。另外，研究多机器人的队形保持问题，对于自动公路系统及战斗机编队等也有指导意义，因为它们的共同之处都是多个智能体协作实现共同

27、的目标。对于含有多个移动机器人的系统而言，如何产生各个机器人的协调无碰撞运动路线是对它的一项基本要求，因此，本课题研究的路径规划和编队问题对于多机器人系统的研究具有重要的和实际的应用价值和意义。1.2 国内外研究历史及现状移动机器人的研究始于60年代末期，斯坦福研究院(SRI)的Nils Nilssen和Charles Rosen等人，在1966年至1972年间研制出名为Shakey13移动机器人。目的是研究如何在复杂环境下将人工智能技术应用于机器人系统，以完成自主推理、规划和控制的功能。该时期的移动机器人的研究，主要是集中在室内结构化环境下，移动机器人所有应用到的基本技术，包括机器人结构设计

28、、控制技术、传感器技术、信息融合、路径规划等。进入20世纪80年代，人们研究方向逐渐转向面向实际应用的室内移动机器人8，并逐步形成了自主式移动机器人AMR（Autonomous Mobile Robot）概念。这时期的研究成果有美国海军研究的Robart-I&II，橡树岭国家实验室的核电站机器人等。90年代以来，以研制高水平的环境信息传感器和信息处理技术，高适应性的移动机器人控制技术，真实环境下的规划技术为标志，开展了移动机器人更高层次的研究。一大批世界著名公司和大学也加入到移动机器人研究工作中，开发的较著名的机器人实验平台有Martin公司的ALVin，FMC公司的ARV，RWI公司的mic

29、roARTV9，ActivMedia公司的pioneer-2 DX。国内对移动机器人的研究起步较晚，但经过多年努力，也取得了一定成绩。目前以清华大学研制THMR3系列比较著名。随着机器人技术的发展，机器人的能力不断提高，机器人应用领域也不断开拓，尤其是一些危险的、特殊的领域，如核工业故障、太空作业等，迫切需要机器人的介入。由于单机器人的局限性，一些复杂任务需要通过多机器人协调来完成。多机器人系统的研究始于20 世纪70 年代。随着机器人应用领域的不断拓展、机器人工作环境复杂度、任务的加重，对机器人的要求不再局限于单个机器人，多机器人的研究已经成为机器人学研究的一个热点。多机器人系统的研究分为多

30、机器人协调(Multi-robot Coordination) 和多机器人合作(Multi-robot Cooperation) 两大类，主要研究给定一个多机器人系统任务后，如何组织多个机器人去完成任务，如何分解和分配任务以及如何保持机器人之间的运动协调一致。 近年来，国际上很多研究机构在该方面的研究取得了一定的成果。 美国Oak Ridge 国家实验室的Cooperative Robotics 实验系统26研究的协作机器人是集成了感知、推理、动作的智能系统，着重研究在环境未知且在任务执行过程中环境动态变化的情况下，机器人如何协作完成任务。 美国USC大学Socially Mobile 和Th

31、e Nerd Herd27实验系统在多机器人学习、群行为、协调与协作等方面开展工作。日本Nagoya 大学的CEBOT 系统28的研究，涉及到系统的体系结构、通讯、信息交互许多方面。中国科学院沈阳自动化所的MRCAS系统29在多机器人协作理论研究的基础上开展多机器人协作的实验研究。目前，以多机器人为主体的系统大多采用集中性节拍同步控制，这存在对整个机器人系统的规划算法过于复杂、已生成的系统扩充或修改困难、局部故障会造成系统瘫痪、系统负载过大而机器人本身的资源无法发挥其全部作用等一系列问题，故而有必要对多机器人系统进行研究，使之达到多机器人协调的目的。多机器人的协调是为了提高工作效率，完成复杂劳

32、动，并且由于单个机器人的独立性及机器人之间的协调性，某一机器人发生故障其他机器人仍可以完成一定的工作，同时有良好的可扩充性，即加入某个机器人只需加入相应的控制程序即可使之与原机器人系统各机器人协调工作。多机器人系统并不是多个机器人的简单堆叠自然产生的，简单的堆叠不能发挥多机器人的优势，反而会存在多机器人之间的冲突，使整体性能反而降低。因而需要研究多机器人的体系结构及它们之间的协调控制机制。多机器人协调最基本的问题是多机器人之间信息的传递，多机器人之间通过必要的信息交流实现多机器人的同步或协调，如坐标确定、路径规划、防止死锁、避免碰撞等。路径规划是自主式移动机器人导航的基本环节之一，它是按照某一

33、性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。根据机器人对环境信息知道的程度不同，可分为两种类型: 环境信息完全知道的全局路径规划和环境信息完全未知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局部路径规划。全局路径规划包括环境建模和路径搜索策略两个子问题。其中环境建模的主要方法有: 可视图法(VGraph)、自由空间法(Free Space Approach) 和 栅格法(Grids) 等。 可视图法13视机器人为一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以

34、及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。 运用优化算法，可删除一些不必要的连线以简化可视图，缩短搜索时间。该法能够求得最短路径，但假设机器人的尺寸大小忽略不计，使得机器人通过障碍物顶点时离障碍物太近甚至接触并且搜索时间长，对于N 条连线的搜索时间为T(N)。Voronoi Diagrams 法和Tangent Graph 法15对可视图法进行了改进；自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形16等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划

35、。 该法比较灵活，起始点和目标点的改变不会造成连通图的重构，但算法的复杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短路径；栅格法17将机器人工作环境分解成一系列具有二值信息的网格单元，多采用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该法以栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响着环境信息存储量的大小和规划时间的长短。栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密集环境下发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境下发现路径的能力强，但环境信息存储量大，规划时间长，可以采用改进的栅格法18弥补栅格法的不足。

36、路径搜索策略主要有:A* 算法19、D* 最优算法20等。局部路径规划的主要方法有: 人工势场法(Artificial Potential Field )、遗传算法( Genetic Algorithm )、模糊逻辑算法( Fuzzy Logic Algorithm ) 和神经网络等。 人工势场法是由K.hatib 提出的一种虚拟力法。其基本思想是将机器人在环境中的运动视为一种虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目标点产生引力，引力和斥力的合力作为机器人的加速力，来控制机器人的运动方向和计算机器人的位置。 该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广

37、泛的应用，但对存在局部最优解的问题，容易产生死锁现象(Dead Lock)22，因而可能使机器人在到达目标点之前就停留在局部最优点；J. Holland23在60年代初提出了遗传算法，以自然遗传机制和自然选择等生物进化理论为基础，构造了一类随机化搜索算法。它利用选择、交叉和变异来培养控制机构的计算程序，在某种程度上对生物进化过程做数学方式的模拟。它不要求适应度函数是可导或连续的，而只要求适应度函数为正，同时作为并行算法，它的隐并行性适用于全局搜索。多数优化算法都是单点搜索算法，很容易陷入局部最优，而遗传算法却是一种多点搜索算法，因而更有可能搜索到全局最优解。由于遗传算法的整体搜索策略和优化计算

38、不依赖于梯度信息，所以解决了一些其它优化算法无法解决的问题。但遗传算法运算速度不快，进化众多的规划要占据较大的存储空间和运算时间；基于实时传感信息的模糊逻辑算法30参考人的驾驶经验，通过查表得到规划信息，实现局部路径规划。该方法克服了势场法易产生的局部极小问题，适用于时变未知环境下的路径规划，实时性较好。神经网络作为一个高度并行的分布式系统，对于解决机器人系统实时性要求很高的问题提供了可能性，它在智能自主移动机器人路径规划中的应用已显示出其优越性。国内在移动机器人的研究起步较晚，大多数研究尚处于某个单项研究阶段，主要的研究工作有清华大学智能移动机器人于1994年通过鉴定，涉及到五个方面的关键技

39、术:基于地图的全局路径规划技术研究；基于传感器信息的局部路径规划技术研究；路径规划的仿真技术研究；传感技术、信息融合技术研究；轨迹跟踪技术研究。近年来，机器人编队控制已经成为了多移动机器人研究的一项关键技术。多机器人编队控制比单机器人控制具有更强的优越性，如鲁棒性、智能性、高性能、柔性等。这些优点使得它在大范围搜索营救，监视，绘制环境地图，远距离地形空间探索，扫雷，以及卫星和无人机的控制等方面得到广泛应用。编队控制是指多个机器人在到达目的地的过程中，保持某种队形同时又要适应环境约束(例如存在障碍物或者空间的物理限制) 的控制技术51。多机器人研究中的主要问题是机器人间的协调和协作，通常协调是为

40、了解决机器人之间的冲突和矛盾，而协作指机器人通过一种机制合作完成一项任务。 对于自主移动机器人编队问题来说，解决冲突主要就是使机器人避免和障碍物以及机器人之间发生碰撞；合作就是保持队形。广义上，机器人编队研究可以分为两类。第一类是集中式控制，它通过一个集中控制单元来监督整组机器人并分别命令每个机器人的运动。第二类是分布式控制，每个机器人利用局部信息自主运动。本质上，目前多移动机器人编队方法主要有以下三种：领导跟随法（leader-following）、基于行为法(behavior-based)和虚结构法(virtual-structure)。文献5152对这三种方法做了详细介绍并列举了相关参考

41、文献。其中，虚结构法利用集中式控制器，而基于行为法和领导跟随法通常使用分布式控制器。以上三种方法都可以控制机器人以一定队形运动，但在复杂未知环境中，却存在一定缺陷。领导跟随法在静态环境中可以获得比较准确、稳定的队形，但对动态环境的适应能力不强，机器人之间的避碰等问题没有得到很好的解决。而基于行为的编队方法对环境的适应能力较强，但保持队形上存在一定缺陷。1.3 本文内容与结构 本文的主要内容是机器人路径规划方法和多机器人编队控制的研究，利用Player/Stage建立服务器端多机器人仿真环境，在Eclipse下利用Java编写客户端控制算法程序，通过TCP Socket进行通信，控制服务器端仿真

42、机器人。本文共分为6章，具体内容包括：第1章：绪论，介绍了本课题研究领域的背景及意义、国内外研究现状，并安排论文的结构。第2章：移动机器人路径规划理论及算法，介绍了几种常用的移动机器人路径规划理论及算法，在此基础上提出一种基于模糊逻辑的行为融合路径规划方法。第3章：多机器人编队问题研究，介绍了多机器人编队相关理论及算法，提出一种基于观察者的编队方法。第 4 章：开源机器人项目Player/Stage，介绍一种新的开源机器人仿真项目Player/Stage。第 5 章：基于观察者的机器人编队仿真，在Player/Stage机器人仿真工具下构建仿真环境，并对所提出的编队方法进行仿真实验。第6章：工

43、作总结和展望，在这一章节中，对全文作了总结，并指出自己所作的工作和创新点，以及需要进一步改进的地方。第2章 移动机器人路径规划理论及算法2.1 路径规划问题概述路径规划是自主式移动机器人导航的基本环节之一。它的任务是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。根据机器人对环境信息了解的程度不同，路径规划可分为两种类型: （1）环境信息完全已知的离线全局路径规划；（2）环境信息完全未知或部分未知，通过传感器对机器人的工作环境进行探测，以获取障碍物位置、形状和尺寸等信息的在线局部路径规划。目前，关于环境信息完全已知的全局路径规划方法已经得到了很好的发展，由于它是一种离线

44、静态规划方法，因此通常可以得到最优路径。这类方法主要有：可视图法(V-Graph)、自由空间法(Free Space Approach)以及栅格法(Grids)。但当移动机器人在环境信息完全未知或局部未知的环境下工作时，就无法使用这些离线方法了。因此，需要使用基于传感器信息的局部路径规划方法。这类方法通常有：势场法（Potential Field）41、VFH42、D*法43等。局部路径规划利用传感器提供的信息来进行规划，这些常用传感器包括有:声呐、超声波传感器、激光测距仪和视觉传感器等。2.2 常用路径规划算法2.2.1 模糊逻辑法基于实时传感信息的模糊逻辑算法参考人的驾驶经验，通过查规则表

45、得到规划信息，实现局部路径规划。该方法克服了势场法易产生的局部极小问题，适用于时变未知环境下的路径规划，实时性较好。模糊逻辑控制是以模糊集合论、模糊逻辑、模糊语言变量以及模糊推理为基础的一种非线性的计算机数字控制技术。模糊逻辑控制系统具有这样的特点：它获取不精确的数据，处理它，然后得到精确的数据结果；因此，可以作为一种解决环境信息不确定性问题的合适工具。2.2.1.1 模糊逻辑基础概念在人们的思维中，有许多没有明确外延的概念，这类概念就叫做模糊概念。模糊概念没有明确的外延，因而不能用普通集合来描述，只能用模糊集合来描述。1965年，Zadeh教授发表的开创性论文“Fuzzy Set”中，首次提

46、出模糊集合的基本概念和基本理论31。模糊命题是含有模糊概念或模糊性的陈述句，而研究模糊命题的逻辑就是模糊逻辑。语言变量用以表征那些十分复杂或定义很不完善而又无法用通常的精确术语进行描述的现象。一个语言变量可定义为一个五维数组 ( X，T(X)，U，G，M )。其中: X语言变量的名称；T（X）语言变量语言值名称的集合；U论域；G语法规则；M语义规则。例如，图2.1是以障碍物距离为论域的模糊语言变量五维数组的示意图。距离近中远211020.40.80.410.50.510.81论域U语义规则M语言变量X语言值T(X)图2.1 模糊语言变量五维数组示意图模糊推理是应用模糊关系表示模糊条件句，将推理

47、的判断过程转化为对隶属度的合成及演算过程。它是模糊决策的前提条件，更是模糊控制规则生成的依据。2.2.1.2模糊控制基本原理模糊控制的基本原理可由图2.2表示，它的核心部分为模糊控制器。模糊量化处理模糊推理去模糊化处理执行机构被控对象传感器模糊控制器输入变量精确控制量图2.2 模糊控制基本原理图由上图可以概括出模糊控制的四个基本步骤：（1）根据本次采样的系统输出值，计算所选择的系统输入变量；（2）将输入变量的精确值变为模糊量；（3）根据输入变量（模糊量）及模糊控制规则，按模糊推理合成规则计算控制量（模糊量）；（4）将上面得到的控制量（模糊量）进行去模糊化处理，计算出精确的控制量（精确值）。2.

48、2.2基于栅格法的自主机器人实时路径规划2.2.2.1环境的栅格模型栅格模型采用二维矩形栅格表示环境，每个矩形栅格有一个累计值CV值(CV值是各种传感器信自、融合后存在障碍的可能性)，表示此方位中存在障碍物的可信度，高的CV值表示存在障碍物的可能性高。传感器不断快速采样环境，存在障碍物的栅格将会不断地被检测到，导致高的CV值。如果是环境的干扰信息被传感器读入，很少能导致高的CV值。采用这种方式表示环境信息不仅能将环境信息存储在计算机中，更重要的是使用方便，使得问题的求解有较高的效率。2.2.2.2栅格大小的选取栅格大小的选取直接影响着路径规划算法的性能。栅格选得过小，环境分辨率高，但抗干扰能力

49、弱，环境信息存储量大，决策速度慢；栅格选得过大，抗干扰能力强，环境信息存储量小，决策速度快，但分辨率下降，在密集障碍物环境中发现路径的能力减弱。栅格大小的选取也与传感器的性能有关，如果传感器精度高而且速度快，栅格可以选得小些。2.2.2.3方向的选择在机器人前面开出一个以长度R为半径的半圆形假想窗口，称为活动窗口，环境坐标系中暂时属于活动窗口的栅格称为窗口栅格。窗口栅格是方向决策的主要依据。对于具有对称形状的机器人，窗口中心简单地选在机器人的几何中心。对于一般的矩形车体机器人，窗口中心定义在车体前方的1/2处。在活动窗口中，建立一个窗口坐标系，使栅格从环境坐标系中映象到窗口坐标系中。在活动窗口

50、中，分出k个角度为(180/k)的扇面，分别表示行驶方向，如图2.3所示。 每个个扇面的障碍密度可以由公式(2-1)获得： （2-1） 图2.3环境的栅格表示和活动窗口Ci，j表示坐标为(i，j)的活动栅格的确信度；Hk反映出在扇面K中的障碍密集程度，即对扇面内的所有栅格的CV值求和。把有一定数量的几个连续的扇面而且每个扇面的障碍密度Hk低于一个阀值的区域称为侯选扇区。侯选扇区为移动机器人行驶的安全区域，通常存在有几个侯选扇区，在这个情况下，选取最利于到达目标的侯选扇区作为行驶方向。2.2.2.4 环境信息的优化随着机器人的移动，传感器不断对环境采样，环境信息存储量会越来越大，这不仅会造成存储

51、器容量不足，而且对环境信息的处理时间会越来越长，这将不能满足实时性的要求，因此，必须对环境信息进行优化。我们发现，随着机器人的移动，在移动机器人后面一定距离的信息利用率是很低的，这部分信息如果被删除，不会对决策产生大的影响。可以利用以下策略删除此类环境信息: 1从环境坐标系取出一栅格； 2将其映像到窗口坐标系中； 3如果此栅格落后与机器人，且与窗口中心的距离大于一定值，则从环境坐标系中删除此栅格。通过这样的处理，使得所存储的环境信息不至于随着移动机器人的移动而无限增大，减少了处理时间，工作空间不再受到限制。2.2.3 人工势场法人工势场法41是将机器人在周围环境中的运动，设计成在一种势场中运动

52、，是对机器人运行环境的一种抽象描述，机器人在场中具有一定的抽象势能，势场的源有两类；斥力极和引力极。机器人不希望进入的区域和障碍物属于斥力极；目标及机器人系统建议通过的区域为引力极。在极的周围由一定的算法产生相应的势，在任何一点的势为两极在该点产生的势之和，该势的负梯度称为有势力。势场的建立主要用于动态避障，此时的引力极是局部环境中的中间目标斥力极则是局部环境中的障碍物。 建立势场的方法由实际需要而定。O. K Ratb提出一种只与系统位置有关的建立方法。对于目标引力极，定义抽象力为以该目标为参考位置的比例控制；对于斥力极，建立等势线与障碍物边缘形状相似的斥力场。这种方法的主要困难在于，一般障

53、碍物的形状不很规则，物体边缘曲线方程难以建立，更为严重的是这种方法产生局部极点即零势点。所有障碍物与目标在这些点上形成的抽象力之和为零，系统在这些点上受到零控制力而停止，以至没有到达目标。为消除上述不利因素，可以设法将速度因子引入到势场，建立位置速度相关势场，克服极点，提高系统的稳定性。2.2.4 VFH方法VFH+方法54是一种用于机器人实时路径规划方法，它是对Borenstein 和Koren 在1991年开发的VFH（向量域直方图）法的一种改良版本。和VFH方法一样，该方法的输入是局部环境的栅格图，叫做直方图（histogram）。图2.4 VFH+方法的一个例子为了计算机器人新的运动方

54、向，VFH+方法利用了一个四级数据缩减过程。在前三级里，机器人当前位置周围信息由二维栅格图缩减为一维极线直方图。在第四级，该方法通过遮罩的极线直方图（the masked polar histogram）和代价函数（cost function）来选择一个最合适的方向。VFH+方法首先在遮罩的极线直方图中选择所有的开放区域（the openings），然后确定一组可能的候选方向。最后，利用代价函数来评价这些候选方向，选择代价最低的那个候选方向作为机器人新的运动方向。在图2.4所示的例子中，机器人会选择通过障碍物A、B的方向运动，然后向左转，而不是直接向左转，因为这样机器人会碰到障碍物A。VFH+

55、方法已经通过大量实际检验，并成功运用于一种导盲机器人GuideCane上。实验表明，该方法可以得到高效、安全、平滑的运动轨迹。关于该方法的详细介绍，可以参考文献54。2.3 基于模糊逻辑的行为融合路径规划方法2.3.1 方法概述目前，在未知环境中的自治机器人路径规划问题正成为机器人研究的热点之一。由于机器人周围环境信息具有不完整性、不可预知性、近似性以及缺少相关数据信息等特点，因此，未知环境中机器人路径规划存在的一个很严重的问题是具有很大的不确定性。而且，这种不确定性还存在于传感器测量数据以及计算过程中。为了使机器人能够在未知环境中实现自主导航，就需要给它更多智能以及增加它的自主性。基于行为的

56、控制结构是把复杂的任务分解成很多简单的可以并发执行的单元，每个单元有自己的感知器和执行器，这两者紧耦合在一起的，构成感知动作行为，多个行为相互松耦合构成层次模型。这种方法的主要优点在于每个行为的功能比较简单，对周围环境的变化能做出快速的响应，实时性好。但也存在两个缺点：（1）行为不易描述；（2）多个行为间的冲突和竞争难以协调。本文中的方法是将模糊逻辑控制和行为控制相结合，构建了一个基于模糊逻辑的行为控制路径规划器。利用模糊逻辑来构建这些基本行为的好处是它可以很容易的构建这些行为，并且可以通过一个行为合成过程来融合多个行为的输出结果。这样就能有效解决传统行为控制方法的两个缺点，使整个系统具有很好

57、的实时性和鲁棒性。同时，本系统根据需要还可以增加更多的行为，如紧急行为、跟墙行为等。2.3.2 移动机器人模型本文中，本文构建了一个半径为r =20厘米，装备了10个声纳传感器的圆形移动机器人，传感器分布如图2.5中所示。每个传感器si (i=0，9)的测量距离li（10cmli400cm），测量角度为22.5。这些传感器分为5组，用sgi (i=1，5)表示，如，sg1（s0，s1）。因此，机器人的总视角为225。每组传感器测得的障碍物到机器人中心的距离di(i=1，5)由下面的公式计算：di = r min（l2i-2 ，l2i-1）;(i = 1，5) (2-2)图2.5 机器人传感器分

58、布示意图同时，为了实现路径规划任务，本文做出如下假设：（1）机器人通过内部传感器总是知道自己当前位置坐标p(X ，Y)，并且目标点位置坐标pt (X t ，Y t)已知；（2）机器人通过装备的声纳传感器探测障碍物进行避障；（3）机器人的运动控制层按照制定的路径运动，不考虑其中的误差。2.3.3 坐标系和控制变量图2.6 坐标系和控制变量本文构建了两个坐标系，一个是环境世界坐标系XOY，另一个是机器人局部坐标系xoy ，如图2.6中所示。其中，机器人导向角，即X轴和y轴夹角；目标位置和机器人当前位置的连线与X轴夹角； 目标位置和机器人当前位置的连线与y轴夹角；障碍物和当前位置的连线与y轴夹角。2

59、.3.4 路径规划器结构移动机器人（MR）模糊行为监督器（FBS）避障行为（OA）目标导向（TS）模糊化规则库模糊推理模糊化规则库模糊推理去模糊处理行为融合去模糊处理模糊推理规则库模糊化d i W d t，d min , d og行为加权（BWS）行为融合（BFS）Vo ，oVt ，tV ，图2.7 基于模糊逻辑的行为控制路径规划器图2.7详细描述了该路径规划器（Path Planner）的结构。它主要由三部分组成：一个避障行为（Obstacle Avoidance），简记为OA；一个目标导向行为（Target Steering），简记为TS；以及一个模糊行为监督器（Fuzzy Behavio

60、r Supervisor），简记为FBS。这三部分都是基于模糊逻辑构建的。OA的功能是在不考虑目标位置的情况下进行避障，模糊输入变量为di，输出为Vo和o 。TS的功能是不考虑避障而只考虑到达目标位置，模糊输入变量为d t和，输出为Vt和t 。FBS的功能是融合OA和TS而得到无碰平滑的路径规划路线。FBS包括两个部分：行为加权部分（Behavior Weighting Section），简记为BWS，和行为融合部分（Behavior Fusion Section），简记为BFS。2.3.4.1避障行为（OA）避障行为是自治机器人的基本需要之一，它能帮助机器人在未知环境中自由运动而不发生碰撞。