（电子科学与技术专业论文）基于粒子群优化算法的多机器人编队控制技术.pdf

a b s t r a c t w i t ht h ee x p a n s i o no fr o b o ta p p l i c a t i o n ，t h ed e m a n dt or o b o t s a b i l i t yi sm o r ea n dm o r eh i 曲m u l t i p l er o b o t sc o o p e r a t i v e l yc o i n p l e t e m o r ec o m p l e xt a s kt l l a ts i n g l er o b o tc 锄n o tc o m p l e t e f o m a t i o nc o n t r o l i sac o m m o na n dt y p i c a lm u l t i r o b o tc o o r d i n a t i o n ，a i l di ti sa l s om eb a s i s f o rm u l t i r o b o tc o o r d i n a t i o n f o r m a t i o nc o n t r o lc a ng r e a t l yp r o m o t ea n d f a c i l i t a t em u l t i r o b o tc o o p e r a t i v es y s t e mr e s e a 心h h e r ew ea d o p tb e h a v i o 卜b a s e di n u l t i r o b o tf o m l a t i o nc o n t r o lm e t h o d ， b u tt h e r ea r et v 旧p r o b l e m si nt h em e t h o do ff o r m a t i o nc o n t r o l ，t h o s ea r e t h ed e s i g no fe f 纸t i v eb a s i cb e h a v i o ra n dt h ec h o i c eo f b 甜e rp a r a m e t e r s o f w e i 曲tv a l u e s f i r s t l y ，f o rm ep r o b l 锄o fe f f e c t i v ed e s i g no f b a s i cb e h a v i o r ，t h j s t h e s i sm a k e si m p r o v e m e n t so na v o i ds t a t i co b s t a c l e sa n da v o i dr o b o t w e d e s i g nay a 、va n g l et h a ti n c r e a s e sw i t ht h em i n i m u md i s t a n c eb e 咐e e n r o b o ta h do b s t a c l e so ro t h e rr o b o t sd e c r e a s e s ，w h i c hc a ns m o o t h l va v o i d s t a t i co b s t a c l e so ro t h e rr o b o t s f o rt h ep h y s i c a ll e a d e rr o b o t sp o o rf a u l t t o l 咖c e ，w es e tav i r t l l a l l e a d e ra tt h eg e o m e t r i cc e n t e ro ft h ef o m a t i o n 。 a n dg u i d et h ew h o l eg r o u p sm o v i n g s e c o n d l y ，f o rt h ep r o b l e mo fd i 衔c u l 够i ns e l e c t i n gt h eb e t t e rc o n t r o l v a l u e s ，、eu s ep a l t i c l es w a mo p t i i i l i z a t i o na l g o r i t l l i nt os e l e c tam o r e a p p r o p r i a t ec o n t r o lc o e 衢c i e n t s h o w e v e r ，d u et oh i g h d i m e n s i o n a lo p t i m i z a t i o no b j e c ti sa 向n c t i o no fi n u l t i p l ee x t r e m ep o i n t s ，t h es t 2 n l d a r d p a r t i c l es w 锄o p t i m i z a t i o na l g o r i t h mf o rh i g h - d i m e n s i o n a l t a 玛e te a s i l y g e t si n t ot h ep r o b l e mo fp r e m a t u r i t ya 1 1 dh a ss l o wc o n v e 玛e n c e ，s o 、e p r o p o s e da ni m p r o v e da d a p t i v ep a f t i c l es w 锄o p t i m i z a t i o n ，t h a ti s ， a c c o r d i n gt ot h es p a t i a ld i s t 曲u t i o na n de v o l u t i o ns t a t eo fp a n i c l e s ，w e s e tt h ec o r r e s p o n d i n ga d 印t i v ec o n t r o lp a r a m e t e r s ，a n dt h ep a r t i c l ew h i c h g e t si n t oag l o b a lo p t i m a lp o i n tt a k e sn o n u n i f o m l l yj u m p i n go u ta n d e s c a p i n gs t r a t e g y t h es i m u l a t i o ns h o w st h a tt h ei m p r o v e da l g o r i t h mh a s b e t t e rp e r f o 锄a n c e f i n a n y ，t h ei m p i - o v e do r i e n t e dh i g h d i m e n s i o n a la d a p t i v ep a r t i c l e i i s w a 衄o p t i m i z a t i o ni s 印p l i e dt om u l t i r o b o tf o m l a t i o nc o n t r o l ，a n dw e g e tab e t t e rp a r a m 甙e r s t h e nw ed ot h es i m u l a t i o no fm u l t i p l er o b o t s f o n i l a t i o nc o n t r o lo nm a t l a bp l a t f o m l t h er e s u l t p r o v e d t h e f e a s i b i l i t yo ff o n n a t i o nc o n t r o la l g o r i t h ma n db e t t e rp e r f o n n a n c e k e yw r o 剐d s n m l t i - r o b o t ，a v o i dr o b o t ，a v o i do b s t a c l e ，f o m a t i o n c o n t r 0 1 ，p a n i c l es w a n no p t i m i z a t i o n i i i 硕士学位论文 绪论 第一章绪论 1 1 课题研究的背景和意义 1 1 1 背景 机器人技术是一门多学科技术，综合了材料、机械、控制、智能、传感器等 各方面的最新研究成果。随着机器人技术的发展，机器人已经在很多方面帮助或 代替人类完成繁杂、危险和重复性工作，对人类的生产、生活产生深远的影响。 因此自上世纪中期以来，该领域的研究得到迅速发展。在较长时间里，人们对机 器人领域的研究重点都集中于单个机器人的结构、动力学、控制方法、传感器和 信息处理等方面。近年来，单个机器人的能力、可靠性、鲁棒性得到了显著地提 高。但随着工业的发展，人们对机器人的要求也越来越高，单个机器人被用来完 成更深入、更复杂的任务。虽然单个机器人能力已经得到很大的提高，但仍然难 以满足这些新的应用需求。 在生物界，比如蜜蜂、鸟类、狼群等群居动物，依靠内部的分工合作、信息 传递，才能在复杂的环境中获得食物、逃避天敌，他们具有低阶的社会性。在人 类社会中，很多活动单个人是无法完成的，需要多人合作才能进行。受到生物群 体社会性的启发，人们开始考虑由多个机器人组成的群体系统通过协调、协作来 完成单机器人无法或难以完成的工作【l 】。 受到社会需求的推动和分布式人工智能的发展，自上世纪8 0 年代以来，多 机器人系统的研究得到了广泛关注，并被作为一个相对独立的专门研究领域，从 理论到实际应用系统都取得了丰富的成果。多机器人群体系统相比单机器人系统 的优越性表现在以下几个方面： ( 1 ) 机器人之间的相互协调和协作，可以表现出单机器人不具有的“涌现 能力。多个机器人作为一个整体系统的能力远大于各个单机器人能力之和，并且 具有单机器人不具有的能力。这样多机器人通过协调协作和共享资源，就可以弥 补单机器人能力的不足，完成单机器人系统无法完成的复杂任务； ( 2 ) 多个简单机器人的设计比单个复杂机器人更容易，制造成本也更低： ( 3 ) 群体机器人系统本身具有的并行性特点可以大大节约任务完成时间，提 高工作效率； ( 4 ) 群体机器人系统的冗余性和平行性可以提高系统的容错性和鲁棒性等； ( 5 ) 系统更加容易升级。当需要提高系统新的性能时，只需加入新的机器人 硕士学位论文 绪论 即可，而不需要对整体进行大的调整，因此能降低升级代价【2 3 】。 由于以上优点，多机器人系统在很多领域得到广泛的应用：协助军事行动、 远地作业、自动仓库管理、协助震后搜索与营救、清除危险区域、自动建造、智 能环境、自动化工厂和农业机器人等。 多机器人系统是通过协作来完成任务的，人们对多机器人系统的协作研究主 要集中在以下几个方面：群体结构、学习、冲突消解、协调协作、环境辨识等。 为了使研究成果具有普遍意义，人们的研究主要集中在编队、搬运、分类、搜索、 围捕以及跟踪等一些基本的问题。在这些基本问题中，编队是一类广泛存在的标 准问题。 1 1 2 意义 编队控制是一个具有典型性和通用性的多机器人协调问题，是多机器人协调 问题的基础。所谓编队控制是指多个机器人在到达目的地的过程中，保持某种队 形，同时又要适应环境约束的控制技术【4 】。多机器人编队系统在运动过程中可能 遇到动态障碍物、静态障碍物、或狭窄的通道，这时机器人要暂时离开在队形中 的理想位置，采取避障、避碰、队形变换等形式来完成复杂的任务，偏离队形的 机器人在完成任务后会尽快恢复原先队形。经过编队的多机器人系统能够协调一 致的向目标点运动，可以更可靠地执行任务、提高系统效率，可以减少系统消耗， 并且提供冗余度、重构能力和系统结构韧性【5 1 。 通过研究开发及实用化，多机器人编队技术在国防工业、工农业生产、柔性 制造和无人探险等领域的应用前景逐渐表现出来。这些领域的应用包括形成固定 队形搬运大的物体、形成弧形队形包围、捕获入侵者、完成空间任务等【6 1 。随着 多机器人被广泛地应用，多机器人编队控制理论也日益成熟，并成为多机器人系 统研究中一个非常活跃的方向。 1 2 多机器人编队技术研究现状 自1 9 8 0 年代以来，多机器人系统的研究开始发展起来。进入9 0 年代后，多 机器人编队问题开始在多机器人学中逐渐活跃起来。迄今为止国内外对多机器人 编队进行研究的单位越来越多，理论研究也日益多样和成熟。 在多机器人编队技术研究方面，近年来无论从理论还是实验都取得了较大的 进展。在对机器人队形控制研究方面，目前按群体的体系结构分为集中式和分布 式两种【刀。 在集中式多机器人系统编队控制研究方面，尺c a r e l l i 等人【8 】设计了一个中央 2 硕士学位论文 绪论 控制器控制多机器人的编队运动。中央控制器通过摄像头获得群体机器人的位置 信息和环境信息，决定群体的运动规划，向每个机器人发送线速度和角速度值， 实现在复杂环境下对多机器人系统进行编队控制的目的。集中式编队方法的优点 是易于控制、精确度高和可行性高，缺点是整个整个系统完全依赖于中央控制单 元和通信，存在通信瓶颈问题，并且容错性、灵活性和适应性较差。 由于集中式控制存在固有的缺点，人们研究更多的是多机器人系统分布式编 队控制。在分布式编队控制系统中，多机器人群体没有统一的控制中心，机器人 都是平等的协作者。分布式编队控制具有更好的缩放性、鲁棒性和环境适应性， 但是构建比较困难。分布式编队控制方法目前主要有基于行为的方法、领航跟随 者方法、虚拟结构方法、人工势场方法、基于一致协议方法等。 以上几种编队控制方法都有特定的应用场合，并且有固有的缺点。然而可以 把其中的几种方法有机结合起来，融合各个方法的优点，避其缺点，就能实现更 有效的编队控制。“w a i l g 【9 】就是把基于行为的方法和基于势场的方法进行结合， 群体采用势场法保持队形并向目标前进，在遇到障碍物时，把每个障碍物所在区 域分成三个区域( 安全区、避障区和危险区) ，每个机器人进入到这三个区选择不 同的行为方式以避障，这样可以快速有效的避开障碍物。 另外，为了适应复杂环境下的编队控制，近年也有不少研究将学习机制用到 多机器人编队控制中，比如基于遗传算法的行为控制参数的学习、增强式学习以 及学习分类器( l c s ) 系统学习等。文献【l o 】讨论了各种基本行为控制参数的优化 问题，作者采用遗传算法搜索最优控制参数，提高了队形控制的性能。王醒策等 f 1 1 】在把强化学习的方法应用在机器人的动态避碰自适应编队方法中，实现了自主 避障编队。文酬1 2 】贝0 在基于遗传算法的队形控制和基于强化学习的避障之间使 用了一个切换算法，使得在障碍物环境中能够重建多机器人队形。 除了以上介绍的几种方法外，近年又出现一些其他的方法，比如基于概率方 法【1 3 1 、基于视觉的方法【1 4 1 、基于磋商的方法【1 5 】、基于图论的方法【1 6 】等。 1 3 本文主要研究内容和章节安排 1 3 1 本文主要研究内容 前文已经简要地介绍了多机器人系统编队控制的一些研究概况，并分析目前 多机器人编队控制存在的问题。本文将在此基础上研究基于粒子群优化算法的多 机器人编队控制方法，并对机器人编队控制算法做了进一步改进。同时还编写了 多机器人编队控制的仿真程序。本文的主要工作概括如下： ( 1 ) 针对标准粒子群算法在优化高维目标时易出现早熟和收敛慢的问题，提出 3 硕士学位论文绪论 了改进的自适应粒子群算法。 ( 2 ) 以队形的几何中心作为机器人位置的参考点，并把参考点作为虚拟领航者 机器人，引导队形运动。对虚拟领航者机器人和跟随机器人分别设计了基本的行 为库。虚拟领航者机器人根据系统整体环境的不同，引导跟随机器人采取不同的 控制策略。 ( 3 ) 把改进的面向高维优化目标的自适应粒子群优化算法用于行为控制参数 的优化选择，描述了在静态环境下的多机器人编队控制算法。 ( 4 ) 在m a t l a b 平台上编写了多机器人编队控制程序。通过仿真，证明了上述 编队控制算法的的可行性。 1 3 2 本文章节安排 本文结构安排如下： 第一章绪论，介绍多移动机器人编队的研究背景和意义，编队控制的研究现 状和本文的研究内容。 第二章给出了多移动机器人系统研究的内容、编队控制几种主要方法、编队 控制实现的相关问题。 第三章研究了粒子群优化算法的改进。面对高维优化目标，本文对基本粒子 群算法做了改进，使之适合于多机器人编队控制系数的优化。通过仿真测试，证 明了该改进算法的有效性。 第四章研究了多机器人编队控制问题，设计了基本的行为库，选取队形几何 中心作为虚拟领航者，提出了在有障碍物环境下的避障策略，最后对编队控制算 法做了描述。通过仿真实验，验证了它们在不同复杂性地图中编队控制的可行性， 并根据仿真结果进行了分析和比较。 第五章对本文的工作进行归纳总结，并对今后的研究方向进行了展望。 4 硕士学位论文多机器人系统及编队控制 第二章多机器人系统及编队控制 多机器人编队的研究是以多个机器人组成指定队形的运动为研究对象，研究 的目标是设计一套分析、设计及控制机器人的有效方法，使其能够有效、高质的 完成协调编队任务。本章从整体上对多机器人编队控制的实现进行了分析。 2 1 多机器编队系统的体系结构 多机器人群体体系结构是多机器人进行有效编队控制的重要因素，主要研究 如何设计合适的软硬件结构把机器人群体联系起来。体系结构决定着系统的整体 行为和整体性能，是整个多机器人系统的基础，体系结构的安排是机器人整个系 统性能的关键。多机器人系统体系结构的设计既要考虑个体机器人是否能够灵活 自如的完成任务，同时还要考虑系统本身的开放性以及对环境的自适应性。 多机器人体系结构可以分为集中式、分布式和混合式三种结构【。丌，如图2 1 所示。 带 日j 口南 2 1 1 集中式结构 自治机器人 自治机器 ( b ) 分布式结构( c ) 混合式结构 图2 1 多机器人体系结构 集中式结构如图2 1 ( a ) 所示。它有一个主控单元和若干受控机器人，主控机 器人通过和受控机器人的通信，获得了受控机器人信息和环境信息。当要让机器 人执行某项任务时，只需向主控单元发送任务命令，这时主控单元结合机器人和 环境信息，运行各种规则算法，对任务进行分解和分配，然后向受控机器人发布 命令以完成任务。受控机器人本身不具有决策和相互协调的能力，只是一个执行 体。在这种体系结构中，受控机器人只和主控单元之间进行通信，和其他机器人 之间不进行通信。 集中式结构的优点是控制方法简单，实现较为直观。它的缺点在于容错性、 5 西 硕士学位论文 多机器人系统及编队控制 适应性和灵活性差，对主控机器人的要求高，当某一个机器人出现问题，特别是 主控机器人出现问题时，会导致整个系统的瘫痪。 2 1 2 分布式结构 分布式结构如图2 1 ( b ) 所示。在这种结构里面，各机器人都是平等的，没有 主控和受控之分，各机器人通过自身的感知系统和通信系统，自主地进行行为决 策。和集中式结构相比，分布式结构具有并行运行、故障冗余、可伸缩性等优点， 因而具有更好的灵活性、鲁棒性、较强的环境适应性。目前主要有以下几种分布 式结构： ( 1 ) a l l 认n c e 结构【1 8 】。在这种结构体系中，机器人利用动机模型自适应地 选择动作，输出由机器人自身的传感信息、机器人之间的通信、行为间相互制约 关系、内部动机等确定。 ( 2 ) 面向多机器人协作系统( m r c s ) 的体系结构【1 9 】。这种结构包括协作规划 层、协调规划层及行为控制层三层结构，每层规定了单个机器人的行为和机器人 之间的通信协作，使得机器人设计模块化和简单化。 ( 3 ) 基于行为的混合分层体系结构【2 们。该结构是基于行为分解的基础上提出 来的，整个结构分为三个层次模块，即行为模块层、行为管理层和行为综合层， 通过在线调整行为模块的激活状态、改变行为算法参数、改变行为综合方式和参 数，使得整个群体更能适应动态环境。 ( 4 ) 面向多机器人任务级协作的体现结构【2 。该体系结构包括系统监控层、 协作规划层和行为控制层三个层次，具有鲁棒性、模块化等优点，是一种适合大 规模机器人系统、复杂环境的体系结构。 但是这种结构的整体协调性较差，并且控制很复杂，很难设计一个理想的控 制方法。 2 1 3 混合式结构 混合式结构如图2 1 ( c ) 所示。混合式结构有一个主控单元和若干受控机器人。 受控机器人和主控单元以及受控机器人之间都有通信。主控单元接收用户发来的 任务，然后根据环境和机器人状态信息，对任务进行分配，同时协调受控机器人 之间的冲突等问题，但不具体的控制受控机器人的运动。受控机器人接收主控单 元发来的任务，根据自身的状态和局部环境信息做出相应的行为，同时把相关信 息发送到主控单元。 6 硕士学位论文 多机器人系统及编队控制 2 2 机器人在群体中的感知和通信 在多机器人系统中，机器人做出行为决策是基于环境信息、自身状态和其他 机器人信息，而这些信息的获得要靠机器人自身的感知和与其他机器人的通信来 完成。 其中感知包括对环境的感觉和对感觉到的信息的理解两个方面。机器人根据 自身传感器获取环境信息，然后对信息有效地处理，从而“理解这些信息的意 义。同时在执行一些复杂任务时，机器人需要协作，这时各机器人不仅要处理自 身传感器获得的信息，还需要将自身传感信息与其他机器人传感器信息融合以获 取对外部环境正确的和较全面的理解。这时多机器人系统的感知需要解决信息的 融合和信息的理解问题，以及如何通过协调协作实现对外界环境信息乃至机器人 自身信息的全面了解。 各机器人通过感知，可以估计协作者的意图和动作效果，从而降低对通信的 依赖，快速响应环境变化，更新和维护系统模型田】。 各机器人要获取其他机器人的意图、状态、对环境的感知信息、动作策略以 及协调协作，都需要与其他机器人进行通信，才能进行有效地磋商，协作完成任 务。机器人之间的通信可以分为隐式通信和显式通信两类。隐式通信【2 3 】指多机 器人系统通过外界环境和自身传感器来获取所需的信息并实现相互之间的协作。 显式通信【2 4 】指多机器人系统利用特定的通信介质，通过某种共有的规则方式实 现各机器人间数据、信息的转移和交换。隐式通信下多机器人系统可以完成一些 低层次协作任务，但是却无法完成高级协调协作策略。而显式通信通过信息交换， 可以完成高级协调协作策略，但存在通信的实时性差、可靠性差、通信延迟、带 宽限制等问题，在数目庞大的机器人系统中显得尤为突出。 隐式通信与显式通信是多机器人系统各有优缺点，因此在设计多机器人系统 的时候，常常把隐式通信运用在机器人之间的底层协调，显式通信用在隐式通信 无法解决的冲突或死锁问题，利用少量的通信和协调工作就可以解决，这就充分 利用了两种通信的优点，实现多机器人系统灵活地应对各种动态未知环境，完成 复杂的任务。 2 3 多机器人编队控制的基本问题 多机器人编队控制的基本问题包括队形问题、编队控制的基本要求两个问 题。 多机器人队形问题包括队形形成和队形控制两方面。队形形成主要研究如何 7 硕士学位论文 多机器人系统及编队控制 使多机器人系统由一个杂乱的状态形成一个整体具有规律性或者符合设计者要 求的稳定状态。而队形控制问题主要研究机器人系统在朝着目的地行进的过程 中，既要遵循一定的队形约束，又要适应当前环境的约束( 如障碍物或空间的物 理限制) 的控制技术。在多机器人编队控制系统中，首先要建立一个指定的几何 队形，设计合适的队形形成方法，命令各机器人到指定的地点形成一个队形。其 次要设计队形控制方法，使得系统能够按要求到达目的地。 编队控制对队形形成的基本要求为：在队形形成过程中能够避开障碍物和其 他机器人，在更短的时间内形成一个稳定的几何队形。在队形控制的要求则为： 多机器人系统在向目的地前进的过程中，能够在遇到障碍物和其他机器人暂时离 队并且能够尽快恢复原队形，或根据环境和任务的需要切换队形，在更短的时间、 更高的队形保持率情况下到达目标点。 2 4 多机器人编队控制方法 对多机器人系统的编队控制方法分为集中式控制和分布式控制，而集中式控 制存在固有的缺点，应用较少。分布式多机器人编队控制方法很多，主要包括基 于行为的方法、领航跟随者方法、虚拟结构法和人工势场法等。 2 4 1 基于行为的方法 基于行为方法的基本思想是为每个机器人预先设定几种理想的基本行为，然 后在各个时刻进行控制决策，将基本行为的加权合成作为该时刻的控制动作。这 些基本行为可能包括目标搜索、机器人避碰、机器人避障和队形保持等，还包括 其他一些基本行为。b a l c h 与a 呔i i l 【2 5 】首次提出将单机器人行为控制法用于多机 器人编队控制，他们在文中为每个机器人预设几种理想的基本行为，将基本行为 速度的加权平均合成的速度作为该控制动作。 文献【l o 】根据所要实现的系统，定义了4 种基本行为：驶向目标行为、保持 队形行为、避免与静态障碍物碰撞行为、避免与其它机器人碰撞行为。输出行为 是基本行为按照一定的机制综合出来的。目前主要有三种行为综合方法【2 5 。2 6 】： ( 1 ) 加权平均法。 输出向量是各个基本行为向量和相应权重乘积的矢量和，权值的大小对应相 应行为的重要性，矢量和归一化后作为机器人的行为输出。 ( 2 ) 行为抑制方法。 对各个基本行为按一定的原则规定优先级，没一时刻选择高优先级行为的输 出作为机器人的输出，即高优先级的行为抑制低优先级的行为。 硕士学位论文 多机器人系统及编队控制 ( 3 ) 模糊逻辑法。 根据模糊规则综合各行为的输出，从而确定机器人的输出。 文献【2 7 1 采用的基于行为编队控制方法，给每个机器人动态分配其在队形中 的理想位置，并用局部通信来提高性能，从而实现机器人队形的形成和保持，并 能完成各种队形的切换。文献【2 8 】【2 9 】中，作者将复杂的队形运动分解为一系列基 本的队形运动，即平移( t r 距s l a t i o n ) 、旋转( r o t a t i o n ) 和扩展收缩 ( e x p 肌s i 伽c o n 吼舐o n ) ，并且基于行为控制的基本思想，提出了队形控制的关 联动态法( c 0 u p l e dd 删c s c o n 们lm e 川) ，即将目标搜索和队形保持相结合 提出了综合目标函数，采用“y a p 城o v 方法设计了稳定的控制律。 基于行为的编队控制方法的优点是当机器人出现多个相互冲突的目标时，可 以很容易导出控制策略，而且系统存在明显的队形反馈和较好的柔性。缺点是其 群体行为是“隐现出来的，难以明确定义，而且用数学方法分析控制行为比较 困难，队形的稳定性难以保证。 2 4 2 领航跟随者法 领航跟随者( l e a d * f o l l o w 砷控制法的基本思想是：在多机器人组成的群体 系统中，将某个机器人被指定为领航者，其余机器人作为它的跟随者，跟随者以 一定的距离间隔跟踪领航机器人的位置和方向。此外还可以在群体系统中指定多 个领航者，但整个系统只有一个总领航者。根据跟随机器人与领航者之间的相对 位置关系，就可以形成不同的网络拓扑结构，也就是说，可以形成不同的队形。 跟随领航者法中，由领航者发送自身运行参数给跟随者，跟随机器人根据领 航者的参数自行计算自身的运动参数，从而控制自己对领航者的跟随。因此在编 队过程中，仅给定领航者的行为或轨迹，就可以控制整个机器人群体的行为，使 得系统具有更好的可扩展性、更灵活的运动策略和计算的并行性。该方法主要缺 点是没有队形反馈，如果领航者在运动时过快可能导致落后机器人离队，另外整 个系统过重依赖于领航者机器人，如果领航者机器人发生故障，整个系统就会瘫 痪。 - 针对该方法的缺点，一些文献提出了相应的解决办法。文献【3 0 j 利用反馈线 形化实现了非完整约束机器人的轨迹跟踪控，文献【3 l 】设计了平滑时变反馈控制 法构成一个开环链式的队形，文献【3 2 l 中引入了合作的方法，即f o l l o w e r 的运动不 仅由自身决定，还受到其它机器人的影响。文献【3 3 】针对l e a d 昏f o l l o w e r 多机器人 系统队形控制中的f o l l o w e r 离队问题，采用了基于条件反馈机制的 l e a d e r - f o l l o w e r 多机器人编队控制方法。对于第二个缺点，文献p 4 j 提出了动态 l e a d e r 更换法来克服l e a d e r 失效的缺点，当l e a d e r 失效时，按一定的规则安排他 9 硕士学位论文 多机器人系统及编队控制 机器人作为l e a d e r 。 2 4 3 虚拟结构法 l e 丽s 和1 锄【3 5 】首先提出了虚结构法的概念，其基本思想是将全体机器人的 队形看作是一个类似刚体的结构，每个机器人是虚拟结构上相对固定的一点。当 刚体在空间中运动时，刚体上的各点位置之间的相对位置保持不变。每个机器人 在向目标点运动过程中可以暂时离队，并且在理想目标点仍可以以一定的自由度 来改变自己的方向。该方法适用严格队形保持的系统，理论上在避障时可以保持 队形。 虚拟结构法的算法为：首先调整虚拟结构位置使其与当前的机器人位置尽量 匹配，然后根据局部或全局生成的轨迹，微调虚拟结构的位置和方向，得到每个 机器人的期望位置和方向，最后机器人确定各自的轨迹并调整速度以跟踪虚拟结 构上的目标位置点，如此循环往复 虚结构法的优点是能够很容易的指定机器人群体的行为，可以进行队形反 馈，能够取得稳定的队形控制，较高精度的轨迹跟踪效果，有一定的智能性，机 器人之间没有明确的功能划分，不涉及复杂的通信协议。其缺点是它要求队形作 为一个虚拟的结构，以至于无法考虑整体的避障问题，并且该方法通常是集中式 控制，需要机器人与集中控制站之间的大量通信，不便于实现。这就大大限制了 它的应用范围，缺乏灵活性和适应性。 为了克服以上的缺点，虚拟结构法通常与其它方法结合使用以达到更优的控 制效果，q i n “和z h o n g p i n gj i 锄寸3 6 】将使用虚拟结构法和人工势场法结合进行无 碰的队形控制，通过虚拟结构法，每一个机器人被指定去追踪一个虚拟的局部领 航者v l l ( v i m 脚l o c a ll e a d 神以维持队形的外形，而为了实现组群内部的避碰目 的，各个机器人的运动都被限制在v l l 周围的一个特定区域。 2 4 4 人工势场法 人工势场法思想类似于电子在正负电荷产生的电场中运动。将目标看作吸引 点，障碍物看成排斥点，机器人沿吸引点和排斥点产生的合力方向运动。它构造 一个叫做势能函数的标量函数，使得机器人的目标位姿对应于其最小值，障碍物 区域对应于一些较大的值，在任何其它的位置，势能函数都是向机器人目标位姿 单调递减的。通过控制器的设计，使机器人沿势函数的减小方向运动，最终到达 目标点。基于人工势场的编队控制方法的关键是如何设计势函数和如何避免局部 极小点。， 1 0 硕士学位论文多机器人系统及编队控制 人工势场法由鼬l a 虹b f 3 刀于1 9 8 6 年提出，它的基本思想是机器人在一个虚拟 的力场中运动，障碍物被斥力势场包围，其产生的排斥力随机器人与障碍物距离 的减少而迅速增大；目标点被引力势场包围，其产生的吸引力随机器人与目标点 的接近而减少；在合力的作用下机器人沿最小化势能的方向运动。这样，不论机 器人处于自由空间的任何位置，只要有路径存在，它都能通过势能值的负梯度方 向找到目标位姿。对应于障碍物的区域有较大的值，可以保证生成路径的无碰性 人工势场法的特点是：概念清晰，控制方法简单，函数形式多样，队形形成 容易，易扩展规模，且易于实现队形稳定问题( f 伽m a t i o ns t a b i l i z a 虹o np r o b l 锄) ， 但容易陷入局部极小点。因此需要讨论更一般的机器人模型和研究势函数的结 构，并且要求保证系统的全局稳定性。 针对人工势场法中机器人易陷入局部极小值的缺点，文献【3 8 】提出了一种超 二次型的人工势场法结构来代替传统的二次型势场，保证了多机器人在编队的过 程中有效地避障。此为还有区域隔离法、人为随机波动引入法等措施。为了保证 系统全局稳定性，可以采用l e a d * 如l l o w e r 的队形结构，并对势函数严格采用文 献【3 9 】中提出的控制模型，使得领航机器人带领其他机器人准确到达目标。 2 5 多机器人队形控制的相关问题 2 j5 1 多机器人编队的队形 在多机器人编队过程中，需要解决很多问题。其中，首先要解决的问题是机 器人队形的选择问题。选择合理的队形，对机器人系统执行任务的性能有着很大 的影响。例如在障碍密集的地区，柱形可以灵活地避开障碍物。通常，机器人编 队的基本队形有线形、柱形、菱形和楔形这四种对称的形状2 5 1 ，如图2 2 所示： ooo o 线形 oo 2 5 2 队形参考点的选取 图2 2 机器人编队基本队形 oo oo 楔形 要保证机器人都能在规定的队形中，必须有队形的调节机制。多数情况下， o o 觌 o o o o 觇 硕士学位论文 多机器人系统及编队控制 机器人并没有环境的全局信息，因此每个队形中都要选取参考点。只要队伍中的 机器人知道同该参考点的相对位置，就可以保持期望的队形。根据不同的需求， 参考点的选取有三种方法【2 5 1 ，如图2 3 所示。 叼 中心参考领航参考 邻居参考 图2 3 队形参考点 ( 1 ) 以编队的几何中心为参考点。根据每个机器人的位置，计算出当前的 几何中心，每个机器人都保持同该几何中心的相对位姿，同样也可以保持队形。 该方法要求所有机器人知道其他机器人的位姿信息，通讯量较大。 ( 2 ) 以领航机器人为参考点。从机器人队伍中选取一个机器人作为领航机 器人，其他机器人以该机器人为参考点，只需保持自己与该机器人的相对位姿和 期望值相同，就可以保证编队的队形。由于领航机器人没有参考点，所以不考虑 队形约束，队形的保持由跟随者实现。一般情况，领航机器人在队形的最前位置， 因为该位置受到其他机器人影响较少。 ( 3 ) 以相邻机器人为参考点。当编队队形确定后，每个机器人可以保持同 队形中相邻机器人的相对位姿来达到编队的目标。同前两个方法比较，除了不被 选作参考点的机器人不需要广播信息之外，其他机器人都要向环境中发出自己的 位姿信息，信息量自然较大。另外，为了识别邻居，对邻居的标识信息也需要通 过通讯来告知其他机器人，因此该方法在通讯上消耗了大量的时间。通常，该方 法是配合其他传感器进行的。例如利用视觉传感器可以方便的识别邻居机器人， 并不需要任何的通讯标识。配合距离传感器，也可以得到邻居机器人的相对位姿。 2 5 3 队形的表示方法 在多机器人队形描述中，一般以图的方式表示编队，图中的结点表示机器人， 节点之间的连线表示两机器人之间的关系。在文酬3 9 1 定义了矩阵s 来表示队形 的形状，定义f 表示不同的编队参考矩阵。 队形矩阵s 表示为 球2 1 【- 九风j 矩阵s 为n 行2 列矩阵，力和肛分另i j 表示队形中的各个机器人位置相对于领航 1 2 硕士学位论文 多机器人系统及编队控制 机器人的角度和距离，n 表示队形中共有位置的个数，即为机器人的个数。矩阵 中每一行表示一个机器人相对其领航者的参数。第一行表示领航者机器人，因此 参数为 oo 】。 参考矩阵f 为 ，= i 仍。d 。d 尺刍2 仍，d厶，d r d 9 n 矗l n 矗 矩阵f 中每一行表示一个机器人的参数，第一列表示本行所代表的机器人所 要跟随的机器人的编号，第二列仍d 表示相对于跟随人所要保持的方向角度，第 三列d 表示相对于领航机器人所要保持的距离。矩阵中第一行规定为领航者的 参数，其值就固定为【o o o 】，这样就可以清晰地描述多机器人系统中不同的队形， 当机器人队形需要变换时，只需改变一下矩阵中的参数即可。 2 5 4 多机器人编队性能评估 为了验证编队算法性能的好坏，需要对编队算法进行评估。对队形算法优劣 的评估主要有三个指标【3 8 】： ( 1 ) 路径长度比率。该比率定义为队形的平均行走距离同初始位置到达目 标位置直线距离的比值。该比值可以用来衡量算法的避障性能。如果没有障碍物， 该比值为l ，没有意义。 ( 2 ) 队形维持率。在整个编队行进过程中，机器人在期望位置的时间所占 的比例。与之相对的概念就是个体偏移率，即机器人在编队过程中不在期望位置 的时间比例。该数值可以用来评价算法在避障过程中，队形保持的性能。 ( 3 ) 运行时间。指机器人团队到达目标并且形成队形所用的时间。该指标 用来描述机器人团队避碰过程的有效性。 2 6 队形控制的容错性和稳定性 在实体机器人的控制中，机器人出现故障的情况应该充分考虑到的，也即机 器人的容错控制。容错控制是指在多机器人系统完成任务过程中，在某个机器人 出现错误后，应能把他的任务分配给其他机器人来完成，让其他机器人来顶替该 机器人的位置，并且要保证出现故障的机器人在恢复正常后，能自觉地找到自己 的新位置，不影响整个系统任务的完成。文献f i s 】对机器人系统容错性做了深入 研究。 硕士学位论文 多机器人系统及编队控制 稳定性是队形控制中的一个重要方面，在多机器人编队控制中必须保证最后 队伍的收敛性和稳定性。在多机器人系统编队控制中，不仅要保证队形开始时是 稳定的，而且在发生故障、重新调整队形后，队形仍然是相对比较稳定的。 本论文中的队形控制设有反馈机制，虚拟领航者机器人每一时刻都在监控跟 随机器人的状态。如果某一机器人出现故障或从故障恢复正常，虚拟领航者就根 据需要决定是否重新调整队形矩阵，其他跟随机器人根据队形矩阵决定自己的运 动。 2 7 本章小结 本章对多机器人编队系统从总体上进行了阐述，对多机器人系统中可能遇到 的体系结构、感知和通信、编队的基本问题、编队控制的几种主要方法、队形控 制的相关问题以及系统的容错性和稳定性进行了分析，并说明了本论文将要采用 的方法。对多机器人编队系统从总体上的概述，为后面章节的多机器人编队控制 方法分析和设计提供了基础。 1 4 硕士学位论文粒子群优化算法及其改进 第三章粒子群优化算法及其改进 在基于行为的多机器人编队控制中，基本行为控制参数值的选择决定了机器 人能否有效地完成编队，而行为参数值的选择事先很难确定。在静态环境中，可 以利用粒子群优化算法确定较优的行为控制参数值。而在较大规模的多机器人系 统中，要优化的行为控制参数很多，即优化目标维数高，目标函数极值多，采用 标准的粒子群优化算法及后来改进的粒子群算法，很难快速收敛到全局最优值。 为此，本章对基本粒子群算法做了进一步改进，设计了个面向高维目标函数的 自适应粒子群算法( o r i e i l t e dh i g hd i n l 肌s i o na d a p t i v ep s o ，o h d a p s o ) ，使其适 合高维多极值点目标函数的优化。 3 1 基本粒子群算法 粒子群优化算法( p a n i c l es w a mc i p t i i n i z 撕0 n ，p s o ) 是k 锄e d y 和e b e r h a r t 于1 9 9 5 年提出的一种群体自适应搜索的进化优化算法【柏】，其思想来源于人工生 命和进化计算理论。p s o 算法要调整的参数较少，易于实现，且可进行并行计算 和无梯度计算，有较好的全局搜索能力。因此该算法一提出就获到了众多学者的 重视，并已经在神经网络的训练、电力分布网优化、结构优化、函数优化、生物 化学处理、模糊系统控制和生物系统中系统辨识等领域取得了大量的研究成果。 在基本粒子群算法中，速度迭代公式包含“历史速度”、“认知速度 和“社 会速度 三个部分。“历史速度是为了保证算法的全局搜索能力。“认知速度 使得微粒不断探索自己的最优位置，这样就不断的探索局部最优，保证了种群多 样性。“社会速度 使得种群向当前历史最优收敛，并且增加了收敛速度。 基本粒子群算法描述如下： 在算法中优化目标记为n 维，粒子个数为m ，第i 个粒子的当前位置为 五= ( 薯。，薯：，气) ，当前速度为m = ( 。，y f ：，) ，当前历史最优位置为 b = ( 易。，a ：，) ，即粒子i 所经历的具有最好适应值的位置。对最小化问题而 言，目标函数值越小，其对应的适应值越好，即对应的位置越优。设当前群体所 经历的当前最优位置为岛= ( 以，岛：，) ，称为全局最优位置。 p s o 的进化方程为 屹o + 1 ) = 缈o ) ( f ) + c 1 ( 助( f ) 一而( f ) ) + c i 眨( ( f ) 一而( f ) ) ( 3 1 ) 而o + 1 ) = 峋( f ) + 而( f ) ( 3 2 ) 硕士学位论文 粒子群优化算法及其改进 其中t 为进化代数，下标“j 表示微粒的第j 维，r 1 和r 2 为两个独立的、 服从区间 o ，1 】上均匀分布的随机数；d 和c 2 为加速权重，c l 调节微粒飞向自身 最优位置，c 2 调节微粒飞向全局最优位置，通常c l = c 2 - 2 0 5 。为了减少在进化 过程中微粒离开搜索空间的可能性，将限定在一定范围内，即吻【- ，】。 w 为惯性权重，用来控制历史速度对当前速度的影响程度。初始时w 取较大的 值以加快全局搜索，随后w 逐渐减小以获得更为精细的结果。p s o 算法步骤为： s t e p l ：依照初始化过程，对微粒群的速度和位置初始化。 s t e p 2 ：计算每个微粒的目标函数适应值。 s t e j p ：对于每个微粒，将其适应值与所经历过的最优位置只的适应值进行比较， 若较好，则将其作为该微粒的当前最优位置。 s t e p 4 ：对于每个微粒，将其适应值与群体所经历过的最优位置的适应值进行 比较，若较好，则将其作为群体的全局最优位置。 s t e p 5 ：根据式( 3 1 ) 和式( 3 2 ) 对每个微粒的