（计算机软件与理论专业论文）多主体环境下的行动选择和意图冲突研究.pdf

多主体环境下的行动选择和意图冲突研究 姐雪尧 藕导老师：陈小平撇 摘要 动态4 i 确定环境f 的多主体决策是人i ：智能研究中的+ 个关键问题，该决策问题可以归结为 尚层的意图乍成和“意图冲突”调解问题以及底层的行动选择问题。奉论文分析了当前动态 小确定环境f 多毛体推理决策和意图冲突研究的现状，指出r 当前研究的缺陷，为r 适应动 态不确定环境所包含的行动的不确定性，艇察的不确定性以及环境的不可预测性，给出r 翌至! 竺些笪达董焦显搓型型! ! 哑堑垄些堡型圭垄：兰丝岂三堡型塑盗蒌兰竺竺鳖，枣 图冲突描述机制，意图生成机制以及意图冲突调解机制并且与相关工作进行了比较，分析 说明了模型的合理性。m i c i p 模型的主要特点是将p ( ) 物p 理论、规划方法和b d i 理论相结合。 这样做的好处是：1 ) 系统依然保存了传统规划理论的一些特点比如m e a n s - c a d 推理等：2 ) 增加了p o m d p 中的量化分析手段，便于系统地分折合作和冲突问题：3 ) 更加方便准确的 描述环境的动态不确定性，符合实际问题的需要。因为模型结合了p o m d p 和p i t s 的一些 优点，p o m d p 可以更好的描述环境的动态不确定性而p r s 中计划的引入以及类似于p r s 的规划和子规划的持续选择和展开保证了推理的及时性，也能够更加适应环境的动态不确定 性。4 ) 模型中引入了通讯的概念并对通讯和观察作了详细的讨论，分析了不同条件下模型 的复杂度问题。 最后，沦文讨论r 模型的系统实现框架，给出了具体的决策推理算法。由于四足机器狗比赛 环境是一个研究动态不确定环境下多主体的行动选择以及意图冲突的典型甲台，作者又在该 典型环境下设计了1 个两个机器狗的关于局部进攻和防守合作的典型问题，使用m t i c p 模 型抽象该问题并且进行r 试验分析，进步和以往使用的传统的有限状态机结合决策沦的方 法进行r 比较，说明_ r 模犁的合理性。 关键词：智能t 体；b d i ；p o m d t ： ；意i 睾l ：冲突：规划；行动选择 a c t i o ns e l e c t i o na n di n t e n t i o nc o n f l i c t sr 朗腿h i nm u l t i a g e n tc o n t e x t s l i ux u e l i a a g d i r e c t e db y ：p r o f c h e nx i a o p i n g a b s t r a c t m u l t i a g e n td e c i s i o na n dc o o p e r a t i o ni nd y n a m i ce n v i r o n m e n t si sak e yp r o b l e mi na r t i f i c i a l i n t e l l i g e n c er e s e a r c hm a n yb e h a v i o rd e c i s i o np r o b l e m si nm u l t i a g e n ts y s t e m sc a l lb ec o n s i d e r e d a si n t e n t i o ns e l e c t i o n ，i n t e n t i o ng e n e r a t i o na n di n t e n t i o nc o n f l i c t sr e s o l u t i o np r o b l e m sa th i g h d e c i s i o nl e v e la n da c t i o ns e l e c t i o np r o b l e ma tl o wd e c i s i o nl e v e lt h i sp a p e ra n a l y s e st h e d e f i c i e n c i e si nt h ec u r r e n tr e s e a r c ha n dt h e np r e s e n t san e wm o d e l ( m t i c p ) ，w h i c hc a nb em o r e a d a p t e df o rd y n a m i ce n v i r o n m e n t s ，s u c ha sa c t i o nd y n a m i c s ，o b s e r v a t i o nd y n a m i c se t cw i t ht h i s m o d e lw ec a r lh a v ear e s e a t - c ha b o u tm u l t i a g e n tc o o p e r a t i o n , i n t e n t i o ng e n e r a t i o n ，i n t e n t i o n c o n f l i c t sr e s o l u t i o na n da c t i o ns e l e c t i o np r o b l e m sn e x tt h ep a p e ra n a l y s e st h ec o w e c t n e s $ o ft h e m o d e lm t i c pm o d e li n t e g r a t e sp o m d pt h e o r y ，p r sl i k ep l a n i n ga n dt h ei d e a si nb d i t h e o r y s ot h em o d e lh a st h ef o l l o w i n ga d v a j 3 t g e s ；1 ) t h em o d e la l s oh a st h ep r o p e r t i e ss u c ha s m e a n s e n dr e a s o n i n ga n dp l a n n i n g ；2 ) t h em o d e lh a sq u a n t i t a t i v ea n a l y s i sp r o p e r t yw h i c hc a nb e u s e dt oa n a l y z et h ep r o p e r t i e so f t h em o d e l ；3 ) t h em o d e li sb e t t e rf o rd y n a m i ce n v i r o n m e n t sa n d c a na l s or e a s o nt m m e d i a t e l yf o ri t si n t e g r a t i o no ft h ep o m d pa n dp r s sp r o p e r t i e s - 一p o m d p a b s t r a c t st h ed y n a m i cp r o p e r t i e so ft h ee n v i r o n m e n t sa n dp r su s e sp l a na n ds u b p l a ng e n e r a t i o n a n ds e l e c t i o nt or e a s o na n dr e a c t i m m e d i a t e l y 4 ) t h em o d e li n t r o d u c e st h ec o n c e p to f c o m m u n i c a t i o n ，a n dt h e nc l a s s i f i e st h eo b s e r v a t i o na n dc o m m u n i c a t i o n ，j u s t i f i e st h eq u a n t i t a t i v e p r o p e r t i e so f t h em o d e l n e x tt h ep a p e ra n a l y s e st h es y s t e mc o n s t r a c f i o no f t h em o d e la n dg i v e st h ed e t a i l e da l g o r i t h m so f t h es y s t e mi m p l e m e n t a t i o ns o n ya i b of o u r - l e g g e dr o b o ts o c c e rm a t c hi sa g o o dp l a t t b r mf o r r e s e a r c ha b o u tm u h i a g e n ts y s t e md e c i s i o na n do t h e rf r o n t - e d g ep r o b l e m ss oi no r d e rt op r o v et h e c o r r e c t n e s so ft h em o d e l ，w ed e s i g nat y p i c a lp r o b l e mi nt h i sp l a t f o r m ：t w or o b o t su s i n gt h e e n v i r o n m e n t si n f o r m a t i o no f v i s i n n ，l o c a l i z a t i o n ，a n dc o 皿帅u n i c a t i o ni n f o r m a t i o nt or e a s o na b o u t t h e i rb e h a v i o r sw h o s ef u n d a m e n t a lb e h a v i o r sa r ea t t a c k i n go r s u p p o r t - a t t a c k i n g t h e nw e i m p l e m e n tt h eb e h a v i o rs y s t e mu s i n gm t i c pm o d e la n dc o m p a r ei tv a t ht h ef m i t es t a t em a c h i n e d e c i s i o nm e t h o da n dp r o v et h ec o l t e c u l e s so f t h em t i c i ) k e y w o r d ：a g e n t s ；b d i ；p o m d p ；i n t e n t i o nc o n f l i c t s ；p l a n n m g ；a c t i o ns e l e c t i o n 中圜科学技术是肇硕士学位论文 第一章绪论 1 0 引言 动态不确定环境下多主体系统( m u l t i a g e n ts y s t e m ) 的决策推理是当前人工智 能研究的一个基本问题。环境的动态不确定性主要表现为以下几个方面： ( 1 ) 环境的不可预测性。主体只是环境的一个组成部分，在环境中还有许多 其他未知或不可察的因素作用于环境，所以环境的演化是不能精确预期的。 f 2 ) 行动的不确定性。主体的行动效果是不确定的，不能准确预测其对环境 的作用效果。 ( 3 ) 观察的不确定性。主体从环境中获取的观察可能是部分、不准确的，在 合作通讯中主体从同伴获得的信息也有可能是不可靠的( 即使同伴是诚实可信条 件下1 。 针对环境的动态不确定性，传统的推理方法已经不能适用，所以目前的研究 也提出了不少模型和系统，p r s 和p o m d p 等是其中的代表性工作。 同时多主体系统决策中的很多问题的解决归结为意图冲突的刻画和意图冲 突的调解机制。在动态不确定环境中，一个阴队及团队中的单个主体在执行其目 标的过程中，时时都会面临新的“机会”或新的“风险”，这就要求主体表现出 一定的适应性。主体应该如何在动态不确定环境中作出合理的决策? 主体是否应 该修改关于自身或对团队的承诺? 主体应该如何改变原有的承诺? 主体应该如 何衡量不同意图之间的优劣? 这些问题从概念上被认为是“意图冲突”( i n t e n t i o n c o n f l i c t ) 问题，解决这些冲突的机制被称作意图冲突调解( i n t e n t i o n r e c o n c i l i a t i o n ) 机制。1 ：。意图冲突是近年来多主体系统研究的一个新兴热点和研 究手段，不过目前，对意图冲突的深入研究还比较少，大部分的研究还处于通过 模拟试验观察特性的阶段，没有上升到理论的高度“。“。 由于环境的动态不确定性的影响，主体内部和主体间的冲突也具有动态不确 定性。 中国科擘技术太学硕士学位论之 ( 1 ) 冲突具有f = _ = 可预测性：由于环境的变化足不可精确预期的t 所以冲突的 演化也是不可精确预期的。 ( 2 ) 冲突具胄小可避免性：由于行动和观察的不确定性，行动的结果随时可 能和合作意图以及本身的期望等遗成矛盾，所以冲突也足不可以完全避免的。 由于这些动态不确定因素，冲突不能够事先描述完全，像很多现实系统应用 i 】的领域知i ：f ! 一样，我们不能够按照已有的冲突类型等进行划分并在系统中给出 设计好的解决方案，所以我们需要的是一个一般性的描述冲突和调解冲突的机 制。而且冲突的研究同时需要一个好的试验平台，传统的推理系统由于其本身对 环境动态不确定性描述和适应能力的缺陷因此不适合冲突的研究，作者研究了 p o m d p 和p r s 这两个模型和系统，这两个系统的结合不仅可以更好的解决环境 的动态不确定性对推理造成的困难，而且也为冲突的研究提供了一个新的平台。 同时，近十几年来的合作研究主要采用b d i 理论、o 6 给出合作的形式 化规范描述，指导领域内具体合作问题的锯决。尽管b d i 在一定程度上可以给 山多主体合作的形式化描述，但是由于本身方法的描述手段和特性的局限，还有 一些问题无法解决或者说不在b d i 模型的主要考虑范围以内“： ( 1 ) b d i 方法没有办法给出合作描述的有效性，即没有办法采用“定量方法” 分析其所给出的方案的复杂性等。比如联合意图理论( j o i n ti n t e n t i o n ) ，共享规划 理论( s h a r e d p l a n ) 等等”1 5 。 ( 2 ) 尽管当前的某些具体系统实现中结合进了决策论的方法9 ”，但是仍 然没有给出系统的有效性和复杂性，问题依然存在。比如t a m b e 的空战系统结 合了j o i n ti n t e n t i o n 和决策论的内容，系统利用决策论来选择t 体是否通信， 但是仍然没有办法给出系统的算法复杂度等有效性分析。 为了解决上述问题，在b d i 模型的基础上，许多研究者又采用了新的研究 方法，也扩充了新的研究内容，即合作阔题的量化分析。髫前研究主要采用两种 方案：( 1 ) 合作问题依然采用b d i 理论实现，但是又重新用p o m d p 的方法刻画 系统，分析系统的有效性”；( 2 ) 合作问题的实现采用p o m d p 方法c 1 2 ：, 并分 析其有效性，同时采用b d i 方法监视系统的一些关键问题。所以，目前的研究 都是p o m d p 和b d i 各为独立的部分，系统模型中并没有有效的结合。 作者论文的主要_ t 作是采用一种新的模型描述和解决多主体系统的推理决 策问题，并且在此模型基础上进一步研究多主体系统合作中的冲突问题。该模型 中国科学技术走学硕士学位论支 结合rp o m d p ，d l 理论以及持续规划理论p r s 的优点，以p o m d p 为旗奉框 架，州入规划概念。和b d 概念。这样做的好处是：( 1 ) 系统依然保存了传统 规划理论的一些特点，比如m e a n s - e n d 捧理，规划的持续展开和选择等；( 2 ) 系 统增加rp o m d p 中的量化分析手段，便于系统地分析合作和冲突问题；( 3 ) 系 统可以更加方便的描述环境的动态不确定性，也更加符合实际环境的这种动态不 确定的特点。i j = ；l 为系统模型结合了p o m d p 和ip r s 的一些优点，能够有效的进 行推理和适应环境的动态不确定性。 本文研究的主要背景是四足自置机器人( 机器狗) 比赛，机器狗所处的环境 就是一个动态不确定的环境，同时多个机器狗之间需要合作来共同完成进攻和防 守的任务。在比赛过程中，单个机器狗时刻面l 临新的选择，形成许多潜在的意图， 这样机器狗很多时候都会面临意图冲突和调解的问题。所以，四足自主机器人比 赛是一个研究和分析多主体合作环境下的决策，行动选择问题以及意图冲突和调 解机制的典型平台。本研究中给出了模型的原型和系统实现，同时在四足自主机 器人平台中进行了试验分析。 1 。1 行动选择问题 “行动选择”是人工智能、博奔论和经济学等领域共同关心的一个基本问题， 具有极其重要的科学意义和极其广阔的应用背景。从人工智能的观点看，智能主 体需要在复杂动态环境中，利用有限的时问和其他资源，合理地选择自己的动作。 因此，智能主体的性能在很大程度上是由行动选择机制的性能决定的。 行动选择机制的研究已经积累了大最成果，提出了多种不同的思路和方法， 比如基于符号主义的传统规划方法：联接丰义采用的神经网络，强化学习方法2 6 i 2 7 ：2 8 川；b r o o k s 的反应式系统：2 3 ：2 4 ：2 f ：学习分类器系统( l c s ) 。1 9 ：2 0 口。；m a s m ( m a e sa c t i o ns e l e c t i o nm e c h a n i s m ) 方法”。“”等等。根据不同 的角度，现有行动选择机制可以有不同的分类标准。例如有基于时间的行动选择 机制和基于状态的行动选择机制；层次式结构的行动选择机制和非层次式结构的 行动选择机制；带学习功能的行动选择机制和不带学习功能的行动选择机制：反 应式机制和慎思式机制等等。 行动选择问题不意味着为了追求一个单独的目标而进行的底层动作的选择， 而是在高层有冲突或者异构的目标之问的选择。这些目标可以被并发的执行，它 们可以组合起来形成更大的目标，不过，一般来说它们只是会相互影响。它们可 中圆科学技术戈学硕士学位论丈 能没有终i i ：条件。 奉文的研究工作也归为行动选择问题的研究，文l i 给m 的模型系统及其实现 也不足单一的单f = i 标推理系统( 这种推理方式类似于传统的舰划系统) ，而是一 种岛层f 1 标或扦意图之间的选择，这种选择会进一步分解为底层的原于动作。意 | 之开j 可以被并发执行，同时它们也根捌需要被挂起或者恢复，甚至中止后续执 行。 1 2 决策冲突问题 多差体系统中的决策推理是人r t 智能研究中韵一个基本问题。多主体系统 中，很多研究工作采用b d i 方法描述主体的合作框架，并且采用规划的方法进 行决策推理。同时，主体在决策推理过程中会造成有很多方面的冲突，从主体本 身的意图冲突到主体间为了争夺资源引起的资源冲突等等，冲突是主体决策推理 中不可回避的一个概念。 所以冲突研究也是分布式人工智能和社会学中的一个主要问题。自从g e o r g s i m m e l 一现代社会学的开创者只一，在一个世纪以前发表了一篇著名的关于冲突 斗争的文章之后，冲突已经被认为是社会学研究中的主要课题只一，不过仅仅在 l o 年前m a r ck l e i n 才首先提出冲突应该是分布式人工智能中很重要的并且是很 关键性的问题，但是现在还没有全面的理论上的理解清楚和描述清楚问题的本 质。不过社会学己经成功的解决了一些问题，所以对分布式人工智能( d a i ) 的 研究很有借鉴意义。 首先我们看看在社会学中关于冲突的看法。在社会学研究中，s i m m e l 认为： “通过冲突可以发现那些隐藏的价值和准则，因此冲突不是对一般价值的偶然的 证交，而是一个媒介，那些价值可以通过其而被证实”。在s i m m e l 的社会学观点 中，冲突问题具有正面的作用，认为其对社会生活有益处。今天，社会学研究中 已经普遍认为冲突是证实社会基本价值的关键手段也是结构性社会变革的主要 嘲j3 。 和社会学的研究相反，认为“冲突不应该被简单的避免或者o u t d e s i g n e d ” 在d a i 研究中还是比较新的观点【”。自从分布式问题求解作为集中式求解办 法的一种替代办法以来，d a i 研究一直被多主体系统引发的“混乱的非内聚的个 体形成的团体”所困扰。确实，合作问题求解的终极目标，全局的内聚性，一直 受到以下方面的威胁：“主体可能传播错误的和扭曲的信息，多个主体可能同时 4 中圆科学技术戈学硕士学位论丈 相互竞争非共享资源，i 体可能不明智地通过某些行为抵消r l 他k 体行动的作 用效果，或者同一个行动可能被多次冗余的执行等等。从而导致这样的系统变得 非常复杂，引发了非线性的冲突和混乱。在这种情况卜合作( c o o r d i n a t i o n ) 变得 非常踊难，1 _ l 足也非常重要”。 当然自_ 很强的观点支持在冲突混乱变得致命以前我们亚应该避免和 o u t d e s i g n i n g 冲突的发乍。但是当多主体系统变得复杂以后合理的冲突避免也变 得更力复杂。这样，在d a i 中就仃r 一个新的观点：冲突不能够仪仅被避免而 是必须被认为是正常的社会行为”。冲突变得f i 可避免，吲为满足了多主体系 统中增长的规模和自 性的特性1 3 3j 。因为冲突已经被认为是“合作的焦点”，它 们“必须显示地被解决”而不能够被排除在研究之外，仅被简单的认为是“会伤 害整个主体社会性能的不想要的副作用”1 32 。所有这些引入都传递了同样的信 息：“在多主体系统中冲突是无处不在的”。自主性( a u t o n o m y ) 和智能性 ( i n t e l l i g e n c e ) 是主体的重要的性质。事实 i ，如果主体只是被动的或者机械的执 行一个严格指定好的任务，它可能不会很好的解决很多问题，因为它不能适应外 部环境的动态性和不确定性从而寻找更好的解决方案。当然这里有一个折衷：如 果主体越自主和智能( 能够解决问题，能够具有选择性，能够自主推理和规划) ， 那么它也许就会有更多的“叛逆性”，会有更多的矛盾冲突等需要解决。 多主体合作( c o l l a b o r a t i v e ) 环境意味着冲突的发生不是由于主体间的竞争 或者敌对，而是由于主体间合作的矛盾而引起的。进一步来说，一个主体a 。想 要执行一个不是a 2 所期望的帮助性的行动，或者a 想要执行一个代理性的但是 不是a 2 所期望的动作的原因不是由于主体本身的自身利益的驱动，而是为了更 好的合作( c o i l a b o r a t i o n ) 。 1 3 内容安排 第：章主要讨论和多t 体决策推理以及和意图冲突研究有关的一些重要研 究工作：第三章介绍作者研究的推理系统模型和冲突模型：第四章讨论模型的系 统实现和模型的一些性质；篇五章针对个具体应用讨论模型的一些问题；第六 章总结作者的研究工作。 中国科学技术走学硕士学位论文 第二章相关研究简述 这一章卜要介绍和本文研究相关的一些研究t 作，这些研究t 作是关于动态 1 i 确定环境下决策推理、行动选择和意图冲突等研究的经典工作，他们是本文研 究工作的起点，为本文的研究提供_ r 思路和基础性理论支持。f 面，我们分别介 绍和讨论。 2 。1c o m m t d p 模型 d a v i dvp y n a d a t h ，t a m b e 等人的c o m m t d p 模型“扩充了博弈论基本模 型，用于描述b d i 框架中的合作理论，比如j o i n ti n t e n t i o n 和s t e a m 等，并且 研究了该模型的复杂度问题。c o m m t d p 模型可以转换为p o m d p 模型，所以 可以认为c o m m t d p 依然是采用p o m d p 的方式刻画多主体合作理论，这样本 文中很多关于p o m d p 部分的原理和c o m m t d p 模型的基本原理是相通的”。 c o m m t d p 基本模型是 ，可以说从基本模型的刻 画上来说，c o m m t d p 和本文有很多相似之处，但是本文基奉模型的刻画引入 了规划理论中的一个重要概念汁划，结合rp r s 关于系统推理的很多优点，同 时在模型的基础上具体阐述j ，b d 的体现和作用。 2 2p r s 系统 p r s ( p r o c e d u r a lr e a s o n i n gs y s t e m ) 存意图的激发过程中也体现了意图冲突 的概念，但是在p r s 叶1 并没有明确这个概念。而且p r s 的实现主要采用过程性 知识，使用的是渭词逻辑，所以它主要还是可以认为是b d i 工作的一部分分支。 本文的研究部分借鉴了p r s 中过程性知识的表示以及过程性知识的推理。“ p r s 是从使用传统编程语言以及基于规则的专家系统构建实时、持续活动的 智能系统演化而来，传统的编程语言不能适应参数等的动态指定问题，而专家系 6 中国科学技术大学磺士学位论文 则不能够很容易地描述动作或测试等1 1f 义环境。在p r s 中最主要的概念就是 规划。p r s 足一个持续舰划系统，它交许地寅拖规划和行动，根据环境的演进小 断扩展、调整计划并执行适当的行动，岗而能够在一定程度i ：适应环境的动态特 性，爿：j 自较高的决策效率。p r s 的e 要特点是推理过程是建立在事先定义好的 过程性知识( 计划) l ：，系统j 有快速的反应性同时具有面向目标性，同时系统 具自_ 兀级别的推理，也就是远离于领域知识的推理过程，它足一个一般性的关于 意图生成和管理的过程。p r s 仵知识库c l 预存领域相关的局部计划，即所渭过程 性知识。在实际解决问题的过程中，系统根据即时信念、事件和目标，不断的选 择、组合( 扩展) 、修改和执行局部计划。这种方式使得p r s 既能够较好地利用领 域定性知识，又能够较好的适应环境的动态变化。但是，p r s 没有为环境和行动 的不确定性提供专门的处理机制。 p r s 己被n a s a 用于航天飞机的故障处理并获得成功。6 ，此外还开发出 了各种不同种类的p r s 实用工具和环境，比如d m a r s ”。和u m p r s “等。 另外r a o3 8 。，w o o l d r i d g e = 3 等人对p r s 类系统作了比较深入的形式化研究。 2 。3d b & s 冲突研究 哈佛大学的d a v i d g s u l l i v a n ，b a r b a r aj g r o s z ，s a r i t k r a u s 设计了一个模拟 试验平台s p i r e ，用于试验分析各种外部环境因素以及效用函数对主体意图的修 改和选择的影响，并且给出数据分析的结果。m i t 的s a n m a yd a s 对s p i r e 平台 做了修改，加入了对学习功能的研究。他们的分析并没有从理论上刻画意图冲突， 只是在试验的基础上研究意图冲突表现出来的一些性质。；。 他们的_ _ i 二作主要研究的内容是关十自我并且合作的主体当它们对团队行动 的承诺和新来的对其他的行动或计划的承诺冲突时所作的决策问题。他们结合了 当前研究的两个方向：一个是关于多主体系统的合作研究一4 1 m h 川4 4 。，这些 合作研究主要是给出了合作的定义性的描述，建立了个体对联合行动( j o i n t a c t i o n ) 的承诺。尽管各种具体的理论对于承诺的定义不尽相同，但是它们都承 认其作为中心位置的地位；另外一个方向是理性和资源有限推理( r a t i o n a l i t ya n d r e s o u r c e b o u n d e dr e a s o n i n g ) “1 4 6 1 该理论中主体需要根据需要动态的采纳计划 采适应环境中突现的机会和变化，有的时候还需要放弃承诺。但是这种理论主要 集中研究计划在单个个体计划的上下文中的管理和演化。所以d b s 的工作就 是结合了这两个方向的工作，研究主要解决了合作性主体在多主体环境中管理计 7 中国科学技术太学硕士学位论吏 划和意1 5 l 的需要，联合的推理 - f 本对单i ：体计划的承诺以及对i ；羽队行动的承诺 等。 d b & s 研究的问题可以简单的描述为如果t 体已经采纳j ，去做行动的意 图，这时它又被给r 可以做另外一个行动y 的机会但是在某种程度，i ：如果做r 它 就不能够继续做卢j - ，那么主体就必须在行动p 和，之间作m 选择。也就是它必 须进行意图调解，决定是否继续维持对口的意图还是放弃该意图而采纳对行动， 的意图。 d b & s 的研究的意图调解问题是在合作行动卜下文中，也就是说相互冲突的 意图之间至少有一个是关于主体对诩队计划的承诺的。作者认为以前的合作和协 商理论都是假设主体对合作行动的承诺是固定的，一成不变的，同时在博奕论中 如果主体破坏了这种承诺会采取严厉的惩罚来加强这种承诺。作者的研究中加入 了“d e f a u l t 这个概念，认为某种程度上的d e f a u l t i n g 是可以接受的。 d b s 的研究中假设：1 ) 每个任务( t a s k ) 只持续一个时间片并且是单主 体动作；2 ) 模型试验中只有一个团队行动重复的被同一团队反复执行；3 ) 模拟 试验中为了简化每一周的开始通过”w e e k l yt a s ks c h e d u l e ”( 、t s ) 重新分配组任 务。 d b & s 中通过当前收益( c u r r e n ti n c o m e ：c i ) ，期望收益( f u t u r ee x p e c t e di n c o m e ： f e i ) 年i 社会性点数( b r o w n i ep o i n t s ：b p ) 来进行决策和意图冲突调解。社会性点数 反映了主体作为团队合作者的荣誉度。一开始的时侯所有的主体部分配一样的社 会性点数。如果主体d e f a u l t ，它就会损失部分社会性点数，如果主体没有d e f a u l t 它就会获得社会性点数的增长，这反映j ，主体正在做对团队有益的事情。因为主 体的荣誉度不仅仅反映在它是否d e f a u l t 上面，还有t 体在决策时侯的卜下文环 境，所以社会性点数还考虑进来了，决策中涉及到的任务和机会。具体计算公式如 卜： u 出r 2 t e l w e i g h t 4 n o r m t e l , k f + b p w e i g h t + n o r m b p 槲 u n o - c l e f 。t e l w e i g h t + n o r m t e i n 州c f + b p w e i g h t + l l o r m b p n o - d e f 其中t e l w e i 曲t + b p w e i 曲t 一1 ，并且t e l 表示t o t a le s t i m a t e di n c o m e 是c i 和f e i 的和。 那么如果u d e f u n 砌e f 主体则d e f a u l t ，否则主体n o n d e f a u l t 。 中国科学技术大擘硕士学位论之 2 4b o i d 模型 b o i d 模型t 要分析b d i 舜论中b ，0 ，i ，d 之问的冲突和蕾要模型的性质。 “b o i d 研究的1 - 要内容是b ，o ，l ，d 之间仟意两个发，t 冲突的情况是该如何处 胛以及每种处理方法的意义所在。这样根据不同的处理方式，系统就会有很多 不问的结构。 研究b o l d 中，作者还分析了b d i 和q d t 的一些问题。一种模璎足建谚在 主体的思维状态属性的抽象模型基础上的：信念，愿望和意图( b d i ) ；第种模 型是决策论的定量扩展( aq u a l i t a t i v ee x t e n s i o no fd e c i s i o nt h e o r y ：q d t ) 。对于 b d i 理论也有不同的模型，它们有不同的目的。比如主要的有用于软件工程中的 汁算性的b d i ，它显示的考虑结构和实现方法；有关于b d i 的认知理论，它主 要考虑决策中的社会性和认知性的概念；最后还有b d i 的逻辑形式化，这个也 是本文所引用的b d i 的主要概念。比较b d i 和q d t 主要有两个问题：首先是定 量决策规则的本质问题，比如说效用的最大化。给定了概率分布( 相当于主体的 信念) 和评估函数( 相当于主体的愿望) ，选择执行动作的规则。其次是关于决 策巾知识的作用。它分析用于决策中的不同的表示数据的方法，并且处理潜在的 冲突。通常来说，b d l 只是潜在的假设了选择功能( 比如说规划算法的应用) ， 但是q d t 提供了显示的过程。这些分析也是本文所要讨论的一个问题。 2 5m a s m 理论 m a s m 。”7 ”的系统结构中使用冲突链接直接的描述了冲突，这种描 述是简单直观的，同时系统实现了动物的行动选择。 m a s m 理论彼认为是对传统的规划理论和反应式系统的特点的融合， m a s m 中行动选择的目标足建立一个智能系统即一个i ! 体问相互交、合 作并且从整体一i ：系统呈现某种全局性质的多主体系统。这里所指的主体的概念很 简单，主体只是具备一定的能力的功能性模块，没有思维和意念这样，具体不 同的功能的模块可以被看作不同的主体，拓展和简化r 主体的概念。针对动物行 动选择问题，t y r e l l 通过计算机模拟实现了该模型。 m a s m 系统由大量节点组成，节点之间以及节点和外部环境、目标之间用 不同类型的联接构成一个非层次式的网络结构。 9 中国科学技术走学i i 士学位论走 体( 或称为能力模块、壮点) 可以描述为一个四冗组( c 、，a 、，d 、。q 、) ，具体见( 图一) ，c 、表示卜体的前提条件集，即c 、足命题逻射 叶- 命题公，的 集合，只自前提集含巾的每一个条件1 l i | ；成一时卜体l 可能执行该能力模块代表的 动作：戤硐ld 、称作增加州表和删除列表，表示当执行完能力模块代表的动作以 后产生的效果，即该能力模块导致的新成的命题集含和不能够继续成奶的命题 集合：o 、表示该能力模块的激活阀值。这样，能j 模块x 往t 时刻被选择的条 件需要满足前提集为真并且这个时刻该模块的激活能力已经超过r 该模块的激 活阀值。 输入： 输出： 前驱联接 后继联接 冲突联接 环境 目标 前驱联接 后继联接 冲突联接 ( 图一) 节点的组成 m a s m 的基本机制就是通过内部联接和外部联接，以及它们的之问的激活 能量的传递和抵消，使能力模块中的激活能量逐渐积累，如果某个能力模块的激 活能量达到了一定的值( 比如说超过_ r 实现预定的阀值时) ，该能力模块就会被 激活，从而执行相应的实际行动。 m a s m 体现r 一定的面向目标性。血- 向f 1 标性体现在激活能鼍通过目标输 入联接和前驱联接的反向传递上，而面向环境则体现在能最通过外部环境输入和 后继联接的前向传递上。面i 旬日标祁面向环境本身足一对矛盾体，适! j 的调节全 局参数m 和y 的比值可以改变系统面向目标或环境的强弱程度。 体所处的外部环境如果不断的发生变化，这些变化会通过环境输入联接和 系统的内部联接立即反映到系统中，主体可以实时的做出反应。所以m a s m 体 现出了反应式系统的部分优点。 1 0 中固科擘枝术丈学硕士学位论丈 同时，系统也可以体现一定的慎思能力，由于系统中的能茕足逐步积累起 来的，这样! 1 i 体执行某个行动序列时会仃种倾向性继续完成这个序列，即使 这时有新的f 1 标引入，但是【l i 这个目标传递的能茕还没自积累到一定的程度，所 以系统体现一定的规划性和持久性。 2 6p o m d p 模型 p o m d p ( p a r t i a l l yo b s e r v a b l em a r k o vd e c i s i o np r o c e s s ) “4 是决策论 中处理动态不确定环境问题的一种典型方法。p o m d p 为求解最优行动策略提供 了一种数学模型。它将环境的变迁看作状态空问 的m a r k o v 链，崩状态空问上 的信念分布表示主体对当前状态的估计，并根据主体的行动和获取的观察加以更 新。p o v i d p 可以划分为两部分，如( 图二) 所示。智能体获得观察然后生成执行 动作。橱能体保持一个信念状态集，b ，它保存了智能体以前获得知识或经验。 s e 状态估计部分，它根据主体以前的信念状态集，上一次的行动和当前观察更 新信念状态集。而模块万是智能体的策略，它负责生成智能体的动作，策略函数 是关于信念状态集到动作集的一个映射。 ( 圈二) p 0 i d p 系统原理图 1c n 在此基础上，p o m d p 依据效用最大化原则，根据回报函数和状态转换函数 中圆科学技术太擘硕士学位论丈 计算最优策略。经典算法是v a l u e - i t e r a t i o n “。c a s s a n d r a ”k a e l b l i n g 4 7 。，z h a n g “以及p i n e a u ”等人分别进行r 不剐的优化和改进，一定程度上提商了决簧 效率。p i n e a u 。通过对动作集进行分级划分米减小决策的复杂度。 f | i 足，玎前p o m d p 仍然缺乏面向复杂环境的实用高效的策略乍成方法，本 文拒其体实现m t i c p 模型时也遇到了同样的问题，由于问题比较复杂，所以红 实现过程中采取的办法悬酵最简化问题， ! 是这样在很大程度 ：使最终的实现不 能达到实用的阶段。 中圉科学技术走学硕士学位论支 第三章m t i c p 模型 3 1 模型描述 m t i c p ( m u l t i a g e n tt e a m w o r ka n di n t e n t i o nc o n f l i c tp r o b l e m ) 模型面对的实 际问题是动态不确定环境下一组相互合作的智能体，它们需要协同合作来完成 “某些目标任务”( 这里不是一般所指的完成指定好的某一个“特定”的任务) ， 而模型所要解决的主要问题是给出该动态不确定环境下的多主体决策模型，该 模型能够很好地描述出动态不确定环境的本质特点以及合作的一些基本特征，进 一步可以给出使用该模型的决策推理过程，推理对环境具有很强的适应能力，并 且可以刻画动态彳i 确定环境下多智能体决策中的意图冲突以及一般性的意图冲 突调解机制。 多主体合作环境f 的决策以及意图冲突问题( m u l t i a g e n tt e a m w o r ka n d i n t e n t i o nc o n f l i c tp r o b l e m ：m t i c p )可以用一个多元组 m = 描述。这里我们假定团队中的每个主体都相信这个模 型每个主体都相信整个团队的其他主体也都相信这个模型而且每个主体都是 诚实可信的。 3 1 1 世界状态集s s = s ，s ，x s ，表示所有主体的状态世界集，它实际上表示为每个主体的 状态世界集的笛 尔积。其中主体口的状态集s 。：表示为特征命题公式的集合， s 。= 让，成 。每个主体的状态集合是有限集，每个单独状态的描述是抽象出 一些关于世界描述的关键性特征。 3 1 2 主体动作集a 中四科学技术大学硕士学位论吏 a = a a n 表示所有主体的行动聚合，这些行动的结果是客观龇界的状态 的改变。其l 1 1 - 9 4 口的动作集一。= ：，“2 - c l ： 。动作集毽的动作表示t 体可以 改变_ t | = 界的最基本的动作，也叫做原了动作。这些原了= 动作是后而将要引入的“计 划”的重要组成部分。 3 1 3 状态转换函数， p ：= s a s 寸【0 ，l 】，也就是说时间t 的状态是s ，执行厂动作a 以后主体到 达时刻t + l 的状态，用公式表示为p r ( s “1 = j - | s = s ，a 。= “) = p ( s ，口，s ) 。 3 i 4 观察函数o 和观察集q q 表示所有主体可以观察到的客观世界描述的集合，q = q 。x q 。其中 主体口的全部观察集表示为q 。= 轨，醒 ，集合中的观察项表示为命题逻辑 中的命题。 o ：s a q 使用函数表示为o ( s ，口，口) = p “q ：= 万fs7 = s ，a ) ，0 主要 用于描述执行原子动作后观察的部分和不确定性。 0 。：s p - - + q 用十描述计划执行后的不确定性和观察的部分性等。关于 o 。的具体解释见下文关于计划体部分。 3 1 5 计划库j d 三 p l = p l 。- p l 。表示主体的计划库， 其中二 ! 体口的计划库表示为 p 上。= 铣，珑 。这里部分采膈rp r s 中对k a 的定义，定义每条计划巩，它 l 】以卜- 几个部分组成： 3 t 5 1 前提条件集：计划执行的前提条件集合，由原子命题组成。前提条 件集合中的每个前提条件有个重要参数：前提条件影响凶子日。 操作函数q ( 尸芝) 表