【毕业学位论文】移动机器人的全区域覆盖算法研究-计算机软件与理论

分类号 密级 U D C 编号 士学位论文 论 文 题 目 移动机器人的全区域覆盖算法研究 学 科 专 业 计算机软件与理论 研 究 生 姓 名 曾维彪 导师姓名及专业 技 术 职 务 蔡自兴教授 on 原 创 性 声 明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学 位或证书而使用过的材料。 与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 日期： 年 月 日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名： 导师签名： 日期： 年 月 日 本论文来源于国家自然科学基金支持的重点项目 “未知环境下移动机器人自主导航理论与方法的研究”(项目号：60234030)和国家基础研究项目“多移动体的协作技术研究”(项目号：20060159)。作为上述项目研究的一部分，本论文研究目标是针对未知静态区域，分别提出一种单、多机器人的全区域覆盖算法，使移动机器人可靠、高效的遍历区域，遍历过程中完成相应的任务。 根据研究目标，本论文开展了以下几个内容的研究: (1) 提出一种新的全区域覆盖算法法的改进。算法根据机器人位置的变化确定机器人行走方向， 当机器人沿障碍物边界行走时，如果机器人行走方向发生改变，则可检测到障碍物的关键点。可解决 法中要求机器人带有全方位传感器、仅能处理边界曲线光滑的障碍物以及不能有切线平行于障碍物边界的缺陷。 (2) 结合中南大学智能控制研究所自行研制的移动机器人过实验，验证了本文新的全区域覆盖算法的可行性和正确性，详细分析了实验结果。 (3) 针对单机器人进行全区域覆盖的一些缺陷，在算法的基础上,结合本文新的全区域覆盖算法，提出一种基于多机器人协作的全区域覆盖算法。 算法利用两探索机器人沿边界行走时是否改变机器人行走方向和两者是否直线可见两种 方式检测障碍物的关键点； 设计了两探索机器人沿边界行走时保持直线可见的行走规则以及两探索机器人直线可见被中断时， 如何恢复两者直线可见并保证仅环绕覆盖障碍物上下相邻区域的规则； 算法既可用于快速的环境探索又可用于高效的全区域覆盖。 (4) 本文提出的单、多机器人全区域覆盖算法中，都不需要证完全覆盖区域或引导机器人走向未覆盖区域，而是设计一种新的区域覆盖方式：根据一定规则依次覆盖所有障碍物的上下相邻单元， 当机器人找到凹关键点且左、右凸关键点集不存在其它关键点时，全区域覆盖成功，可解决 法和 算法不能处理同一切线上存在多个关键点的缺陷。 关键词 全区域覆盖，机器人行走方向，关键点，直线可见 in by 0234030 in by 1420060159. As a of to to to (1) We a we of to in we of on of of it of t to of (2) is by of in (3) To by by a we a is on of of of to of We to We to of is to of of to (4) a t to to go to we a in of in to no in is of a t of 第一章 绪论.题来源和研究意义.机覆盖策略.确单元分解法.似单元分解法.于模板的方法.于传感器的全区域覆盖.机器人覆盖.文章节的安排.第二章 一种新的全区域覆盖算法.种新的全区域覆盖算法.法思想.本概念.碍物类型.键点检测.形运动. .法实验.第三章 一种基于多机器人协作的全区域覆盖算法.机器人进行全区域覆盖的缺陷.算法简介.种基于多机器人协作的全区域覆盖算法.法思想.键点检测.探索机器人的行走规则.种情况的处理. 真结果与分析.第四章 总结与展望.文总结.一步研究方向.参考文献 . 60 致 谢 . 66 攻读学位期间主要研究成果.硕士学位论文 第一章 绪论 1第一章 绪论 机器人是一种自动化的机器，这种机器具备一些与人或生物相似的智能，如感知能力、规划能力、动作能力和协同能力，是一种具有高度灵活性的自动化机器。自 1962 年第一台机器人诞生以来，机器人有着突飞猛进的发展，机器人的诞生是二十世纪自动控制领域最有说服力的成就， 是二十世纪人类科学技术进步的重大发明成果。机器人在人们的日常生活中正起着不可替代的作用，国内外众多学者的已开展大量的研究1 机器人在工业、国防和科学技术中应用日益广泛，它能够在枯燥和危险的复杂非结构化环境下工作，可用于工业生产、行星探测、深海探矿、排雷除险、地质勘测、战场搜救、核能发电、家庭服务、娱乐生活等各个方面，机器人使用大大提高了人们的工作效率，改变了人们的生活方式，带来了巨大的经济和社会效益，有力地推动了有关学科和技术领域的发展。 路径规划是机器人一个重要研究内容。 常规的路径规划是指点到点的最优路径规划，其目标是寻找一条从起始点到目标点的无碰撞最优路径。全区域覆盖是指在某个区域中，按一定的评价标准，机器人或机器人的传感器能够遍历整个工作区域，在区域遍历过程中自主可靠地完成指定的操作任务。因此全区域覆盖的路径规划其目标是产生一条有效路径来遍历工作环境的每个可达区域。 两者的差别如图1(a)常规的路径规划 (b)全区域覆盖的路径规划 图 1种路径规划方法的比较6在现实生活中，全区域覆盖都有着广泛的应用，从陆地到海洋、从农业到工业、从资源勘察到星球探索、从军事侦察到搜寻救助都有着广阔应用前景。具体包括： 硕士学位论文 第一章 绪论 2服务保障方面，草坪修剪、清理油污、室内外清扫7。 工业方面，汽车、船体的喷漆作业。 安全保卫方面，对敏感设施或区域的安全监控。 矿产资源方面，陆地、海底的地形测绘、地球物理勘探数据采集。 军事方面，战场侦察、布雷扫雷8。 题来源和研究意义 本论文来源于国家自然科学基金重点项目 “未知环境下移动机器人自主导航理论与方法的研究”(项目号：60234030)和国家基础研究项目“多移动体的协作技术研究”(项目号：A 1420060159)。作为上 述项目研究的一部分，本论文研究目标是针对未知静态区域，分别提出一种单、多机器人的全区域覆盖算法，使移动机器人可靠、高效的遍历区域，遍历过程中完成相应的任务。 在现实生活中，如战场侦察、排雷、室内外清扫、修剪草坪、敏感设施或区域的安全监控等，全区域覆盖都有着广泛的应用，具有重要的研究意义。 内外研究现状 由于移动机器人的全区域覆盖在现实生活中具有广泛的应用，近年来，国内外许多学者进行了大量的研究49针对不同应用提出了一些方法，如随机覆盖策略、精确单元分解法、近似单元分解法、基于模板的方法、基于传感器的覆盖方法、多机器人覆盖等，各种方法都具有一定的适用场合和优缺点。 机覆盖策略 随机覆盖策略是指机器人无法直行时就随机转个角度继续前进， 该策略对机器人的感知和计算能力要求不高，无需定位传感器且算法简单。但不能保证完全覆盖整个区域，重复覆盖率高，效率很低。文献9中割草机器人采用随机覆盖策略进行工作，最终仍有5%的草坪被遗漏。1995年0。 此外1， 如果没有定位能力机器人的价钱仅是有定位能力机器人的1/5时，随机覆盖策略是一种更有效的方式。 在实际应用中如排雷，由于随机覆盖策略无法保证完全覆盖区域，一般应用较少。 硕士学位论文 第一章 绪论 确单元分解法 精确单元分解法可保证区域的完全覆盖， 是目前全区域覆盖算法中运用最广的方法之一。它以障碍物为边界，将空闲区域分解为一些互不重叠的单元，由于单元中不包含任何障碍物， 机器人可用简单的往返运动实现单元覆盖， 如图1用邻接图等表示单元的连接关系，其中结点表示单元，边表示单元之间的连接关系，区域的全覆盖就转变为从一个单元到另一个单元的运动规划。 图 1返运动12 1. 991 年 出 解法13。假设一条称为切线的直线，从左至右的扫过含有多边形障碍的封闭区域，切线与多边形障碍物的顶点相遇时，将空闲区域分解成一系列的不等边四边形单元,如图1图 1解法12 2. 时会产生过多的单元，从而有许多不必要的往返运动，如图11997年进行改进，提出了Bo 解硕士学位论文 第一章 绪论 4法12。用一条切线从左至右的扫过封闭区域，当切线的连通性发生改变时生成新的单元：当连通性增加时，旧单元结束，两个或多个新的单元生成；相反连通性减少时，多个旧单元结束，新单元生成，如图1少了重复覆盖，但作者没有详细叙说关键点的检测方法，只适合于已知环境。 图 1 比较12(a)连通性增加，两个新的单元生成 (b)连通性减少，一个新的单元生成 (c) 区域分解完成 图1解法123. um 对已知的多边形环境提出一种“um ”分解法14。其思想为覆盖路径中转弯次数越少，所需代价越小。理由是机器人转弯需要先减速，转弯，再加速，将耗费大量的时间，而从一个单元移动到另一个单元的代价远远低于转弯，通过给不同单元选择不同的覆盖方向，可以有效的降低算法所需的代价，如图1者没有在理论和实际上证明。 硕士学位论文 第一章 绪论 5图 1定不同的覆盖方向产生更少的转弯次数144. 化)分解法 )进行构建分解的 5，16。机器人执行一个直线轨迹后， 算法选择一条仅依赖当前环境(C)和机器人所在位置(P)的新轨迹，新轨迹的选择由一系列所有可能情况下都能保证机器人继续搜索的规则决定。算法的完全性通过创建一个有限状态机（证明，有限状态机（够描述只有在覆盖完成时才终止。解，一个切片通过机器人的自由空间，当切片改变其连通性或长度时，一个新的单元就形成了，如图1图 1化)分解法17 5. 解法的基础上提出 解法，适合基于传感器的全区域覆盖，在理论和实际上都取得了一定的成功18它基于1，62，机器人利用传感器 信息在线的寻找障碍物关键点22可通过构造不同的以适合机器人覆盖不同形状的环境。 硕士学位论文 第一章 绪论 6(a)基于 论寻找关键点 (b)切线的连通性在关键点处改变 图 1解法19 似单元分解法 5，26，基本思想是将目标区域分解成一系列的单元，与精确单元分解不同，它将区域看成一个单元，递归的细分区域为形状大小相同的四个小单元，直到满足需求，这种方法也叫四分树分解。当目标区域被递归的分解成一些更小的单元后， 将所有不包含障碍物的空闲单元建成连接图，通过对连接图的搜索，产生一条穿越所有空闲单元的路径。 空闲单元之间的大小和形状一致，所有空闲单元的总和近似于目标区域，机器人机身或传感器范围与空闲单元大小一致，当机器人走过一个单元，就完成该单元的覆盖，机器人按该路径行走就可以实现区域的全覆盖。 由于复杂图的搜索比较困难，有时候该路径即使存在也不能保证经常找到。 根据近似单元分解法，1993年7。算法初始时目标单元设为0，0周边单元设为1，1周边单元设为2，依此类推，直到所有空闲区域都予以赋值才终止，如图1过以下方式可产生一条覆盖路径：从起始点出发，选择周边单元中未覆盖且值最大的单元，如果有两个或更多相同条件的单元，则随机选择一个，直到目标点。 硕士学位论文 第一章 绪论 7(a)起点到目标点的波阵面扩散 (b)产生的覆盖路径 图 1规波阵面算法282001 年 出 法29，30，将目标区域递归的分解成一些单元，丢弃被障碍物占用的单元，空闲单元再细分成四个一样大小的子单元，子单元的大小与机器人机身或传感器范围相同，构建一棵包含所有空闲单元的生成树， 通过对生成树的访问而实现区域的全覆盖。 线和 种版本。在线的 法需要环境的先验知识，得到最优覆盖路径的时间需要O(N),其中线的器人通过自身的传感器检测障碍并获取环境的信息，并建立相应的生成树，得到最优覆盖路径的时间需要 O(N)且需要 O(N)的内存空间。 法不需要环境的先验知识，得到最优覆盖路径的时间需要O(N)且仅需O(1)的内存空间，如图1(a)目标区域的近似分解 (b)空闲单元的生成树 图 1法的近似单元分解28 硕士学位论文 第一章 绪论 于模板的方法 1997 年 e 提出一种基于模板的全区域覆盖算法31。该算法依靠于已覆盖区域的先前知识，预先定义的 5 种模板分别是：前)， 型转弯)，切换） ，路返回)，型交错转弯）,如图1据已覆盖区域所获取的先前信息，将当前环境信息与各个模板进行匹配；重复的预测新区域并执行区域覆盖，从而整个覆盖路径就转换成执行一系列不同的模板。为简化路径规划阶段，可预先扩大环境以致于将机器人看作一点，文献31中的仿真结果如图1该算法需要先前地图和记忆一些模板，很难处理动态环境，比如覆盖过程中突然出现某个障碍物。 （a）版 （b）版 （c）版 （d）版 硕士学位论文 第一章 绪论 9（e）版 图 1全覆盖路径6图 15 种模版6于传感器的全区域覆盖 基于传感器的全区域覆盖是指在未知环境中利用传感器的信息寻找一条路径，使机器人或机器人的传感器遍历所有区域并执行相应任务。用全方位传感器检测障碍物的关键点20，23， 采用器人通过循环运动实现空闲单元的覆盖，用 表示单元与关键点之间的联系32,33，保证区域的完全覆盖。不久 用 对算法进行了改进22，24，即在大范围的空闲区域中，探测距离 为小范围空闲区域，机器人根据图1(a)仅循环运动(b)结合 ，考虑宽和窄区域 图 1种基于传感器的全区域覆盖算法19硕士学位论文 第一章 绪论 机器人覆盖 在自然界中，许多低级生物体通过多个个体的协作而完成惊人的任务，近年来，由于多机器人具有容错性强、效率高、可降低信息的不确定性等优势，近年来，多机器人的全区域覆盖研究逐渐成为热点。 2004年提 出一种基于多机器人的全区域覆盖算法34。机器人之间只有相互直线可见时才能通信， 共享和更新信息， 在一定情况下可分组或联合，机器人角色分为探索机器人和覆盖机器人。 两台探索机器人以相同速度沿边界前进，当不能相互直线可见 (表明两者之间存在障碍物。当某关键点终止一个单元但又产生两个新的单元时，各个机器人分成两个小组，分别覆盖障碍物的上下单元，如果相遇则联合成一组 。采用器人通过简单的往返运动实现空闲单元的覆盖，用证区域的全覆盖，如图1由于个单元仅用两个关键点表示，算法对切线上存在多个关键点的情况无法处理；此外，往往有机器人覆盖最右端单元后再返回覆盖一个或几个较左端单元的情况，从而产生大量的重复覆盖。 图 1器人的两种角色34在自然界中，一些昆虫如蚂蚁通过特殊的信息素来进行通信与任务协调，受此启发，5机器人之间通过留下的特殊气味来通信，算法还假设留下的气味会逐渐挥发，在某个时候机器人能感应气味强度。机器人之间的关系是一种共享存储空间的分散式系统，利用近似单元分解法将环境建成连接图。该算法与深度优先搜索算法不同，在覆盖过程中即使有机器人出现故障或连接图发生增边或减边的变化，只要图仍然连接，其它机器人仍能保证区域的全覆盖。 第一章 绪论 11虫的启发提出了类似的算法40，41。 文献40中采用类似蚂蚁在走过的路径上留下信息素的办法让机器人在经过的地方留下标记， 其它机器人通过感知这些标记来避免重复覆盖。 改进单机器人覆盖算法，使其成为能应用于多机器人覆盖的算法42，43，以便增强机器人覆盖的鲁棒性和有效性，如图1提出不允许原路返回和允许原路返回的两种方法，只要单机器人的这两种算法也能保证完全覆盖。不允许原路返回的算法的最坏情况是 K(K2)台机器人完全覆盖区域的时间等同于单机器人尽管允许原路返回的算法中，机器人也许会访问相同单元两次，产生一定的重复覆盖，但其最坏情况K（K2）台机器人完全覆盖区域的时间仅是单机器人 法的一半。44。 出一种基于传感器的多机器人协同覆盖算法 16，限环境为方型区域，机器人为方型且仅使用触觉传感器。 提出的多机器人覆盖算法中45，不需要环境的全局地图也无需全球定位系统(其基本思想是机器人在 一定范围内感知到其它机器人时就相互排斥，从而使多个机器人尽量均匀的分散在环境中，提高覆盖的效率。算法没有规划覆盖路径，类似于随机覆盖策略。 文章节的安排 本论文研究目标是针对未知静态区域，分别提出一种单、多机器人的全区域覆盖算法，使移动机器人可靠、高效的遍历区域，遍历过程中完成相应的任务。文章主要内容是两种单、多机器人的全区域覆盖算法：一种新的全区域覆盖算法基于多机器人协作的全区域覆盖算法， 论文章节安排如下： 第一章简要介绍论文的课题来源和研究意义， 重点介绍了全区域覆盖的国内外研究现状。 第二章简要介绍针对出了一种新的全区域覆盖算法以细分析了实验结果。 第三章简要介绍算法，在算法的基础上，结合第二章新的全区域覆盖算法，提出一种基于多机器人协作的全区域覆盖算法。 第四章总结全文，对下一步的研究内容进行了分析与展望。 硕士学位论文 第二章 一种新的全区域覆盖算法 12第二章 一种新的全区域覆盖算法法的改进 在现实生活中，全区域覆盖都有着广泛的应用，从陆地到海洋、从农业到工业、从军事侦察到搜寻救助都有应用前景。具体包括：服务保障方面，如室内室外清扫、铲除积雪、修剪草坪、清理油污。工业方面，汽车、船体的喷漆作业。安全保卫方面，对敏感设施或区域的安全监控。矿产资源方面，陆地、海底的地形测绘、地球物理勘探数据采集等。 近年来，国内外的许多学者进行了大量的研究，针对不同应用提出了一些方法，如随机覆盖策略、精确单元分解法、近似单元分解法、基于模板的方法、基于传感器的全区域覆盖、 多机器人覆盖等， 各种方法都有其适应的场合和优缺点。 基于传感器的全区域覆盖是指在未知环境中利用传感器的信息寻找一条路径，使机器人或机器人传感器遍历所有空闲区域并执行相应任务。在众多学者提出的一些算法中，如4，尽管最早提出基于传感器的全区域覆盖算法，但没有讨论算法的实现细节。求机器人装载接触传感器且障碍物和环境为方型16。真正在理论和实际上都予以详细探讨的是 法19，6。 尽管仍然存在一定的限制。因此，在 法的基础上，本章提出一种新的全区域覆盖算法法简介 法的基本思想 机器人以循环运动覆盖空闲区域， 在覆盖过程中利用传感范围有限的全方位传感器检测区域中障碍物的关键点， 并用用来表示空闲单元与关键点的关系，随着覆盖过程的进行 也不断的更新，当完成所有空闲单元的覆盖时，全区域覆盖成功，算法流程如图2硕士学位论文 第二章 一种新的全区域覆盖算法 13N N Y Y N Y 图 2法流程图19 法的关键技术 由算法的基本思想可知， 循环运动、 基于面予以详细介绍。 1. 循环运动 对已知区域，机器人采用往返运动可实现区域覆盖，但对未知区域，往返运动可能遗漏关键点，如图2此，机器人运动轨迹由多个循环组成， 每个循环分为三个阶段： 前进阶段、 后退阶段、回归阶段，如图 2一个循环中机器人从循环起点 发，沿箭头所指路线行走一圈最后回到 一个循环结束，然后第二个循环开始，机器人从 为点避免重复覆盖，算法定机器人走到二个循环结束。如此往复，机器人的整个运动轨迹由多个循环组成。 执行循环运动 检测到关键点？ 查找 已覆盖所有单元？全区域覆盖成功 更新从 开始 执行前进和后退阶段 到达 回归阶段 循环完成 硕士学位论文 第二章 一种新的全区域覆盖算法 14图 2返运动可能错过关键点19图 2环运动192. 基于义 线函数 h 是一实值函数： ,一条切线 h 的原象，即 |() ,CS x CS h x = ,切线函数的梯度表示为 ()。 定义 h 是流形 M 上的一个光滑实值函数,点 p M ，若点 中选取局部坐标1( ,., ),nx x 有1( ) . ( ) 0,= =则 p为 ()f p 称为关键点值。若它的 阵2()x是非奇异的，则 果一个函数的所有关键点都是非蜕化的，则该函数是定义 障碍物边界曲线是一连续函数 : 的原象，即| () 0x m x= =， ()为的曲面法线。 度函数:用di(x)表示梯度函数，其定义如下： 00()| |ix c=| |(2定义 离函数:点到物体的最短距离，用 di(x)表示距离函数，其定义如下： () |(2上述两个定义中，根据可用传感范围为到 di(x)和di(x)的 值后，如果di(x)平行于h，则找到障碍物边界上的关键点CP=x - di(x)* di(x)，否则该点不是关键点，如图 2 2 硕士学位论文 第二章 一种新的全区域覆盖算法 15图2 di(x) 平行于 h19图 2 di(x)不平行于 h 3. 断是否已完成全区域覆盖，并引导机器人走向未覆盖单元。在 中，关键点为结点，单元为边，见图2(a)区域的 解 (b)区域的 图 2表示单元与关键点之间的关系19法的一些缺陷 1. 论研究流形上光滑函数的关键点与流形本身拓扑结构之间的关系，于法要求区域中障碍物边界曲线光滑，否则会出现退化关键点，即不是所有关键点都孤立。在管作者使用退化梯度来定义非光滑点的法线46，但仍然需要退化梯度为非空集。作者指出算法基于两个假设：没有切线与障碍物边界平行的情况，如图2于切线与障碍物边界平行的情况，理论上可以检测到退化关键点，但硕士学位论文 第二章 一种新的全区域覆盖算法 16基于不确定传感器的具体实现留给了将来的工作。 图 2线与障碍物边界平行192. 关键点数取决于切线方向，当改变切线方向时，同一切线上可能有多个关键点，如图2于同一切线上存在几个关键点的情况，算法无法处理。 图 2线方向的改变产生多个新的关键点193. 算法要求全方位传感器和圆形机器人 ，从而不需要考虑传感器的方向。当传感器仅能获取有限角度的数据时，传感器的方向就特别重要，因为只