【毕业学位论文】多机器人协同覆盖技术研究-计算机应用技术博士论文

博士学位论文 多机器人协同覆盖技术研究 作者姓名 崔益安 学科专业 计算机应用技术 学院 (系、所 ) 信息科学与工程学院 指导教师 蔡自兴 教授 中 南 大 学 二八年 九 月 分类号 密级 _ 博士学位论文 多机器人协同覆盖技术研究 on on 者姓名 崔益安 学科专业 计算机应用技术 学院 (系、所 ) 信息科学与工程学院 指导教师 蔡自兴 教授 论文答辩日期 _ 答辩委员会主席 _ 中 南 大 学 二 八年九月 要 本论文来源于国家基础研究项目 “异质多移动体的协同机制与重构技术基础研究” （ ，属于其子任务“多机器人协同”的研究方向。本文主要研究了以“覆 盖”为目标任务的多机器人体系结构、通信链路、地图表示、 覆盖单元分解与分配以及覆盖效果评价等问题。目的在于探索多机器人协同协作进行覆盖任务的有效方法，构建适合覆盖任务的多机器人体系结构， 通信模式以及地图知识表示方法， 从而提高多机器人的协同协作水平， 最终实现优化覆盖的目的。 合理的体系结构是多机器人协同完成 覆盖任务至关重要的基础，本文首先将自组重构策略引入分层式多机器人体系结构， 形成自组分层式结构。系统由上而下分成三层：指挥层、协调层和执行层，采用“指令”通信模式和自适应重组的策略来实现 协作任务。仿真实验表明自组分层式多机器人体系具有较高的鲁棒性和容错性， 对任务和环境具有较好自适应性。通信是多机器人能实现有效协同协作的关键，同时也是自组分层式系统的最基本要求。 针对实际覆盖任务中多机器人通信可能中断的情况下，提出 略、 略和 略三种机器人按需主动建立通信链路的 方法来保障系统的正常运行。 机器人覆盖离不开环境知识， 环境知识的表示方法即地图表示方法对已知环境中的多机器人覆盖尤其重要。因此，论文针对多机器人覆盖提出了 4 维环境地图的地图表示方法。 空间点的 4 维坐标由 3 维空间坐标和 1 维环境特征值构成。 3 维空间坐标由机器人的测距传感器观测获得，同时利用多传感器信息获得该点的 1 维环境特征值。观测获得环境中许多空间点的 4 维坐标数据， 并采用完全二叉树结构进行存储后，就获得该区域的 4 维环境地图。 4 维环境地图通过 利用高程变异算子可生成单元分解地图以及通过二叉树查找可生成拓扑地图。 这些地图，特别是单元分解地图，都是许多研究者热衷于研究的机器人覆盖地图。 在 4 维环境地图的基础上，研究了变长切线的单元分解方法。变长切线法通过“切线扫掠”目标区域 ，按一定规则选取由切线与障碍区产生的切点或交点作为关键点来进行单元分解。 而在 4 维环境地图中，可以通过简单的循环二叉树查找 来获得这些关键点的坐标值。与目前公认较优的 元分解法相比，变长切线法单元分解不仅算法更为简单而且分解出的单元数目大大减少。 这大大降低多 使系统可以用较小的计算量来获得较优的分配与规划。在自组分层式系统中， 针对单元数量与机器人数量的不同关系，分 种情况分别分析讨论了基于近似矩形化单元面积估计的单元分配策略。 对模拟环境进行了不同数量的多机器人协同覆盖仿真测试， 各种情况下的多机器人系统均能成功实现对目标区域的覆盖。而后，尝试研究了多机器人在未知环境下的覆盖策略。 在基于 论利用测距传感器获得环境关键点的基础上，提出切线覆盖和波纹覆盖 2 种未知环境的覆盖方法。由于机器人进行测距等观测的同时，实际也完成了 4 维环境地图的建图，所以这类覆盖方法又称为同时覆盖与建图。 最后，为分析评价机器人对目标区域 的覆盖效果，利用甘特图来描述多机器人系统覆盖过程。并研究了覆盖率 、时耗比、能耗比以及有效路径比等定量分析覆盖效果的评价因子。 并特别针对多机器人协同覆盖，提出覆盖协同指数 关键词 多机器人，体系结构，环境地图，单元分解，协同覆盖 he by to of on of of on in of of at is of In a on of a of up to to it is to is in is In to as SS of in of It is to -D is in 4-D -D -D of -D be by s -D of be by at -D of in as a a 4-D is a -D by by in by is -D to of or as to by a -D be by is as an of of In on by nm, n? m n= m, a in of in to by On -D as of At in to of in is of as , to CI is 第一章 绪 论.内外研究现状分析 . 覆盖的分类 . 多机器人覆盖技术研究现状 . 多机器人覆盖研究的重点和趋势 .论文的研究内容 .论文的组织结构 .二章 自组分层式体系结构.本假设与定义 .层体系结构 . 指挥层 . 协调层 . 执行层 .统通信模式 .组重构算法 .真实验测试 .章小结 .三章 主动通信链路.题描述 .型假设与定义 . 基本假设 . 连通树与连通前沿 . 空间坐标与通信距离 . 通信链 .动通信链路建立策略 . . . .真实验 . . . 3种算法效果比较. . .章小结 .四章 4维环境地图 .维环境地图的概念.间属性与特征属性的获取 . 空间属性获取 . 环境特征属性获取 .境地图创建 . 采样式建图 . 地图的存储 .图转化 . 地图的栅格化 . 地图的单元分解 . 地图的拓扑化 .章小结 .五章 基于4维环境地图的多机器人覆盖.本定义 .元分解 . 变长切线法 . 4维环境地图中变长切线法单元分解的实现. 变长切线法分解效果 .务分配 . 的分配 . 的分配. 的分配.径规划 . 单元内的路径规划 . 单元之间的路径规划 .真实验与测试 . 2个机器人的覆盖测试.4个机器人的覆盖测试. 8个机器人的覆盖测试.章小结 .六章 未知环境的多机器人覆盖.键点的获取 .线法.纹.真实验与测试 . 切线法. 同条件方法测试 .章小结 .七章 多机器人覆盖效果评价.特图 .盖率 .盖时耗比 . 标准耗时 . 时耗比 .盖能耗比 . 标准耗能 . 能耗比 .效路径率 .盖协同指数 .章小结 .八章 总结与展望.论文工作总结 .一步工作的展望 . 考 文 献.致 谢.3 攻读博士学位期间主要研究成果.士学位论文 第一章 绪论 1第一章 绪 论 虽然 “机器人 ”一词的提出还只是出现于上个世纪，但人类对于机器人研究的尝试和探索可以追溯到几千年前。人类希望制造一种像人一样的机器，以便代替人类完成各种工作。早在西周时期，我国的能工巧匠偃师就研制出了能歌善舞的伶人。春秋后期，鲁班制造的木鸟，能在空中飞行 “三日不下 ”，令人叹为观止。随着计算机和自动化控制技术的发 展，单机器人已经从当初的 “可编程示教再现型机器人 ”、 “知觉判断机器人 ”发展成 “智能机器人 ”。这些机器人在越来越多的领域发挥它们的作用。 但随着人类在各个领域的不断研究探索，对机器人也提出了更高的要求。其中一个比较突出的就是多机器人协同工作的要求。20世纪80年代开始，协同工作的多机器人系统成为一个比较热门的研究课题 ,随着应用领域的不断拓展,尤其是水下、空间、危险环境探索、服务及教育领 域等场合的应用需求,促使多移动机器人领域的研究课题逐渐深入和广泛1。 日本对多机器人系统的研究开展得比较早，著名的研究有 和。美国学者 K。 图1 理论和仿真研究外，也出现了实验系统研究的项目。如 ，演示了基于多机器人系统的群集、搜寻等群体协作行为。 美国国防部高级研究计划署（ 支持下开展地面无人车辆系统 研究6。其目标是为美国军队开发出一批可以投入战场使用的无人驾驶侦察车辆，目前已开发出 。该研究小组对基于反应控制的 结构化及危险环境下的协同工作做了深入研究，并在多移动机器博士学位论文 第一章 绪论 2人导航、避障、编队行进、搜寻及任务指派等 方面取得一定的成果。卡耐基，他的研究主要集中于目标的跟踪与检测。此外，欧盟专门设立了一个进行多机器人系统研究的 （旨在研究多机器人在开放的环境下协调工作而尽可能少的用到中心控制。 我国多机器人系统的研究相对于国外起步 较晚，目前已逐渐引起人们的重视。中国科学院自动化研究所针对多机器人系统协调协作开展研究工作，建立了一个多微小型仿生机器鱼平台9。通过开展多机器鱼协调游动的水动力学模型研究、多机器鱼协调运动和队形控制等一系列技术研究，为水下多机器人群体协作提供必要的理论和技术基础。 上海交通大学的自主机器人研究小组针对以团队整体绩效为目标的多机器人系统10， 研究了适应性群体行为产生与发展的机理和快速的学习算法，并结合典型的群体任务开展了实验研究。哈尔滨工业大学、东北大学等也开发出了各种形式的群体机器人系统。 虽然国内外对多机器人系统的研究已取得了一定的进展，但总体上来看，基本上还处于起步阶段。与单机器人相比，实用性尚有很大的差距，需要解决的问题还很多。 如何使机器人个体之间相互通信和相互作用； 如何在各机器人间表达、描述问题，分解和分配任务；如何保证机器人在行动中的行为协调一致；机器人彼此之间如何识别和解决冲突等等。 可以说多移动自主机器人系统仍是一个较新的领域，甚至于在这个领域内的任何研究课题都是不够成熟的，需要人们投入更多的精力，也需要更多的人参加进来。 题来源与意义 本论文课题研究主要来源于国家基础研究项目 “异质多移动体的协同机制与重构技术基础研究 ”（ ，部分内容也得到国家自然科学基金重点项目 “未知环境中移动机器人导航控 制的理论与方法研究 ”(60234030)的资助。论文针对 “覆盖 ”这一任务目标，着重研究多移动机器人协同协作的体系结构、通信链路构建、环境地图的知识表示等问题，在此基础上研究了多机器人协同覆盖的算法以及覆盖效果的评价。目的在于探索针对覆盖任务的协同协作机制与方法，提高对目标区域覆盖的完全性，并降低完成覆盖的系统消耗与硬件要求，从而提高多机器人的覆盖效率。 多机器人系统许多鲜明的优点，其应用范围非常广泛。在农业、工业、国防、空间开发等几乎所有与人类生存发展息息相关 的领域均大有用武之地。正是如此，世间各国纷纷投入对多机器人系统的研究。由于多机器人系统的研究牵涉到博士学位论文 第一章 绪论 3自动控制、计算机科学、电子技术、人工智能等多个学科领域。无论是基础理论，还是方法技术都相对较为复杂。为便于问题的描述与讨论，一般都会针对具体的目标任务或事例来进行探索和研究，如队形保持11、大件物体搬运12等。因此，本论文课题针对多机器人覆盖这一任务目标开展多机器人相关问题的研究。 相对多机器人其他方面的研究而言，多机器人覆盖的研究成果很少，且主要集中在国外，国内较少见。多机器人覆盖是指多个机器人协作、快速高效地遍历一个含障区域内的全部自由空间。覆盖具有重要的现实意义，其潜在实际应用非常广泛，从陆地到海洋、从农业到工业、从家政服务到医疗诊治、从资源勘察到星球探索、从军事侦察到搜寻救助都有应用前景。具体包括： 服务保障方面，包括室内室外清扫、铲除积雪、修剪草坪、清理油污。如文献13、14分别讨论了机器人在家庭和超级市场清扫垃圾的问题。 工业方面，汽车、船体的喷漆作业。如 . 5。 军事方面，布雷扫雷、对战区情况侦察等。 J. 6， A. 17研究了多机器人基于通信的联合侦察。 安全保卫方面，对敏感设施或区域的安全监控、自然或人为灾难后的人道主义搜救。 8，文献19提出了一种新颖的多机器人搜救策略， 文献20研究矿井灾难后机器人覆盖搜救中的定位问题。 医疗方面，文献 21对利用微型机器人为病灶 区涂抹药物的算法进行了初步研究，文献22则考虑覆盖算法在外科手术中处理骨骼关节的表面覆盖问题。 矿产资源方面，陆地、海底的地形测绘、地球物理勘探数据采集等，如文献23采用水下机器人覆盖海底来进行海底的地形测绘。 此外，还有许多文献提到覆盖在农业、林业方面的应用，如可以实施农林业的播种、耕作与收割24,25。 针对多机器人覆盖的研究， 涵盖了多机器人体系结构、 环境知识表示与交流、多机器人协商协作、多机器人覆盖算法及效果评价等几个方面的内容。这些内容也是近年来多机器人系统研究的重点和难点。 可以把覆盖研究看作是多机器人系统研究热点问题的集中平台，相关问题的解决具有普遍的实用价值。 正是由于应用需求仍然对多机器人协作理论的研究方向起决定作用26，因此各国已经竟相开展多机器人探索与覆盖方面的研究。 而我国在这方面的研究相对比较少，积极开展这一新兴领域的研究具有相当深远的战略意义。 博士学位论文 第一章 绪论 内外研究现状分析 D. W. 概念27， 但未对覆盖问题进行严格的定义。之后许多研究者在研究覆盖问题时，从不同的角度对覆盖进行过许多定义。如 . 为传感器、执行器或机器人进行路径规划，使之可以到达一环境中的每一点 ”28。 . 机器人或工具必须遍访工作环境中所有可以到达的表面 ”29。 而 . 是为了侦测目标而在环境中布置传感器的问题 ”30，并把多机器人覆盖的问题定义为 “使机器人团队的传感器所覆盖的区域最大化问题 ”31。 在已知环境中遍访所有位置，并实施某项任务 ”32。 . “利用传感器信息在未知环境中让检测器或执行器遍历所有的点的路径规划问题 ”33。4认为覆盖必须满足 “覆盖路径尽可能短，重复路径应尽可能避免 ”，还把覆盖问题简化成 2个子问题 “寻找能填充简单区域的运动方式 ”和 “寻找一条连接各填充简单区域过程的可靠的途径来保证全区域覆盖 ”。 这些定义虽然基本描述了机器人覆盖的含义， 但都是出于研究者自己感兴趣的或便于问题描述的角度，不够全面、缺乏普遍性。文献 35提出较严格的、完整的覆盖的定义： 利用移动机器人或固定传感器在物理接触或传感器感知范围内遍历目标区域， 并尽可能地满足时间短、 重复路径少和未遍历区域小的优化目标。该定义明确了覆盖的主体为移动机器人或固定传感器， 客体为目标区域内的每一个可到达点，方式为物理接触或传感器感知，优化目标为同时满足时间最短、重复路径最少、未遍历区域最小中的一个或多个。 盖的分类 早期的覆盖研究主要考虑单个机器人的情况，如 6讨论了单个机器人采用基于栅格算法对目标区域进行覆盖， 7研究基于生成树的单机器人覆盖算法。国内也有祖莉38、王俭39等对单个机器人的覆盖进行了研究。而 0采用单个机器人与环境中固定通讯节点配合实现目标区域探索与覆盖。 . 0和 . O41则采用固定通讯节点作为路标来引导多机器人实现覆盖。当然也有纯粹多个机器人覆盖的研究，如文献42、43等。 、栅栏式覆盖（ 扫掠式覆盖（ 27。地毯式覆盖让机器人静态的布满整个目标区域；栅栏式覆盖利用多机器人排列成一道 “栅栏 ”，移动目标体在试图通过 “栅栏 ”时就被检测发现；扫掠式覆盖由机器人利用合适的路径规划算法，博士学位论文 第一章 绪论 5遍扫整个目标区域。 图1毯式覆盖 图1栏式覆盖 图1掠式覆盖 0。动态覆盖通过机器人的运动，实现动态地 “覆盖 ”目标区域；而静态覆盖，类似地毯式覆盖，指机器人团队静态地散布在目标区域内，并使区域内每处地方都在机器人感知范围中。可以把静态覆盖看作是特殊的动态覆盖。 许多针对覆盖问题研究大多假设环境已知或部分已知， 如文献32、 44等，. 5,46，讨论未知环境下的覆盖问题，类似的研究还有文献24等。因此，从环境信息是否已知的角度可以将覆盖氛围已知环境覆盖和未知环境覆盖。 除 . 7中提到简单三维物件表面的覆盖问题外，目前绝大多数中覆盖问题的研究只考虑二维 （平面） 地形， 尚未涉及三维地形的覆盖。此外，也还有个别文献48、49考虑覆盖时间最短、覆盖面积最大或重复路径最小的覆盖算法。 博士学位论文 第一章 绪论 6综合各种分类方式的覆盖分类见表 1。 表1盖详细分类 覆盖主体 覆盖方式 覆盖形态 环境信息 覆盖地形 优化目标 单机器人 地毯式 动态 已知环境 二维地形 最短时间 单机器人、固定节点联合 栅栏式 静态 未知环境 三维地形 最大面积 多机器人、固定节点联合 扫掠式 部分已知环境 最小重复路径 多机器人 机器人覆盖技术研究现状 覆盖作为一种面积性的工作，多机器人覆盖具有明显的优越性。因此对多机器人覆盖的研究逐渐增多，取得了一定的研究成果，主要体现在多机器人覆盖路径规划算法上。不同的覆盖算法一般对通信和环境地图表示有不同的要求，下面就多机器人覆盖中的通信、地图表 示、覆盖算法和覆盖效果评价 4个方面的研究现状进行讨论。 机器人体系结构 多机器人体系结构是指系统各机器人间的拓扑结构关系，目前对多机器人体系结构的研究一般考虑主从式（集中式）和分布式两种模式。 主从式体系结构中，一般由某一功能相对强大的机器人担任 “领导 ”对其它成员进行集中控制。所有机器人传感器信息均传送给它集中分析处理后，对每个机器人作出具体的下一步动作规划。早期的多机器人系统大都如此，系统的协调性较好，但实时性、动态性较差，集中式的优点 在于理论背景清晰,实现起来较为直观,但是容错性、柔性和开放性较差。主控 机器的故障直接导致系统的崩溃,系统中机器的个数变化困难,无法用于非结构化、动态环境。 分布式结构则没有中央集权控制机构 ，各成员机器人具有高度自主自治能力、平等、自主地协同完成给定任务，与其它智能体相互通讯以协调各自行为。这种结构有较好的容错能力和可扩展性， 但对通讯要求较高， 多边协商效率较低，有时无法保证全局目标的实现。国外对分布式 体系结构研究的系统有许多。是由日本 等人提出的通过设计底层的通讯结构而把机器人、周边设备和计算机等连接起来的自治多机器人智能系统，这个系统的主要特点是系统的单个动作和合作动作的并存。 日本名古屋大学的 第一章 绪论 7被认为是对移动机器人团队协同工作研究的首次尝试。 系统中每个机器人可以自主地运动，没有全局的世界模型，整个系统没有集中控制，可以根据任务和环境动态重构系统的体系结构、可以具有学习和适应的群体智能，具有分布式的体系结构。