多机器人协同覆盖技术研究

论文摘要

本论文来源于国家基础研究项目“异质多移动体的协同机制与重构技术基础研究”(A1420060159),属于其子任务“多机器人协同”的研究方向。本文主要研究了以“覆盖”为目标任务的多机器人体系结构、通信链路、地图表示、覆盖单元分解与分配以及覆盖效果评价等问题。目的在于探索多机器人协同协作进行覆盖任务的有效方法,构建适合覆盖任务的多机器人体系结构,通信模式以及地图知识表示方法,从而提高多机器人的协同协作水平,最终实现优化覆盖的目的。合理的体系结构是多机器人协同完成覆盖任务至关重要的基础,本文首先将自组重构策略引入分层式多机器人体系结构,形成自组分层式结构。系统由上而下分成三层:指挥层、协调层和执行层,采用“指令”通信模式和自适应重组的策略来实现协作任务。仿真实验表明自组分层式多机器人体系具有较高的鲁棒性和容错性,对任务和环境具有较好自适应性。通信是多机器人能实现有效协同协作的关键,同时也是自组分层式系统的最基本要求。针对实际覆盖任务中多机器人通信可能中断的情况下,提出CAM策略、CSM策略和SSS策略三种机器人按需主动建立通信链路的方法来保障系统的正常运行。机器人覆盖离不开环境知识,环境知识的表示方法即地图表示方法对已知环境中的多机器人覆盖尤其重要。因此,论文针对多机器人覆盖提出了4维环境地图的地图表示方法。空间点的4维坐标由3维空间坐标和1维环境特征值构成。3维空间坐标由机器人的测距传感器观测获得,同时利用多传感器信息获得该点的1维环境特征值。观测获得环境中许多空间点的4维坐标数据,并采用完全二叉树结构进行存储后,就获得该区域的4维环境地图。4维环境地图通过Krige法进行插值可生成栅格地图、利用高程变异算子可生成单元分解地图以及通过二叉树查找可生成拓扑地图。这些地图,特别是单元分解地图,都是许多研究者热衷于研究的机器人覆盖地图。在4维环境地图的基础上,研究了变长切线的单元分解方法。变长切线法通过“切线扫掠”目标区域,按一定规则选取由切线与障碍区产生的切点或交点作为关键点来进行单元分解。而在4维环境地图中,可以通过简单的循环二叉树查找来获得这些关键点的坐标值。与目前公认较优的Boustrophedon单元分解法相比,变长切线法单元分解不仅算法更为简单而且分解出的单元数目大大减少。这大大降低多机器人覆盖单元分配的复杂度,使系统可以用较小的计算量来获得较优的分配与规划。在自组分层式系统中,针对单元数量与机器人数量的不同关系,分n≈m、n》m和n《m3种情况分别分析讨论了基于近似矩形化单元面积估计的单元分配策略。对模拟环境进行了不同数量的多机器人协同覆盖仿真测试,各种情况下的多机器人系统均能成功实现对目标区域的覆盖。而后,尝试研究了多机器人在未知环境下的覆盖策略。在基于Morse理论利用测距传感器获得环境关键点的基础上,提出切线覆盖和波纹覆盖2种未知环境的覆盖方法。由于机器人进行测距等观测的同时,实际也完成了4维环境地图的建图,所以这类覆盖方法又称为同时覆盖与建图。最后,为分析评价机器人对目标区域的覆盖效果,利用甘特图来描述多机器人系统覆盖过程。并研究了覆盖率、时耗比、能耗比以及有效路径比等定量分析覆盖效果的评价因子。并特别针对多机器人协同覆盖,提出覆盖协同指数CCI这一综合评价因子。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题来源与意义
• 1.2 国内外研究现状分析
• 1.2.1 覆盖的分类
• 1.2.2 多机器人覆盖技术研究现状
• 1.2.3 多机器人覆盖研究的重点和趋势
• 1.3 本论文的研究内容
• 1.4 本论文的组织结构
• 第二章 自组分层式体系结构
• 2.1 基本假设与定义
• 2.2 分层体系结构
• 2.2.1 指挥层
• 2.2.2 协调层
• 2.2.3 执行层
• 2.3 系统通信模式
• 2.4 自组重构算法
• 2.5 仿真实验测试
• 2.6 本章小结
• 第三章 主动通信链路
• 3.1 问题描述
• 3.2 模型假设与定义
• 3.2.1 基本假设
• 3.2.2 连通树与连通前沿
• 3.2.3 空间坐标与通信距离
• 3.2.4 通信链
• 3.3 主动通信链路建立策略
• 3.3.1 CAM策略
• 3.3.2 CSM策略
• 3.3.3 SSS策略
• 3.4 仿真实验
• 3.4.1 CAM算法仿真
• 3.4.2 CSM算法仿真
• 3.4.3 SSS算法仿真
• 3.5 算法效果分析
• 3.5.1 3种算法效果比较
• 3.5.2 CAM算法优化
• 3.5.3 SSS算法改进
• 3.6 本章小结
• 第四章 4维环境地图
• 4.1 4维环境地图的概念
• 4.2 空间属性与特征属性的获取
• 4.2.1 空间属性获取
• 4.2.2 环境特征属性获取
• 4.3 环境地图创建
• 4.3.1 采样式建图
• 4.3.2 地图的存储
• 4.4 地图转化
• 4.4.1 地图的栅格化
• 4.4.2 地图的单元分解
• 4.4.3 地图的拓扑化
• 4.5 本章小结
• 第五章 基于4维环境地图的多机器人覆盖
• 5.1 基本定义
• 5.2 单元分解
• 5.2.1 变长切线法
• 5.2.2 4维环境地图中变长切线法单元分解的实现
• 5.2.3 变长切线法分解效果
• 5.3 任务分配
• 5.3.1 n≈m的分配
• >m的分配'>5.3.2 n>>m的分配
• 5.3.3 n<
• 5.4 路径规划
• 5.4.1 单元内的路径规划
• 5.4.2 单元之间的路径规划
• 5.5 仿真实验与测试
• 5.5.1 2个机器人的覆盖测试
• 5.5.2 4个机器人的覆盖测试
• 5.5.3 8个机器人的覆盖测试
• 5.6 本章小结
• 第六章 未知环境的多机器人覆盖
• 6.1 关键点的获取
• 6.2 切线法SCAM
• 6.3 波纹SCAM
• 6.4 仿真实验与测试
• 6.4.1 切线法SCAM测试
• 6.4.2 同条件RekleitisⅠ方法测试
• 6.5 本章小结
• 第七章 多机器人覆盖效果评价
• 7.1 甘特图
• 7.2 覆盖率
• 7.3 覆盖时耗比
• 7.3.1 标准耗时
• 7.3.2 时耗比
• 7.4 覆盖能耗比
• 7.4.1 标准耗能
• 7.4.2 能耗比
• 7.5 有效路径率
• 7.6 覆盖协同指数
• 7.7 本章小结
• 第八章 总结与展望
• 8.1 本论文工作总结
• 8.2 进一步工作的展望
• 参考文献
• 致谢
• 攻读博士学位期间主要研究成果