（模式识别与智能系统专业论文）面向任务的多机器人系统的组织设计研究.pdf

博士论文面向任务的多机器人系统的组织设计研究 摘要 随着计算技术的发展，多机器人技术研究的深入以及应用领域的不断扩大，机 器人应用的数量规模也在不断扩大，国际上已经开始研究1 0 0 个以上机器人组成团 队时的协调合作问题。随着机器人数量的增加，机器人之间的通信压力和协调难度 将会加大，使得关于机器人组织的形成以及基于机器人组织的求解机制等问题的研 究变得越来越重要。 本论文结合总装备部预研基金、国防科工委基础科研项目以及江苏省自然科学 基金等项目，面向任务对大规模机器人组织设计中的相关问题进行了研究，包括多 机器人系统组织的研究框架、个体机器人体系结构设计、面向任务的机器人团队组 织模型、组织的形成方式、组织演化的模型分析、团队运行的监控等。论文所做的 主要工作和研究成果如下： l 基于机器人面向应用的观点，从构建多机器人系统的目的出发，提出多机 器人系统的研究可以从全局层、局部层和个体层三个层次来进行，并且利用给出的 三层控制模型划分了该领域中已提出的系统性能术语。 2 在动态环境下，面向任务的多机器人系统中的个体机器人体系结构，应该 突出机器人的实时反应能力、行为自主决策能力以及合作能力，而这三点在已知的 典型体系结构中没有全面地表现出来，特别是对行为决策能力。为此本文提出了基 于行为的五层混合式机器人体系结构，分别是系统监控、组织协调，行为决策、行 为控制、反应五个层次。 3 将机器人移动过程中的行为与它到任务阃的距离相联系，给出了“状态角 色”的概念，提出根据状态角色的不同而发送不同的信息，从而减少机器人之间交 互的通信量；另外，状态角色之间设置有优先级，便于机器人对任务的选择以及实 现管理者的更换。 4 给出多机器人的树型层次化组织模型。根据任务将机器人划分为不同的任 务小组，一方面降低了机器人间的协调难度，便于对多机器人进行管理。另一方面， 减少了彼此间的通信量。在机器人组织基于合同网的形成中，充分考虑机器人在动 态环境下运行时的不确定性，提出机器人在同时满足多个任务需求能力的前提下， 进行任务组的投标时，不但要考虑距离，还应综合考虑任务、环境以及自身状况等 各种因素，并且给出了使用多属性决策矩阵来进行任务组选择的算法。管理员招标 时，除了考虑机器人的能力外，还要考虑机器人对任务组选择的不确定性，给出了 基于熵的组成员筛选办法，以减少维护组成员的不必要开销。从某种意义上讲完善 摘要 博士论文 了基于合同网协议的招投标过程，提高了合同网协议的招标效率以及任务的完成质 量。 5 针对目前国内外关于机器人行为、团队形成的研究大都停留在定性分析阶 段，缺乏对团队合作随环境、任务需求变化的动态过程描述及预测。本文给出两个 分析模型，不仅从定性而且还从定量上对机器人的行为、系统的动态演化过程进行 预测。一个模型是利用有限m a r k o v 链和进化计算，全面描述机器人团队形成的动 态演化模型。通过该模型，操作者不仅能整体、动态地把握机器人团队的合作状况， 同时，还能够依据模型的描述，对机器人团队面临新的任务需求时的合作关系和行 为做出预测。另一个模型是机器人选择任务组行为模型。利用该模型可以揭示机器 人任务组选择行为的演化规律，从而可以为系统提供实时信息，制定合理策略有效 引导个体机器人的任务组选择行为。 关键字：多机器人系统大规模机器人团队机器人体系结构组织结构任务分配 合作通信模型 博士论文 面向任务的多机器人系统的组织设计研究 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n ds u b s t a n t i a lr e s e a r c ho f m u l t i - r o b o ts y s t e m ( m r s ) a sw e l la st h ee x p a n s i o no fi t sa p p l i c a t i o n , t h ea m o u n ta n d s c o p eo fr o b o ta p p l i c a t i o na r ec o n t i n u a l l ye x p a n d i n g t h er e s e a r c ho nc o o r d i n a t i o na n d c o o p e r a t i o no fr o b o tt e a mt h a tc o n s i s to fo v e r1 0 0r o b o t sh a sb e e nc o n d u c t e d d u et oa l l i n c r e a s ei na m o u n to fr o b o t , t h ed i 筒c u l t yo fc o m m u n i c a t i o na n dc o o r d i n a t i o na m o n g r o b o t sw i l la l s oi n c r e a s e i tb e c o m e sm o l ei m p o r t a n tt os t u d yi n t ot h ei s s u e ss u c ha st h e f o r m a t i o no f r o b o to r g a n i z a t i o na n dt h er e s o l v i n gs y s t e m , e r e b a s e d0 1 1p r e r e s e a r c hf o u n d a t i o no fc p l ag e n e r a e q u i p m e n td e p a r t m e n t , b a s i c r&d p r o j e c to fc o m m i t t e eo fd e f e n s es c i e n c ea n di n d u s t r y , a n dn a t u r es c i e n c e f o u n d a t i o no fj i a n g s up r o v i n c e , t h o s es t u d yf o c u s e so ni s s u e sr e l a t e dt ot h ed e s i g no f l a r g e - s c a l er o b o tt e a m s ，i n c l u d i n gf r a m e w o r ko fm r s ，a r c h i t e c t u r ed e s i g no fi n d i v i d u a l r o b o ts y s t e m ，o r g a n i z a t i o nm o d e lo fr o b o tt e a m s ，e s t a b l i s h m e n to fo r g a n i z a t i o n , m o d e l a n a l y s i so fo r g a n i z a t i o ne v o l u u o n , a n dm o n i t o r i n ga n dc o n t r o lo ft e a mo p e r a t i o n , e t e t h ep r i m a r yw o r ka n da c h i e v e m e n t s 盯ca sf o l l o w s ： 1 o nt h eb a s i so f r o b o ta p p l i c a t i o n , i no r d e rt oe s t a b l i s hm r s t h er e s e a r c hc o u l db e c o n d u c t e df r o mt h r e ea s p e c t s ：g l o b el e v e l ，l o c a ll e v e la n di n d i v i d u a ll e v e l t h e r e f o r et h e s y s t e mp e r f o r m a n c eh a sb e e nc l a s s i f i e di nt e r m so f t h r e el e v e lm o d e l 2 a saw e l ld e s i g n e dt a s k - o r i e n t e dr o b o ta r c h i t e c t u r e ，i ti se s s e n t i a lt oe m p h a s i z e t h ec a p a b i l i t yo fr o b o t sr e a l - t i m er e a c t i o n , m a k i n gd e c i s i o na n dc o o p e r a t i n gw i t ho t h e r s h o w e v e rt h e s ea l en o tw e l la d d r e s s e di nat y p i c a la r c h i t e c t u r e ，e s p e c i a l l yt h ec a p a b i l i t y o fm a k i n gd e c i s i o nb yr o b o ti t s e l f i nt h i sr e s e a r c hf i v el e v e l so fr o b o th y b r i ds t r u c t u r e w e r ep r e s e n t e d , n a m e l ys y s t e mm o n i t o r i n gl e v e l , c o o r d i n a t i o nl e v e l ，d e c i s i o n - m a k i n g l e v e l ，a c t i o nc o n t r o ll e v e la sw e l la sr e a c t i o nl e v e l 3 i ts t u d i e st h em e a s u r e st o 姒u ps t a t er o l e sf o rr o b o t s a s s o c i a t i n gt h eb e h a v i o r o fr o b o ti nm o v i n gw i t ht h ed i s t a n c e sb e t w e e ni ta n dt a s k , r o b o tw i l ls e n dd i f f e r e n t s i g n a l sa c c o r d i n gt od i f f e r e n ts t a t er o l e s ，t h e r e f o r er e s u l t si nar e d u c e dt h ew o r k l o a do f c o m m u n i c a t i o n i na d d i t i o n , p r ii sa l s os e tu pa m o n gd i f f e r e n tr o l e ss ot h a ti ti se a s yt o c h o o s et a s kf o rr o b o ta n dt os h i rm a n a g e r 4 t h eo r g a n i z a t i o n a lm o d e lo fm r si sd e s c r i b e d s e p a r a t et a s kt e a m sa r ea s s i g n e d s ot h a to no n es i d ei tw i l lr e d u c et h ec o m p l e x i t yo fc o o r d i n a t i o na n dp r o m o t er o b o t 1 i i a b s t r a c t 博士论文 m a n a g e m e n t ；o nt h eo t h e rs i d ei tc o u l dr e d u c et h ew o r k l o a do fc o m m u n i c a t i o n g i v i n g f i i l ic o n s i d e r a t i o nt ou n c e r t a i n t ye h a r a c t e r i s t i c so fr o b o t si nd y n a m i cc h c u m s t a n c e s a n d o nt h ep r e m i s eo ff u l f i l l i n gs e v e r a la s s i g n m e n t ss i m u l t a n e o u s l yw h e nb i df o ra s s i g n m e n t s ， n o to n l yt h ed i s t a n c e sb u ta l s ot h et a s k , c o n d i t i o na n ds e l f - s t a t u ss h o u l db ec o n s i d e r e d c o m p r e h e n s i v e l y t h ec h o i c eo ft a s k t e a m si s c o m p l e t e db ym u l t i p l ea t t r i b u t e s d e c i s i o n - m a k i n gm a t r i x w h e na d m i n i s t r a t o ri n v i t e sb i d d i n g ，c a p a b i l i t yo fr o b o t sa n d u n c e r t a i n t yo ft a s kt e a m s c h o i c es h o u l db ec o n s i d e r e d n es e l e c t i o ns h o u l dc o n s i d e rt h e e n t r o p yv a l u et or e d u c eu n n e c e s s a r ys p e n d i n go fm a i n t a i n i n g i ti m p r o v e st h eb i d d i n g p r o c e s sa n dt h ee f f i c i e n c ya n dq u a l i t yo f t h i sp r o c e s s 5 a tp r e s e n gm a j o r i t yr e s e a r c ho nr o b o ta c t i o na n dt e a mf o r m a t i o nq u a l i t a t i v e a n a l y s i so n l y t h ed e s c r i p t i o na n df o r e c a s to fd y n a m i cp r o c e s so ft e a m sc h a n g e dw i t h c o n d i t i o n sa n dt a s ka l el a c k e d t l l i sa r t i c l ep r e s e n t st w oa n a l y s i sm o d e l sa n df o r e c a s tt h e r o b o tf o r m a t i o na n dd y n a m i cs y s t e me v o l u t i o nb yq u a l i t ya n dq u a n t i t y o n eo ft h e m c o m p r e h e n s i v e l yd e s c r i b e dt h ed y n a m i ce v o l u t i o no fr o b o tt e a m sb yl i m i t e dm a r k o v c h a i na n de v o l u t i o n b yw i t ht h i sm o d e l ，o p e r a t o r sc a nm o n i t o rt h eo p e r a t i o no f t h er o b o t t e a m f u r t h e r m o r eb e c a u s et h ec u r r e n ts t a t u si sw e l lu n d e r s t o o d , t h et e a mm e m b e r s r o l e s a n db e h a v i o r sa r ep r e d i c t a b l ew h e nn e wt a l ka p p e a r s t h eo t h e rm o d e li sar o b o t b e h a v i o rm o d e lf o rt h ec h o i c eo ft a s kt e a m s w i t ht h i sm o d e l i tc a nr e v e a lt h er u l e so f r o b o tb e h a v i o rf o rc h o o s i n gt a s kt e a m s t h e r e f o r ei tc a no f f e rt h er e a li n f o r m a t i o nf o rt h e s y s t e ma n dm a k et h eo p t i m a d e c i s i o nt og u i d et h ei n d i v i d u a lr o b o t sb e h a v i o ro fc h o i c e t ot a s kt e a m s k e y w o r d s ：m u l t i r o b o ts y s t e m s ，l a r g e - s c a l er o b o tt e a m s , r o b o ta r c h i t e c t u r e ，o r g a n i z a t i o n a l s t r u c t u r e ，a l l o c a t i o no f t a s k , c o o p e r a t i o n , c o m m u n i c a t i o n , m o d e l i v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：口舜1 3 r 砖b 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的全部或部分内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的全部或部分内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：0 ；年，2 月日 博十论文 面向任务的多机器人系统的组织设计研究 1 绪论 随着多机器人技术研究的深入，机器人应用领域的不断扩大，对多机器人实际 应用的数量规模也提出了新的要求，一些研究机构已经开始大规模机器人系统的研 究。本章从多机器人系统的组织设计中需要解决的问题、多机器人系统中任务的分 类、国内外代表性的实验室及他们的在研项目、多机器人系统的主要应用等方面进 行了综述。特别指出在复杂动态环境下的大规模机器人团队的组织合作研究，将成 为多机器人系统研究的主要内容之一 1 1 引言 多机器人系统( m u l t i p l e r o b o t s y s t e m 简称m r s ) 的研究始于2 0 世纪8 0 年代。 随着机器人应用领域的不断拓展、机器人工作环境复杂度以及任务的加重，对机器 人的要求不再局限于为操作者提供简单服务的个体机器人。与个体机器人相比多机 器人系统具有更多的优势【“5 】： ( 1 ) 具有更强的功能。有时由于个体机器人功能的不足，完成某些任务是不可 能的，但是却可以利用多个机器人的合作来完成这些任务。可以把复杂的任务分解 成多个简单的子任务，利用多个机器人团队协调工作，有效地完成任务；另外，多 机器人系统可以由不同功能的机器人组成，某一机器人无法实现的工作可以交给其 它可以胜任的机器人去做，多机器入系统比个体机器人具有更高的柔性；总之，多 机器人不仅能高性能地完成个体机器人能够完成的任务，而且可以完成个体机器人 无法完成的工作，具有比个体机器人强得多的任务处理能力。 ( 2 ) 具有更高的效率。完成某些任务，使用个体机器人可能会花费大量的时间， 而利用由多个机器人组成的群体，由于多个机器人执行任务的并行性，将会大大节 省完成任务的时间。例如机器人可分布在不同的区域内同时工作，也可以在不同分 布时间内执行任务：另外，在一个区域较大的环境中，多个机器人分布在环境中， 各自感知周围的环境，通过共享感知到的信息，大大扩展了机器人系统对环境的感 知范围。 ( 3 ) 具有更强的鲁棒性。利用机器人数量上的冗余，能提高整个系统的可靠性。 当个体机器人工作环境发生变化或系统局部发生故障时，多机器人之间通过其固有 的自组织能力及合作机制可以重新确立合作关系，故障机器人的功能可以完全被别 的机器人所替代，因此，多机器人系统增强了整个机器人群体在完成任务时的冗余 性和鲁棒性。 。 第一童绪论博士论文 ( 4 ) 具有较低的造价。对复杂任务的操作，如果设计一个复杂的个体机器人系 统来完成该任务，则成本太高、制造难度较大且难以实现。而为完成该任务，制造 多个简单机器人的成本，设计难度远远低于制造这样一个复杂机器人。 随着机器人技术的发展，多机器人技术研究的深入，机器人应用领域的不断扩 大，对多机器人实际应用的数量规模也提出了新的要求。从两、三个机器人组成的 多机器人系统发展到1 0 0 个机器人组成的大规模机器人团队( l a r g e s c a l er o b o t t e a m s ) ，甚至非常大规模机器人团队( v e r yl a r g e s c a l er o b o tt e a r a s ) 。随着机器人系 统中机器人数量的增加，机器人之间的通信压力和协调难度将会增加，使得关于机 器人组织的研究以及基于机器人组织的求解机制等问题的研究越来越重要。这些大 规模的多机器人系统如何能在真实、复杂的环境下，有效合作，完成不同的任务， 已成为许多大学、研究机构新的研究热点 6 4 1 。本文主要针对这种数目较多的多机器 人系统组织设计中的相关问题进行研究。 1 2 多机器人系统的组织设计研究中的一些相关问题 目前有关多机器人系统的定义还未形成统一的观点，多机器人系统主要从体系 结构、协调机制、任务分配、通信、学习等方面进行研究【5 】，而对多机器人系统的 组织简称机器人组织( r o b o t o r g a n i z a t i o n ) 研究的较少。多机器人组织主要研究多 机器人之间的组织形式，形成组织的方法。其中组织中多机器人之间、机器人与领 导、随从等角色间的关系与交互是多机器人组织研究中的关键问题。 下面我们就多机器人系统的组织设计中将要涉及的一些关键问题，从不同的侧 重面，对相互关联的部分作一简要的介绍。内容包括多机器人系统的体系结构、组 织结构、形成组织的方法、任务的分配、通信等问题。 1 2 1 机器人体系结构 机器人体系结构( r o b o t a r c h i t e c t u r e ) 又称为控制结构，主要描述个体机器人的 组成模块、这些模块间的关系以及这些模块间的交互。多机器人体系结构是多智能 体和多机器人领域一个主要的研究内容，许多研究者力求通过设计一个性能优良的 控制结构来解决多机器人系统中的一些问题。目前为止，己经有很多研究者提出了 一些有效的多机器人体系结构并且进行了仿真和实验研究1 9 l ，著名的有： ( 1 ) c a l o u d 等人提出“g o p h e r ”体系结构i l ，该体系结构分为任务分解，任 务分配，运动规划和执行控制四层。任务的分配过程涉及集中处理，由中心任务处 理系统c t p s ( c e n t r a lt a s kp r o c e s s i n gs y s t e m ) 完成。c t p s 首先与所有通信范围内 博士论文 面向任务的多机器人系统的组织设计研究 的机器人进行通信，对所有机器人的运行状态和任务的完成情况进行全面了解。然 后，c t p s 产生计划结构，并将其通知所有的机器人。为此各机器人知道了系统在 完成任务过程中自身的目标，它利用任务分配算法来决定自身的状态角色，并利用 传统的a j 规划技术来实现该目标。利用g o f e r 已经成功地完成了三个机器人进行 推箱子、跟踪等任务。但是系统中限制任何机器人在完成当前任务前不能参与其它 任务的执行。在c t p s 中没有明显的规划机器人如何从错误及失败功能中恢复。这 些限制减弱了资源的优化利用和对动态环境的反应。另外对受限资源的优化利用和 状态角色的确定没有一个明显的解释。 ( 2 ) l e p a l ( e r 开发的a l l i a n c e 分布式体系结构【】，它是一种基于行为，具有 容错和自适应能力的多机器人协调体系结构。个体机器人采用基于行为的控制器， 并将行为扩展为“行为集合”，这些行为集合靠动机( m o t i v a t i o n s ) 模型来帮助机器 人自适应选择动作和行为，从而使机器人去完成其它机器人不能完成的任务或放弃 自己不能完成的任务。虽然在这种体系结构中机器人系统具有容错能力和适应性， 但系统不能够对动态变化的条件作出快速优化的反应。进一步，机器人没有考虑如 何合理地利用受限资源并且对这些资源进行优化。并且不容许新类型的任务被动态 指派。利用这种结构已经实现完成了推箱子、收集圆盘、队形前进等任务。 ( 3 ) l u e t h 和l a e n g l e 提出一个k a m a r a 队的分布式控制结构【1 2 1 ，用于多机器 人协调问题，进行多机器人容错行为和误差纠正的研究。这个分布式式控制结构基 于通用a g e n t 的概念，每个a g e n t 负责机器人中的一个部件，用于协调复杂机器人中 的不同部件。每个a g e m 由一个通信者、头、身体组成，通信者负责通信，头负责 任务的规划和行动的选取；身体处理执行。每个身体有一个或者多个执行部件构成。 尽管没有能力的a g e n t 不能参与协商因此不能被分派任务，但是没有提出任何一种 方法来确保指派给无能力的a g e n t 的任务能够完成。另外，因为资源利用没有优化， 每个a g e n t 要求存有每个机器人上的资源，将灾难性地增加a g e n t s 间的协商。 ( 4 ) t a m b e 提出著名的基于层次反应规划的结构s t e a m t ”】，它建立在联合意图 和共享规划理论基础上，团队的反应能力中加入了联合意图。该模型不依赖特定领 域的知识，具有很好的重用性。为了降低通信开销，设计了基于决策理论的通信选 择机制，以保证联合意图的实现可以在不通信的情况下进行，适于通信资源有限的 环境。目前t a m b e 等人已经在该模型基础上设计了基于协商的c o n s a 模型。 ( 5 ) n o r e i l s 提出了一个包括规划层、控制层和功能层的三层控制结构【1 4 1 。规划 层将任务分解成小的子任务单元，并将这些子任务单元分配给一个机器人网络。控 制层组织机器人执行任务，而功能层提供实际的控制。n o r e i l s 报告了这个体系结构 在多个机器人合作推箱子任务上的实现。其中一个机器人充当领导，其余机器人则 作为跟随者。 3 第一章绪论 博士论文 以及a s a m a 等描述了一个叫a c - t r e s s 的控制结构【l 习，它的协商式控制结构允 许机器人在需要时召集其他机器人帮助：c o h e n 提出了他们的f i r e b o s s 控制体系结 构用以解决合作作战问题1 16 】等等。开发出的这些适合于多机器入系统的机器人体系 结构，大多是层次递阶式控制结构。因为采用分层式合作可以降低规划的复杂性， 提高系统的效率。 事实上，每种体系结构都有其优点，也有一定的局限性，主要是受机器人本身、 任务、环境等诸多因素影响。开发一个机器人控制结构的主要目标是使多机器人系 统具有鲁棒性，可靠性、柔性和协作性。 注意：多机器人体系结构虽然与多机器人系统的组织有关系，结构上有共同点， 但是它与多机器人组织结构是两个概念。例如，多机器人的体系结构事先也许被定 义为固定的层次结构，而多机器人之间的组织结构也是层次的，但是组织结构一般 是变化的，它们之间没有必然的联系。多机器人系统的组织更多地研究机器人间的 交互、合作关系问题。 1 2 2 多机器人系统的组织结构 多机器人的组织结构( o r g a n i z a t i o n a ls w a c t i l r e ) 是为了有效地完成预定的任务如 何把智能机器人联系到一起的一种结构【l ”它是系统中机器人之间逻辑上和物理上 的信息关系和控制关系，以及问题求解能力的分布模式，是整个系统执行协调合作 任务的基础。组织结构确定了机器人在系统中的控制关系与功能关系，也决定了多 机器人系统的运作机制，事关合作效率的高低。从系统设计的角度而言，机器人系 统要有利于个体能力最大程度的发挥和任务的最高效完成。另外，机器人系统面向 的是动态变化的环境，因而系统要对环境有自组织适应能力。 从控制角度看，多机器人的组织结构分为集中式( c e n t r a l i z e d ) 和分散式 ( d e c e n t r a l i z e d ) 两种。在分散式体系结构中，又可分为分层式( h i e r a r c h i c a l ) 和分布的 ( d i s t r i b u t e d ) 。集中式体系结构可用一个单一的主控机器人( l e a d e r ) 来规划，该机器 人具有关于系统活动的所有信息。而分布式体系结构则没有这样一个机器人，分布 式结构中所有的机器人相对于控制是平等的。尽管集中式体系结构具有可能得到最 优规划的优点，但普遍的看法是分散式结构比集中式结构要好，如故障冗余、可靠 性、并行开发的自然性和可伸缩性等。近年来，在分布式体系结构中，为了克服机 器人在实际环境中对环境建模的困难，提高多移动机器入合作系统的鲁棒性和行为 能力，一些学者采用了基于行为的反应式控制体系结构，将合作行为建立在一种反 应模式上，加快了移动机器人对外界的响应，避免了复杂的推理，从而提高了系统 的实时性。 博士论文 面向任务的多机罂人系统的组织设计研究 从个体差异性看，机器人的组织结构有同构个体和异构个体两种结构【1 。同构 个体结构系统中的各机器人的能力是等同的，而异构结构则不同。一般地，异构结 构由于各个体具有不同的能力，使得系统任务分配更复杂，个体之间的通信或建模 更困难。因此，过去很多机器入协调系统的研究是建立在同构结构上，如s w a r m 结构。而近几年来，也呈现一些优秀的结构处理异构个体，如a c t r e s s 和 a i 。i 。i a n c e 。 1 2 3 多机器人系统形成组织的方法 多机器人组织是进行有效合作和协调控制的基础，它也是系统柔性和可靠性的 保证。形成组织的方法主要有两种，一种是静态方法，即当系统设计好后静态地确 定组织，在运行过程中通过通信等手段解决行为一致性问题。另一种则是在运行过 程中动态地创建组织。系统的复杂性和不确定性特征是决定组织结构的两个重要因 素。复杂性包括环境复杂性、任务复杂性及合作复杂性。不确定性包括信息不确定 性、算法不确定性、环境不确定性和行为不确定性等。 自2 0 世纪9 0 年代以来，多智能体系统( m u l t i p l ea g e n ts y s t e m ，简称m a s ) 理论的研究已经成为分布式人工智能研究的熟点，并成为继面向对象方法之后出现 的又一种进行系统分析与设计的强有力的方法和工具。在m a s 中，对多智能体的 组织与合作问题进行了大量研究，提出许多组织形成的方澍嘲。 ( 1 ) 基于协商的合同网协议【1 9 - 2 0 1 当一个a g e n t 发现自己面临的问题难以独立求解或者合作求解更有效时，通过 与其他a g e n t 的协商，将其部分或全部任务委托其他a g e n t 来完成，在他们之间形 成顾客与服务员关系形组织。 ( 2 ) 基于依赖关系的社会推理【2 l 】 通过a g e n t 之间依赖关系的社会推理，发现与其目标有依赖关系的其他a g e n t ， 并与他们形成不同形式的合作组织。 ( 3 ) 基于对策论的联盟形成f 2 2 - 2 3 1 通过联盟效用的计算与分配，依据a g e n t 个体、联盟和群体理性原则，在a g e n t 之间形成不同的联盟。 ( 4 ) 基于价格调控的市场机制 2 4 - 2 5 】 a g e n t 根据自己的能力与喜好参与到市场的买卖中，通过市场价格的调整， a g e n t 之间形成供求平衡下的买卖关系。 ( 5 ) 基于结构的组织形成方法【猢7 】 多智能体问题求解中表现的组织形态称为组织结构。组织结构中定义各种不同的 角色、角色的职责、被分配的工作和目标的期限，并以组织结构为前提进行角色的分 5 第一章绪论博士论文 配和调整。现在对组织结构越来越采用显式的表示方式p 6 ，即先明确表示组织的结构， 然后根据角色的要求募招智能体加入组织，并在组织的形成过程中考虑组织的需要和 侯选a g e n t 能力及效益等问题。结构的显示表示有利于智能体进行推理、失败的监测 和恢复，以及进行与多智能体联合行动有关的控制。一些学者认为，面向结构的a g e n t 组织形成方法与人类社会的组织产生机制相符，是一种高级的目的明确的组织形成方 法f 1 8 2 6 2 9 。 以上是多智能体系统领域中关于组织形成的研究，在机器人领域也有相关研究， 如角色的配置 3 0 1 ，使用拍卖的方法【3 1 3 2 l ，利用体系结构来约束机器人的行为1 0 1 2 等，但是相对来说研究较少。主要原因是过去研究的机器人系统规模较小，利用明显 的组织形式来协调机器人之间的关系作用不大。随着多机器人应用领域的扩展，机器 入的数量规模将逐渐加大，如何为完成任务构建恰当的合作组织形式，并允许实时进 行结构的重构，以适应环境、任务处理过程中不断变化的要求，是一个具有挑战性的 问题。 1 2 4 多机器入系统组织中的任务分配 任务分配一般是指在确定的多机器人多目标任务情况下，如何为每个机器人分 配任务及其执行任务路线，从而保证系统整体的消耗代价最小，同时又要满足多个 限制条件约束。一般任务分配包括两个步骤：任务的分解和分配。任务的分解是指 将要完成的任务，按照任务本身的特性、要求以及资源配置分成若干个子任务。在 任务的分解过程中，还要保证子任务的相对独立性，以便减少个体机器人之间的数 据交互，最大限度地利用局部资源，从而提高系统的整体效率。到目前为止，由于 其复杂性，还没有一个计算机系统可以自动实现这一功能。任务的分配就是将已经 分解好的子任务分配给各个机器人，并根据需要任务实时执行情况进行协调。 j a c q u e sf e r b e r 3 3 对多智能系统中的任务分配方式，总结为如图1 1 所示的几种 主要模式。 注意：这里智能体在任务的执行过程中，依据实时获得的信息，自主选择合适 的任务来执行的方式也认为是一种任务分配方式，称为涌现式任务分配( e m e r g e n t ) 。 动态环境下，多机器人系统在实际任务执行过程中具有较多的不确定性，这就决 定了任务的分配具有灵活性、适应性、动态性、复杂性，以及具有高维数等特点，单 纯采用上述任何一种方式都不大可能满足要求，因此在实际应用中，我们根据实际情 况将以上方法结合起来使用，如在团队的形成中，任务分配主要采用合同网加涌现式 分配方法。当团队形成后，主要采用集中式分配方式，实现多任务目标的优化。 6 博士论文 面向任务的多机器人系统的组织设计研究 1 2 5 多机器人系统的通信 图1 1 主要的任务分配模式 处于动态，不确定环境中机器人的感知能力往往是有限的，机器人无法预知环境 的全部信息，信息需要不断的完善或者已知的信息需要不断的更新。在任务执行过程 中，机器人为了更好的组织，还需要知道其他机器人的位置状态以及其他机器人感知 到的环境、任务信息，因此机器人间有大量的信息需要交互、协商，才能达到协调与 合作的目的。现有的通信能力很大程度上限制了多机器人作为一个整体的能力。因此， 需要在机器人之间建立网络通信系统，解决通信瓶颈问题。 目前，多机器人系统中的交互可以按多种方式进行分类瞰l 。 ( 1 ) 根据交互的媒介进行分类，大致可以分为三种类型：以环境为媒介的交互 i m c r a c t i o n v i a e n v i r o n m e n t 、以传感器为媒介的交互i n t e r a c t i o n v i as e n s i n g 和以通信为 媒介的交互i n t e r a c t i o nv i ae o m m u n i c a t i o i l s 【”。 以环境为媒介的交互，也称为无通信合作c o o p e r a t i o nw i t h o u tc o m m u n i c a t i o n ，指 不存在明确通信或个体之间的交互。个体之间的交互通过环境这个“黑板”作为媒介， 这是最简单的通信方式。对大规模分布式移动机器人系统可能是有用的。 以传感器为媒介的交互，指利用传感器在个体之间进行相互感知，是发生在机器 人之间的一种局部交互。此类交互需要个体具有辨别群体中其他个体和环境中其他物 体的能力。 以通信为媒介的交互，也称为显式通信e x p l i c i tc o m m u n i c a t i o n 。这种形式的交互 涉及个体之间的明确通信，有意识地传播点对点的或广播式的消息。 7 第一章绪论 博士论文 ( 2 ) 根据交互的信息内容分类。b a l c h 和a r k i n 按照机器人交换的信息内容将交互 分为目标通信g o a lc o m m u n i c a t i o n 、状态通信s t a t ec o m m u n i c a t i o n 和无通信n o c o m m u n i c a t i o n 3 s l 三类。无通信实际上不涉及机器人之间的直接通信。状态通信允许 机器人之间传送状态信息。目标通信要求机器人在可检测范围内检测到吸引子时，能 够识别并广播该吸引子的位置。大量的模拟研究的定量分析得出关于结论 3 5 3 6 ：通 信能大大改善任务的执行；通信不是必要的；对一些任务来说，复杂的通信策 略不比基本的通信策略有更多好处。 ( 3 1 按照交互信息的层次分类，可以分为任务层交互、规划层交互、行为层交互。 任务层交互指机器人交互的内容是任务信息：规划层交互指机器人之间交流路径规划 信息，协调机器人之间的路径规划；行为层交互指机器人之间不交流高级的任务规划 信息而是仅在相遇后按照反应式的方法控制机器人的行为。 1 3 多机器人系统中的任务分类 多机器人系统相对于个体机器人而言具有一个很大的优越性就是它既能更快 地完成那些个体机器人所能完成的简单独立任务，又能合作完成个体机器人不能完 成的复杂合作任务。按照机器人之间相互约束的关系划分，机器人所要完成的任务， 可以分成松散型任务、紧密耦合型任务以及松散耦合型任务。松散型任务指在多机 器人系统中的任务是可以分成多个不同的子任务，让不同的机器人独立地完成，各 个子任务完成结果的总和就是总任务的完成结果，如搜索、觅食任务。紧密耦合型 任务是指机器人执行的任务本身不可分割，必须由多个机器人密切合作才能完成， 如大型工件的运输，推箱子等。在一个完整的多机器人系统中，紧密耦合型任务和 松散型任务的划分不是绝对的，而是相对的。我们可以将多机器人系统的最终目标 看作完成紧密耦合型任务，而在合作完成最终目标的过程中产生的瞬时合作策略看 作一种可以分解的独立松散型任务，这样，有了第三种松散耦合型任务。松散耦合 型是指任务的执行有时需要机器人独立完成，有时又需要密切合作才能完成，如机 器人足球赛、围捕、大空间范围内清理污染性废物等工作。第三类任务可以看作是 前两类任务的综合，在多机器人的合作研究中更典型，便于在策略上对机器人的分 工和任务的分配进行讨论。本文主要研究此类问题，文中所说的任务也特指此类任 务。 目前多机器人系统所能完成的任务主要有四种，搜寻( f o r a g i n g ) 任务、遍历 ( g r a z i n g ) 任务、编队或聚集( f o r m a t t i n go rf l o c k i n g ) 任务和目标运送( o b j e c tt r a n s p o r t ) 任射堋。其中搜寻任务指在未知( 或部分未知) 环境中，随机分散地放一些目标， 机器人群体的任务就是找到它们，并把它们带回某个特定的位置。编队或聚集任务 g 博士论文 面向任务的多机器人系统的组织设计研究 指多个机器人形成某个