（计算机应用技术专业论文）未知环境下多机器人协作地图构建问题研究.pdf

本文研究了复杂未知 粒子群优化算法进行全局 协作构建地图的方法。并 果表明该方法可以使机器 测效率。其次，针对动态 是基于卡尔曼滤波的轨迹 此算法在机动目标非线性 对比，实验结果表明，该 优于其他算法。 关键词：多机器人系统， 迹预测 a b s t r a c t i nt h i sp a p e r ，f i r s t l y ，m u l t i - r o b o tm a pb u i l d i n gp r o b l e mi nac o m p l e xa n du n k n o w n e n v i r o n m e n ti si n v e s t i g a t e d ，p r e s e n t sam a pb u i l d i n ga p p r o a c hb a s e do np a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mf o rg l o b a lo p t i m i z a t i o n ，a sw e l la sh i l b e r tc u r v eo nt h et a r g e t r e g i o nd e t e c t i o no fm u l t i r o b o tc o l l a b o r a t i v e e x p e r i m e n to fc o m p a r i n gw i t hss h a p e r a n d o me x p l o r i n ga l g o r i t h ms h o w st h a tt h i sm e t h o dw i l le n a b l et h er o b o tt of i n dt h e a p p r o x i m a t eo p t i m a lt a r g e ta r e a ，r e d u c et h ep r o b a b i l i t yo fd u p l i c a t ed e t e c t i o n ，a n d i m p r o v et h ee f f i c i e n c yo fd e t e c t i o n s e c o n d ，f o rd y n a m i ct a r g e to ft r a je c t o r yp r e d i c t i o n ， t h i sp a p e rd e s c r i b e st w ok i n d so ft r a j e c t o r yp r e d i c t i o na l g o r i t h m ，at r a j e c t o r yp r e d i c t i o n a l g o r i t h mb a s e do nk a l m a nf i l t e lo n ei st h em o n t ec a r l oa l g o r i t h mb a s e do nt r a j e c t o r y p r e d i c t i o n ，u s i n gt h i sm e t h o dt ob eg a u s s i a nd i s t r i b u t i o nt oa p p r o x i m a t el o c a t i o no ft h e p o s t e r i o rd i s t r i b u t i o no fs t a t ev a r i a b l e s a n dd i s c u s s e st h ea l g o r i t h mf o rm a n e u v e r i n g t a r g e tt u r n i n gm o v e m e n ti n t h en o n l i n e a rt r a j e c t o r yp r e d i c t i o np r o b l e m ，u n d e rt h e f l i c k e rn o i s e ，ac o m p a r i s o no ft h et w oe x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dd o e s n o tn e e dt or e p e a t s a m p l i n g ，i nf i l t e r i n ga c c u r a c ya n dc o m p u t i n gt i m e ，t h ei s a l s o s u p e r i o rt oo t h e ra l g o r i t h m s m ay i n g w e i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f l i uc h a n g a n k e yw o r d s ：m u l t i - r o b o ts y s t e m ，m a pc o n s t r u c t i o n ，p a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h m ，h i l b e r tc u r v ed e t e c t i o n ，t r a j e c t o r yp r e d i c t i o n 华北电力大学硕士学位论文 目录 摘要i a b s t r a c t i 第一章引言1 1 1 课题研究的背景及意义1 1 2 地图构建研究发展状况2 1 2 1 地图构建中的研究的问题2 1 2 2 未知环境下地图构建方法。3 1 3 本文研究的主要内容4 第二章多机器人地图构建中的环境信息及群体行为6 2 1 引言6 2 2 多机器人系统研究模型8 2 3 多机器人系统基于搜集的任务分配8 2 3 1 多机器人任务分配1 1 2 3 2 多机器人地图构建中搜索任务分配算法1 0 2 4 本章小结1 5 第三章在未知环境下多机器人协作地图构建1 6 3 1 引言16 3 2 基于粒子群优化算法及希尔伯特曲线的地图构建1 6 3 2 1 设置算法的环境16 3 2 2 粒子群优化算法及实现17 3 2 3 希尔伯特曲线搜索1 9 3 3 仿真实验及分析2 0 3 4 本章小结2 3 第四章动态目标的轨迹预测方法研究2 4 4 1 引言2 4 4 2 动态目标的轨迹预测方法2 4 4 2 1 基于卡尔曼滤波的轨迹预测2 4 4 2 2 基于蒙特卡罗算法的轨迹预测3 0 4 3 仿真结果与分析2 7 4 4 本章小结。2 8 第五章结论与展望2 9 参考文献31 致谢3 6 l i 1 1 课题研究的背景及意义 自2 0 世纪6 0 年代初第一台机器人问世以来，人类始终渴望制造一种像人一样 的机器人，以便将人丛繁重的、枯燥的、危险的活动中解脱出来。虽然当今机器人 的本领还十分有限，但它正在迅速发展，并开始对人类生产、生活的各方面产生越 来越大的影响，经过近半世纪的发展，机器人技术不但使工业生产的面貌发生了根 本性的变化。机器人学早期的研究主要集中在单体机器人的结构、控制和信息处理 等方面。这期间单体机器人的控制能力、鲁棒性、可靠性和效率都有了很大的提高 1 - 4 】。但是随着机器人结构、环境、任务等向复杂化方向的发展，人们也越来越希望 机器人能够完成一些更加复杂的任务，对机器人的要求也不断提高。为了提高系统 运行效率和适应更加复杂的任务需求，很容易想到利用多个机器人相互协调与合作 共同完成任务，多机器人系统应运而生。 起初多机器人系统只是单个机器人在数量上的简单扩展，随着研究的深入，如 何组织多个机器人构成系统、如何在多机器人系统中实现机器人之间的协调与合作 成为研究的重点。对于多机器人系统的研究目前集中在以下几个方面：多机器人觅 食、未知环境探测及地图构建、多机器人路径规划、编队控制、机器人足球赛等1 5 j 。 地图构建是近几年来机器人研究领域中发展起来的一个新的研究方向，受到了 研究人员的日益关注。机器人的一个重要工程应用领域就是空间和危险场合探测。 目前，许多工作是采用单个机器人进行环境信息的探测，其不足是：探测速度缓慢， 感知环境信息欠完整，而且系统的容错性和鲁棒性也很差。而利用多机器人协作进 行地图探测则提高了任务完成的效率与准确度【6 j 。很多情况下，作业空间的信息是 未知的，这样在安排机器人进入该环境时作业时，较强的信息获取以及自主决策能 力的是机器人系统顺利完成任务的保证，就需要机器人首先对其作业的环境进行有 效的探测，构建出环境的地图，进而展开更多的工作。机器人探测潜在的在该方向 的研究主要集中在机器人的自定位与感知环境两方面。 随着多机器人系统的研究的深入，多机器人之间的协调与协作和对环境的感知 成为多机器人研究中的两个重要方向，是体现多机器人系统优越性的重要方面。所 以未知环境中多机器人地图构建这个问题，对多机器人系统的研究是很有意义的 【7 - 8 l 。另一方面在地图构建过程中采用多机器人系统与单机器人系统相比有明显优 势：首先，多个机器人可以并行探索，因此探索一个区域的速度要比单机器人快； 其次，多个机器人可以增加信息冗余度，与单机器人系统比较，多机器人系统的容 错性和鲁棒性更强；再次，如果多机器人之间能够交换信息，那么多机器人系统定 1 华北电力大学硕士学位论文 位会更加有效1 9 1 。 1 2 地图构建研究发展状况 1 2 1 地图构建中的研究的问题 机器人建立地图的过程，实际上就是一个机器人根据传感器的感知对其活动环 境建模的过程。机器人的环境建模和自定位是紧密相关的。环境模型的准确性依赖 于定位精度，而定位的实现又离不开环境建模【1 0 j 。在完全未知环境中，机器人对环 境一无所知，不存在任何先验知识，包括环境大小、障碍物的位置、形状等等，因 此机器人创建地图的行为完全必须依赖于其传感器所获得的信息。目前地图创建的 研究主要包括以下几个方面： ( 1 ) 环境的表示方法 环境的表示方法应该能够方便机器人完成特定的任务，目前大致有三种地图表 示方法：栅格表示、几何信息表示和拓扑图表示。若采用栅格地图，则可以把探索 地图这一任务描述为确定每一个栅格是否存在障碍物；若采用几何信息则在探索过 程中将环境定义为面、角、边等的集合；而若采用拓扑图则是主要建立环境各元素 之间的关系。如何建立一种探索任务方式既能体现机器人对环境探索的效率，又能 体现出对环境元素的和信息的描述的精确程度这是个需要进一步研究的问题。 ( 2 ) 机器人地图创建中的导航问题 在机器人创建地图的过程中必然涉及到机器人的导航问题【1 ，包括自定位、运 动规划和避障。目前地图创建的一个主要难点是难以解决机器人自身精确定位的问 题，已有的研究中对这个问题的解决可分为两类：一类是利用自身携带的多种内部 传感器( 包括里程仪、罗盘、加速度计等等) ，通过多种传感信息的融合减小定位 误差，使用的融合算法多为基于卡尔曼滤波的方法，这类方法由于没有参考外部信 息，在长时间的漫游后误差的积累会比较大。另一类方法在依靠内部传感器估计自 身运动的同时，使用外部传感器( 如激光测距仪、视觉等等) 感知环境，对获得的 信息进行分析抽取环境特征并保存。但这种方法依赖于能够取得环境特征。 ( 3 ) 不确定信息的描述和处理方法 由于传感器自身的限制，感知信息存在不同程度的不确定性。通常需要对感知 信息再处理，通过多感知信息的融合获得较为准确的环境信息。因此，不确定信息 的处理方法是机器人地图创建中的一个关键问题。人工智能工作者已经提出了多种 用来处理不确定性的度量方法，如模糊度量、概率度量、信任度量、可能性度量、 证据理论等等。目前在创建地图中使用较多的主要是模糊度量i l3 j 和概率的方法。 ( 4 ) 多机器人协作探索策略 2 华北电力大学硕十学位论文 多机器人协作的地图创建需要考虑选择何种控制结构、如何实现协作、相互间 的定位等单机器人地图创建不需要考虑的问题。选取好的探索策略无疑会提高多机 器人系统的效率。目前针对多机器人地图构建问题还没 有人提出一个总的解决方案。更为有效的协调各个机器人之间动作，减少机器 人之间的冲突和避免不必要的重复探索仍i e t 是学者们研究的主要问题。 1 2 2 未知环境下地图构建方法 随着科学技术的发展，机器人学的研究已经从最初的工业领域拓展到航空航 天、军事等许多不同的领域，其中有些作业环境不适合人类的直接参与，例如行星 探测、核废墟等，这就需要机器人在这些未知环境中能够自主地完成各种智能任务。 有效的环境探索是机器人建立环境模型及完成各种复杂智能任务的关键，在实际应 用中具有十分重要的意义。 比较早的分布式多机器人环境探索系统中各个机器人之间没有协调，各个机器 人独立工作，只有当机器人在通信范围内时才互相交换地图【“】，环境探索的策略也熟， 是比较简单的沿墙走或随机行走等被动策略。 y a m a u c h i 利用栅格表示地图【1 5 】，引入了边界的概念，即接近未探索区域的己知 区，每个机器人前往距离自己最近的边界获取新的地图信息。这种方法中各机器人，一峨， 之间除了共享地图信息以外没有别的协作协调。所以这种方法会使机器人重复探索 其他机器人已经探索过的区域，降低整个系统的效率。 s i m m o n s 提出了新的多机器人环境探测策略l l 引，该方法基于y a m a u c h i 的边界t 7 的概念，各个机器人首先计算到一组边界点的耗散值，然后每个机器人计算所得的 耗散值交由一个中央机器人来处理，这个中央机器人把每个边界点具体分配到每个 机器人最终完成目标点的投标。这一算法的缺点就是系统采用集中式结构，其性能 完全依赖于中央机器人，系统的容错性和可靠性不高，这也是中心式控制结构共同 的缺点。 v a z q u e 提出的分散式多机器人环境探索方法i l7 。，机器人总是与至少一个机器人 保持通信，通过与其他机器人的通信，各机器人能够通过共享目标点实现协调和最 小化重叠，提高了容错性和系统的可扩展性，并且由于行为协调，避免了次优解； 基于行为的多机器人环境探索的体系结构，该分散式体系结构中的移动传感网通过 局部短距离通信协调，该系统能够针对环境探索过程中移动传感网的动态变化作出 适当反应，从避免碰撞、鼓励对未知环境的探索和维护移动传感网的目的出发定义 行为，基于当前的不同网络条件选择行为。 张洪峰等提出一种基于动态分区方法的多机器人协作构建地图方法【1 引。他们利 用距离传感器获得地图信息，用栅格表示地图，最后对数据用d e m p s t e r s h a f e r 证据 理论法进行融合。该方法有主控机器人根据全局信息对地图的不确定区域进行了分 3 华北电力大学硕士学位论文 区，每个机器人只需要在各个子区域内探测环境信息，这种方法有效的减少了地图 的重复探测率。 k i nyj 等人提出了一种基于不确定性度的协同简化算法【1 9 l ，利用m u l t i a g e n t 自主智能机器人联合建图。首先将地图划分为一些区域，设计每个机器人的几种基 本行为：巡逻、扩张、交换、共享和等待。根据这些行为定义每个机器人的个体结 构，每个机器人个体执行周期性的动作，每个事件单元执行上述的一个动作。执行 完所有行为后机器人从第一项重复执行。个体执行变异来产生后代，对领地进行n 轮循环后每个机器人计算平均确定比作为个体的一个适应度值。通过比较个体和后 代的适应度值，确定比较优秀的个体被选择和继续进行变异。这种算法的优点是可 以减小环境模型的不确定性。 王东等人基于m a s 理论，提出了一种进化的多a g e n t 在里学习的算法，通过 两个适应度函数：空间扩散适应度和区域覆盖适应度函数，选择具有最高适应度个 体来确定机器人的运行方向。机器人之间共享学习到的经验，这样在其中一台学习 到稳定的行为反应时，其他机器人也在类似的情况下就会有相同的反应。这样机器 人很快可以覆盖到整个带搜索区域。 近几年来研究人员已经在多机器人环境探索研究中取得了卓有成效的成果，但 是仍旧存在一些问题。研究当中采用何种环境描述和何种控制策略仍旧是值得我们 深入研究的问题。 1 3 本文研究的主要内容 为实现以上的研究目标，本课题主要研究以下几方面的内容： ( 1 ) 地图构建的任务描述：在多机器人环境探测问题中，对于任务的描述都是 根据环境的描述方式来确定，而这又取决于后期探索策略的选取。目前较常用的环 境描述主要有栅格地图、几何地图和拓扑地图。若采用栅格地图，则可以把探索地 图这一任务描述为确定每一个栅格是否存在障碍物；若采用几何信息则在探索过程 中将环境定义为面、角、边等的集合；而若采用拓扑图则是主要建立环境各元素之 间的关系。如何建立一种探索任务方式既能体现机器人对环境探索的效率，又能体 现出对环境元素的和信息的描述的精确程度这还是个需要进一步研究的问题。 ( 2 ) 目标点选取策略：根据地图的任务描述采取相应的目标点选取策略是构 建地图的一大难点。目前机器人探索的环境比较简单，当面对更为复杂的动态环境 时，存在着搜索空间的组合爆炸问题。随着搜索空间的增加，求得最优解将变得十 分困难。 ( 3 ) 机器人之间的协调与协作：目前针对多机器人地图构建问题还没有人提 出一个总的解决方案。更为有效协地调各个机器人之问动作，减少机器人之间的冲 4 华北电力大学硕士学位论文 突和避免不必要的重复探索仍旧是学者们研究的主要问题。 ( 4 ) 动态移动目标的轨迹问题：当障碍物为移动目标时，目标观测物的轨迹 预测，具有重要的现实意义。 本文的组织结构如下：第一章介绍本文的选题背景、研究现状及研究目的；第 二章研究多机器人地图构建中的环境信息及群体行为，提出一种改进的异构算法来 提高机器人的搜索效率，并将同构算法、异构算法以及改进的异构算法进行了对比 分析；第三章研究在未知环境下多机器人协作地图构建，提出一种基于粒子群优化 算法进行全局优化，以及对目标区域进行希尔伯特曲线探测的多机器人协作构建地 图的方法；第四章针对动态的移动目标，研究蒙特卡罗算法，提出一种基于蒙特卡 罗算法的轨迹预测算法。第五章对全文作总结与展望。 5 华北电力火学硕士学位论文 第二章多机器人地图构建中的环境信息及群体行为 2 1 引言 多机器人系统以多个机器人组成的系统为研究对象，研究的重点是协调问题， 即给定了任务、环境以及具有不同功能、不同类型的一组机器人，研究机器人之间 如何配合完成指定任务的过程。如何将不同子任务合理分配给适合的机器人? 这一 直是多机器人系统研究中的重要问题。由于完成子任务的最佳个体并不容易发现， 所以必须在一群符合要求的机器人中决定由那一个机器人来完成这项子任务，通常 来说这是一个耗时的搜索过程。影响多机器人任务分配的因素很多，机器人单体的 认知能力、行为能力、通信能力、任务本身的特性以及机器人群的社会结构等，都 会影响到任务分配的效果。 2 2 多机器人系统研究模型 多机器人系统的设计一般要考虑一下几个方面：机器人个体性能、群体体系结 构、协调规则等。机器人个体的能力一定程度上决定了整个系统的性能；群体体系 结构确定了机器人之间的关系约束；而协调规则定义了机器人的行为约束。当没有 按照一定方式将机器人组织在一起共同完成某一任务时，各个机器人都有自己的行 为，从整个系统来说，是无规则的行动。但是，当多个机器人按照一定的方式组织 在一起时，机器人之间以及机器人与环境之间进行一系列的活动，各自调整自己的 行为，最后形成一个有一定结构的系统。系统相对于环境做出的任何变化均成为系 统的行为。 根据机器人个体、任务( 目标) 以及工作环境的特点，抽象出如图2 - 1 所示多 机器人系统的研究模型。 从图2 - 1 可以看到，把多个机器人组织在一起形成一个系统，将着重研究任务、 环境、信息对整个系统行为的影响。 6 华北电力入学硕十学位论文 团瓮、( 鹾、三麓、汪叵团爿，、( 菡、爿，应) 、爿：，叵 型一 图2 1多机器人系统研究模型示意图 对于多机器人系统来说，系统的任务可能是一个复杂的任务，也可能是相对简 单。任务的复杂性将直接影响系统的效率，同时对机器人能力要求也不同。 机器人的工作环境不同，对于机器人的能力要求也不同。结构化的工作环境( 即 任务和工作环境已知) 对于机器人的自主性没有太高的要求，而对于工作在非结构 化环境中的机器人，则要求其具有较高的自主性。将机器人的工作环境分为以下三 类：争 ( 1 ) 潜在信息环境：潜在信息环境是指自然环境，它包含大量的信息，但是 要获取这些信息，则要求机器人具有较高的智能。 ( 2 ) 被动信息环境：被动信息环境是指包含人工信息的自然环境，机器人要妒 获取这些信息并不要求多高的智能。 ( 3 ) 主动信息环境：在主动信息环境下，机器人的信息是由环境主动赋予的。 由于机器人间的协调是建立在机器人对环境信息的获取、处理之上的，因此在 多机器人协调的研究中，特别是在动态、非确定性环境中工作时，机器人感知是一 个重要的环节。没有有效的传感，机器人就难以与环境交互，也就无法实现其自主 性、协调性。 机器人的传感信息按采集信息的位置分类，可分为外部传感信息和内部传感信 息。外部传感信息是指检测到的机器人所处的环境状态信息，常用的传感器有视觉、 红外、超声等传感器，主要应用于环境检测、避障、跟踪、测距等。内部传感信息 是指检测到的机器人的内部状态，主要有机器人的位置、角度、加速度、姿态等信 息。 在多机器人传感方面，侧重于外部传感的研究，目的在于能正确动态地描述周 围环境，为多机器人在不确定环境中的决策提供依据。机器人外部传感信息可分为 互补信息、竞争信息、协同信息三类。 互补信息：若两种或多种独立的信息源所提供的信息综合起来可以给出更加全 7 鼍 华北电力大学硕士学位论文 面的描述，而且各信息源提供的信息无冲突，称这些信息为互补信息。 竞争信息：若两种或多种独立的信息源所提供的是关于环境同一部分的信息并 且必须根据这些信息形成一个相对准确的描述，称这些信息为竞争信息。 协同信息：若一种信息源必须与另一信息源相互配合等才能获得观测信息，称 这些信息为协同信息。 根据多机器人系统内机器人信息的完备性、机器人对系统全局目标的认识以及 对全局知识的获取能力的不同，考虑一下三种情况： ( 1 ) 机器人信息不完全：机器人不具备系统的全局状态的信息和知识，它只具 有局部环境感知能力和对局部环境状态做出反应的能力。为此，设计机器人个体行 为控制规则，通过机器人个体之间的交互，以及机器人个体与环境的交互创现出链 型队列，然后进行货物的“r o b o t t o r o b o t ”传递。 ( 2 ) 机器人信息相对完全：尽管机器人不具备系统全局状态的信息和知识，但 他具有一定范围内的通信能力，通过机器人间的信息交互，把分布在不同机器人上 的传感器所提供的局部环境的不完整信息加以综合，以形成对环境的相对完整的理 解。然后利用相对完整的信息和知识知道机器人间个体行为的协调，最后实现链型 排列。 ( 3 ) 机器人信息完全：机器人具备系统的全局目标以及实现全局目标所需要的 全局信息和知识，可充分利用这些信息进行决策以获得一个协调的机器人群体。 2 3 多机器人系统基于搜集的任务分配 2 3 1 多机器人任务分配 如何将不同子任务合理分配给适合的机器人? 这一直是多机器人系统研究中的 重要问题。由于完成子任务的最佳个体并不容易发现，所以必须在一群符合要求的 机器人中决定由哪一个机器人来完成这项子任务，通常来说这是一个耗时的搜索过 程【2 0 1 。影响多机器人任务分配的因素很多，机器人单体的认知能力、行为能力、通 信能力、任务本身的特性以及机器人群的社会结构等，都会影响到任务分配的效果。 任务分配和任务分解是密不可分的，任务分解是指将系统要完成的任务按照任 务本身的特性、控制要求以及资源配置【2 1 j 分成若干子任务；而任务分配则是要将已 经分解完毕的子任务分配给相应机器人。如果无法找到合适的机器人，则需重新进 行任务的分解分配。 集中式分配和分布式分配是常用的两类任务分配模式，如图2 2 所示。集中式 分配有两种情况：对于分层式系统结构，任务分配由一个上层监控机器人统一完成， 这种分配方式称为“派定分配”。由于不够灵活，这种方法通常只适用于结构相对 8 华北电力大学硕士学位论文 固定的系统；另外，集中任务分配可由一类特殊工程的中介机器人来完成，按照不 同机器人的供需要求，中介机器人集中实现任务分配协调。在分布式分配模式中， 机器人个体以某种方式提供或索取“服务”，不需要特别考虑系统结构，包括两种 实现机制：基于“熟人模型”的任务分配以及通过合同网进行分配。 图2 - 2 常见的任务分配模式 ( 1 ) 基于熟人模型的任务分配 通过机器人内部已有的有关其他机器人能力的知识对所需完成的任务进行分 配。在各机器人内部有一张由熟人机器人标识及其所能完成的任务组成的表格。当 机器人进行分配时，可采用两种分配策略：直接分配和间接分配。当采用直接分配 策略时，机器人按完成任务所需的技能从其内部的表格中挑选适于完成任务的机器 人，并将任务分配给它；当采用间接分配策略时，机器人委托其他机器人来寻找合 适的任务完成者，并对任务进行分配。下面给出一分配过程： ( 1 ) 机器人接受一项任务。 ( 2 ) 在内部各机器人技能表中选择可完成任务的机器人。 ( 3 ) 向选定的机器人发出请求。 在选定的机器人接受任务时，就将任务分配给它，任务分配过程结束；若选定 的机器人拒绝时，返回( 2 ) 从新选择；若无机器人可完成该任务，则进行间接分 配。 向本机器人所知的机器人发出委托请求，等待可完成此任务的机器人响应。 接受所收到的第一个对此进行相应的机器人的确认，将任务分配给它，同时， 向其他机器人确认任务已分配，结束任务分配过程。 0 华北电力大学硕士学位论文 当在小范围内使用直接分配策略时，机器人可以对任务进行很好的响应，及时 进行任务分配。当直接分配策略不能使用，机器人以委托的方式进行任务执行者的 搜索时，对任务的响应速度将受到影响，多个机器人可能因要求完成同一任务而产 生冲突，也可能导致为了等待此任务的分配而影响对其他任务的响应。 ( 2 ) 基于合同网的任务分配 通过合同网协议【2 2j 在机器人系统中进行任务和资源的分配。在这种方法中，机 器人可以有两种角色：管理者将任务分解成多个子任务，寻找合适的承包人来完成 各项子任务；某一向子任务的承包人既可以作为完成者独立完成该项子任务，也可 以作为管理者对该项子任务进一步分解，并将分解后得到的子任务承包给其他机器 人去完成。 管理者选定承包人的招、投标过程如下： ( 1 ) 管理者声明一项任务。人保人得到任务的说明后依据自身的能力、工作 负担等对任务进行评估。 ( 2 ) 承包人将投标值发送给管理者。管理者对所有收到的承包人的投标值进 行综合评估【2 3 1 ，选出合适的承包人订立合同，由其来完成该项任务。 ( 3 ) 管理者等待承包人完成任务的结果。 由上述描述可以看出，合同网协议是分布式的，一个机器人可以同时以管理者 和承包人的身份出现。任务可以进行动态的分配，机器人可以动态的加入或退出， 可以较好地平衡各机器人的负载，无需事先知道其他机器人的能力信息，灵活、简 单易行。但是，合同网方法对通信比较敏感，这在某种程度上抵消了它的优势。 上述两种分配方式具有不同的特点，将两者结合起来可以充分发挥各自的优点， 建立更加灵活的任务分配机制，提高任务分配效率。当机器人需要对某任务进行分 配时，采用合同网方式，在较大范围内进行任务的分配。各机器人可以按照各自的 能力进行投标，在本身缺乏某种能力时，机器人也可通过查询内部表格，寻找具有 相应能力的机器人，然后向其发出申请进行联合投标。在得到联合投标确认后，机 器人将综合后的能力、条件结合起来进行投标值的计算，而后参与投标。进行任务 分配的机器人，根据各投标值来选择完成该任务的机器人。 2 3 2 多机器人地图构建中搜索任务分配算法 作为多机器人系统的任务之一，搜索有着重要的理论意义及应用背景，吸引了 很多研究学者的注意。文献 2 4 1 开发了一种划分区域的异构所搜策略【2 4 1 ，该策略首 先将搜索空间等分成若干子区域，机器人则分别在制定的区域完成搜集任务，受到 蚂蚁等在经过的地方会留下化学物质的启发，d r o g o u l 开发集中搜索策略，其中“带 路”机器人会在通往搜索目标的途中给其他机器人留下某种记号。对于系统中某个 机器人来说，它并不需要了解其他机器人在任意时刻的行为，如果其他机器人出现 】0 华北电力大学硕士学位论文 在它的传感范围之内，则会被当作移动的障碍物处理。 为了讨论与任务分配相关的因素，下面将对采取不同任务分配方案的三种搜索 算法进行比较和分析。 方案一：同构算法。搜索任务没有被分解，搜索到地图构建的整个过程将由每 个机器人单独完成。 方案二：异构算法。机器人的任务被分解为两个子任务：搜索和地图构建。任 何一个机器人在某一时刻只能选择其一。根据环境中的各个状态因素，机器人决定 是否进行任务切换。其中，任务的分配是建立在机器人从环境中获得的信息的基础 上，在整个过程中，不同机器人可能选择不同的子任务，所以成为异构算法。 方案三：改进的异构算法。与异构算法类似，改进算法也将机器人的任务分解 为两个子任务，机器人根据从环境中获得的鱼任务进度相关的信息来决定任务切换 的实际，同时，机器人以往的“表现”也作为选择子任务的依据之一。 结合任务本身的特点，针对以上三种任务分配方案，采用基于有限状态自动机 ( f s a ) 的算法结构。f s a 结构包括一系列的状态和行为，其中每个状态都将决定 下面应采取的行为，而这一行为又将导致下一个状态。下面分别对三种搜集算法进 行介绍。 ( 1 ) 同构算法 同构算法不对搜集任务分解，而是将其作为一个整体交给机器人来完成。算法 基于f s a 结构，状态、行为集见表2 1 和表2 2 。 表2 1 同构算法机器人状态集 状态 注释 自由 机器人不参与任何子任务 避障完毕机器人已经绕开在其前进方向上的障碍物 选择搜索目标完毕 机器人从已发现的被搜索物中选择了自己将要地图构建的目标 遇到障碍物 机器人在其前进方向探测到障碍物 发现待探测目标机器人在其传感区域内探测到被搜索目标 抵达搜索目标机器人到达其搜索目标附近区域，使机器人可以地图构建 华北电力大学硕士学位论文 表2 - 2 同构算法机器人行为集 行为注释 漫游机器人在空间里随机运动 避障 机器人躲避其前进方向上出现的障碍物 选择所搜目标机器人从已发现的待搜索物中选择其一，作为目标 向搜索目标运动机器人向预先选好的目标移动 抵达搜索物机器人地图构建 如图2 3 所示，当机器人没发现任何搜索目标时( 即处于“自由”状态) ，就在 环境中随机运动；一旦探测到待探测物，机器人就从中选择一个作为搜索目标，并 向所选的目标移动；当机器人与搜集目标距离足够小时，机器人就会进行地图构建； 完成构建后，机器人回到“自由”状态。在整个运动过程中，机器人遇到障碍物会 任务 、地 机， 华北电力大学硕士学位论文 并选择正确的子任务。异构算法中用到的状态行为集是从同构算法中扩展出来的， 表2 3 ，表2 4 只介绍同构算法中未包含的一些重要的状态和行为。 表2 3异构算法机器人部分状态 状态表示 选择完毕其他机器人已经从搜索机器人发现的待探测物体中选择出自己的目标 报告完毕搜索机器人已经把发现的待探测无的位置报告给其他机器人 预定失败其他机器人未能从搜索机器人发现的物体中选择出自己的目标 搜索失败在一定的时间内，搜索机器人不能找到未被报告过的待探测物 有待探测物环境中有已经发现，但尚未被预定或探测的待探测物 没有待探测物 环境中没有已经发现，但尚未被预定或探测的待探测物 表2 - 4 异构算法机器人部分行为 行为表示 选择其他机器人从搜索机器人发现的物体中选择出自己的目标 预定 机器人把已选择的目标通知其他机器人 报告通过广播，搜索机器人把发现的待探测物的位置报告给其他机器人 选择子任务机器人在搜索与构建地图中做出选择 如图2 4 所示，在任务开始时，机器人随机选择一个子任务，并根据选择的子 任务分别启动搜索算法和地图构建算法。选择搜索子任务的机器人按照搜索算法在 环境中随机运动，一旦发现待探测物，它就会把该物体的位置报告给其他的机器人， 而选择进行构建地图任务的机器人则根据搜索机器人发现的待探测物种选择合适 的目标，并向选定的目标运动；到达目标附近后，则进行地图构建，完成后，机器 人开始进行下一轮的地图构建工作。当机器人再也找不到已发现并且尚未被探测物 时，它也会进入“选择子任务 。任务选择主要由环境状态决定。当环境中没有意 境发现但未被探测的探测物时，机器人将选择搜索；当环境中仍有已发现但未被探 测的待探测物时，机器人考虑地图构建。与同构算法不同，异构算法引入了任务分 解概念，并通过一个简单的子任务选择机制，使机器人系统根据环境变化实现自主 任务分配。 1 3 华北电力大学硕士学位论文 图2 4 异构算法的状态行为序列 3 改进的异构算法 改进的异构算法基本上与异构算法相同，只是在任务切换时，除了考虑环境信 息，即环境中意境发现但未被探测的待探测物的状况，还考虑了机器人本身的能力 因素。定义如下两个表征机器人能力的参数。 a n ；_ n ( 2 1 ) 铲等 2 ， 其中，a 。( a ，) 代表单位时间内，搜索( 地图构建) 机器人探测到( 构建出) 的物 体的数目；n ，( ) 则代表被机器人发现( 构建) 的物体个数；乙( 气) 是机器人 花在搜索( 地图构建) 上的时间。在这里，预先设定两个阈值，4 l 和4 。对于机器 人来说，当a n ) 4 或a c ( 4 或环境中不再有发现但未被探测的待探测物时，机器人将 选择搜素；当a n ( 4 或a c ) 4 ，且环境中尚有已经发现但未被探测的物体时，机器人 选择探测。 图2 5 给出了三种搜索算法效率比较图，可以看出，采用同构算法的机器人效 率较低。综上，合理的分解分配任务有助于提高异构多机器人系统的工作质量。机 器人自身的能力、任务完成过程中工作环境的变化等是解决任务分配问题时需要考 虑的因素。 1 4 华北电力大学硕士学位论文 2 4 本章小结 船 较 征 辎 兰种搜索算法效率比较 图2 5 三种搜索算法效率的比较 本章介绍了多机器人系统研究状况，给出了几个有代表性的多机器人系统。从 机器人信息对群体行为的影响、任务分配以及基于局部交互的协调等方面讨论了多 机器人协调与控制问题。并针对多机器人搜索任务，探讨了三种对应不同任务分配 方案的搜索算法。通过算法效率比较，可看出合理的分解分配任务有助于提高异构 多机器人系统的工作质量。 1 5 华北电力大学硕士学位论文 3 1 引言 第三章在未知环境下多机器人协作地图构建 在未知环境中由机器人自主地依靠其自身携带的传感器提供的信息来感知其周 围的环境并建立环境模型已成为自主移动机器人研究中的一个热点问题【1 1 。为了能 够有效地探索未知区域并完成给定的任务，机器人需要自主创建地图【2 j 的能力。多 机器人协作地图构建与单机器人相比，可以减少构建时间，提高效率，并通过协作 定位技术和信息融合技术可以提高地图的精确度。 3 2 基于粒子群优化算法及希尔伯特曲线的地图构建 3 2 1 设置算法的环境 本章研究了复杂未知环境下多机器人地图构建的问题，提出了一种基于粒子群 优化算法进行全局优化，以及对目标区域进行希尔伯特曲线探测的多机器人协作构 建地图的方法。粒子群优化算法兼有进化计算和群智能的特点，利用该算法使多个 机器人尽量保持相互远离，距离原来的位置最近，并且每个机器人之间到达目标区 域的时间相差最短进行最优环境搜索。希尔伯特曲线探测配合机器人的可探测半 径，可以避免重复探测相同的区域。通过将本文提出的算法和基于s 型随机地图构 建算法进行比较，仿真结果表明该方法可以使机器人找到近似最优目标区域，减少 机器人重复探测，提高探测效率。 采用栅格法进行地图建模，如图3 1 所示，根据未知环境的整体大小设定正方 形区域作为待探测区域。把待探测区域分割为一些子区域，而每个子区域再分割即 为传统的栅格，栅格的大小相当于机器人的可探测范围，并采用粒子群算法为多个 机器人分配优选的子区域，而在子区域内部采用希尔伯特曲线探测。图3 1 中r j 、 r 2 、r 3 为机器人，黑色区域为障碍物。 1 6 华北电力大学硕士学位论文 图3 - 1 多机器人协作探测 对算法环境作如下假设： ( 1 ) 环境采用栅格法进行建模和描述，各栅格c e l l ( i , 力值e n v i j s o ，1 】- ，0 表 。 示没有被障碍物占据，1 表示被障碍物占据。 ( 2 ) 机器人已知其初始位置。机器人可以依据其当前所在的位置坐标计算下一。； 步的位置，在仿真中不计因机器人和任意物理因素而导致的定位误差。机器人可以 探测障碍物的范围即为传感器可以感知的范围r 。 ( 3 ) 环境对机器人来讲是未知的，当其对环境进行探测之后，才能构建环境地峨： k* 图。 ( 4 ) 每个机器人都可以保存局部地图，在整个地图构建完成之前，每个机器人 都保存自己所探测的地图。经过一段时间，机器人将其保存的局部地图传给多机器 人系统，这时，完成整个地图的构建，而每个机器人所保存的环境地图被再次置空。 3 2 2 粒子群优化算法及实现 在p s o 系统中，采用速度位置搜索模型，每个备选解被称为“粒子，该粒子 为解空间候选解，解的优劣程度由适应度函数【2 5 2 6 】决定。多个粒子并存，合作寻优， 速度决定粒子在搜索空间单位迭代次数的位移，其中，适应度函数根据优化目标定 义。 p s o 随机初始化为一群粒子，其中第i 个粒子在d 维解空间的位置为 x ；= ( x i 。，置：，x 谢) 。每次迭代，粒子通过动态跟踪两个极值来更新其速度和位置。 第一个极值是粒子从初始到当前迭代次数搜索产生的最优解：个体极值 p b e s t ( i ) = 晚。，见。，批，。第二个极值是粒子种群目前的最优解：全局极值 g b e s t = 俘，g d ) 。第i 个粒子的位置变化率( 速度) 为向量k = ( v i 。，v i 2 ， , r i d ，。 1 7 华北电力大学硕士学位论文 粒子根据以下公式来更新其速度和位置： v , d ( t + 1 ) = w g v i a ( t ) + c l g r l g p i d i t ) 一x , d ( t ) l + c 2 9 r 2 9 g d ( t ) 一x 缸( t ) 1 x 试( t + 1 ) = x 缸( t ) + a g v f d ( t + 1 ) ( 3 1 ) ( 3 2 ) 其中，i = j ，2 ，咒；d = 五2 ，p ；c ，c ：为非负常数，称为加速因子，通常取c 。= c ：= 2 ； 兀和厂2 是介于【o ，1 l n j 的随机数；w 和a 为非负常数，前者称为惯性因子，后者称为约 束因子，用来控制速度的权重；惯性权重w 描述了粒子上一代速度对当前迭代速度 的影响。控制其取值大小可调节p s o 算法的全局与局部寻优能力【2 7 2 8 1 。大量实验证 明，w 值较大，全局寻优能力强，局部寻优能力弱，反之则局部寻优能力增强，而 全局寻优能力减弱。使用动态惯性权值，在此采用s h i1 2 9 】建议的线性递减权值即： = 帆f 一j r 乙。- o i t m 。+ ( 3 3 ) 其中，k 为最大进化代数，；为初始惯性权值，为进化至最大代数时的惯性 权值，f 为当前迭代数。典型取值：w i ；= d 9 ，w 伽= 0 4 ，设d 口dsd ) 维的位置变化 范围为纵删，l 删j 7 ，速度变化范围为严圪删，屹删，( 即在迭代过程中，若和 超出边界值，即将其设为边界值) ，邑删、k 和屹删均是用户设定的常数。 华北电力大学硕士学位论文 e 2 善 r e ( x i ，y i ) e ( x i ，y i ) + e ( x t ，y i ) ( 3 6 ) 其中，e ( x i ，y i ，和e 纯，y ；j 为