（计算机应用技术专业论文）多智能体协作策略的研究及在robocup中的应用.pdf

摘要 多智能体协作是多智能体系统m a s 研究的核心问题。在复杂、 动态、不确定的多智能体环境中，为了满足多智能体协作中对局部配 合和通信受限的要求，本文对智能体策略寻优、行为协调和动作规划 问题进行研究，来构建适用于不同情况下的多智能体协作策略，并在 典型的m a s r o b o c u p 机器人足球仿真系统平台下进行检验。 首先，为了实现智能体行为选择的优化和多智能体的局部协作， 提出基于行为协同优化的多智能体协作策略。智能体通过模块化模糊 q 学习对其他智能体的行为进行评估，考虑它们的行为对自身行为选 择的约束，来优化自身的行为决策，再采用共享联合意图的协调方法 解决智能体之间的行为冲突，得到其最优行为策略。 其次，在通信受限的情况下，提出基于多智能体行为图的分层规 划协作策略。根据智能体感知到的局部环境信息，利用行为图对其行 为过程进行预测规划，再结合模块化模糊q 学习中获得的行为选择 的先验知识，逐层调整其初始行动计划，获得智能体协调一致的动作 规划序列，使其针对当前环境快速做出有效决策来实现与其他智能体 的协作。 论文提出的多智能体协作策略应用到中南大学c s uy u n l u 机器 人足球仿真球队中，在实际训练和对抗比赛中验证了其有效性。 关键词多智能体系统，协作策略，模块化模糊q 学习，分层规划 a bs t r a c t m u l t i a g e n tc o o p e r a t i o n i sa n i m p o r t a n t r e s e a r c hf o c u so f m u l t i - a g e n ts y s t e m ( m a s ) i nc o m p l e x ，d y n a m i c a n du n c e r t a i n m u l t i - a g e n te n v i r o n m e n t ，t h i sd i s s e r t a t i o ns t u d i e st h e s ep r o b l e m s ，s u c h a s s t r a t e g yo p t i m i z a t i o no fs i n g l ea g e n t ，b e h a v i o rc o o r d i n a t i o na n da c t i o n p l a n n i n g ，t os a t i s f y t h e r e q u i r e m e n t s o fl o c a lc o l l a b o r a t i o na n d c o m m u n i c a t i o nl i m i t a t i o ni nt h ep r o c e s so fm u l t i a g e n tc o o p e r a t i o n t h e n m u l t i a g e n tc o o p e r m i o ns t r a t e g i e s a r ec o n d u c t e dt ob ea p p l i c a b l ei n d i f f e r e n tc a s e sa n de x a m i n e di nr o b o c u ps o c c e rs i m u l m i o ns y s t e m f i r s t l y , i no r d e rt oi m p l e m e n tb e h a v i o rs e l e c t i o no p t i m i z m i o no ft h e a g e n t a n dl o c a lc o l l a b o r a t i o no f m u l t i p l ea g e n t s ，am u l t i - a g e n t c o o p e r a t i o ns t r a t e g yb a s e do nb e h a v i o rc o m m o no p t i m i z a t i o ni sp r o p o s e d e a c ha g e n tu s e sm o d u l a rf u z z yq - l e a r n i n gt os p e c u l a t et h eb e h a v i o r so f o t h e ra g e n t s c o n s i d e r i n gt h e i rb e h a v i o rr e s t r i c t i o n s ，i n d i v i d u a lb e h a v i o r d e c i s i o n m a k i n gi so p t i m i z e d t h e nt h eb e h a v i o rc o n f l i c t sa m o n ga g e n t s a r es o l v e db yt h ec o o r d i n a t i o nm e t h o ds h a r i n gj o i n t - i n t e n t i o n st oo b t a i n t h eo p t i m i z e db e h a v i o rs t r a t e g y s e c o n d l y , al a y e r e dp l a n n i n gc o o p e r a t i o ns t r a t e g y b a s e do n m u l t i a g e n tb e h a v i o rg r a p hi sp r e s e n t e di nt h ec a s eo fc o m m u n i c a t i o n l i m i t e d a c c o r d i n gt ot h el o c a le n v i r o n m e n ts t a t ei n f o r m a t i o nt h a ta g e n t s o b s e r v e ，t h eb e h a v i o rp r o c e s so fa g e n t si sp l a n n e du s i n gb e h a v i o rg r a p h i na d v a n c e t h e nc o m b i n i n gw i t ht h ep r i o rk n o w l e d g eo fb e h a v i o r s e l e c t i o no b t a i n e db ym o d u l a rf u z z yq l e a r n i n g ，i n i t i a la c t i v i t yp l a n n i n g i sg r a d u a l l ya d j u s t e df r o ml o w e rl a y e rt oh i g h e ro n e ，s ot h a tc o n s i s t e n t a c t i o ns e q u e n c eo fe a c ha g e n ti sa c q u i r e d ，w h i c he n s u r e st h ea g e n tt o m a k ea c t i o nd e c i s i o nf l e e t l ya g a i n s tc u r r e n te n v i r o n m e n tt oc o o p e r a t e w i t ho t h e r sn e a t l y t h e s ep r o p o s e dc o o p e r a t i o ns t r a t e g i e sa b o v eh a v eb e e na p p l i e di n t o c s u - y u n l us i m u l a t i o nt e a m t h ef e a s i b i l i t y i sv e r i f i e di na c t u a l a n t a g o n i s mt r a i n i n ga n dc o m p e t i t i o n k e yw o r d s m u l t i a g e n ts y s t e m ，c o o p e r a t i o ns t r a t e g y , m o d u l a rf u z z y q l e a r n i n g ，l a y e r e dp l a n n i n g m a s a g e n t d a i r o b o c u p r l m f q l m a b g l p c s m u l t i a g e n ts y s t e m 符号说明 d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e t h er o b o ts o c c e rw o r l dc u p r e i n f o r c e m e n tl e a r n i n g m o d u l a rf u z z yq l e a r n i n g m u l t i a g e n tb e h a v i o rg r a p h l a y e r e dp l a n n i n gc o o p e r a t i o ns t r a t e g y 多智能体系统 智能体 分布式人工智能 机器人足球世界杯 强化学习 多模块模糊q 学习 多智能体行为图 分层规划协作策略 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名： 童) 塑 日期：型年月监日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：邀年上月么 硕十学位论文 第一章绪论 第一章绪论弟一早三百t 匕 多智能体系统【i 】( m u l t i - a g e n ts y s t e m ，m a s ) 是近年来分布式人工智能【2 】 ( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ，d a i ) 领域的一个活跃的研究分支，在问题求 解、机器人技术和人机交互等方面有着重要的研究意义。在复杂、动态、不确定 的多智能体环境下，由于单个智能体具有的资源和能力有限，就需要与其他智能 体通过协商、协调和协作来完成系统的目标任务。r o b o c u p ( t h er o b o ts o c c e r w o r l dc u p ) 即机器人足球世界杯赛p 】，是一个通过提供足球比赛这样一个标准 问题来促进人工智能、智能机器人以及相关领域的研究而建立的国际性的研究和 教育组织。r o b o c u p 机器人足球仿真系统是一个典型的m a s ，在完全分布式控 制、实时异步、有噪声的对抗环境下同样需要解决多智能体间的协作问题。 为了满足r o b o c u p 中多智能体协作对局部配合和通信受限的需求，本文引 入多智能体学习和规划技术，对智能体的策略寻优、行为协调和动作规划问题进 行研究，寻求有效的多智能体协作策略，一方面使智能体能具备自协调学习的能 力，增强对环境的适应性，实现行为的有效选择和智能体问的局部协作，另一方 面在不依赖或极少依赖通信的情况下具有良好的动态反应特性，针对当前环境快 速做出决策，提高多智能体的协作效率。 1 1 课题研究背景 本课题来源于国家杰出青年科学基金项目( 6 0 4 2 5 3 1 0 ) 和湖南省自然科学基 金项目( 0 6 j j 5 0 1 4 4 ) “基于状态预测的多智能体动态协作模型研究”，在r o b o c u p 机器人足球仿真比赛的平台下开展研究。 m a s 是由多个相互作用的自治智能体形成的集合【4 】，其研究的核心问题是 寻求建立一种有效的协作机制，使功能简单、相互独立的多个智能体通过协商、 协调和协作完成复杂的目标任务或解决复杂的问题。多智能体协调是指具有不同 目标的多个智能体对其目标、资源进行合理安排，以解决它们策略上存在的行为 冲突，最大程度地实现各自目标。而多智能体协作是指多个智能体通过协调各自 行为，合作完成共同目标。协作是m a s 与其他相关领域，如分布式计算、基于 对象的系统、专家系统等区别丌来的一个关键性标志【5 1 。 对于m a s 来说，在复杂实时动态的环境下，由于存在时间约束和资源约束， 需要解决m a s 的资源分配、任务调度、行为协调、冲突消解等协调合作问题， 并使功能独立的智能体通过采取有效的协调机制，在有限时间、有限资源情况下 完成某些相互受益且自身无法独立求解的复杂任务或解决复杂的问题。因而对于 硕十学位论文 第一章绪论 m a s 的研究，重点在于结合实际应用系统，对于其协作的环境、协作模型和协 作机制进行深入的分析和设计怜】。 r o b o c u p 是_ 项为促进人工智能、智能机器人以及相关领域的研究而进行的 国际性合作项目。1 9 9 7 年，在国际最权威的人工智能系列学术大会第1 5 届 国际人工智能联合大会( t h e15 mi n t e r n a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a l i n t e l l i g e n c e ，简称i j c a i 9 7 ) 上，由k i t a n o 、v e l o s o 和t a m b e 等来自美、日、瑞 典的9 位国际著名学者联合发表重要论文“t h er o b o c u ps y n t h e t i ca g e n t c h a l l e n g e9 7 ”，系统阐述了机器人足球的研究意义、目标、阶段设想、近期主要 研究内容和评价原则，将机器人足球正式列为人工智能的一项挑战 7 1 。至此，机 器人足球成为人工智能和机器人学新的标准问题。 目前r o b o c u p 所举办的赛事主要包括：仿真组、小型机器人组、中型机器 人组、s o n y 有腿机器人组、类人型机器人组等比赛【8 】。仿真组比赛全部是在一个 标准的计算机环境下进行的，研究平台的建立只需投入少量资金，是所有 r o b o c u p 项目中参赛球队数目最多的一种，而其余的比赛都是以实物机器人形式 进行比赛。r o b o c u p 仿真环境与人类足球比赛的环境相似，比赛队员的仿真模型 与实际人类足球队员也很接近，比赛舰则基本上与国际足球联合会的比赛规则一 致，只是在某些方面有很小的改动，比赛采用c l i e n t s e r v e r 方式【9 】，由r o b o c u p 委员会提供标准的s o c c e rs e r v e r 系统，各参赛队编写各自的c l i e n t 程序，模拟人 类足球实际比赛的情况，故其对于分布式人工智能理论的研究具有重要意义。 r o b o c u p 仿真比赛是一个典型的多智能体系统，它提供了一个完全分布式控 制、实时异步的多智能体环境，避开了诸如对象识别、通讯和硬件设计等机器人 底层问题，使研究人员能够集中精力研究多智能体之间的协作、学习、规划等高 层次问题，通过这个平台可以检验各种多智能体理论、算法和智能体的体系结构， 在实时异步、有噪声的对抗环境下模拟实际足球队员的比赛，研究多智能体间的 合作和对抗问题【1 0 1 1 1 。因此，本论文选择r o b o c u p 仿真比赛作为研究完全分布 式的、既有合作又有竞争的多智能体系统协作策略的理想测试平台，并以 r o b o c u p 仿真比赛的软件设计和开发作为切入点，是非常合适的。 1 2 国内外研究现状 近年来，国内外学者针对多智能体协作进行了深入的研究，主要集中在m a s 的体系结构、协作策略、协作模型以及学习算法等方面【1 2 , 1 3 ，并取得了较大进展。 其中，针对复杂动态不确定的环境而提出的多智能体协作策略主要有以下三类典 型的方法： ( 1 ) 基于协商的多智能体协作策略 2 硕士学位论文第一章绪论 在动态复杂的多智能体环境中，一致性的协作行为经常因为智能体之间的信 念、规划和行为的冲突所阻碍，当自治智能体对动态事件做出反应的时候，可能 在无意之中就干扰了其它智能体的行动，或者错误的感知信息可能会给智能体提 供具有冲突的信息等等，导致了多个智能体去执行一个动作或没有智能体去执行 动作等行为冲突，进而影响其协作效率。因此，冲突是多智能体协作策略中普遍 存在的问题，目前解决的一个重要方法是协商，通过协商去改变智能体的意图、 规划或行为，使其对问题求解达成一致意见，采取共同的适应行为策略，通过协 作尽快完成系统的目标任务。 j e n n i n g s 等以联合意图作为多智能体协作的基础，建立了复杂动态多智能体 环境下的协作框架【l4 1 ，通过意图交互，保证了各个智能体在问题求解中采取一 致的行动策略，合作完成共同目标。s m i t h 等人将合同网( c o n t a c tn e t ) 技术应 用至i j m a s 的协作问题求解中【l5 1 ，合同网是针对资源不足的多智能体动态环境的 情况，采用任务分解、任务分配、任务监督和任务评价等要素构成的一种协商策 略。合同网的每个节点代表一个智能体，当一个智能体发现自己没有足够的知识 或能力去处理当前的任务，把一个任务分解成一系列子任务，利用合同网进行协 商，给有关协作智能体指派任务，并确定其角色，但是由于节点间以广播的形式 互相通信，随着节点数增加，协商效率随之降低，所以这种方法仅适用于智能体 数目较少、任务较易分解成独立的子任务的m a s 环境中。 范波等人提出了基于m a r k o v 对策的多智能体协作方法【l6 1 ，在智能体目标矛 盾的前提下，按照m a r k o v 对策对智能体进行策略的制定，通过建立其他智能体 的策略模型来修正自己的策略，通过协商实现各自行为的协调，既能使多个智能 体通过协同和合作完成一个特定的任务，又能有效地处理智能体之间的竞争关 系。但在多智能体环境中，智能体之间存在着竞争和合作两种关系，该方法仅适 合处理智能体之间的竞争关系。 上述方法本质上都是基于协商的，在协商过程中不同程度地依赖于智能体间 的信息共享，通过通信来获得其他智能体的行为决策信息，而使得智能体对自己 的行为策略进行调整，来完成协作任务，无法适应通信受限的多智能体协作中。 ( 2 ) 基于多智能体强化学习的协作策略 智能体行动选择应该建立在对环境和其它智能体的行动了解的基础上，而智 能体通过学习可以不断修j 下其对环境和其他智能体的感知能力，适应外界环境的 动态变化，根据环境变化去自行调整行动策略，消解智能体间存在的行为冲突， 做出相应的最优行为决策，进而提高协作能力。因此，多智能体协作策略的制定 应考虑使智能体能够从自己过去的失败经验中不断学习，增强对环境的适应性。 目前较为成熟、应用较广的实现多智能体学习的方法【j7 】主要有遗传学习算 硕十学位论文 第一章绪论 法、贝叶斯学习和强化学习。遗传学习【1 8 】是一种借鉴生物界自然选择和自然遗 传机制的随机化的搜索方法，由于它具有简单、健壮、隐含并行性和全局优化等 优点，对于传统搜索方法难以解决的复杂和非线性问题具有良好的适用性，应用 到多智能体协作中，特别是缺少环境信息的协作中，可以有效地给出优化结果， 但遗传算法不能保证所得解都为最佳解。贝叶斯学习【l9 】是学习智能体从建立在 对另一个智能体可能采取的策略的初始信念丌始，不断根据贝叶斯法则更新信 念。贝叶斯方法被应用到条件学习中，一个智能体在过去记录条件下学习其它智 能体的策略，这种学习方法不同于在假设行动中的研究的静态策略，行为策略的 识别比静态策略要困难得多。 强化学习【2 0 】是多智能体协作中用的最多的、也最成熟的学习方法，是智能 体从环境状态到动作映射的学习，但是在m a s 中由于多个智能体的存在使系统 高度复杂，问题的求解需要考虑多个智能体之间的相互影响，求解空间非常巨大， 不能用马尔可夫模型( m a r k o vd e c i s i o np r o c e s s ，m d p ) 来描述，因此不能将基 于马尔可夫模型的强化学习方法直接应用到多智能体环境中，如何使智能体具备 分布式环境下的学习能力来提高智能体之间的协作效率已成为近年来研究者的 一个研究热点。 n a g a y u k i 等人提出了基于其它智能体内部模型的多智能体强化学习 2 1 l ，通 过对其他智能体的状态和响应进行建模，预测它们行动产生的效果来建立和修f 智能体的信念，在对其他智能体建模过程中实现自身行为的学习。周浦城等人提 出了一种综合了模块化结构、利益分配学习以及对手建模技术的多智能体强化学 习方法【2 2 1 ，利用模块化学习结构来克服状态空间的维数灾难问题，将q 学习与 利益分配学习相结合以加快学习速度，采用基于观察的对手建模来预测其他智能 体的动作分布，得出智能体更优的行为策略，并将所提方法的应用在追捕问题中， 这种方法的适用性还有待进一步研究。范波等人提出的基于分布式强化学习的多 智能体协作方法【2 3 】采用分级结构，在不同层次上进行学习，协调智能体将复杂 的系统任务进行分解处理，利用中央强化学习进行子任务的分配，每个任务智能 体接受各自的子任务，利用独立强化学习分别选择有效的行为，相互协作完成系 统总的任务，这种方法本质上基于独立学习的多智能体协作，每个智能体在自身 行为决策时没有考虑其他智能体的行为对其环境状态的影响和约束，造成行为决 策的局部性，进而影响它们之间的协作。 h u a n g 等人在对强化学习进行改进的基础上提出一种分布式q 学习算法【2 4 】， 并将其应用到多智能体行为协作决策中，该算法采用一种改进的e 贪婪策略，在 智能体间引入了状态一动作空间共享策略，将学习最优动作策略的总任务分解成 若干个子任务，再根据环境的变化动态分配给每个智能体，使它们各自的行为决 4 硕十学位论文第一章绪论 策保持协调一致，实现多智能体间的团队协作，但在该学习方法中每个智能体子 任务决策的依据还是自身的局部规划，而不是全局规划，学习的效果不够理想。 t e h r a n i 等人提出了一种新颖的模糊强化学习算法【2 5 1 ，采用模糊函数逼近方法对 m a s 连续的状态空间进行泛化，通过通信方式与其他智能体进行交互，协商协调 各自行为，利用强化学习来调节模糊推理参数，进而获得最优的模糊规则，智能 体根据规则结果进行动作决策，但这种方法对系统的通信效率要求比较高。 ( 3 ) 基于多智能体规划的协作策略 规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系 列行为动作并建立一个操作序列，直到求得目标状态为止【2 6 1 。传统的规划方法 一般是基于单智能体的环境，当环境中有其他智能体时，智能体就简单地将它们 包含在它的环境模型中，而不改变其基本规划过程，降低了规划的性能。多智能 体规划就是为多个智能体制定协调一致的问题求解过程，使得每个智能体能够知 道在当前状态下，对于最优的联合规划它应采取的动作。 d e c k e r 等人提出的部分全局规划p g p ( p a r t i a lg l o b a lp l a n n i n g ) 的多智能体 协作方法，在该方法中智能体具有自己的求解目标，并且每个智能体考虑其它智 能体的行动和约束，从而进行各自独立的规划即部分规划。d e c k e r 对p g p 方法 进行改进，提出了一种通用规划方法【27 】( g e n e r a l i z e dp a r t i a lg l o b a lp l a n n i n g ， g p g p ) 方法，g p g p 方法是几种协调机制的集合，允许智能体异构、通信和交 换少量的全局信息，在计算智能体的团队协同工作得到了应用。这两种方法本质 上都是基于智能体的独立全局规划，其观察状态的不确定性，随着坏境复杂度的 增大而增大，因而很难满足实时m a s 协作要求，存在局限性。 清华大学蔡云鹏等人提出从局部观察来进行全局协调规划的协作方法【2 引， 该方法遵循一种基于抢先式的竞争机制，由仲裁器、评估器、行为产生器三个模 块组成，行为产生器产生一些列队行为后，交给评估器来对行为进行评估，以评 价智能体采取当前行为的优劣性，最后仲裁器决策出智能体的最终动作。这种协 作策略能够及时地对外界环境变化进行实时反应，但智能体难以体现。c o x 等人 提出的多智能体规划协作算法【2 9 3 0 1 ，采用规划空间搜索每个智能体规划状态，智 能体之间共享各自每个规划步，在搜索过程中不断修正智能体的每一步规划，动 态减少了搜索空间的大小，但该算法会导致智能体搜索状态呈指数增加，进而影 响到搜索效率。d i m o p o u l o s 等人将经典规划扩展到多智能体环境中，提出了一 种分支界限算法【3 ，利用该算法组织协调各个智能体的规划，在智能体之问形 成一致、无冲突的规划，使具有不同能力的多个智能体互相协助，实现各自目标 任务，这种方法仅适用于多智能体协作的一种特殊情况协助，而在完全合作 的m a s 中存在局限性。 硕十学位论文 第一章绪论 综上所述，在不确定、复杂、动态的环境下多智能体的各种协作策略中，多 智能体的协商适用于智能体数目较少、任务较易分解成独立的子任务的m a s 环 境中，对通信效率要求高，问题求解速度慢；智能体通过学习能改进自身行为决 策，使协作达到更好的效果，但目前应用到多智能体的学习中的强化学习技术还 不够成熟【3 2 】，需要提出一种新的或改进的多智能体强化学习算法；多智能体的 规划具有良好的动态特性，但现有的方法缺乏全局性和适用性。因此，寻求既具 有良好的动态反应特性和全局性，又具备自适应学习能力的有效的多智能体协作 策略，使其适用于不同情况下是非常必要的。 1 3 研究目的及意义 在m a s 中智能体是自主的，对于每个智能体来说，本身具有的能力一方面 使其能够进行各自独立的行为规划，并采取相应的动作来执行规划，实现各自目 标，自主解决局部问题；另一方面，每个智能体又具有不同的资源和能力，当单 个智能体没有足够的资源和能力去接近整个问题时，就需要与其他智能体进行有 效的协作，产生共同的适应行为，共同完成系统的目标任务。所以多智能体协作 策略的研究将有助于动态、复杂环境中协作问题的求解，对促进多智能体系统理 论和协作技术的发展具有重要的科学意义和实用价值。 在复杂、动态不确定的r o b o c u p 仿真比赛中，各智能体所处的环境是复杂 而多变的，为了赢得比赛，不仅需要单个智能体具有灵巧快速的反应能力，更需 要多个智能体有一个灵活有效的整体协作策略，才能完成球队的比赛任务射 门得分。目前由于各r o b o c u p 仿真参赛队伍的底层工作已经相对成熟，制定并 实施合理的高层协作策略就成了队伍致胜的关键，对r o b o c u p 中仿真球队在比 赛中取得好成绩是至关重要的。因此，本文在r o b o c u p 仿真平台下对m a s 中学 习、协调和规划等理论进行研究，在对国内外仿真队伍所采用的协作策略进行综 合比较分析的基础上，针对r o b o c u p 这样一个动态、实时、不确定环境下的多 智能体协作问题，构建适用于该仿真环境的有效的多智能体协作策略，并应用到 中南大学r o b o c u p 仿真球队( c s uy u n l u ) 的丌发中，通过参加国内外大赛检 验协作策略的有效性。 1 4 主要研究内容和构成 本论文以m a s 为研究对象，以r o b o c u p 机器人足球仿真比赛作为检验平台， 将重点放在多智能体的协作策略的研究上。在对目前r o b o c u p 中多智能体协作 的关键技术及难点进行分析的基础上，为了满足r o b o c u p 中对智能体的局部配 合和反应速度的需求，针对多智能体协作中智能体策略寻优、行为协调和动作规 6 硕十学位论文第一章绪论 划问题，引入多智能体的学习和协调方法，来优化智能体的动作决策，有效实现 智能体之间的局部配合；通过分层规划为智能体制定协调一致的行为规划序列， 使其针对当前环境快速做出决策，实现通信受限的情况下多智能体的协作。主要 研究内容如下： ( 1 ) r o b o c u p 中多智能体的协作问题 在复杂、动态、实时、不确定的r o b o c u p 仿真环境中，分析多智能体协作 中面i 临的主要问题，对实现多智能体协作的难点及关键技术进行研究，如何选择 合适的方法来满足多智能体协作的不同需求，是建立灵活、有效的多智能体协作 策略的关键所在。 ( 2 ) 基于行为协同优化的多智能体协作策略 在复杂、实时、动态的m a s 中，由于其他智能体的行为会对智能体所处的 环境产生影响，使得各智能体针对当前动态环境达成协同一致的行为决策存在很 大的挑战。为了实现智能体行为的有效选择，本文提出一种基于行为协同优化的 多智能体协作策略。智能体利用模块化模糊q 学习对其他智能体的行为进行评 估，学习它们的行为策略，来实现自身行为决策的优化；再采用共享联合意图的 协调方法解决智能体之间的行为冲突，获得自身的最优行为决策，共同完成系统 的目标任务。通过在r o b o c u p 球员防守协作中的实际训练验证其有效性。 ( 3 ) 基于多智能体行为图的分层规划协作策略 在通信受限的多智能体环境中，提出一种基于多智能体行为图的分层规划协 作策略。通过引入多智能体行为图模型，对其他智能体的行为过程进行初始规划； 再结合智能体在模块化模糊q 学习中获得的行为选择的先验知识，逐层细化智能 体的内部状态和行为属性值，使其根据当前形势快速做出计划调整，在行动上达 成共识，从而实现一种不依赖于通信的显式的多智能体协作。将此规划协作策略 应用n r o b o c u p 进攻协作中，检验其合理性。 论文后续章节安排如下： 第二章主要对r o b o c u p 中多智能体协作策略的相关问题进行探讨，分析 r o b o c u p 中协作策略面临的问题、目前国内外强队采用的协作方法和制定协作策 略的关键和难点所在，是后面章节的研究基础。 第三章提出一种基于行为协同优化的多智能体协作策略，并将其应用到 r o b o c u p 仿真球队的防守协作中，通过实际训练检验该方法的有效性。 第四章将分层规划技术引入到多智能体协作中，研究一种基于多智能体动作 图的分层规划协作策略，并在r o b o c u p 进攻协作中进行实践，在对抗比赛中对 其规划性能进行验证。 第五章对论文所做研究工作进行总结，并提出今后进一步的研究方向。 7 硕十学位论文 第二章r o b o c u p 中多智能体协作策略的研究 第二章r o b o c u p 中多智能体协作策略的研究 r o b o c u p 仿真机器人足球比赛在标准软件平台上进行，平台设计充分体现了 多智能体环境的动态、实时和不确定性的特点，其研究重点是仿真球队的高层协 作策略，包括多智能体的任务合理分配、协作过程的实时规划、行为策略的学习 和及时的动作决策等关键性问题。深入分析多智能体协作过程是提出协作策略的 必要条件，本章对r o b o c u p 中多智能体协作面临的问题、国内外仿真球队现有 的协作策略、设计协作策略的关键技术和存在的难点进行详细论述。 2 1 多智能体的协作 在m a s 中智能体不仅需要同环境交互，也需要同其他智能体进行交互，从 而避免有害的相互作用，促进有益的相互作用。此外，每个智能体都有共同的目 标任务，当单个智能体没有足够的资源和能力独立完成任务时，需要向具有问题 求解所需的资源和能力的其他智能体提出合作请求，通过它们之间的联合行动来 完成任务。即使单个智能体具有完成任务的能力，可以单独解决问题而无需依赖 其它智能体，但通过多个智能体的共同努力可以弥补单个智能体由于资源和能力 有限造成的不足。因此，协作是m a s 必须具备的能力，不仅能提高单个智能体 以及由多个智能体所形成的系统的整体行为性能，增强智能体及整个系统问题求 解的能力，还能使系统具有更好的灵活性。 2 1 1 协调与协作 m a s 的研究重点在于如何协调在逻辑上或物理上分离的、具有不同目标的 多个智能体的行为，使其为了联合采取行动或求解问题，协调各自的知识、希望、 意图、规划、行动，以对其资源进行合理安排，最大程度地实现各自和总体目标。 因此，各智能体在社会层次上的知识和行为、协调与协作成为m a s 研究的核心 问题。 多智能体协调是指具有不同目标的多个智能体对其目标、资源进行合理安 排，以解决它们策略上存在的行为冲突，最大程度地实现各自目标。而多智能体 协作是指多个智能体通过协调各自行为，合作完成共同目标。协调是合作的基础， 合作又反过来提高系统的协调一致性【3 3 1 ，采用合适的协调合作技术，使单个智 能体局部一致，多个智能体全局一致，从而出色地完成复杂任务。 m a s 由多个相互作用的自治智能体组成，对于每个智能体来说，本身具有 的智能一方面使其能够进行各自独立的行为规划，并采取相应的动作来执行这个 硕+ 学位论文 第二章r o b o c u p 中多智能体协作策略的研究 规划，实现个人目标，自主求解局部问题【3 4 1 。另一方面，随着分布式人工智能 的发展，需要处理的问题也越来越复杂，但是对于些复杂的任务，如具有分布 式数据或知识，或要求分布式控制的系统等，单个智能体的资源和问题求解能力 则显得比较单薄，为了达到系统共同的目标，它必须与其他智能体建立有效的合 作关系，产生共同的适应行为，通过相互协作来完成目标任务。 但在实时、动态、不确定的多智能体环境下，由于知识获取难以具备完备性 以及时间和资源存在约束，不可避免会产生各种资源、任务、目标和行为等冲突， 严重影响m a s 中各智能体的独立能力和系统总体性能【3 5 】。在有限时问、有限资 源的情况下对各智能体资源、目标、行动策略进行合理安排，使它们之间达成协 调一致的行动，可以提高协作的效率，所以m a s 协作的研究应与多智能体间的 行为协调相结合。 在多智能体环境中，对具有合作关系的智能体群体行为进行协调的重点在于 通过智能体问的交互，解决它们之f b j 的知识、目标、策略和规划等冲突问题，调 整各自的行为意图，对各自的目标、资源等进行合理安排，避免智能体执行行动 时出现死锁，或多个智能体都在执行某个行动造成资源浪费，最大程度地实现各 自目标。单个智能体个体能力的完善及高度智能化才是m a s 群体进行有效协同 工作的保证。 多智能体的协调与协作的实现方法可分为三大类：无通信的协调与协作、有 中心控制的通信协调与协作、基于协商的协作【3 州。虽然多智能体协作有多种研 究方法，但普遍存在建模不精确、信息不完全的问题，这是m a s 本身特点决定 的，同时也导致相关分析方法的实用性不强。如何更完全的表达系统内容信息， 在此基础上开发有效的任务传达和分配机制，减少系统的通讯量，提高多智能体 协作的效率，有效地避免资源浪费和冲突，是多智能体协作研究的主要目标。 r o b o c u p 机器人足球仿真系统是一个典型的m a s ，它提供了一个完全分布 式控制、实时异步的多智能体环境。一个r o b o c u p 仿真球队由1 1 个球员智能体 和1 个教练智能体组成，其中1 1 个球员智能体由相同的个体进行设计和实现且 具有共同的目标，即“多进球赢得比赛”。尽管1 1 个球员智能体都具有带球、截 球、奔跑和射门的能力并可独立工作，但是没有一个智能体具有求解问题所需的 足够专长、资源和信息，并且不同智能体具有求解问题不同部分的专长，比如守 门员智能体具有比其他球员智能体更好的防守能力，所以一个球队中的智能体必 须协作来完成团队共同的目标。另外，r o b o c u p 仿真比赛是一个对抗性的多智能 体环境，这一点也要求智能体之间必须相互协作才能与对手对抗。因而，选取 r o b o c u p 作为检验平台，来对多智能体的协作进行研究，是非常合适的。 r o b o c u p 仿真比赛是在一个标准的计算机环境内进行的，由r o b o c u p 委员 9 硕士学位论文第二章r o b o c u p 中多智能体协作策略的研究 会提供标准的服务器系统，各参赛球队编写自己的客户端程序，模拟实际足球队 员参加比赛。在仿真球队的设计中主要面临的协作问题有： ( 1 ) 任务合理分配 在r o b o c u p 仿真比赛中，整个球队所需完成的总任务就是1 1 个球员智能体 共同协作实现进球得分。在比赛不同阶段每个智能体要根据自身的任务去确定采 取的动作，当智能体不能独自完成当前目标任务时，就需要与其他球员协作。然 而，不同智能体具有不同的能力，可采取的行动不同，完成任务的情况也就不同， 最终就会影响目标的实现。因此，需要将这个总的目标任务进行分解，分配给合 适的智能体，使单个智能体及所在的子团体和整个合作团体可以根据场上形势进 行分工协作，充分利用系统的资源，共同完成所赋予的目标任务【3 7 , 3 8 】。 ( 2 ) 团队显式合作 为了实现r o b o c u p 团队合作，必须解决在动念对抗环境中多智能体团队合 作中的实时规划、重规划、执行等问题。在当前的智能体体系结构中，缺少团队 合作的理论，如团队目标、团队规划、共有信念和联合承诺等【3 9 1 。特别是，团 队目标、团队规划、共有信念没有被显式的表示，而团队承诺连概念都没有。这 样，智能体不能显式的表示它们的团队目标和规划，也不能进行推理，更不能在 意外事件发生时进行灵活的通讯或协调。由于r o b o c u p 仿真比赛只提供了一个 单通道、低带宽的通信机制，所以需要一种不依赖于通信的显式合作。 ( 3 ) 协作策略的学习 在r o b o c u p 仿真球队的设计中，要完全依靠程序员的手工编程实现其基本 行为的设计和高层协作策略的制定，任务非常繁重，甚至是不可能的。近年来， 多智能体的学习成为一个新的研究热点，这个研究方向的一个关键问题是用学习 技术增强智能体的智能，也就是其自己解决问题的能力。在诸多学习方法中，强 化学习方法是得到最广泛关注的一种方法。r o b o c u p 的学习任务包括：单个智能 体的离线技术学习、智能体团队的离线协作学习、在线协作学习和在线对抗学习。 2 1 2r o b o c u p 仿真球队协作策略分析 国外比较著名的球队有c m u ，它是由美国卡耐基梅隆c a r n e g i e m e l l o n 大学 的p e t e rs t o n e 等人丌发的，曾获得r o b o c u p 9 8 、9 9 仿真组的冠军。该队采用决 策树方法对球员的基本动作，高层决策和队员间的协作进行训练，提出阵型和站 位的概念，并根据比赛结果和剩余时间动态改变阵型，同时研究在m a s 中各个 智能体为达到一个目标是如何进行协调和学习的，提出分层学习的多智能体学习 框架。 f cp o r t u g u a l 队是由葡萄牙的罩斯本大学和波尔图大学合作完成的一支球 1 0 硕十学位论文 第二章r o b o c u p 中多智能体协作策略的研究 队，它是在c m u 9 9 公开的底层源代码的基础上，对m a s 的协作方面进行深入 研究，扩展球员阵型和站位这些概念，并在球员类型、战术以及角色的动态分配 机制等方面提出了自己特有的球队策略，取得了较大的进展。该球队最主要特点 是基于场上形势的策略站位【删( s i t u a t i o nb a s e ds t r a t e g i cp o s i t i o n i n g ，s b s p ) 、动 态站位和角色变换( d y n a m i cp o s i t i o n i n ga n dr o l ee x c h a n g e ，d p r e ) ，球员不仅 能够改变它们的站位，而且还可以在当前阵型下改变球员类型。 u v at r i l e a r n 是荷兰萨姆斯特大学的一支球队，也是欧洲的老牌强队，它采 用推理层和执行层的双层结构，m a s 结构特点不是很明显，主要是把异构球员 的方法应用到m a s ，同时采用了p r i o r i t y c o n f i d e n c e 模型【4 1 4 2 】进行决策算法的设 计，取得了良好的效果，所以该球队的攻击力比较强悍。 德国卡尔斯鲁厄大学的球队b r a i n s t o r m e r 采用强化学习技术进行球员的底层 动作的学习【4 3 1 ，把r o b o c u p 问题看成部分可观察的马尔可夫决策问题，简化世 界状念和动作集，通过使用动态规划的方法，用前向反馈神经网络来近似一个对 连续的状态空间进行评价的y 函数，通过不断尝试学习去提高v 函数的性能， 它们的最终目标是能够做到在仅仅给定一个命令告诉智能体去完成进球任务的 情况下，智能体能够自主的通过和环境的交互，去学习各种技能，选择合适的动 作，甚至是策略。 国内著名的球队有清华大学的t s i n g h u a e l o u s ，该队的研究重点在智能体的 可调节性上，智能体根据来自教练和其他智能体的建议来调节决策参数l ，对 每一个动作的使用和选择都比较合理，个体技术较强，如截球、带球等具有较高 水平，在此基础上其采取的进攻跑位和防守跑位策略实现的协作准确性很高。另 外一支是中国科技大学的w r i g h