（计算机应用技术专业论文）基于pso优化的多机器人协作机制研究.pdf

南京师范人学硕二学位论文摘要 摘要 多机器人系统具有结构灵活、适应性强的特点，在航天、国防、工业、服务业等许多领 域都有广泛的应用前景，合理地设计多机器人群体的协作机制并使用算法对系统进行优化是 发挥其优势的关键。为此，本文围绕多机器人协作领域待解决的三大问题：围捕问题，觅食 问题，多目标观测问题，通过改进的p s o 模型构建优化的多机器人群组协作行为，对系统 性能和协作效率进行优化。 ； 本文在阐述p s o 基本原理的基础上，分别引入邻域模型，聚类方法和自适应速度因子 等对p s o 优化器进行改造，用以解决不同的协作问题。设计了p s o 的邻域模型构建多机器 人围捕中环形缩放式搜索策略，分析了p s o 邻域模型对围捕行为的影响。以觅食问题为背 景，实现了p s o 的全局侦察和局部探索相结合的搜索模式及面向任务的分工模型，分析了 前期使用p s o 搜索对多机器人协作搬运和整个觅食过程性能的影响。引入了聚类方法实现 多目标的分组，用以构建p s o 动态自适应算法解决多机器人多目标观测问题，并与传统的 c m o m m t 和a - c m o m m t 方法进行比较分析，很好地解决了局部最优问题。仿真实验表 明，通过p s o 构建优化的群组协作行为对系统进行优化，可以极大地提高多机器人的协作 效率和系统性能。 关键词：多机器人；p s o ；协作；围捕；觅食；多目标观测 南京师范人学硕l 学位论文 a b s t r a c t a b s t r a c t w i t hf l e x i b l en r t l u t u r ea n dh i g i la d a p t a b i l i t y m u l t i r o b o ts y s t e m ( m r s ) e a i qb ew i d e l yu s e di n m a n ya l i a ss u c hn sa s t r o n a u t i c s ，n a t i o n a ld e f e t t s e ，i n d u s t r y ，s e t w i c ea n ds oo i l t ot a k et h e a d v a n t a g eo fm r s ，t h er e a s o n a b l ed e s i g no fc o o p e r a t i o nm e c h a n i s ma n ds y s t e mo p t i m i z a t i o n u s i n ga l g o r i t h m sa l et h ek e yo ft h ep r o b l e m t h e r e f o r e ，t h i sp a p e rt a k e st h r e ec l a s s i cc o o p a l a l i o n p r o b l e m s ( h u n t i n g f o r a g i n g , a n do b s e r v a t i o no fm u t t i p l et a r g e t s ) 器t e s tp l a t f o r m a n du s e s m o d i f i e dp s oo p t i m i z e rt 0b u i l do p t i m i z e dg r o u pb e h a v i o u r so fm r sf o ri m p r o v e m e n to ft h e c o o p e r a t i o ne f f i c i e n c ya n ds y s t e mp e r f o r m a n c e 1 m i sp a p e rp r o p o s e st h ei d e a so fn e i g h b o r h o o do p e r a t o r , c l u s t e ra n a l y s i s a d a p t i v ev e l o e i t y f a c t o rt os o l v ed i f f a l e n tp r o b l e m sb a s e d t h eb a s i cc o n c e p to f p s o mr m i 曲b o r h o o do l m m t o r o f p s 0 i s p r o p o s e d f o r t h e m u l t i - r o b o t h u n t i n g t o b u i l d t h er i n g f o r m a t i o n f o rc o l l a b o r a t i v es e a r c l l a n di t sp e r f o r m a n c ei sa n a l y z e d t h es e a r c h i n gm e t h o do fg l o b a lp a t r o la n dl o c a le x p l o i ti s a c h i e v e da sw e lja st a s k - o r i e n t e dw o r k - d i v i s i o nm o d u l e t h er e l a t i o n s h i pa m o n gt h ec o l l a b o r a t i v e s e a r c hi nf l r s tp e r i o d t h ep e r f o r m a n c eo f t h et r a n s p o r t a t i o na n dt h ew h o l ep r o c e s so ff o r a g i n gi s a n a l y z e dt h ea d a p t i v ep s oi sd e s i g n e df o rm u | t i - r o h e to b s e r v a t i o no f m u l t i p l em o v i n gt a r g e t s p r o b l e mb a s e do r lg r o u pd i v i s i o no fm u l t i t a r g e tu s i n gc l u s t e rm o d u l e a n di t sp e r f o r m a n c ei s c o m p a r e dw i t ht h et r a d i t i o n a ic m o m m ta n da - c m o m m tm e t h o d s ；m o r e o v e r , i ts o y e s t h e p r o b l e mo fl o c a lo p t i m i z a t i o n s i m u l a t i o ns h o w st h a tu s i n gp s ot oo p t i m i z em r sc a l lh i g h l y i m p r o v et h ec o o p e r a t i o ne f f i c i e n c ya n ds y s t e mp e r f o r m a n c e k e y w o r d ：m u l t i - r o b o t ；p s o ；c o o p e r e t i o u ；h u n t i n g ；f o r a q , b a g ；m u l t i - t a r g e t o b s e r v a t i o n 学位论文独创性声明 本人郑重声明： i 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所傲的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅：有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名： 日期： 南京师范大学硕j ：学位论文 基于p s o 优化的多机器人协作机制研究 1 1 研究背景 第一章绪论 多机器人系统( m u l t i - r o b o t s y s t e m ，m r s ) 具有代替人类在未知领域工作的潜力，但也 面临着在复杂环境中自主规划任务、进行协作的挑战。如何组织多个机器人组成的群体，在 群体中如何实现多机器人的群体协作( g r o u pc o o p e r a t i o n ) 是当前多机器入学研究领域的前沿 和新课题，具有重要的理论和现实意义。 目前而言，多机器人协作领域主要的研究问题有觅食、放牧、围捕l “”、多机器人编队【4 】、 群体搬运1 5 6 1 、多机器人多目标观测f 7 1 多机器人对未知环境的探测【3 i 、机器人足球赛9 噜。 以上这些领域的任务已成为研究多机器人协作效率、评估其性能的理想测试平台，许多协作 方法与思想的提出均是基于在这些领域的应用。 然而，这些协作任务难度大( 大多属于n p 难问题) ，受环境因素和机器人规模的影响， 常常引起决策空间维数的爆炸，因此现有的协作方法大多采用行为主义的设计思想，直接面 向任务的实现，着重于研究系统的可行性、灵活性、适应性，稳定性，而常常忽略系统性能 优化的要求，或者将协作方法的实现和优化分为两个不同的阶段和任务。这在一定程度上影 响了多机器人系统性能的发挥。当机器人规模进一步扩大时已有的协作方法往往成为任务 的瓶颈。 为此，本文选取多机器人协作领域三个最为典型的研究课题：觅食问题、围捕问题、多 目标观测问题，作为研究多机器人协作机制的载体，并在已有研究成果的基础上，对p s o 模型进行改进，用以构建优化的多机器人群组协作行为，达到优化整个群体的协作效率的目 的，实现群体智能的涌现。 p s 0 算法与多机器人协作相结合，并将p s o 思想融入行为的设计中，通过行为本身的优 化和合理的组合来构造高效的协作任务，可以说基于p s 0 的思想为多机器人协作的研究提供 了新的思路，新的协作模型，符合多机器人系统的研究和社会学、生物学相结合的发展趋势。 另一方面，通过对多机器人协作领域的应用分析，促进p s 0 本身的行为分析、协作机理的理 论研究。 1 2 多机器人协作的研究现状 多机器人协作机制和方法的研究与其具体应用领域紧密相关，众多优化的适应性算法或 协作思想的提出都依附于具体的协作课题。同时这些课题的解决又需要寻求可行的协作模 型、设计灵活的协作策略、提出优化的适应性算法，来促进协作机制和方法的创新。 本文以觅食问题，围捕问题、多目标观测问题作为研究多机器人协作的平台和载体。其 研究现状如f ： 南京师范人学坝f 学位论史绪论 l 、觅食问题 由于多机器人系统设计的主要思想来自于生物界。研究的目标是模仿生物群体的智能行 为。因此很多的多机器人领域的研究都是仿生的，一个很典型的例子就是觅食。在觅食实验 中，多机器人系统中的各个机器人在预先设定的任务空间中游走，试图找到食物并将其搬运 回一个设定的“家区域”中。觅食在现实世界中有许多应用领域，如到一些危险的区域( 火 山口、核废料区等) 采集资料，以及在星际探索时收集样本等。这些都使得对觅食任务的研 究得到更多来自现实的关注。 ： 为此，许多学者针对觅食行为的设计作了大量工作：m a t a r i c 最早建立了实际的行为主 义机器人系统，并让她的机器人完成了一系列包括扩散、游荡、回家、跟踪、放牧、觅食等 基本行为i t o , lj l ，为以后的研究确定了基本的行为设计框架，但其研究的模型仅能完成基本的 觅食任务；a r k i n 和b a l c h 进行了一系列的关于觅食实验的研究”i ，他们的工作主要集中在 通讯对于多机器人系统觅食性能的影响上：f o r t a n 和m a t a r i e 研究了将实验空间根据机器 人的个数划分为n 个区域”，提出了分区觅食的思想。虽然分区觅食与全局同质觅食相比 可以减小冲突，但整体效率并不占有优势。并且，当机器人的个数与分医的数目大于一定值 时，系统的协作效率反而会由于冲突的增多而降低。 2 、围捕问题 自然界遵循着“优胜劣汰”的竞争法则。在这种模式下，竞争最激烈的英过于捕食行为。 捕食双方通过在竞争的过程中相互学习，相互促进，从而为演练团队协作能力提供了一个开 放式的环境。这一模型可以很容易地移植到众多的多机器人协作领域中，如：搜救问题、监 控问题，机器人足球赛、定位和追踪移动物体等。 目前，许多学者主要从编队搜索和设计适应性算法两个方面对这一问题进行改进。如： y a m a g u c h i 提出了采用队形矢量控制群体队形，编队包围捕获单“移动目标”的策略l l 。 o e n z i n g e r 等利用最邻近规则( n e a r e s t n e i g h b o rr u l e ) 对当前状态进行分类，对每一个状 态用遗传算法搜索来决定围捕智能体应当采取的最优动作f 1 5 i 。o s a w a 提出了m e t a l e v e l 协 调策略，实现了协作式围捕【l “。然而，纵观这些文献，大多数只讨论了嗣捕单目标问题， 或者仅给出了移动目标采用随机逃跑策略而机器人采用随机独立的搜索策略，这一方面降低 了围捕的难度，另一方面并没有发挥多机器人协作式搜索的优势。 3 、多目标观测问题 多机器人对多个目标进行观测是当前多机器人研究领域中的一个热点问题。这一问题在 许多关于安全、检测及侦察的场合都有应用，例如画廊保安问题和探测灯规划问题【1 7 , 1 5 j ，前 者主要研究在己知的多边形区域中，怎样安排最少的传感器使得该区域的每一个角落都可以 被探测剑：后者则研究在既定区域内怎样通过对机器人探测灯的规划尽快寻找刮一个目标。 多机器人领域的多目标观j 1 1 4 问题中，目标和观测者都是运动的，而且每个机器人的观测 区域也远小丁二整个任务区域，闪此更为复杂。目前l e p a r k e r 在这一领域的研究最为突出。 2 南京帅范人学硕i 学位论文举j 二p s o 优化的多机器人协作机制研究 她在a l l i p , n c e i ”l 系统的基础上，设计了解决多机器人多目标观测的c 1 6 0 删t 方法p i ，通过计 算在机器人的观测范围附近的目标及其它机器人的吸引和排斥力，为该机器人寻找一个适当 的点，使得在这个点上各个力达到平衡，从而实现在一个较为理想的位置上观测尽可能多的 目标。该方法的不足是，在目标分布较为集中时，往往诱导机器人向密度集中区域聚集，以 此达到个体观测率的最大化，但造成了多个机器人重复观测相同的目标，使整个系统的覆盖 率反而降低陷入局部最优化。之后，她通过对位于重叠观测区域内的目标所产生的力进行 加权来减弱其引力作用，修正c m 0 i a i t 方法，提出了改进的a - 咧0 m m t 方案，减小了各个机器 人的重叠观测区。虽然提高了覆盖率，但加权系数的选取又成为新的问题。 从多机器人协作的三个重要领域的研究现状可以看出，多机器人的协作与协调方法的研 究就目前而言还远没有成熟，许多方面的探讨多是初步的。每年在i c r a ( p r o c e e d i n g so f t h e i e e ei n t e r n a t i o n a lc o n f e r e n c eo nr o b o t i c sa n da u t o m a t i o n ) 、1 r o s ( i e e e i r s ji n t e r n a t i o n a l c o n f e r e n c eo nr o b o t sa n ds y s t e m s ) 等重要国际会议中，都有大量文献讨论这一主题，从中可 以看到各国对这一方面研究的积极支持。例如，m a t a r i c 的“多机器人协调和学习”项目得 到了美国国家自然基金和国防先进研究项目局d a r p a ( t h ed e f e n s ea d v a n c , e dr e s e a r c h p r o j e c t sa g e n c y ) 的资助，研究可用于实际机器人系统的协作和协调算法。r ca r k i n 的“自 适应机器人队列形势估计”项目也获得了d a r p a 的资助。 我国多机器人协作的研究相对于国外起步较晚，目前已逐渐引起众多学者的重视。国家 自然基金从9 9 年起，平均每年批准一项关于多机器人系统的项目。其中，中科院自动化研 究所的谭比教授带领的研究小组研究了多机器人系统的体系结构，提出了基于遗传算法的参 数优化方法i z o i ，并研究了地图生成、围捕，船位对接等方面的问题。上海交通大学的席裕 庚、陈卫东教授所在的研究组，研究了动态优化的路径策略、利用局部式广播消解冲突的策 略，以及在线地图创建口“、机器人足球等领域的应用。哈尔滨工业大学的顾国昌、张汝波 教授着重研究了再励学习在多智能机器人领域的应用田j 。 1 3p s o 算法在多机器人协作领域的研究现状 粒子群算法( p s 0 ) 是一种基于群体智能的优化方法，它用无质量无体积的粒子作为个 体，并为每个粒子规定简单的行为规则，从而使整个粒子群表现出复杂的特性，可朋来求解 复杂的优化问题。白粒子群算法提出以来，已经广泛应用于函数优化、神经网络训练，模糊 系统控制以及其他使用遗传算法优化的应用领域 2 3 2 4 1 。 近年来，国内外许多学者开始将p s 0 算法引入多机器人领域，意图优化多机器人在具体 任务中的协作效率和系统性能。其中包括：d o c t o rs 等将p s o 算法应_ | j 丁多机器人的移动目 标定位问题”，很好地实现了多机器人向特定目标的追踪和聚集；孙波，陈卫东等将p s o 算法麻_ i j 丁j 机器人路径规划，并验证了算法的可行性1 2 6 1 ；闵华清等使用p s o 算法实现了移 动目标的避碰，并指出对_ 丁避碰类问题该算法的效率要优于遗传算法p ”。 夯阅国内外众多文献，不姬发现，p s o 算法在多机器人领域中的麻川人多仅从任务性能 南京帅范大学硕士学位论文绪论 优化的角度出发将p s o 算法嵌入其他协作方法中进行性能的优化和参数的优化，或者仅给 出可行性的解决方案，未能充分挖掘该算法在设计优化的群组行为方面的能力，尚未形成系 统性的领域应用。为此，将p s o 优化思想融入行为的设计中，通过行为本身的优化和合理的 组合来构造高效的协作任务，将成为一个待解决的研究课题。 1 4 本文的主要工作与论文结构 作者认为，可以将每个机器人模式化为在p s o 优化器中的一个微粒。这些微粒拥有相似 的行为集合，遵循共同的行为准则，共享一定范围内的群体信息，并通过个体间的协同进化 和相互影响构建群组协作行为，如聚集( a g g r e g a t i o n ) 、扩散( d i s p e r s i o n ) 、追踪( t r a c k i n g ) 、 协作式搜索( c o l l a b o r a t i v es e a r c h ) 等。通过这些优化的群组行为，设计面向任务( 如觅 食问题，围捕问题、多目标观测问题) 的协作策略，从而达到优化整个群体的协作效率的目 的。 基于上述考虑，本文将对以下几个方面展开研究： 1 、运用基于行为主义的思想设计多个在多机器人协作领域中常用的基本行为，为构建 更复杂的群组行为提供组合的单元；设计基于黑板模型的通讯协议，为构建基于p s o 的群 组行为提供信息共享的平台。 2 、运用p s o 算法的社会模型构建优化的扩散和聚集行为，分析优化行为和基本行为之 间的协作机制的区别，同时为构建更复杂的面向任务的群组行为打下基础。 3 、以多机器人围捕问题为背景，运用带邻域算子的p s o 算法设计多机器人围捕的缩放 式搜索策略，并在此基础上研究优化的群体合围模式。对比编队围捕方法，分析其适用的 场合、协作的机理和相对的优势。 4 、以多机器人觅食问题为背景，参考社会性昆虫( 蜜蜂) 的觅食行为模型，构造全局 侦查与局部探索的p s o 算法实现，针对食物的差异化分布的特点，研究合适的搜索与搬运 分工模型，与前期的搜索相适应。对比其他觅食方法，分析本方法的内在优势。 5 、以多机器人多目标观测为背景，研究自适应的p s o 算法用于解决个体观测率和系统 覆盖率的平衡问题，从而解决局部最优化问题。并结合p s o 协作式搜索模型，构建完整的 问题解决方案。 通过前面的分析，可以看出多机器人系统具有许多突出的优点，应用背景也非常广泛， 而保证其系统性能的核心是协作和协调策略。为此，本文将结合p s o 算法的优化模型和多 机器人系统协作理论，围绕多机器人领域的= 个具有挑战性的合作任务，利用p s o 来构建 多机器人的群体协作行为展开研究。 本文结构如卜| ： 第章：绪论部分。介纠本研究课题的研究背景，研究现状及存在的问题，指出了本课 南京师范大学硕j 学位论文基于p s o 优化的多机器人协作机制研究 题的研究内容及目的意义。 第二章：介绍行为主义的思想起源，方法和发展以及在多机器人领域的应用；详细分析 了通过基本行为的分解和组合，实现复杂任务的思想和方法，为本文使用p s o 构建群体行 为提供基础。 第三章：在介绍p s o 标准模型的基础上，通过p s o 方法来构建优化的群组行为，并结合 群体聚合和扩散行为，给出了基于p s o 优化的设计方法，为p s o 构建更复杂的群组行为打下 基础。 第四章：以围捕问题为背景，应用f s m 理论划分群体行为，建立行为问相互转化关系； 研究了通过带邻域算子的p s o 模型构建环形协作式搜索的行为，分析了该行为对整个任务 性能的影响，对比其它算法说明p s o 算法的可行性、高效性。 第五章：以觅食问题为背景，实现了p s o 的全局侦察和局部探索相结合的搜索模式及 面向任务的分工模型，分析了前期使用p s o 搜索对多机器人协作搬运和整个觅食过程性能 的影响。 第六章：利用p s o 模型解决多机器人多目标观测问题，研究了自适应的p s o 模型在个 体观测率和系统覆盖率协调中的作用。与传统的c m o m m t 和a - c m o m m t 方法进行基准 测试，比较两者的效率，并有效地解决了传统算法的局部最优问题。 第七章：总结与展望。 南京帅范大学颂f 学位论史 牡十行为的多机器人系统 第二章基于行为的多机器人系统 随着2 0 世纪5 0 年代人工智能的兴起，学术界呈现出很多不同的学派，如符号主义、联 接主义、行为主义等。而设计多机器人系统的思想体系和方法学大多来源于人工智能，尤其 是行为主义思想的影响。本章简要叙述了行为主义的发展历史和设计思想，并重点介绍了通 过行为的分解与合成，实现复杂行为的方法。这一方法也是本文后续工作的基石。 2 1 思想简介 2 0 世纪7 0 年代机器人学的进展缓慢，已有的体系结构和设计方法复杂而低效为此， 许多学者将目光投向生命科学，开始用人造系统模拟动物的行为，试图寻找获得智能的新的 组织形式和方法。与此同时，b r o o k s 在8 0 年代提出了行为主义的设计思想，形成了人_ 【智 能领域和机器人学的主要设计思想。 b r o o k s 认为1 2 s , 2 9 ，生命最基本的目的是生存，在了解高层次的智能之前，首先要了解 有关生存的反应能力，这种反应力的本质就是感知和运动行为的映射关系。同时，通过学习 调整这种映射关系，个体就可以具有适应环境的能力，从而促成整个系统满足某个目标。这 种把智能描述成一种“输入一输出”的黑箱方式，略去了对智能内部因素的分析，不仅简化 了系统的设计，还提高了系统的适应能力和实用性。目前各实验室开发的多机器人系统，多 基于这一思想。 在基于行为的多机器人设计中，每个机器人从传感器组中感知环境信息，从通讯接1 2 中 获知其它机器人当前的状态，激发相应简单行为，而多个简单行为又需要按照任务的要求合 成复杂行为，复杂的行为表现在多机器人协作和协调时，又称为群组行为。这些行为又与执 行器相关联，生成机器人的执行动作。这里，我们可以对行为集中的某个行为b b 的映射 关系进行形式化的描述： b - p x 一 o ，l 】 ( 2 1 ) 其中，尸为传感器不断收集环境数据形成的感知队列，为执行集，每个在感知队列 中的感知序列组合p p + 和对应的执行集中的一个动作x x 构成一个组合( p ，x ) ，然后 对这些组合根据任务的需要或与其它并发行为的交互，分别赋予0 到1 的参考值，表示行为 的执行程度。基丁行为的机器人框图如l 圣| 2 1 所示： 南京帅池人学硕j + 学位论文基于p s o 优化的多机器人悱作机制研究 2 2 行为的组织方式 图2 1 基于行为的机器人框架图 行为主义思想虽然具有简单、灵活的特点，但只能产生某一方砸的简单行为，而实际上， 机器人的智能有多个方面，重要性各不相同，彼此关系复杂。因此对于复杂的行为，需要设 计合适的行为织织方式，这里，我们简要介绍构建复杂行为的两种组织方式：分层结构和组 合结构。 2 2 1 分层结构 分层结构由b r o o k s 提出，是行为主义的一种基本结构 3 0 - 3 3 l 。与基于功能的思想不同， 这种结构不是根据功能划分，因此没有“感知子系统”、“中心系统”、“行为系统”一类的功 能模块。而是将智能划分为以目标为单位的行为层，每一个行为层都直接与传感器、执行机 构相连，实现某个目标卜的环境交互。 当有多个层存在的时候，若各个层做出的决策不同，较为高级的层可以抑止或者超越较 为低级的层。这里抑f r 是指禁止较低层次的决策输出，而超越是指强加自己的决策到较低层 的输出。在同一个层的内部，也可能存在着一些级别不同的各种行为模块，它们之间也可以 存在着抑制和超越的关系。由于舍弃了中心系统的概念，在采用多层行为的时候，因为环境 的变化而使得系统性能崩溃的可能性就减小了。当环境发生一定的变化时，可能最多只是其 中的一个或者几个层受到影响，如果环境继续改变，与预先设计的系统环境差异越来越大， 则系统的性能将会进一步的降低，但不会产生剧烈的改变。图2 2 是分层结构的示意图： 7 南京师范大学硕 学位论文基于行为的多机器人系统 2 2 2 组合结构 图22 分层结构图 在多机器人系统中，由于每个机器人相对于其他机器人而言，都是环境的一部分，其自 身状态的改变必然同时影响其他机器人的环境，因此环境的复杂性和动态性都很高，对环境 进行描述需要的状态量也很大，其数量随机器人数目呈指数增长。如果需要对每一种状态制 定相应的行为，则会因为庞大的状态数量使得多机器人系统的问题变得几乎不可解。为此， m a t a r i c 通过将环境和行为进行归类的方法来减小问题的维数，并提出了组合结构来合成复 杂行为的思想l j 。组合结构是分层结构在多机器人系统实现中的改进。 为此，她提出了情景和基本行为的概念，将感知信息和执行动作进行融合。所谓情景， 是指将所有传感器的信息融合后得到的特定的状态类型，每一种情景与特定的行为相对应。 通常情况下，执行一个行为所需要的情景由这一行为的定义给出。可见，情景对传感器信息 的融合，大大减小了输入空间的维数。 所谓基本行为，是指一系列基本动作的组合，用来实现一个特定的目标。设计基本行为 的目的，是省去对底层控制的表述，直接给出需要的输出。设计优良的基本行为对于系统的 动态性能和环境的变化具有很好的鲁棒性。由于基本行为对动作进行了合成，也减小了输出 空间的维数。 基本行为的数量一般是有限的，更为复杂的行为，则通过基本行为的合成来实现。对此 b l a t a r i c 提出了两种行为组合的方式l ：商接组合和序列组合。 如果任务比较简单，只有一个单一的目标，可能只需要将几个基本行为的输出直接叠加， 即可以达到高一级的行为，这时就可以选_ i j 直接组合。一个典型的例子是放牧，即多个机器 人向着一个共同的目标前进，在前进的过程中，相邻机器人的距离既不可太近也不可太远。 这样可以定义回家、聚集、扩散等几个基本行为，通过适当的直接组合来形成放牧行为。 有的情况下，一个任务中含有多个目标，在任务的不同阶段，目标是不同的。这时，就 不能简单地通过多个基本行为的叠加来实现，而是要以序列行为组合来实现。一个典型的例 子是机器人的觅食：开始时，机器人席该彼此扩散开来，接f 来机器人在任务空间中游荡， 南京师范人学硕士学位论文基于p s o 优化的多机器人协作机制研究 若是找到食物，则开始回家这一行为，将食物运送同家。觅食任务就是通过不同的情景激发 这一系列的基本行为来完成的。 图2 3 组合结构 图2 ，3 显示了组合结构的组合方式，0 表示直接组合：q 表示序列组合。m a t a r i c 基于 这两种的组合方法，在实际的多机器人系统中第一次实现了如放牧、觅食、靠墙停泊等复杂 的功能。 2 3 基本行为的实现 由于组合结构可以减小问题的维数，产生复杂行为时，可以不需要高层的指导信息，具 有很大的灵活性。本文的系统实现，都采用了这一方法。为了保证组合结构的特点，合理构 造基本行为集是问题的关键。 2 3 1基本行为集合的选择 一个机器人所具有的主要目的不同、设定的应用场景不同、使用的控制策略不同，都会 使得它需要配有不同的传感器，拥有不同的基本行为集。m a t a r i c i 川指出，在一个给定的领 域和任务环境中，选择一个基本行为集合应满足下面的两个标准： l 、必要性：集合中的任何一个基本行为都应当能够完成或保持一个目标，并且这个目 标不能由集合中的其它行为或行为组合来完成。 2 、完备性：基本行为集合不需要不属于这个集合中的其它行为的辅助来完成这一给定 领域中的任务。 在满足上面两个条件的同时，人工选择基本行为集合的时候臼然还应当考虑以下这些方 面： 简洁性：选择的行为应当是越简单越好。 稳定性：行为对于激发它的外部情景的变化，不应当特别的敏感。 可重复性：在合理的情景f 和允许的误差范围内，在每一次进行实验时，基本行为都应 该能够实现定义时所描述的功能。 南京帅范人学硕 学位论义摹十行为的多机器人系统 实际上基本行为集的选择并不是唯一的，因为不同的任务往往有不同的要求和特点。 即馒是同一个任务，也可以选择不同的基本行为集。在目前的多机器人系统研究中，还很难 提出一套同定的评价尺度作为设计最优行为集的标准。其原因在于：多机器人系统的性能与 其特定的任务环境紧密相关，而现有情况下，不仅多机器人系统的任务领域十分宽泛，即使 是同一类任务，也会由于实现该任务的机器人系统的各不相同、环境的差异、任务的侧重点 的不同而显现出极大的分歧，因此很难找到统一的标准来说明到底什么样的基本行为集是最 优的。 2 3 2 常用基本行为 二维环境下，如觅食、放牧、编队运动、靠墙停泊等任务，可以通过定义游荡、避碰、 跟踪、回家、聚集、扩散等基本行为的组合来实现。 1 、游荡 游荡是机器人最为基础的功能之一。对于多机器人系统来说，往往需要面对一个未知的 环境，并且需要系统在某个范围的未知任务空间中自主的随机运动以寻找目标或任务。设机 器人置在任务空间中以恒定的速率不断游走，并以较小的概率p 改变行走方向，则其速度 变化公式为： 矿= ( 铲互) o p ( 2 2 ) 其中，i 是原速度t 互是置的转向角向量( 墨= ( c o s a o , ，s i n a e , ) ) ，并且9 为( 0 ，2 万) 范罔内的均匀分布。两者的相乘是复数形式的乘积，概率因子p 表示执行该公式的可能性 为p 。图2 4 演示了3 个机器人和5 个机器人执行游荡行为的情景。其中带圈的箭头表示 运动中的机器人。 ( a )( b ) 图2 4 游荡行为轨迹图 2 、追踪 在多机器人系统中，有时需要或希望两个或多个机器人共同运动、寻找或完成任务，这 个时候就需要机器人跟踪传感器所探测到的邻近的其它机器人。由丁跟踪的关键在于趋向目 标，冈此我”j 给出了r 追踪置的角速度公式： 1 0 南京师范人学颂f 。学位论文 摹于p s o 优化的多机器人铷作机制研究 鲁诵静地 c z 。， 其中，弓是置指向一的向量，运算符( ) z 是两个向量的向量积的z 分量。c 和q 是常 量。通过式( 2 3 ) 使置动态调整追踪方向，假设双方在速度大小一定，且r 的速度略大于 r j 的情况下，可以实现相应的追踪行为图2 5 展示了3 个机器人跟踪的情景。机器人在 没有发现目标前作游荡运动，发现目标后进行跟踪。 ( a )( b ) 目2 5 跟踪行为轨迹图 3 、避碰 避碰是机器人保护自己、避免冲突的安全措施，按照障碍物的性质，可分为动态避碰和 静态避碰。从实际的应用出发，许多学者提出了众多避碰算法，最有名的是人工势场法f 。 这里我们给出一个简化的模型： 谚卜e + 鼠 ( 2 4 ) 其中，p 为( o ，2 石) 内的均匀分布，以q 的角速度旋转避碰。 4 、扩散 扩散算法是对游荡算法中，避障行为的补充，尤其是在机器人的数目比较多的时候。由 于各个方向都存在其它机器人( 障碍物) 的可能性较人，避障的效率便会大大降低，其至常常 陷入死锁的状态。为此需要扩散算法，在多个机器人过于密集时，则它们都向着其共同中心 的反方向运动，来使个体离中心的距离人于某个闭值元。这时对所有机器人的行为如 式( 2 5 ) 所示： k 丝静 ( 2 5 ) 其中乏，是集群中心指向置的向量，可是r 的速度向营，两者相除应用了向量的复数形式的 南京师范 学硕 学位论文 基于行为的多机器人系统 除法，面是转角向量，( ) ，是向量的x 分量。每个机器人都按照式( 2 5 ) 转过面个角度后， 机器人r 开始沿宜线运动，直到离中心的距离吒 占。肿，随后r 开始新的游荡行为一 5 、聚集 在一些任务中，当机器人彼此过丁分散时，也不利于协作，就需要机器人聚集。这时可 让机器人向共同的中心或目标运动，一般来说聚集可以看作是扩散的逆过程，所以，只需要 将式( 25 ) 中的改为瑶即可。因此，每个机器人都在转过尹个角度后朝向作直 线遥动。直剑离中心的距离小于安全距离t k 。图2 6 分别演示了群体的扩散和聚集行为。 图2 6 扩散和聚集轨迹图 ， 5 、回家 多机器人系统在未知环境工作的过程中，不仅需要在整个空间中漫游寻找并完成工作， 也需要不时地回到某个固定的基地，去进行能源补充、维护以及将自己采集到的信息与资源 运送回基地。这就要求各个机器人都具有回家的能力。回家的目的是减小机器人和某个被称 为“家”的目标点之问的距离，其行为如式( 2 6 ) 所示： 冲嘀 ( 2 6 ) 其中，磊为足指向h o m e 的向量，曩保持矿的速度朝目标点运动。圈2 7 显示了机器人回 家示意图。 图z 7h 家行为轨迹图 ( b ) 南京师范人学硕学位论文基于p s o 优化的多机器人协作机制研究 2 4 小结 本章介绍了当前多机器人系统中被普遍采用的行为主义思想和方法。并重点介绍了组合 结构下基本行为集合的设计。通过基本行为的建立与组合，使基于行为主义思想的机器人具 有了完成复杂行为的能力，可以进一步实现复杂任务，并适应多机器人系统的动态环境。这 一方法可以用来实现觅食、围捕、多目标观测等更为复杂的任务。 南京帅范大学硕j 一学位论文基于p s o 的简单群组i 行为实现 第三章基于p s o 的简单群组行为实现 直接通过基本行为合成的多机器人群组行为仅以完成规定的任务为目的，大多都不考虑 复杂行为的优化，使得系统规模变大时，群体性能急剧下降，甚至失效。为此，本章在介绍 p s o 标准模型的基础上，通过p s o 方法来构建优化的群组行为，并结合群体聚合和扩散行为， 给出了基于p s o 优化的设计方法，为p s o 构建更复杂的群组行为打下基础。 3 1p s o 标准模型简介 k e n n e d y 和e b e r h a r t 在1 9 9 5 年的i e e e 国际神经网络学术会议上正式发表了_ 题为 “p a r t i c l es w a r mo p t i m i z a t i o n ”的文章，标志着p s o ( 粒子群) 算法的诞生。 p s o 算法和其它进化算法相类似，也采用“群体”和“进化”的概念，同样也是依据个 体( 粒子) 的适应值进行操作。所不同的是，p s o 算法不像其它进化算法那样对于个体使用 进化算子，而是将每个个体看作是n 维搜索空间中的一个解。每个粒子都在解空间中以一定 速度飞行，其速度由个体的飞行经验和群体的飞行经验动态地调整。 为表述方便，我们预设如下概念： 墨= ( x f l t 2 ，x m ) 为微粒珀勺当前位置； = ( v l ，v j 2 ，) 为微粒哟当前飞行速度； ，k ，= ( n ，只：，e l 。) 为微粒新经历的历史最优位置一 设( z ) 为最优化目标函数，则 砌州- 籍2 嚣端三悲端 伍， 设g o 为所有微粒所经历过的最优位置，称为全局最优位置： g o “+ 1 ) = p a t ) j m i n f ( p o ( t ) ) ，厂( 眉( f ) ) ，( 只( f ) ) ) ( 3 2 ) 由此标准的p s o 算法的进化方程为： j o + 1 ) = 缈+ v i i ( t ) + c , + r a n d ( ) 术( 只。，0 ) 一z ( f ) ) 1 + 乞。r a n d ( ) + ( 吒( f ) 一z ( f ) ) ( 3 3 ) 【z o + 1 ) = z ( f ) + v a t + 1 ) 其中，下标i 表示第i 个粒子，t 表示第t 代，q 和巳为加速因子，通常在0 2 之间取 值：国为惯性权重，通常的取值范用是( o 4 0 9 ) ，r a n d ( ) 为u ( 0 ，1 ) 之间的随机数发生器。 南京师范大学硕士学位论史摹于p s o 优化的多机器人协作机制研究 从上述p s 0 进化方程( 3 3 ) 可以看出c l 调节粒子e 向自身最好位置的步长，c 2 调节 粒子向全局最好位置飞行的步长。为了减少在进化过程中，粒子离开搜索空间的可能性，矿 通常限定在一定范围内，即矿卜k ，】。如果搜索的空间限定在【一贾。，贾一】内， 则可设定p r 蹦= k z 。，k ( o 1 ，1 0 ) 。 需要注意的是，在基本粒子群算法中并没有g o 这一惯性权重因子，使得粒子的速度往 往过冲，需要或者置。加以约束。为了改善基本p s 0 算法的收敛性能，y s h i 与 e b e r h a r t 首次在进化方程中引入惯性权重甜【，自此形成了标准粒子群算法，式( 3 3 ) 即 为其标准形式。m 使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区 域引入惯性权重缈可清除基本p s 0 算法对p 幺的需要，因为本身具有维护全局能力和 局部能力的平衡作用。 3 2p s 0 的行为分析 在式( 3 3 ) 所描述的速度进化方程中，其第一部分为粒子的惯性速度；其第二部分为 “认知”部分，因为它仅考虑了粒子自身的经验，表示粒子本身的思考。如果基本p s 0 算法 的速度进化方程仅包含认知部分，即 v a t + 1 ) = 埘+ ( f ) + c l + r a n d ( ) + ( j k ( f ) 一一( ，) ) ( 3 4 ) 则其性能变差。主要原因是不同的粒子间缺乏信息交流，即没有社会信息共享，粒子间没有 交互，使得一个规模为m 的群体等价于m 个单个的粒子，因而得到最优解的概率非常小。 式( 3 3 ) 的第三部分为“社会”部分，表示粒子问的社会信息共享。若速度进化方程 中仅包含社会部分，即 ( f + 1 ) = 国+ ( f ) + q + r a n d ( ) + ( 1 7 ( ，) 一z ( ，) ) ( 3 5 ) 则粒子没有认知能力，也就是“只有社会( s o c i a l o n l y ) ”的模型。这样，粒子在相互作用 下，有能力到达新的搜索空间，虽然它的收敛速度比标准算法更快，但对于复杂问题，则容 易陷入局部最优点。k e n n e d y ”7 以x o r 问题的神经网络训练为例进行了仿真实验，验证了上 述结论。 总之，标准的粒子群算法的速度进化方程由惯性速度、认知和社会三部分组成。虽然目 前的一些研究表明，对一些问题，模型的社会部分显得比认知部分更重要，但两部分重要性 还没有从理论上给出结论。 3 3 简单群组行为的p s 0 实现 在2 3 2 节中我们介绍了常用的基本行为，其中包括群体聚集和扩散。由于p s o 算法本 南京师范大学硕上学位论文基于p s o 的简甲群组行为实现 身就是用来模拟鸟群的觅食行为，因此，这两种行为都可以使用p s o 算法刻画，而且具有更 好的性能。为了叙述方便，我们称使用p s o 算法实现的聚集和扩散行为为p s oa g g r e g a t i o n b e h a v i o r ( p s o a b l 乘ip s od i s p e r s i o nb e h a v i o r ( p s o d b ) 。 3 3 1 算法实现 简单的多机器人聚集行为只需要考虑聚集中心点的位置和机器人相互避碰问题。而这 聚集中心恰好对应于p s 0 的全局最优位置，因此可以舍弃个体认知部分。这里，我们将机器 人看作是一个智能体