（计算机软件与理论专业论文）多主体合作的动态不确定环境下的机器人规划系统.pdf

巾 4 科学技术大学倒i ：学位论文 摘要 多主体合作的动态不确定期：境中的机器人规划是当i ；i 人工智能和机器人学 研究的一个重要问题。而环境的动态不确定性表现为： ( 1 ) 环境的不可预测性。主体只是环境的一个组成部分，在环境中还有许多 其他未知或不可察的因素作1 于环境，所以环境的演化是不能精确预期的。 ( 2 ) 行动的不确定性。主体的行动效果是不确定的，不能准确预测其对环境 的作用效果。 ( 3 ) 观察的不确定性。主体从环境中获取的观察可能是部分、不准确的，在 合作通讯中主体从同伴获得的信息也有可能是不可靠的( 即使同伴是诚实可 信条件下) 。 本文对现有的规划系统进行了分析，针对当日u 研究的缺陷，提出了一种新的 多主体规划系统m p o m d p r s ，给出了系统的基本模型，构成框架，运行原理及 性能分析。新的系统保持了p o m d p r s 系统的优点，通过保持p r s 系统的持续 规划机制来适应环境的动态性，通过使用环境状态空间上的概率分御作为主体的 信念来适应环境的不确定性，从而兼顾了两个大方面的要求。同时，m p o m d p r s 系统通过状态集分层来减少信念更新的时间消耗，根据状态间的依赖关系对状态 进行划分，将状态集分为几个子状态集在信念更新时，对不同子状态集上的信 念分布进行分别处理，以达到减少时间消耗的目的；在模型中增加通讯集，以满 足合作的要求，分析信念一致性对合作的影响，并给出了两种不同合作的系统流 程。 基于四足机器人足球比赛这个实验平台，给出了针对某一特定任务的模型实 现。四足机器人足球比赛是一个典型的多主体合作的动态不确定环境，是检验理 论模型性能的良好平台。作者设计了一个三个机器人( 一个守门员与两个进攻队 员) 协同进行进攻防守的例子，用m p o m d p r s 系统来实现问题的设计。通过实 验结果分析，证明了系统的有效性和实时性。 关键词：机器人规划，动态不确定环境，多主体规划，m p o m d p r s ，信念更新 中田科学技术人学碳i 学位论文 a b s t r a c t t h er o b o t i c sp l a n n i n go fm u l t i a g e n tc o o p e r a t i o ni nd y n a m i cn o n d e t e r r n i n i s t i c e n v i r o n m e n ti sai m p o r t a n tp r o b l e mo fa r t i f i c i a li n t e l l i g e n c ea n dr o b o t i c sr e s e a r c h m a i nc h a r a c t e r so fd y n a m i cn o n d e t e r m i n i s t i ce n v i r o n m e n ti n c l u d e ：( 1 ) t h e i n s c r u t a b i l i t yo ft h ee n v i r o n m e n t t h ea g e n ti sj u s tac o n s t i t u t eo ft h ee n v i r o n m e n t t h e r ea l em a n yo t h e rf a c t o r si ne n v i r o n m e n t ，s ot h ee v o l v e m e n to fe n v i r o n m e n tc a n t b ea c c u r a t e l yp r e d i c t ( 2 ) n o n d e t e r m i n i s t i ca c t i o n l h er e s u l to fa c t i o ni sd i c e y w e c a n tp r e d i c tt h ea c t i o n se f f e c t t oe n v i r o n m e n t ( 3 ) n o n d e t e r m i n i s t i co b s e r v a t i o n a g e n t s o b s e r v a t i o n so nt h ee n v i r o n m e n tc o u l db ep a r t i a la n di n a c c u r a t e 。 t h i sp a p e ra n a l y z e st h eb l e m i s ho fe x i s t i n gp l a n n i n gs y s t e m s ，i n t r o d u c e san e w m u l t i a g e n tp l a n n i n gs y s t e mm p o m d p r sa n dp r o v i d e st h eb a s i cm o d e l ，c o m p o s i n g f r a m e ，c i r c u l a t i n gp r i n c i p l ea n df u n c t i o n sa n a l y s i s t h en e ws y s t e mk e p t t h e a d v a n t a g eo ft h es y s t e mp o m d p r s ，r e s e r v i n gt h ec o n t i n u e dp l a n n i n gm e c h a n i s mt o a d a p td y n a m i cc h a r a c t e ra n dd e p i c t i n gt h eb e l i e fo fa na g e n tw i t had i s t r i b u t i o no v e r t h es t a t es p a c et oa d a p tn o n d e t e r m i n i s t i cc h a r a c t e nm o r e o v e r , m p o m d p r sr e d u c e s t h et i m ec o n s u m i n go fb e l i e fu p d a t i n gt h r o u g hd i v i d i n gs t a t e si n t og r o u p sa c c o r d i n g t ot h e i rd e p e n d e n c yr e l a t i o n s w h e nu p d a t i n gb e l i e f , t h ed i f f e r e n tg r o u pw i l lb e r e s p e c t i v e l yh a n d l e d w ea d dt h ec o m m u n i c a t i o nt ot h em o d e l ，a n a l y s i st h eb e l i e f c o h e r e n c e si n f l u e n c et oc o o p e r a t i o na n dg i v et h es y s t e mp r o c e s so ft w ok i n d so f c o o p e r a t i o n b a s e do nt h ep l a t f o r mo ff o u r - l e g g e dr o b o ts o c c e rm a t c h ，t h ep a p e rg i v e st h e m o d e lr e a l i z a t i o nw h i c ha i mt ot h ep a r t i c u l a rm i s s i o n t h ef o u r - l e g g e dr o b o ts o c c e r m a t c hi st h et y p i c a ld y n a m i cn o n d e t e r m i n i s t i ce n v i r o n m e n tw i t hm u l t i a g e n t c o o p e r a t i o n o nt h i sp l a t f o r m ，t h ea u t h o rd e s i g n st h ee x a m p l e ：t h r e er o b o t s ( o n eg o a l i e a n dt w oa t t a c k e r s ) c o o p e r a t ei nd e f e n d i n ga n da t t a c k i n g w er e a l i z et h ep r o b l e mw i t h m p o m d p r sa n dp r o v et h ef e a s i b i l i t yo f s y s t e mb yt h er e s u l ta n a l y s i s k e y - w o r d s ：r o b o t i c sp l a n n i n g ，d y n a m i cn o n d e t e r m i n i s t i ce n v i r o n m e n t ，m u l t i a g e n t p l a n n i n g ，m p o m d p r s ，b e l i e fu p d a t i n g 巾嘲科学技术人学碱j 学位论立= 第一章绪论 机器人规划( r o b o t i c sp l a n n i n g ) 是人二j ：智能和机器人学研究共同感兴趣的一个 重要领域。在l j 常生活中，规划意味着在行动之前决定行动的进程，或者说，规划 足指存执行一个问题求解程序中任何一步前，计算程序几步的过程。一般来说，规 划具有菜个规划1 1 标的蕴含排序，比如，一个机器人要搬动- 4 牛- 物体，需要先移动 到物体的位嚣然后拿起物休，再移动到目标位嚣放下物体。而在人工智能和机器 人学中，规划还没有统一明确的定义综合备剃定义和解释 1 1 1 2 1 ，规划的含义可以 归纳为：规划是指从某个开始状态出发，寻求一系列动作，并按某种序列排列执行， 以达到e | 标状态。 而一个规划系统巾，必须具有执行下列备项任务的方法： ( 1 ) 根据最有效的启发信息，选择应用于下一步的最好规划。 ( 2 ) 应用所选取的规划来计算由于应用该规则而生成的新状态。 ( 3 ) 对所求得的解答进行检验。 ( 4 ) 检验空端，以便含弃它们，以使系统的求解：亡忭阳着更有效的方向进行。 ( 5 ) 检验殆正确的解答，并应片j 具体的技术使之完全正确。 1 1 研究背景与现状 日前已经有些机器人的商层规划系统。其中，有的把重点放在消解原理证明 机器上，它们应用通用搜索启发技术，以逻辑演算表示期望目标，s t r i p s 3 i 和 a b s t r i p s 4 就属于这种。这类系统把世界模型表示为一阶谓词演算公式的任意集 合，采用消解反演( r e s o l u t i o n - - r e f u t a t i o n ) 来求解具体模型的问题，并采用m g a l l s - - e n d s 分析策略来引导求解系统至要求的目标。后米，又开发出了其它的一些规划 巾川科，譬技术人学硕十学位论文 系统，包括非线性规划，回归规划，分层规划等。在这些规划系统中，有如下假设： ( 1 ) 主体拥有完备的列；境知i = 足。 ( 2 ) 主体执行动作的效果是完仝确定的。 ( 3 ) 主体认为自己是引起环境变化的唯一因素。 基于这些假设，智能体可以完全掌握在初始状态下执行一个行动后的所有可能 后继状态。由此它也可以知道所有经过多个行动后，环境所处的状态。一旦其中某 一个后继状态与目标相符，且因为以上第二条假设，智能体即可找到一条确定的状 态转换路径，进而确定这个路径上的所有行动，从而形成一个计划。在确定了这样 的计划之后，将其付诸执行。f u 趋也由于这些假设，使得这些规划系统无法适应环 境的动态不确定性。 而在实际的问题中，丰体面对的环境并非是完全确定的简单环境，所以目前的 研究重点已经转移到动态不确定列i 境下的规划，环境的动态不确定性主要表现在： ( 1 ) 环境的不可预测性。丰休只是翻：境的一个组成部分，在环境中还有许多其他 未知或不可察的因素作用于王1 ：境，所以环境的演化是不能精确预期的。 ( 2 1 行动的不确定性。丰休的行动效果是不确定的，不能准确预测其对环境的作 用效果。 ( 3 ) 观察的不确定性。丰体从环境中获取的观察可能是部分、不准确的，在合作 通讯中主体从同伴获得的信息也有可能是不可靠的( 即使同伴是诚实可信条件 下) 。 传统的规划方法在动态不确定环境下已经不再适用，针对这种动态不确定性， 提出了一些新的模型和方法，p r s 和p o m d p 就是其中的代表性工作。p r s 是一种 基于过程性知识的规划推理系统，它可以在一定程度上适应环境的动态性，但是没 有对不确定性作出专门的处理。而p o m d p 是基于决策论的规划系统，为求解最优 行动策略提供了一种数学模型，p o m d p 可以在一定程度上适应环境的不确定性， 但是缺乏面向复杂环境的实用高效的策略生成方法。 多主体规划系统是由多个丰体参与的规划系统，在系统中，多个主体协同一致， 各自执行一部分子规划，来解决某个多丰体规划问题。较为典型的多主体规划方法 有合同网( c n p ) 【6 】、部分全局规划( p g p ) 7 】和联合意图( j o i n ti n t e n t i o n ) j 8 9 等。 中国科学技术大学碗+ 学位论文 1 2 研究目标与思路 1 2 1 多主体规划系统模型 针对多主体合作的动态不确定环境的特点。对已有的规划系统进行分析，特别 是一种动态不确定环境下的持续规划系统p o m d p r s 。p o m d p r s 系统是一个单主 体的规划系统，无法应用在多主体系统上；在进行信念更新时，会消耗大量的时间， 不利于应用到实际问题中。针对这两个不足，作出改进，提出了新的多主体规划系 统m p o m d p r s 。在新系统中，对主体的状态集进行分层，将互不相关的状态分层 处理，减少了信念更新的时间。在系统模型中添加了团队状态集和通讯集，其中团 队状态集用来存储团队中其它主体的信息，通讯集用来存储主体间需要交流的信息。 对多主体规划的关键问题信念一致性进行分析，给出了两种合作方式，对这两 种合作方式都给出了系统运行的流程。另外，还分析了新系统对动态不确定环境的 适应性和实时性。 1 2 2 应用实例 机器人足球是目前公认的人工智能的标准问题之一，四足机器人足球比赛是机 器人足球的比赛项目之一，也是本文研究的丰要背景。四足机器人足球比赛中，机 器人对环境的了解是不全面不准确的，动作效果也是不确定的，而且机器人之间需 要通过合作来协同完成进攻和防守，因此四足机器人足球比赛是一个典型的多主体 合作的动态不确定环境，所以可以将四足机器人足球比赛作为检验规划系统的平台。 本文将针对比赛的某个任务进行模型的应用，以检验模型的性能。 k 怍r 技术人学硬十学位论文 1 3 本文组织结构 第二章总结概括了已有舰划系统的特点及其对动态不确定环境和多丰体合作的 适应性；第三章描述了面向多：1 i 体合作的动态不确定环境的规划系统m p o m d p r s 的基 本模型、运行机制和性能分析；笫四章针对四足机器人足球的一个具体问题，进行 模型的应用；第五章总结全文： 作和展望下一步工作。 中国科学技术人学硕十学也论文 第二章相关研究简介 在过去的研究中。提出了很多规划系统，这些规划系统在理论上提出很多新的 工作，为本文的研究工作提供了基础理论和思路。本章中将介绍一些相关的研究工 作。 2 1情形演算 2 1 1 基本语法 情形演算( s i t u a t i o nc a l c u l u s ) 1 0 1 1 【1 2 】是一种特殊的一阶语言，设置了一些特 定的语法对象以便描述行动和状态变化。 情形演算包括以下基本语法： ( 1 ) 情形常元和情形变元，作为状态的标识。 ( 2 ) 原子行动符号。原子行动即不可再分解的行动，定义为从行动的主体或对 象到“行动个体”的函数。假定每个原了行动都有一个相应的函数符号。 ( 3 ) 行动复合函数d o 。二元函数d o 将行动个体和情形映射为情形，从而间接 地将行动解释为状态变换。d o 的嵌套使用可表示行动序列。例如，d o ( a 2 ，d o ( a l ，s o ) ) 表示在s 0 上执行a l ，然后接着执行a 2 所得到的结果状态。情形演算假定。世界的 所有变化都是由有名行动产生的。因而对任意给定的初始状态，一个行动序列将决 定一个“历史”。 ( 4 ) 变式( f l u e n t ) 。其值依赖于情形( 状态) 的谓词和函数。 2 1 2 动作刻画 在情形演算中，动作由三个公设来刻画。 ( 1 ) 条件公设( p r e c o n d i t i o na x i o m ) ：条件公设表示行动在任何条件下都可以 m j 辩拙术人中硕十学位论文 执行。 ( 2 ) 效果公设( e f f e c ta x i o m ) ：效果公设描述行动影响变式( 真值变化) 的情况。 一条效果公设足一个虢龠式其前、后件分别表示一个行动的前提条件 和效果。对每一组 j ：动一变式对，要写出一条效果公设以表达该行动对该 变式的影响：从假变典( 止效果) 或者从真变假( 负效果) 。 ( 3 ) 框架公设( f r a m ea x i o m ) ：枢! ! 公设描述行动不影响变式( 真值无变化) 的情况。 2 1 3 框架问题 框架问题( f r a m ep r o b l e m ) 泛指在处理不受行动影响的变式中遇到的各种困难， 分为表示方面和推理方面。表示方面，由于通常大多数变式不被行动改变，因此往 往需要写出很多框架公设。r e i t e r t 3 给出了一种简单的解决办法，在一定条件( 效 果公设完全性等) 下可以用后继状态公设简洁地代替框架公设( 以及效果公设) 。推 理方面，无论用框架公设还是后继状态公设，即使一个变式的真值经过一系列行动 始终未变，仍必须对每一个中间状态逐一推理。至于有关的推理的效率，与所用推 理机制有关。 2 2g p s g p s ( g e n e r a lp r o b l e ms o l v e r ) 【1 4 】由n e w e l l ，s h a w 和s i m o n 等人于1 9 5 7 年开 始研制，1 9 6 9 年公布终版。其h 标是： 1 让机器解决“需要智能( 才能解决) 的问题”； 2 建立一个关于人类如何解决“智能问题”的瑚论。 因此，g p s 是一个通用问题求解系统，但同时具有规划功能，被视为对规划的 最早研究。对后来的发展有深远影响。丰要技术贡献包括： 1 通用问题求解方法与具体应用的领域知识的分离： 中国科学拄术大学硕七学位论文 2 m e a n s - e n d s 分析。 2 2 1g p s 表示 g p s 的表示分两个层次。 1 对象层，主要包括： ( a ) o b j e c t s ，应用领域中的基本对象。例如自动推理中的公式： c o ) o p m t o r s ，应用领域中对象集合上的变换( 行动) 。 2 系统层主要包括： ( a ) 目标( g o a l s ) 。对象的二元组，前一个是“当前对象”，后一个是结果对象 ( d e s i r e do b j c c t ) 。有三种类型； l 。变换( 将一个对象a 变换为另一个对象b ) ，a 与b 无差别时为本原目标 2 消除( 修改对象a 以消除a 与b 间的某项差别) 。该差别无法消除时为本原 目标； 3 施用( 应用一个算子q 于一个对象a ) ，q 可直接应用于a 时为本原目标。 ( b ) 方法( m e t h o d s ) ，实现三种目标的过程( = 表目标分解，表子目标合取) ： 1 变换a 为b = 消除a 与b 的一项差别；输出a 变换a 为b 。 2 消除a 与b 的一项差别= 选择合适的q 并施用q 于a ；输出a 。 3 施用q 于a = 消除a 与q 的前提条件间的一项差别；输出a ”】【施用q 于a ”；输出a 】。 2 2 2m e a n s - e n d s 分析 g p s 的工作过程如下：初始目标是“变换i n i t i a lo b j e c t 为d e s i r e do b j e c t ”，对当 前目标g ，应用对应方法进行分解和处理，并对分解产生的每个子目标g 递归，当 g 为本原目标时，递归终止。这就需要额外机制处理差别和算子的选择。为此引进 m e a n s - e n d s 分析，其基本原理如下： 1 假定对象间差别可以事先定义并划分为不同的类型： q ，科。p 技术人。# 硕十学位论文 2 假定可以根据算了所能洲球的筹别的类型加以分类和检索： 3 选择最“难”的差别利能够消除该差别的算予； 4 允许所选算了q 不能直接i 址永于当前对象( 从而导致了目标“消除当前对象 与q 的前提条件间的一项差别”的建立) 。 2 3s t r i p s 系统 s t r 驴s ( s t a n f o r dr e s e a r c hi n s t i t u t ep r o b l e ms o l v e r ) 3 】，即斯坦福研究所问题 求解系统，是第一个重要的规划系统。s t r i p s 是由f i k e s 和n i l s s o n 在1 9 7 1 年研究 成功的，是s h a k e y 机器人程序控制系统的一个组成部分，因此计划的生成与执行是 分离的。s t r i p s 最大的贡献是它的语言，既保留了较强的表达能力，又较好的解 决了框架问题的两个方面。因此，s t r i p s 得到了深入的研究，并对规划领域产生 了深远的影响。 在s t r i p s 语言中一个目标，状态或状态集被表示为一个文字集，语法上代 表集合中所有文字的合取式。约定其中出现的个体变元都是全称量化的。s t r i p s 中的行动由规则进行描述。规则由二个文字集表示：前提条件p c ，删除表d 和添 加表a 。若将一条规则净( p ed ，爿) 中的所有个体变元都代入个体常元所得结果 r k ( 尸c ld la ) 即为一个s t r i p s 算了( 行动) 。一个行动对环境的影响被定义为 根据这个行动的删除表和添力表对表示状态的文字集中的文字进行增减。任给状态 描述岛和算子r k ( j 口c ld la + ) 。若岛满足p c * ，即s o 印c ，则r 在岛上可执 行，且结果状态为s ，= d r ( s o d + ) u a + 。 上述对于行动的定义基于s t r i p s 假设：凡未被算了删除的特征都不被行动所 改变。由此s t r i p s 使用了一个简单的方法解决框架问题，它不需要框架公设， 而且状态演变的推导效率很高。 根据上述定义，可以给出个简化的s t r i p s 前行规划算法。其中应用了非确 定选择语句c h o o s e 。c h o o s ex e x s tc 表示：从满足条件c 的成员中选择“最好 中国科学技术大学硕十学位论文 ，正确的”x ；若x 的所有成员都不满足c ，则x = n i l 。c h o o s e 语句的使用避免了具 体考虑在z 中搜索j 的过程，以便集中考虑算法的其他方面。 s t r m s 前行规划算法： 1 ) s ：= s o ；叮：= 【】； 2 ) i fs = gt h e nr e t u r n ( r e v e r s e ( o ) ) ；成功 3 ) c h o o s e r = 俨c ，n ) a n d 口s t s o p c o ；算予选择 4 ) i fr = n i lo r 口= n f ft h e nr e t u r n ( “f a i l u r e ”) ； 失9 ! ( ， 5 ) s 净( s al d o ) u 一日；状态修改 6 ) 盯：= 舢l 盯】；计划扩展，插入一个新行动肿到叮表头 7 ) g o t o3 ，迭代， s t r i p s 大大影响了后世的包括近十年出现( t g r a p h p l a n 2 0 ，i p p 2 1 ， b l a c k b o x 2 2 ，s a t p i a n 2 3 等。 2 4 回归规划 回归规划( r e g r e s s i o np l a n n i n g ) 1 5 是从目标公式g 出发，依次找出行动 a na 。，卅。，使得在初始状态邑上顺序执行a 。，a 。，a 。所达到的状态最满足g 。 下面两个序列表明了回归规划与前行规划的区别； 岛山s 山山s = g s o = g ( “) l k g ( l g ( o ) = g 由此可见回归规划的“基本步骤”是“目标回归”，即从一个目标g ( i ) “反向 推出”它的“回归子目标”g ( 件”。 显然，上述两个序列中出现的每一个箭头一般情况下可能不唯一；比如，可能 存在多个不同的通向多个s i 。这就是说，通常存在着以s o g 为根节点、以行动为 弧的树；而上述每一个行动序列仅仅是对应树上的一条路经。一般情况下，规划算 法需要通过搜索才能从树上找到这样的路径。因此，树的大小( 即分支的多少) 将 9 中料# 盘术人学硕十学位论文 影响规划算法的效牢。很多情况、，归规划的分支数比前行规划的少，因而效率 较高。这是回归规划的书要动机之一。 下面给出回归规划的慕本算法。 r e g r e s s ( s ，ga ，p ) ： 输入初始状态描述s ，目标公式g ，行动描述集a ；输出计划p 1 p ：= 【】：g + ：= g ； 2 i fsl = g + t h e nr e t u r n ( p ) ： 成功 3 c h o o s e 口a8 t p r e ( a ) 至少满足g 4 的一个合取予目标； 行动选择， 4 i fa n i l t h e n g ：= g 的通过a 的回归了目标： 产生回归予目标g 5 i fa = n i lo rg 为矛盾式o rg 逻辑蕴涵g + t h e nr e t u r n ( f a i l u r e ) ；失败退出 | 6 g + ：= g ：更新当前目标 7 p ：= 【a lp 】： 扩展计划p 8 g o t o2 ；迭代 回归规划通过目标空间中的“反向”推导生成行动计划，而前行规划是在状态 空间中通过“正向”推导生成计划的。由于目标公式通常比状态描述简单( 包含较 少文字) ，“无关信息”的干扰较小，凶而回归规划的效率往往高于前行规划。另外， 回归规划应用了“提升”技术，部分地采用了“极小承诺”策略，用一个特称量化 目标代表多个可能的基目标中的某个“合适的”，也有利于提高规划的效率。这些是 回归规划的主要进展。 2 5 偏序规划 任给初始状态s 和目标g ，个行动序列a ha 2 。，a 。是一个计划，当且仅当下 列条件成立；( 1 ) a l 在s 上可执行：( 2 ) 执行a i 之后a 可执行( “行动连续性”) ： 中国科学技术太学硕+ 学位论文 ( 3 ) 执行a n 之后g 为真。偏序规划( p a r t i a l - o r d e r p l a n n i n g ) 【16 】 1 7 】不要求在规划 过程中的每一时刻所生成的行动序列必须满足条件( 2 ) ，但要满足条件( 1 ) 和( 3 ) 。 为此，偏序规划将初始状态s 和目标g 分别表示成两个“伪行动”s t a r t 和e n d ( 简 记为s ，e ) 。相应地，广义的部分计划定义为任何以s 为起始行动、以e 为终结行动 的行动的偏序集。这就是说，一个部分计划不仅可以“遗漏”一些必要的行动，而 且可以不完全规定行动的执行次序。偏序规划利用了下述约束：每个行动对目标 中间目标的“贡献”不被其他行动完全破坏，使保留下来的“贡献总和”能够实现 目标中间目标。因此，偏序规划的基本思想和书要进展是：放弃“行动连续性”( 全 序) 限制，以“因果链”、“威胁保护”和“任务”等概念刻画规划的基本约束( 偏 序) ，从而可以更好地应用“极小承诺”策略。 偏序规划采用一种简化的s t r i p s 表示，将一个行动a 描述为一个二元组 。其中p r e ( a ) 为一原子集，代表a 的前提条件；e l f ( a ) 为一文字集，代表a 的 效果。规定p r e ( s t a r t ) = t r u e ，e f f ( s t a r t ) = s ( 初始状态描述) 。同时，规定p r e ( e n 西= g ， e f f ( e n 回无定义。一个偏序规划的部分计划是一个行动的偏序集尸t a l ， ， ， 其中 是p 上一个偏序，a l = s t a r t ，a n = e n d ，并且对p 中任何其他行动a j ( f l ，n ) ，存 在行动a k e 尸，使得a ：a k 并且a f 的执行导致p r e ( a k ) 至少部分成立，即a i 对它后面的 行动有所贡献。在上述情况下，称国与m 之间存在“因果链”。将一条因果链记为 一个三元组a 。山口。，其中行动唧称为q 的提供者，啦称为q 的消费者， q e 颤咖增( 是即对a c 前提条件的“贡献”。特别值得注意的是，一条因果链中 的原子命题q 是提供者行动对消费者行动的“原予贡献”，因为这种“贡献”是不 可能再分解的。换句话说，q 也就是消费者行动的前提条件( 一个中间目标) 能够 被“部分现实”的最小单位。 与因果链密切相关的是“威胁”和“保护”概念。假设在当前部分计划p 中 唧与口c 之间存在一条因果链a 。_ 口。，那么在郎与a 。之间的所有行动都不能 “破坏”q ，否则这条因果链就不起作用，没有存在的必要了。如果一个行动a 会 破坏口，则称a “威胁”因果链a 。l + 口。，因此规划过程在扩展p 时就不应该将a 插到如与a e 之间。这称为因果链的保护。 川l t 支术人学硕十学位论文 在上述讨论的基础上，可以蜓f m 格地考察偏序规划。设在偏序规划过程中，当 前部分计划是p 。对p 中的每行z 山n 的每个q 暑p r e ( a ) ，如果存在一条因果链满足 q ，则q 已被p 实现：否则，q 址个朽待予实现的_ 了目标。对任何有待于实现的 予目标q ，需要从p 中寻找一个有的，或者在p 中插入一个新的行动a ，使得 q 够【口，并且a 既不威胁p 的所钉因果链，又与p 的序约束相容。假如成功地进 行了这一步，就得到一个相对更完枢的部分计划；假如无法成功地进行这一步，则 表明必须放弃p ，规划进入“i ! j ”阶段取消一条因果链，并考虑其他可选因果 链。假如p 中所有行动的所有前挺条件都被p 中的因果链实现了，那么规划过程终 止。于是，偏序规划的基本过程赴：从初始计划 s t a r t , e n d 开始执行以上过程，直 至终1 e 。 2 6 分层规划系统 目前主要有三种分层规划系统：h t n 规划( 又称h t n 分解) 、算子分解和模型 归约。但大多数实用规划系统的研究耩于h t n 规划。 h t n 规划 1 8 】【1 9 2 4 】的壤本概念是“任务”和“方法”。一个任务可以是一项 活动，其含义比“行动”更宽泛。相应地，一种“方法”描述一个任务的一种实现 方式，也比行动描述更宽泛。因此，h t n 规划的表示语言比以上介绍的各种经典规 划的表示语言更一般，支持更多种类的背景知识的使用，因此更接近实用要求。 在h n t 中，有两种任务。( 1 ) 本原任务( p r i m i t i v et a s k ) ，即( 当其前提条件 被满足时可以直接执行的) 行动：( 2 ) 非本原任务，即需要通过一些行动才能完成 的“活动”，故又称“高层行动”。鼹然两种任务都是状态变换，区别在于完成方式 不同。如果不考虑非本原任务，h n t 规划就退化为s t r p s 式规划。 一个h n t 规划问题可以表示为一个四元组p = 。其中d 为初始任务 网即有待于为其制订计划的一f _ 【任务及其约束条件，相当于s t r i p s 式规划中的 目标：i 为初始状态描述；o p 为1 i 丁口算予集；m e 为可用方法集 h n t 规划的基本过程如下： 巾闺科学技术人学硕十。? 他论文 1 输入一个规划问题p ； 2 i f p 仅含本原任务t h e n f 消解p 中冲突： i f 消解成功t h e nr e t u r n ( 结果) e l s er e t u r n ( “f a i l u r e ) ) ： 3 c h o o s e 非本原任务t e p ； 4 c h o o s et 的一个“扩张”t ： 5 在p 中用t 取代t ； 6 调整p ： 7 g o t o2 ： h n t 规划的最大特点是允许使用“高层行动”，因而表达能力更强，这一特点 使得h n t 规划系统可以利用更多的背景知识，因而更接近实用需要，同时也导致 规划过程的复杂化，至今尚未达到实用化水平。规划领域中的很多有价值的想法是 在分层规划的研究中产生的，而且分层规划还与后来的一些非经典规划关系密切。 2 7p 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 ) 2 5 】【2 6 足从使用传统编程语言以及基于规 则的专家系统构建实时、持续活动的智能系统演化而来，其主要特点是推理过程是 建立在事先定义好的过程性知识( 计划) 上，系统具有快速的反应性同时具有面向 目标性，同时系统具有元级别的推理。也就是远高于领域知识的推理过程，它是一 个一般性的关于意图生成和管理的过程。 r 1 i 什技术人学硕十学位论文 一一 l l 一 + 信念结构汁划库 厂一解释器、 环境 、一 、 。7 一t 、 甘标结构意煳结构 7 、”， 蹦- p r s 系统结构 p r s 系统由一个计划库，符号表示的信念、目标和意图结构以及解释器构成。 信念是a g e n t 对一些外部世界和内部状态的认识，通常用一阶逻辑表示 愿望用系 统行为表示：计划库中包含一些部分完成的规划，可以由某些条件触发：意图就是 当前触发的规划。解释器负责更新信念结构，触发规划，执行意图等。p r s 交替地 实施规划和行动，根据环境的演进不断扩展、调整计划并执行适当的行动，因而能 够在一定程度上适应环境的动态特性，并具有较高的决策效率。但是p r s 没有针对 不确定性做出专门的处理。 p r s 曾经用在航天飞机的维护模拟实验中，并且获得了成功 2 6 2 7 1 。此外还开 发出了各种不同风格的p r s 实用：e 具和环境，比如d m a r s 2 8 1 和u m p r s 3 l 】等。 r a o 2 9 】，w o o l d d d g e 3 0 等人刈p r s 类系统作了比较深入的形式化研究。 2 8p 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 ) 3 2 3 3 3 4 是一种基于 决策论的规划系统，为求解最优行动策略提供了一种数学模型，是基于对环境的部 分观察的m d p 4 1 。在p o m d p 模型中，丰体无法直接获得环境的状态，系统通过 获取从环境中得到的观察来了解王 i 境。系统将环境的变迁看作状态空间上的m a r k o v 巾冈科学技术火学颂十学化论文 链，用状态空间上的信念分布表示主体对当前状态的估计，并根据主体的行动和获 取的观察加以更新。而主体对环境的观察是不完全的，所以无法根据观察来完全确 定自身的状态，只能得到对当前状态的一个估计。在p o m d p 中，用信念分布来表 示主体对自身当前状态的估计，而信念分布根据观察和动作反馈来更新。 p o m d p 的目标是生成最优的策略历从而将观察的序列映射到行动集上，以最 大化策略的价值。系统根据策略的价值使用某利，算法( 最常用的是v a l u e i t e r a t i o n ) 来生成最优的策略。经典的v a l u e i t e r a t i o n 3 3 有很高的复杂度，c a s s a n d r a 3 5 k a e l b l i n g 3 2 ，z h a n g 3 6 以及p i n e a u 3 7 3 8 等人分别进行了不同的优化和改进，一 定程度上提高了决策效率。 p o m d p 可以在一定程度上适应环境的不确定性，但是缺乏面向复杂环境的实用 高效的策略生成方法。 h m m d p ( h i d d e nm o d em a r k o vd e c i s i o np r o c e s s ) 【3 9 4 0 是p o m d p 的一种特 例情况。h i d d e n m o d e 模型定义为在同一个状态空间和动作空间上的m d p 有限集 合。每个m d p 称为一种模式( m o d e ) 。每个模式内部的状态转换由一个m d p 模型 决定。在模式内部。状态是完全可观察的。但是智能体处于哪个模式却不是完全可 观察的。h m m d p 可以用p o m d p 表示。在一定条件下，h m m d p 的复杂度比 p o m d p 大大降低。 2 9p o m d p r s p o m d p r s 4 2 系统利用p r s 的持续规划机制，交叉地进行规划与执行，在一定 条件下提高了动态环境中p o m d p 决策的效率；另一方面，用p o m d p 的概率分布 信念模型和极大效用原理替代p r s 的一阶逻辑信念表示和计划选择机制，大大增强 了处理环境不确定性的能力。p o m d p r s 结合了这两种模型的优点，以p o m d p 的 信念模型和计划效用模型弥补了p r s 在适应不确定性方面的不足，以p r s 的持续 规划机制提高p o m d p 的决策效率，从而获得了对动态不确定环境更全面、更有效 l 冲技术人节硕十学位论文 的适应能力。 但是p o m d p r s 系统是个t nl i 体规划系统，无法应用到多主体系统中，而要 扩展到多丰体系统中，需要考虑1 i 仆问的信念一致性等问题。另外，由于一般的实 际问题中状态数目比较多，在进行f l i 念更新时，时间的消耗较大，不利于p o m d p r s 系统应用到实际问题中。 中国科学技术人一# 硕一 ：一社位论文 第三章m p o m d p r s 系统 针对上一章中提到的p o m d p r s 系统的缺点，本文对其作出改进并提出了新的 持续规划系统m p o m d p r s ( m u l t i a g e n tp o m d p r s ) ，新系统可以应用到多主体合作 环境中，采用状态分层的方法来减少信念更新的时间消耗。 3 1 m p o m d p r s 基本模型 m p o m d p r s ( m u l t i a g e n tp o m d p r s ) 系统的赫本模型可以用一个多元组 描述。 1 ) s = s 。x s ：x s 。是所有主体的世界状态集，其中s ，= s i s 掣 ( 1 i n ) 是主体i 的状态集，而s ? ( 1 兰，m ) 是一些互不相关的子状态集， s ，是这些子状态集的笛卡尔积。状态集中包括n 身信息和团队信息。 2 ) a = a a 2x a 。是所有主体的动作集，其中a 。是主体i 的动作集，动作 的结果是客观世界的改变。动作集中的动作是：1 i 休能够执行的最基本动作，也成为 原子动作。在h p o m d p r s 系统中，需要定义动作与予状态集的相关性。 定义l ：主体i 的动作a 与其予状态集s ，相关即 3 s ，s s ，s f j ，使t ( s ，盘，5 ) 0 而a 与s j 不相关即为： v s f ，5 s ，s f 5 ，都有：r ( s ，m s ，) = 0 ，t ( s f ，a ，丑) = 1 3 ) g = g 。g 2 g 。是所有主体的目标集，其中g f 是主体i 的目标集即为 主体i 经过一定的状态转换后达到的某个或某些条件。 4 ) p l = p l 。p l ：尸“是所有丰体的计划集，其中戌，是主体i 的计划集。 5