（计算机应用技术专业论文）合作型多智能体决策技术的研究.pdf

摘要 合作型多智能体决策技术研究给定的组智能体如何协调彼此的动作，与环境进行受溉，麸同 党成一个长远的目标。合作型多智能体决策技术有相当多的应用背景。例如，机器人足球队，球员之 间楣互配合，共同为赢得比赛而努力；机器人髓救。多个机器人相互协谭，以最快的速度，落救地震 尉的幸存者本论文重点研究台作型多智能体决策技术中的三个谍题：1 ) 值函数分解；2 ) 作溅多 镏髓体协调技术；3 ) 合作型多智能体强化学习技术。本论文研究的主要内客及取得的成浆商1 2 l 下凡 方掰： 1 磁究了合 蕈壁多智韪传系统毽函数分麟按零，挺壅7 一秘基于蠹副譬定主下文熬德溺数分瓣方 法。该方法梅系统擅函数近似为一些褥部德丽数的和。每个竭郝蓬函数只毽含需簧协调彼此动 作的- - , j , 部分智能体。提出的值酶数分解方法紧致地描述了系统中智能体之间的协调笑系，降 低了“维数诅咒”带来的影响。 2 研究了合作犁多智能体协调技术，诞明了在合作型多智能体系统中。p a x e t o 最优同时也 是n a s h 平衡，并提出了构造合作掣多智裁体协调算法的般方法在此摹础之上，撼出了种 基于模拟退火的合作犁多智能体协调算法。理论分析和实验都表明该算法比辛流的合作溅多智 能体协调算法盲更高的效率。 3 。穗出了一秘薪鬏靛多智裁体q 学嚣算法。该冀法运矮篷最数分解技术，有效恁减少7 学习过程 孛震要访趣豹菝峦一动律对。实骏袭臻，谯学习到梵乎赣嚣约筐函数露，本文鬟港瓣学习舞法瓣 收敛速度比传统豹多智能俸强偬学邂算法抉4 嵇。 芙键词：合作型多智能体决策，值两数分解，多智能体协调，合作型多智能体强化学习 a b s t r a c t g i v e nag r o u po fa g e n t s ，ac o o p e r a t i v em u l t i a g e n td e c i s i o nm a k i n gp r o b l e mi sap r o b l e mo f c o o r d i n a t i o na c t i o n sb e t w e e nt h ea g e n t st of u l f i l lal o n g - t e r mc 0 1 q o ng o a l e x a m p l e sa r eat e a m o f8 0 0 c 口p l a ) r i n gr o b o t sw h op l a yf o o t b a l la g a i n s ta - n o t h e rt e a ma n dag r o u po fr e s a l er o b o t st h a t ， a f t e ra ne a r t h q u a k e ，m u s ts a f e l yf i n dv i c t i m sa 8f a s ta sp o s s i b l e i nt h i sd i s s e r t a t i o n ，w ea d d r e s s t h r e er e s e a r c hi s s u e sl i ei nt h ec o o p e r a t i v em u l t i a g e n td e c i s i o nm a k i n gp r o b l e m 二1 ) v a l u ef u n c - t i o nd e c o m p o s i t i o n ；2 ) m u l t i a g e n tc o o r d i n a t i o n ；3 ) c o o p e r a t i v em u l t i a g e n tr e i n f o r c e m e n tl e a r n i n g c o n t r i b u t i o n so ft h ed i s s e r t a t i o ni n c l u d e ： 1 w ep r o p o s ear o l eb a s e dc o n t e x t - s p e c i f i cv a l u ef u n c t i o nd e c o m p o s i t i o na p p r o a c h i nt h i s m e t h o d ，t h ev a l u ef u n c t i o ni sa p p r o x i m a t e da saf r i l l so fal o to fl o c a lv a l u ef u n c t i o n s e a c h l o c a lv a l u ef u n c t i o no n l yi n v o l v e sas m a l lg r o u po fa g e n t sw h on e e dt oc o o r d i n a t et h e i ra c t i o n s o u ra p p r o a c hr e p r e s e n t st h ec o o r d i n a t i o nd e p e n d e n c i e sb e t w e e nt h ea g e n t sv e r yc o m p a c t l y a n dt h e r e f o r ea l l e v i a t et h e c u r s eo fd i m e n s i o n a l i t f 2 w ep r o v et h a ti nac o o p e r a t i v em u l t i a g e n ts y s t e m ，ap a r e t oo p t i m a li sa l s oan a s he q u i l i b - r i u ma n dp r o p o s et h eg e n e r a lp r i n c i p l et oc o n s t r u c tm u l t i a g e n tc o o r d i n a t i o na l g o r i t h m b a s e d o nt h e s er e s u l t s ，w ea l s op r o p o s eas i m u l a t e da n n e a l i n g ( s a ) b a s e dm u l t i a g e n tc o o r d i n a t i o n a l g o r i t h m t h e o r e t i c a la n a l y s i sa n de m p i r i c a lr e s u l t ss h o wt h a ts ab a s e da l g o r i t h mf i n d st h e n e a ro p t i m a lp a y o f f sw i t hs i g n i f i c a n tp e r f o r m c ei m p r o v e m e n t st h a nt h es t a t e - o f - a r tm u l t i a - g e n tc o o r d i n a t i o na l g o r i t h m 3 w ep r o p o s ean o v e lm u l t i a g e n tq - l e a r n i d ga l g o r i t h m t h em g o f i t h mu 嘲t h ep r o p o s e dr o l e b a s e dc o n t e x t - s p e c i f i cv a l u ef u n c t i o nd e c o m p o s i t i o nt e c h n i q u et or e d u c et h en u m b e ro fs t a t e - a c t i o np a i r st h a tt h el e a r n e r sn e e dt ov i s i t e m p i r i c a ls t u d yc o n f l r i i mt h a tt h ep r o p o s e dl e a r n - i n ga l g o r i t h mc o n v e r g e st ot h es r r n er e s u l t sl e a r n e db yt r a d i t i o n a lm u l t i a g e n tr e i n f o r c e m e n t l e a r n i n gt e c h n i q u e sw i t hs i g n i f i c a n tl e a r n i n gs p e e d k e y w o r d s ：c o o p e r a t i v em u l t i a g e n td e c 缸i o nm a k i n g ，v a l u ef u n c t i o nd e c o m p o s i t i o n ，m u l t i a - g e n tc o o r d i n a t i o n ，c o o p e r a t i v em u l t i a g e n tr e i n f o r c e m e n tl e a r n i n g 插图目录 2 1 单智能体值函数实例。 1 1 3 1 囚徒烬难问题的支甜矩阵。 3 2s a 算法与v e 羹法豹健镌眈较 3 3s a 算法计算出的刨报( 相对于v e 作折算) 5 1r o b o c u p 2 d 机器人仿囊足球赛开娥时的佬景。4 8 5 2 赭食卷阏题豹开始塌聚。5 5 5 3 捕食者问题试验结果 5 5 锐 耱 ；穹 算法嚣录 霜憩辞鬣算法。，i 肇 角色规则实例化算法， 1 6 德拽m 4 索引算法 1 筑娥瓣糗素舞法薹8 龠俸穗多智能体决策算法2 2 模4 蕃c 邋火算法。瓣 溅投舞涟舞蘧生袋攀瓤 攀鬻裁体q 学嚣3 鏊 蒸予角色特定童。f 震的q 学习。熊 东毫大学学健论文独裁性声翳 零人声骧掰基交的学位论文是我个入谯鼯师撂导下遴孬的研究王传及墩褥驰辑究成果。 爆我所翔，除了文串特翮栩以标注和数谢的撬方外，论文中不包含其他入已经澄糍躐撰写过 的研究成果，也不包含为获得东南大学或其像教育机构的学位或证粥而使用过的材料。与我 一鞠工作熬丽悫对本礤究魇傲瓣任何贡献坶穗在论文孛搀了骧确的说唆并表示了澈慧。 耩巍生签名： 逛鑫垒嚣蘩：坐乒。k l 东南大学学位论文使用授投声龋 东南文学、孛嚣释学装零蕊惑璐究联、辫家窝书键骞较豫蟹零天联送交学馥论文鹃复露 锫秘黩予文档，霹蔽采蘑影露、缭霉载嚣稔笺巷手段缫存论文。搴太窀子文援麴痣察帮纸壤 论义豹内容相一教。除在保密期内酌保密论文外，允许论文被查阅和措阕，可以公廊( 包括 渊爨) 谂文豹全帮或部分内容。论文教公禽( 憩捂列登) 授权东露天紫磅究垒貔绺壤。 研究袅签名：j 嶂母师签名； 1 1 研究胬袋 第一章绪论 鲶j 鞋缀辫能俸，每个餐辘体可以傲一壤确份聪赫霄凝嗣的目标，这贱智能体应该如能协调被 托瓣渤俸，跨戆麓效趣完残稳稍共弱嚣霹耨? 滚秘粼称急两台重# 墅多智缝体决策1 。近年来，虢潞溯 翁技术、人工簿能、控制技寒鳓掴互融合，台体裂参橱能律决策技术已经城隽多智能体系绕、分衙式 太王餐缝、势枣藏羟裁颥域蠹热研究热纛。逡是霹势奔律爨雾舞戆俸凌蘩接寒蠢着耪誊广泛鳃成糟 鬻蕊。 掰翔，巍嚣入足球获，获鬟之麓褥互懿奢，缓就奢稼，簸嗣为蘸熬蘑警露舞嘉；p ：2 p 瓣鼹，蒜是 渗静觜蕊携镶壤就鹣行兔，棼主铰步粒瞬络带鬣耱较抉懿孵成时目满足焉声辩爨据鳃诲瓣髓求鲡， 获取令凇3 义肄) ；个性像阏络搜索，多个鞍穆帮毙体瓣聪搜索丐：联两，荚霹受用声醣菜个特慰 搜索秣滋如，搜索与天气，黢价有关的薪黼) 两撇势；侮麟嚣嘲络，多个传感器，如，缀豫枫、墩 枞仪、投影仪等相瓦合作，熬同监视和记录慕个特燃带件，如，监视游客墩问对博物馆的非漶协 闭；辄辫人髂救。多个机器人蝴鼍协调，以最快熊遴艘，艇少的代价对出搿她点进行搜索，馨救蹴 壤巾麓= 棼释港；分蠢式数据按掘，多今软舞：鬻黥俸黜艨糍。量：静毒豹大蘩耱侮记录数据痒滋错麓糕攥 则( 龋国蜮。裁r u l e ) 挖掘，为敬篆者提供有埘麴销俺铸恩。 遮黪采鑫现赛避赛熬痘弼鬟毒魏下4 个赞照：1 ) 系统串暴蠢多兮凌菠纛。在辊器太麓臻巾瑟多 零薅薮，程戮黔避终枣琵穗绻枣熬垂囊 蕈熹；2 决繁群麓懿谚番瞧。在浃蘩避疆孛，多争罄藐嚣遴逐 鑫：舞翁动镎，勰拳蟪影蟪焉瓣黪环境。秘絮，惑嚣天薷簸巾，蘧蓉搜寻适撵瓣举骞；逶孬，嚣枣越斑巾 漆来靛搜索的送斌不断疆小 3 ) 决策者之蠲交磊簸凝。多个决策者之翅盛绥凄捺疆键诧瓣符淹菇4 镌 以较咖辩谯价凳戚共同盼譬橼：4 ) 决策者乏瓣的邋嘏髂慰变换) 受限翩戏不可褥。决策避糨燎辩 孺程涟镳带鼹渡低甚至列络遴禳完全不可褥静情溉下遵静。翻如，在p 2 p 秘络中，翔果莱个常点教隧 本节点没谢存储_ h j 户需要的m p 3 文件，则它黼群向麒他带点转发明j i 的请求。这里，它椒该向爆燎 少的节点转教埘户请求以避免产生网络堵塞。 缝继卡菇年戆尽龋骚究鬻安我，骚究毳稍蒋漶穗爱、赞翊鞠支持这襻靛甏点： 盼土述4 巾黪魏 钓碰棚艘诚建攥为合作型多键能体系统，并埘台髂型爹错凝体决麓技本来进行求解。遮燎因为，比 熬浆巾斌决壤投零竣专_ 系缓，金箨型多智麓体凌麓技冬其宥鞋下爨赢：l 凌蒙毫效。鸯终壁多鸳 袭髂系绫孛，多令簧篷箨瓣嚣逶孬凌蒙，澎怨蘩审炎暴凌，黉整囊寒，系缓纛撬努；2 譬蒜缝菇。决 1 疰多锷旋律幕糖中靠程嚣一凳多释藏薅莰蕈越疆，黎海巍母璺多帮髓捧捷策。赣母蹙多释蘸体凌攘奄袁藩垂霉替鼗搏采簸鹩嚣蹦攫 罩意争壤多赣撩捧幕缆 争蟹争嚣毙傩f 或每，- 枣扭稽艟体，宵枣瓣瞬蛙棣。竞争罐多酱艇捧决燕投篝誊穰_ 衣鲎醯研巍内释。 l 东南人学博士学位论文 策过程扇多个智能体共嗣参与，单个智能体失效或束糍完成任务，不会导致整个系统瘫痪；3 ) 响应 及孵。凌燕过程实际上怒一个寻建避裁( 嚣文串会详缎论述) ，多令决簸者按照疆後决策进行动律， 加快了响应时间。因此，对合作型多智能体决策技术谶行研究是有重袋意义的。 1 。2 磺突瑗棱 文献i w e i 9 9 和文献 w w 0 1 指出，研究合作型多智能体决策技术的基本思路是将传统的单智能 体决策技术推广到合作型多智能体决镱技术领域。单镏能体决策技术建立在单智能体马尔科夫决策 过程摇絮乏上。 马尔科夫决策过程将智能体通过决策技术完成绘定任务的过程，着成是一个离散时间序列卜， 智能体与所处环境之间的变瓦过程。环境由组状态变龉描述，例如，机器人足球中，环境的状态可 以l | l 臻瑟、足球靼璩门豹健墨簧表示。焱每一个对间步上，蟹撬体残察环境魏当静状态( 列，靛态交 量) ，并执行适当的葫伟，扶一个状态迁移到另一个状岙，进入下一个时闻步。智能体完成任务时所 处的状淼称为吸收状态。我们为状态关联一个值函数，描述该状态服离吸收状态的远近，数值越大 表示距掰暇收状态越近。予是，研究镏熊体的决策过程辘等效于研究在任意初始状态下，智能体鲥 俺援据簸蝤鼗选择适警静动俸，强最僚瓣方式( 最夺翡代赞) 到达吸收状态。 单智能体决策技术融经相当成熟“”“嘲。将i 袅氆技术推广到台作肇多智能体系统的般方 法是将多智能体系统巾的所有智能体蓊成一个“大”的智能体，该“大”智能体的动作即为系统中所 有智麓髂豹联台秘 ；。骧螽，渡“丈”糍缝俸疆霹毅蠖瓣耘建豹攀智熊体决策技术避程决簇脚州。然 而，实际使糟该方法时，存在着很多嘲难：1 ) 值函数寝示。单智能体值函数_ l l 表格表示行表示状 态，列表乐动作，表项巾的值就是值函数的数值。然而，合作型多智能体系统中，联合动作空问的犬 小箍智能体数量静增加黧撰数增长，珥j 掰谓静“维数瑕咒”，如何表永如此规模的毽蛹黢是一个值得 研究豹翊嚣，值函数表穰袭示法不适掰予合作型多智能体系统；2 ) 念作型多智能俸系统中，多个餐 能体i 列时独立决策，如何在各智能体乏问达成一致是个问题；3 ) 念作型多智能体系统的值函数如 何获取。 蛋绕麓砖这鹫淹鹾豹掰究，台痒蘩多智藐蒋疑蒙鼓零擎瑷出班下三个研究热点： 1 值满数分解，研究如何表示和存储台作型多智熊体系统的值雨数。文献b k k 6 3 指出值函数分 艇技术可以有效她克服“维数诅咒”。该技术舶慕本思想是将辫缳值两数近似为许多低维因子 叠毒秘。鑫予存耱分解| 嚣低维因子憝健徐诋予存储骧舞维毽最数豹筏傍，掰淤该技术有效建晦 低丁“维数诅咒”带柬的影响。文献 s s 8 5 提出了一个利用线性因子来近似德甬数的方法文 献i d k 9 0 ，d l 9 5 ，b d g 9 5 l 提出使用动态贝叶斯网络来分解值函数。文献i a a k + 0 2 1 对值函数分 辫瓣瑾论误差遗舒磷究。 2 合作型多智能体协调技术，研究多个智能体如何利用值函数来协同地选择最优联合动作。义 2 第一章绪论 献【o r 刚和文献【o s b 0 3 i 讨论了对策论在多智能体协调技术中的应用，并首次将n h 平衡引入 多智能体系统中。文献i g e 培5 】和文献【c q 讨论了如何使用通讯在多个智能体之间达成一致 文献【s t 9 2 a l 和文献 s t 9 2 b 讨论了如何使用社会规则和社会习俗来协调多个智能体之间的行 为文献p k u 9 6 】提出了基丁：联合意图的多智能体协调方法。 3 合作型多智能体强化学习技术，研究多个智能体如何通过与环境做交互，来学习到最优值函 数。文献h 9 3 】和文献四m 9 7 】是较早讨论合作型多智能体强化学习技术的文献。文献【张6 a 】、 文献【王6 b 】和文献【张3 b 】分别从启发式搜索、随机对策、智能体的社会组织等角度研究了合作型 多智能体强化学习技术。 1 3 研究内容 本论文在充分继承和发展已有研究成果的摹础卜，对合作裂多智熊体决策技术的置个研究热点 问题展开深入的研究。本文将建立一个形式化的框架和一套自动化的算法，将合作型多智能体决策 技术推广到问题规模更大、更复杂的应用中去。本文的主要研究内容有： 1 值函数分解。合作型多智能体决策技术遇到的最大挑战足值函数的存储和表示方法可能遭 遇“维数诅咒”。值函数分解技术是克服“维数诅咒”的有力武器。本文着重研究合作型多智能 体系统值函数的线性分解技术。本文的研究基于以下事实：现实世界的应用中，多智能体之问 的协调关系具有某种“结构性”、。局部性”。例如，在机器人足球赛中，攻入对方半场的前锋队 员，只要在彼此之间协调动作就可以组织有效的进攻，完全不需要和球场另。端的守门员进行 配合。本文将研究如何利用智能体之间协调关系的“局部性”，将大的合作璋! 多智能体系统分 解为一系列小的合作型多智能体予系统，将原合作型多智能体系统的值函数近似为分解后合作 型多智能体子系统的值函数的线性叠加，从而降低“维数诅咒”带来的影响 2 合作型多智能体协调技术。传统的合作型多智能体协调技术存在一些口j 题：1 ) 决策过程不能完 全独立的进行，需要一些辅助手段，如通讯、协商等。2 ) 决策算法不够高效，并且不能以增量 式的方式运行，在算法未能完全终止前，不能提供任何有意义的结果，从哐不能很好的适应系 统实时性的要求。本文在对策论的框架下研究高效的合作型多智能体协调技术。本文从理论上 研究构造合作犁多钾能体防调算法的一傲方法，并研究高效的合作硝多智能体协调算法。 3 合作型多智能体强化学习技术。制约合作型多智能体强化学习技术的主要瓶颈在于，随着系统 中智能体个数的增加，学习过程中需要访问的状态一动作对呈指数增长，使学习过程过丁缓慢。 本文研究如何将值函数分解技术应用到合作型多智能体强化学习中去，减少学习过程中需要访 问的状态一动作对，提高学习速度。 3 东南大学博士学位论文 1 4 论文贡献 本论文的主要研究成果有： 1 提出了一种基于角色特定上下文的值函数分解方法。该方法利用角色将大的合作犁多智能体系 统分解为一组小的合作犁多智能体予系统，每个局部了系统内的智能体相瓦协调动作，且共享 相同的局部值函数，原系统的值函数近似为这些局部值函数的和。使用本文提出的值函数分解 方法，智能体只需存储分解后的局部值函数，由于局部值函数巾智能体的个数远少于分解前坂 系统值函数巾智能体的个数，凼此本文提出的值函数分解方法有效地降低了“维数诅咒”带来 的影响。进4 步，本文使用角色分配算法。在不同的时刻，动态地为智能体分配角色，很好地 解决了传统值蛹数分解技术只能静态地分解值函数，不能适应合作型多智能体系统动态性的缺 点。 2 证明了在合作犁多智能体系统巾，p a r e t o 最优同时也是n h 平衡，为构造高效的合作犁多智能 体协调算法提供了新的思路。在此基础之| ：，本文进步提出了一一种商效的增最式多智能体协 调算法，该算法的时间复杂度只与系统巾智能体数鼋的增长量线性关系。实验表明该算法比现 有丰流的合作型多智能体协调算法有更高的效率，并更适合系统对实时性的要求。 3 将值函数分解引入到合作型多智能体强化学习技术l i l ，提出了种新颖的基于角色特定e 下文 的多智能体q 学爿算法。该算法继承了传统的合作颦多智能体强化学爿技术一联合动作学爿的 优点，保证学习过程能够收敛，同时克服了联合动作学爿算法收敛速度缓慢的缺点。在捕食者 问题卜的模拟实验说明，在学习到几乎相同的值函数时，本文提出的算法的收敛速度比联合动 作学习算法快4 倍。 1 5 论文组织 本论文其余部分是这样进行组织的： 第_ 章介绍合作璎多智能体决策技术的理论基础。 本文的研究建奇= 在合作犁多智能体马尔科夫决策过程框架之上，本章旨先介绍这个理论框架， 然后重点讨论值函数分解技术，介绍g u e s t r i n 等人提出的值函数线性分解技术及其局限性，并在此 摹础之，卜提出基于角色特定卜下文的值函数分解技术。该技术是克服“维数诅咒”的有力武器。后文 中合作穆多智能体协调技术和合作璎多智能体强化学习技术，都以本章提出的值函数分解技术为基 础。 第三章讨论合作犁多智能体协调技术。 本章研究在值函数己知的前提下，如何构造高效的合作型多智能体协调算法，为智能体选择最 优联合动作。本章首先介绍多智能体系统中最优联合动作的两种不同定义：n h 平衡和p a r e t o 最优。 4 籀章绪论 然嚣证明，在会律型多智能体系统中，p a m t o l 忧网爵也是n a s h - _ z 鸯，扶蠢将嚣个定义统一起来，提 出了台作墅多智能体系统协调豹定义。在藏藻础之上，本章提出了构造合俸藿多智裁髂协调算法的 一般方法，并谶一步提出了基于模拟退火算法的合作型多智能体协调算法，该算法的时阐复杂度只 随智能体数阻的增加呈线性增长，从而避免丁“维数诅咒” 第嚣章磺究台箨垄多智麓臻强健学习搜零。 本章研究多个智能体如何通过与环境的不断交互来学习到最优值两数。首先简介单智能体强化 学习技术，然麟讨论单智能体强化学习技术在合作型多智能体系统中的推广，重点谈论推广过程中 避到约嚣难。聚嚣，将值函数努鳞技术g l 入戮合作壁多苕能体强纯学焉领域，挺壤7 一耪鞭颥躲多 智能体q 学习箨法，该算法较 毒统的多智能体强化学习技米窍更快的收敛速度。 第五章介鳄 合作型多智能体决策技术的臆用 本章在两个实际的合作型多智能体仿真环境巾综合实骏文中提出鲍会作型多智能体决镀技术。 本牵誊走讨论撵穗豹多智施髂褥调技零在r o b o c u p2 d 辊瓣入蘩囊足球赛审豹应霜。特嬲瓣，本章 使用文i 1 提m 的协调技术实现机器人仿真足球队的防守策略，并在实验和真实比赛t l 验证了其有效 性。接着，在捕食者问题仿真薹f = 境巾，实验了提出的合作型多智能体q 学刊算法，并与其他：l ：流的合 髂攀多锷毙嚣焱纯学习舞法避纾了递较。 第六章总结今文，并展麓来来的发展 5 第二章禽作型多智靛体决策技术的理论基础 合作型多静能体决策技术研究多个智靛体如何协调缓j 秘：韵动律，完成熬同的任务( 目标) 。合 作型多智能体决策技术遇到的最大困难是值蛹数的表示和存储遭遇“维数诅咒”1 b e 蚧在文 献 b k k 6 3 1 中攒壤，蕊醢数分簿技术楚解决“维数 壁咒”黪旨效方法。爨诿德璐数势解，就楚将器先 畿含多个智熊髂( 裔维，静蕊蕊敷，逅钕为系列弱帮薤丞数懿霹，每令翳帮链函鼗爰毯禽部分警麓 体( 低维) ，从简降低表示和存储值函数所需嚣的代价。本章在已有工作的艇础上，发展出一套基于 角色特定上下义的值函数分瓣方法。该分解方法将作为后续罐节研究合作搿多智能体协调技术秘合 捧型多智糍俸鞋锯学器疆零黪鏊磷。 为便于嘲谶，先介绍文巾数学符号的意义。本文使用大舄斜体字母袭求髓机变最，如x i 小写斜 体字母表示随机变量的一饮观测值，如毒；瓤斛体大写字母袭暴随机向鼋，如x ；粗斜体小舄n 字母表 球菠撬交爱鳃鼹溅僮，懿空心字母裹幕数繁，翔登袭蟊安数巢合。 2 ，l 基本术谲 车苇奔绥台律壅多磐蔻体决策援零孛瓣梵令薹搴壤惑；智能律、嚣璇、状态变藿、奖惩嫒数。虽 然合作型多智能体决策技术已缎研究了很多举，但是这些基本概念并没有窥憋的形式化定义。因此， 本节只对这些檄念作非形式他的批述。 餐箍体；鞴决策蠹，是一个露竣辔舞残溺) 蠲露琴境，静髓藏一缀渤佟来菠变臻蠛懿较捧实 体。 环境：在合作型多智能体系统中，对每个智能体耐吉，环境是除去谶柳髓体一身以外，系统中 其缝蛉部分。捌搬，机器人是豫的俄子中，对每个球员薅言，环境足赛场上除去 轰球员以外的所有其 它簿势，毽瑟瓣骞箕趣臻曼、鼹方薄弱，足球等。这里，琢缝蔗镑对每一个簿艇薅。蠹器镑瓣整令智 能体系统l 何言的，即每个智能体的眼中都有一个环境。 状态变量：环境 l 状态变魁米描述，状态变擐记录了某个时剿环境的究魁物理特性。例扭1 帆器 入是壤孛，获态变量谭驮瘸己穷球曼貔篷甏、对方球曼嚣袋嚣、足球魏篷鬟、辖 撞燕置掰缀戎翁鸯 懿来表示。状态变量的其体数德幽智能俸观测环境得到，并存储在智能体姻内部数据结构( 记忆体) 中。智能体完成任务( 目标) 时所处的状态称为吸收状态。 羹惩函鼗( r e w a r df u n c t i o n ) ：簧器俸熬髫标矮奖惩鹾救来袤运。援定错莪体鑫状态# 下，撬 行动箨矗，奖惩蛹教褥这一获悫一动作对f 盛) 靛瓣静一个实数，称为立努掰搬( i m m e d i a t ep a y o f f ) ， 1 越函数的形式化逭兑将在后丈中详细舟绸 7 东南大学博士学位论文 接述该状态确侉对( s ，堪) 对于智能体姘簧完成目标的价值。数值越大，表示价值越犬。例如，对于机 器入走迷塞豹铡予，霹馘将搬器又楚嶷遴窘出口并惫耄逑塞静较鑫锄俸瓣绘予委翻缀1 0 ，纛绘予 其他状态一动作对负同撤一1 0 。奖惩雨数与后文介绍的值函数之间有明照的区别。奖惩甬数橘述的悬 智能体褥劁的立即同报，而值甬数描述的是智能体经过一个离散时间序列之后，获得的立即回报的 慧枣l ，称砖织累癣壤。 2 2龠作型多智能体马尔科夫决策过程 会撵蘩多舞缝薅系统串，黉能俸鹣块策过程是令与环境豹不壤交鼍过程。在每+ 次交匿巾， 智能体燎知当前环境的状态( 观测状淼变量) ，选取并执行相应的动作改变环境，然后继续观察耕 状态，擞新状态下选择动作，周而复始，直至完成任务( 目标) 这种从状态到动作的映射称为麓 略( p o h c y ) 。显然，完成令羁振有缀多策酶可供选撵，鲡枫黎入走遴窘熬铡予巾，燕出迷富蠢缀多 种走法。健楚，这峰走法巾有冀较好( 很快走出迷宫) ，宥冀走法则魄较费时。为了擞肖决策的效率， 智能体需舞比较各种候邂主受略的优劣。并从中选出最好的策略来执行。合作型多智能体马尔科夫决 策过程为多智能体进行婊昭蚓的比较和选择提供一个形式他的框架。本节将介绍这个框架，然后讨 论策珞，壤旗魄较，最傀绫珞等穰念。 定义1 合作型多智能体马尔科夫决采过程( c m m d p ) r 是一个矾组付，s ，a ，风t 其中，n 是 智匏镑鲢个数；s = 冀，叉 是鸯穷嬲联合状态空惩；a = a 是个智能体的联合动锋盘 褥；系统夔惩函数冗( 冉 怫) = ：l 最( 嚣8 ) ，其中最：蹿a 一酲是智能体 砖奖惩蕊教，表示智舷 体 在状态。下执行联合动作口所获得的点即回报；t ：8xa x s t o ，1 1 是马尔科欠概率转移模型， 表示在状态。下，智能体执行联合动作n 后，从状态。转移到状态一的概率p ( 暑，l 。，8 ) 定义掰形式优的语禽描述了多智能体决策技术中的各要素。冀巾重要酶是多麓能体动作的寝 义，多铆能体的动作嫩义为联合动作，即系统中所有智能体的动作组成的动作向嫩，每个智能休 的动俘对点5 f 于该向量中的个分量。覆后文中，口表承多智能体的联合动捧，啦袭承联合动作口巾 对应餐髓俦磅分璧，帮镭能体 酶魂律。称鬻缝俸f 褒t 孵翔撬行联念磅律8 ，翔莱簿锈俸 在f 霹麴撬 行动作撕，即n 中对应橱能体i 的分量。多智能体的奖惩函数r ( s ，口) ，避义为系统中备镩能体的奖惩函 数危( 毛糕) 乏和 霉簧聪释瓣是条绛羧率转移矩瘁? 瓣g l 入。f 定义? 多智憩薅在敬态。下，执行袋会动孬8 _ i 厅，转 移到新状淼，的概率。为仆么要日l 入祭件概率转移矩i 唪r 呢? 这是冈为在状态8 下，多智能体执行动 作口之后进入的新状态# ，农很多情况下是不确定的。肖很多原因导致状态转移的随机性，如环境存椒 建规噪声，传感器癯测状态变量有误差镣。 为了完成任务，智辘体需要形成一个策略，即，如何在状态# 下选撵联合动作8 。 8 第二二章合作型雾智能体决策技术的理论基础 定义2 策略霄：s a 是一个状态空阍卿动谗空惩垂姨艟，蛤定莱个状态o 曼策略娩定了智能 张在获态8 下扁谊执行选取) 的联合动律靠a 帮( ) 一辄 从定义2 可以看出，策略为状态窄问中的每一个状态指派了一个联台动作。从理论一l 说，合作型 多智能体系绕一共有l a | | s 个w 鼹策略。然聪，如翦文所逮，这些策略并不都是有效的，鸯的策略蓬 惩掇本无法镁锗髓俸完成任务2 。需要建立种院较第略统劣的方法 策略的优劣根据智能体按照该策略遥彳亍完成任务的好坏来衡鼍。举窳开头提到锗能体的目 标( 任务) 用奖惩函数来描述，奖惩函数决定了状态一动作对( 肆d ) 对于目标的好坏因此。我们可以 这样箨蛰蒺嚼：对子绘定豹鞠娥状态一动终j c | ( 葶o ，8 0 ) ，令智麓钵在一夸离教瓣秘痔裂l = ( t o ，t 。 上运行无限长的时间，对予每一个时间步缸，智能体观察当前状态_ ，按照策略霄选取联合动 作口= 口( 骞) ，并得到立即i 旦l 撒n ，计算整个时阃序列t 上。智能体所得到的立即i 叫撤的总和( 称为累积 瓣摄) ，鼗餐越文漩甥繁略越好。 定义3 称函数( r ( 8 ，a ) 为襞略 r 的值函数，如果该函数计算智能体从任意初始状态咖初鲐联合动 作口开始，按熙_ ，r 选取联合动作，运行无限长时间以后得到的累积回报即。 母。和，磅一相毒t ，霄毒t ) ) s o 一南# 岛) = 8 - , 1 0 ，1 )2 t l t 牡。 定义3 用值函数形式化地描述了这个过程。唯一的不同魁定义中引入了折算因子 ，它确定了未 来回撮( ( t o ) 时刻的叫撤) 墨立即回撤0 一o 时刻的叫撒) 的相对比例。确切她说，在未来的第f 时 舞步譬麓俸l | 殳爨豹立帮鏊摄羧颡子爨指数缀折算。懿鬃设置 = & 蒸么耱能律蕤只考密立帮鹜 报。即“只着眼前”。如果设鬣1 接近于1 ，那么朱来回报相对予立即回报就有挺大的重要性3 。把未来 网报相对于崴即回报进行折算是合理的。当我们制定决策的时候，需要考虑眼前利益和长远利益的 辑衷，菏嚣考纛鞭藏剥盏，或楚t 跨瑟考虑长远利益都苓窖翳形成最往决繁 定义4 称裳略霄l 和7 f 2 是等效的，记为霄1 一批，如果对于任意指定的初始状态8 和初始联合动作“裳 略丌1 和他的值蕊数都相等即 q 陬善，8 ) = 蝣辑( 罩，司￥嚣最8 a 穆。2 ) 窳义5 称策略撕优于丌2 ，记为”i 卜砸，如果对于任意指定的初始状态s 和初始联合动作n 满足 q 霄1 以q p ( 毛 并且，至少存巍一个初始状态摹。和初始联合动作o o 满足 露3 ) q ”( 柏，a o ) q ”( 8 0 ，a o ) ( 2 4 ) 4 这一点麻该尽裔链，肇臻鞋罡赫争鹃建状卷夸簿申熬扶叁拯罐麓箨，本身捧拳熊辍涯多智能髂接熙壤鼙喀撬舒。赣一定熊迭捌甍个颈糖 豁珏嚣。 3 这里有一十村魁：能否设置7 1 却米来和现在同尊重蜚或未来比现在蜓重簧誉章的琏如此一束。任何堆杆麓体或多钾能体强化 学习算法部无法收敛一相笑的理论分析可以在空献【s b 弼l 中拽剿， g 东南人学博士学位论文 定义4 和定义5 形式他地定义了筑路之间等效和偏序关系。可以诞明，在智能体阿供选择的候选 策略孛，懋少存在一令繁蛲往予其它褒籽策略，该策蜷称隽最谨寰臻4 。簸往策旗对殿静毽舜数嚣务 最优值漪歉。 定义8 祜麓喀霄是最优篡略，知果对嵇露给定的蓑略一，满足矿卜 定义7 称值函数q 0 ，a ) 为最优值函数，如果q ( ，口) 最最优策略对庶的值函数即，q ( s ，o ) 满足 q ( s ，a 。= m 8 x q 。( 0 ，口) ( 2 5 ) i 最後值函数是合俸型多智能体决蒙技术中最重要的概念根本上说，合作型多镯能体决策技术 就是研究如何获取最优值函数，如何存储展优值函数，以及如何根据蛙优值函数米选择动作本文 剩下约部分将完全匿绕最饯毽函数鹱歼讨论。为叙述，卜方催，下文中如粜没有特璩说明，凡提到德 函数均措簸优僖函数。 一戴有三种获取最优值函数的方法：1 ) 由人类的先验知识直接给出乍看起泉，这似乎很难。 毕竟，台作型多智能体系统一觳比较复杂，设计者如何能仪凭借经验就给出最优值两数? 然而，事变 土遥过转缩蕊设谤、鼹察藿l 试验，设谤卷薅实霉鞋绘斑较好爨篷函数( 虽然霹能苓定最嚣) ，满足 系统的蘩求。本文在第瓜章讨论机器人足球的具体应用时，给出了一个利用先验蜘诚巍接给出值函 数的例予。2 ) 如果合作型多智能体系统的状态转移概率模型己知，即c m m d p 巾的r 已知，值函数 可跃避避动态翘裁豹方法求解b e l l m a n 袋德纯方程缮剃。g u e s t r i n 定文漱 o k p v 0 2 哼 讨论了这种技 术。1 3 ) 如粜状态转移穰串模型也不知邀，剐值函数可甑邋过多智能体缓化学习技术采得到。 本文柱第三章讨论如何根据值甬数进行决策，第四章讨论如何使用多智能体强化学习技术柬向 动学习缎丽数。在此之前，奉文蓄先讨论如何表示、存储和访问合作型多智能体系绕的值甬致。 2 3 德黼数的线性分解 在研究合 # 型多智能体决策技零乏翁，人们已经对单智能体决策技米进行了，“泛鹩研究。借臻 单替藐体决簧技术舔究审l l 孽成莱，著将其推j “刭台律鬃多智能俸决策技术辞l 去蔗育蘸的。 在黔智能体决策技术中，值函数嵌示为两维表格。每一行表示一个状态，每一列袭示一个特定 动作，单冠格中的值就怒值函数的数德。图2 1 给出一个其有4 个状态，5 童- 动作的单锗挠体值甬数的 实恻。其巾，每一嚣存戆了该获态f ，餐麓体羲辜i 备动佟掰能褥到鳃辩欹霾擐熬大夺。该表掇懿嫠翔 非常简单，存每一个时问步，智能体感知当前状态，然艏定位到表格中的某一行取出该行中筹动作 对应的嫩积同报，选取w 以产生最大累积网报的动作执行l p 町。对予一个具有i s l 个状态，l a l 个动作 豹系统，袋将表示法嚣骤o 褒嗣1 - 4 1 ) 个存储空淘。 最馋壤喀岿然存在，但车一逛唯一，研髓存在释千个等效鲍晨优策略嶷避种情醒下嚣艨体赋蔷蔓捷行黄中往榉一十策略即可，嚣丈 会详述这个闷臆 第二章合作型多智能体决镱技术的理论基础 8 1 8 2 8 3 曩l g i o , 2 a s瓠0 , 5 2 3o 9o o1 o1 5 0 20 71 02 0 0 2 1 oo 。7o 5o 1氆2 2 ，3o 。o王，2& 3o 1 图2 1 单钢能体值函数蜜倒 表搔表永法簿萃、高簸，在单智藐髂决繁技求中广为袋耀。原刚上，可以按照班下方式将单智能 体值函数的表格袭示法推广剿合作型多智能体系统中。酋先，将多智能体系统中所有智能体看成一 个的“大”的镪能体，该“大”魍能体的状态缴闻为原多智能体系统的联合状态空闻，该“犬”智能体 黥动箨空闻秀瓣多磐缝钵系缓豹联会动终黧瓣。然嚣，菇翊装捂表示法存撩该“夭”智能俸翁蕴涵 数。不幸的悬，这种值雨数袭承法在实际使用时，存在着不_ 町逾越的困难。雾智能体系统的联合动作 定义为所有智能体的动作组成的向量，假设系统中有n 个智熊体，每个智能体有i a l 个动作，则联合动 俸藏量就有 a 妒令霹艇数取煞。采耀表捂方法存储筐函数，辘嚣耍o ( i s txl a ) 个存储单元。也就是 说，表格的规模随系统中智穗体的数羁静增加垦指数增长，静所谓黥“维数遘咒8 。邵使瓣t ：规模不 人的多智能体系统，这种方法都是不现实的。 合作型多智能体系统的联台动作空问的规模是指数缴的单智能体决壤技术中的值瞬数泛他技 零哭钷赴理 天规模获态空弱，茏法楚理又燧横动幸# 空阉。簸疆论上谎，无法褥据数缓鹃葫撵空离缩 减为多项式规模的动作空间。本质上说，联合动作体现了智能体之间的一种协调关系( 依赖关系) ， 钾能体只有执行联合动作，才能获得期望的累积同报。例如，考虑一个拥有3 个智能体的系统，值函 数为q s ， a l ，犯，8 3 = 1 0 。瓣象磐娩体褒状态。下，怒要获褥1 8 熬累积雕报，那么3 拿智缝俸必簇 同时分剃执行穗l 、a 2 、船。幸j 蠢的是，现实世界中的应用中，智能体之闯的协调关系 依赖荚系) 往 雒只发生在一小组钾能体之间，换句话说，鼹获得一定的累积回报，不一定骚系统中所有的智能体 网对协调动作，褥只藉要一部分智能俸参与协调就可以了。可以利用这种协调关系的局部性，将复 杂豹暂施俸系统翅分为一些独斑的予系统，获两褥琢先高维静氆函数近耘为一连事弱都缀蝤教豹和， 每一个局部值函数只有一部分钾能体参与( 低维) ，从而减小联合动作空间的规模 一个实际的例子更容易说明阿邀。考虑由一个守门员和两个前锋组成黝简化的机器人足球队。 该系统壹3 令磐麓俸维藏，霆魏载会动终蹙一个3 维貔蠹量8 一 ，系统辍丞数囊q 。，8 ) 表 示。考虑这样一个场景：两名前锋在对方禁区内相互传球配合创造射门的机会，这时邀在球场另 一端的守门员并不需要参与两名前锋在对方禁区内的进攻，他完全可以忽略前锋之间的动作，仪 依靠自己豹剐辑猿立进行决繁。也就是说，在这个隧裁，壤娩俸之竭豹汝调关系炙发生涎名藏锋 组成豹子系统之内，守门受释不需要参与前镣之闯的配合。网北，可以将照个系统剃分为两个独 崴的予系统：一个子系统由两名前锋队员组成，另一个子系统由守门掇组成，原系统的全局值 王l 东南大学博士学识论文 函数q ( s ，田，可以近叛为嚣名翦锋的弱帮毽蘧数q 1 2 ( $ ，a 1 2 ) 与守门曼戆局蘩毽i 爱数q 3 ( s ，翘) 之秘， 帮q ( s ，妨一q 控，o , 1 2 ) + b 和，如) 。翔筵一来，磐能诲炎鬟簧存德q n 轴，8 t 2 ) 窝矗秘，锄) 裁剪汉7 缓定镱令球受霹鞋撬行5 个动终。分解蘸，联合凌撵缀阂审茭有驴= 粥个可能的联合动作。分鳞聪， 原先3 缎鹩联合动作向量被分解成一个2 维的联合韵律向豢( 两名前锋) 和一个1 维的动作嶷藿( 寄门 员) ，予怒总的动作个数为2 5 + 5 = 3 7 ，只相当予原先联合动作总数的1 5 ，8 5 的联合动作郝被漓 减掉了。并n ，在减小联合动作空间大小的同时，值甬数分解技术也减小了联合状态空间的人小。双 有需要协调动作的前锋球员之问才需要观察和记录彼此的位置( 状态) 信息，不发生协调关系的球 员之问不需要观察彼此的状态。在上例中，前锋球员就龙衢观察守门员帕状态 搴安上，这种值两数的线性分解在很多时饭町以掇火的缩减决镶时需要存储和考虑的联合动馆 数h ，褥时其至w 以将原先指数规模的动作空润溺减必多项式援模归酬。虽然，值承数分解从暇怒 上其是使期筠帮箍溺数熬魏东近毅全局毽最数。德蹙，崔一定愤嚣下，这秘近织嚣霭逼近蓑至碍以 达到全掰簸溺数，在一般倍嚣下，线性分解嚣豹壤舔数秘全弱燕爨数之蠲豹误差氇霹壤粒铡在一霆 豹范溺黻肉。关予这些理论上熬分辑枣l 娃论，文献 g u e o a 豢l 文献 s b 9 8 有详细弱讨论，鸯 篱辆掰 限，本文举髯赘述 囊此，本节介绍了值函数线性分解技术的基本慰怨。接着，本节将讨论如何表示分桶以厨的德 雨数。单镏能体决策技术中的表格表示法已经不再适用。g u e s t d n 镣人提出使用值规则柬描述分解 以后的髑部值萌数。 定义8 慷规划p - - - - - 是- - 4 m 毒t p ：s a _ 魁满足p ( 口) = 口如果智能体在状态8 下 执行联合动作“英c v 是智能体获得的累积回报，誉划为0 囊鬟。 我们糖髑帮蘧丞数袭示为一系列蕊规剩的和，从瓣，令塌德遗鼗蠹局郝毽蠡数豹线性鳃套米避 定义9 称酝：s a 一裴是由智鹈镶a g e 嘶 嗣一