第2卷第3期 智能系统学报 Vol.2 N23 2007年6月 CAAI Transactions on Intelligent Systems Jun.2007 基于条件效果的对象动态可变图规划 谷文祥，杨永娟，闫书亚 (东北师范大学计算机学院，吉林长春130117) 摘要：主要研究了基于条件效果的对象动态可变的规划问题提出了相关元件、无关元件、创建/删除对象元件和 普通元件等概念，把带有条件效果的动作和不带有条件效果的动作都元件化，并采用了对象命题化的思想.给出了 新的基于目标驱动的规划图扩展算法和前向搜索有效规划算法，并给出了相应的后向传播互斥的定义，使得规划图 的规模比较小，减少了搜索空间，大大提高了求解有效规划的效率.由于算法中的动作创建的效果是依赖于上下文 的描述，这更加符合现实需要，使处理的问题更接近于真实的世界状态，因而此算法比以往的算法应用性更强，更具 有现实意义. 关键词：图规划；相关元件；无关元件；创建/删除对象元件；条件效果 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)03-0012-07 Creating or deleting objects graphplan based on conditional effects GU Wemxiang,YANG Yongjuan,YAN Shurya (School of Computer,Northeast Normal University,Changchun 130117,China) Abstract:Mainly research was done on the creating or deleting objects Graphplan that based on conditional effects.Firstly,several new concepts were proposed,such as correlative component,irrelative compo- nent,creating or deleting objects component,common component and so on.Secondly,both actions with conditional effects and that without conditional effects were considered as components and the conception of transforming object into proposition was introduced.Thirdly,a novel intelligent planning algorithm which expanded the planning graph backwards from the goal set and searched a valid plan forward was pro- posed and also a new definition of mutex inference backwards was given correspondingly.The method re- duced the scale of the planning graph and the search space,improved the efficiency of searching the valid plan greatly.Because the effects created by actions were contex-dependent,it was more suitable for the practical needs compared with previous methods,and made the planning problems to be handled much closer to the real word.Therefore,the method has its advantage over previous ones in application and has more practical significance. Key words :graphplan;correlative component;irrelative component;creating or deleting objects component; conditional effects 近年来，有关智能规划的研究在问题描述和问 些发达国家在此领域获得了很大的发展，规划技术 题求解2方面得到了新的突破，使得智能规划已成 己成功应用于国防和空间技术领域，并取得了巨大 为一个非常热门的研究领域，由于智能规划的研究 的经济和社会效益，NASA于1999年在航天器 对象和研究方法的转变，极大地扩展了智能规划的 “Deep Space One”中运用规划技术，使得规划研究 应用领域，使智能规划的理论和应用研究有了长足 从实验室向实际应用迈出了重要的一步，标志规划 的进展.近几年来，随着客观条件的改善，世界上一 的研究步入了实用阶段.越来越多的学者致力于这 方面的研究，并取得了很多重大成果 收稿日期：20061025. 自1995年Blum和Furst提出图规划算法，2] 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 3 期 智 能 系 统 学 报 Vol. 2 №. 3 2007 年 6 月 CAA I Transactions on Intelligent Systems J un. 2007 基于条件效果的对象动态可变图规划 谷文祥 ,杨永娟 ,闫书亚 (东北师范大学 计算机学院 ,吉林 长春 130117) 摘 要 :主要研究了基于条件效果的对象动态可变的规划问题. 提出了相关元件、无关元件、创建/ 删除对象元件和 普通元件等概念 , 把带有条件效果的动作和不带有条件效果的动作都元件化 ,并采用了对象命题化的思想. 给出了 新的基于目标驱动的规划图扩展算法和前向搜索有效规划算法 ,并给出了相应的后向传播互斥的定义 ,使得规划图 的规模比较小 ,减少了搜索空间 ,大大提高了求解有效规划的效率. 由于算法中的动作创建的效果是依赖于上下文 的描述 ,这更加符合现实需要 ,使处理的问题更接近于真实的世界状态 ,因而此算法比以往的算法应用性更强 ,更具 有现实意义. 关键词 :图规划 ;相关元件 ;无关元件 ;创建/ 删除对象元件 ;条件效果 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0320012207 Creating or deleting objects graphplan based on conditional effects GU Wen2xiang , YAN G Yong2juan , YAN Shu2ya (School of Computer ,Northeast Normal University , Changchun 130117 ,China) Abstract :Mainly research was done on t he creating or deleting objects Grap hplan t hat based on conditional effects. Firstly , several new concepts were proposed , such as correlative component , irrelative compo2 nent , creating or deleting objects component , common component and so on. Secondly , bot h actions wit h conditional effects and t hat wit hout conditional effects were considered as components and the conception of transforming object into propo sition was introduced. Thirdly , a novel intelligent planning algorit hm which expanded t he planning grap h backwards from the goal set and searched a valid plan forward was pro2 posed and also a new definition of mutex inference backwards was given correspondingly. The met hod re2 duced t he scale of t he planning grap h and t he search space , improved t he efficiency of searching the valid plan greatly. Because t he effects created by actions were contex2dependent , it was more suitable for t he practical needs compared with previous met hods , and made t he planning problems to be handled much closer to t he real word. Therefore , the met hod has its advantage over previous ones in application and has more practical significance. Keywords :grap hplan ; correlative component ;irrelative component ; creating or deleting objects component ; conditional effects 收稿日期 :2006210225. 近年来 ,有关智能规划的研究在问题描述和问 题求解 2 方面得到了新的突破 ,使得智能规划已成 为一个非常热门的研究领域 ,由于智能规划的研究 对象和研究方法的转变 ,极大地扩展了智能规划的 应用领域 ,使智能规划的理论和应用研究有了长足 的进展. 近几年来 ,随着客观条件的改善 ,世界上一 些发达国家在此领域获得了很大的发展 ,规划技术 已成功应用于国防和空间技术领域 ,并取得了巨大 的经济和社会效益 , NASA 于 1999 年在航天器 “Deep Space One”中运用规划技术 ,使得规划研究 从实验室向实际应用迈出了重要的一步 ,标志规划 的研究步入了实用阶段. 越来越多的学者致力于这 方面的研究 ,并取得了很多重大成果. 自 1995 年 Blum 和 Furst 提出图规划算法[ 1 - 2 ]
第3期 谷文祥，等：基于条件效果的对象动态可变图规划 ·13· 以来，与领域无关(domaimindependent)的智能规 往的算法没有处理这类问题的能力.又由于在现实 划算法的效率得到了较大的提高，这是一个很好的 中，初始条件中会有很多与求解目标无关的事实，而 算法，它的高效性主要体现在2个方面：一是有效利 文献[8]不能区分这些事实，它会从初始条件出发， 用节点间的互斥关系进行解搜索，减少了搜索空间， 实例化许多与实现目标无关的动作，这严重增加了 从而提高搜索效率；二是在同一时间步尽可能地并 规划图结构的宽度，同时大量时间会浪费在向规划 行执行多个非互斥动作，以保证找到的有效规划是 图中添加无用动作，无用效果，以及推导这些不相关 时间步数最短的规划.图规划的提出使得人工智能 动作及命题的互斥关系上.因此，文中采用了目标驱 规划领域取得了革命性的进展，受到了研究者的广 动方法6,9.)，提出了基于条件效果的对象动态可 泛关注，并在其基础上做了大量研究，已取得了大量 变的规划图的扩展算法，并提出了新的前向搜索有 成果.如Weld等人提出了基于条件效果的图规 效规划算法.这一方面的研究更加符合复杂真实的 划倒，Weld和Anderson等人提出了不确定性规 世界状态，并在很大程度上提高了求得有效规划的 划，，Blum等人提出了规划图框架下的概率规 效率，具有很高的应用价值.这一研究可广泛应用在 划s),Eric Parker提出了基于目标驱动的图规 机器配置、商品生产、运输货物等方面，这进一步丰 划6，Hong Jun提出了基于图分析的目标识别1， 富了规划理论并扩大了规划的应用范围」 以及谷文祥和蔡增玉等人提出了规划图框架下可创 1 研究基础 建/删除对象的规划1等.鉴于图规划良好的性能， 目前国内外仍有许多著名的学者在做图规划框架下 为了方便读者，这里对文中涉及到的几个基本 的研究 概念简要地加以介绍 图规划有其独特的优越性，但也有一些局限，主 规划：一个动作的序列称为一个规划 要的局限是它只能应用于STRIPS领域，规划问题 一个规划问题涉及以下4个集合： 中的动作不能消灭对象也不能创造对象，对对象实 1)一个操作的集合； 施某一动作的结果必须是能被静态确定的人或事. 2)一个对象的集合； 图规划不能处理对象动态可变的规划问题，但是现 3)一个初始条件的集合，其中每个元素都是命 实生活中有很多规划问题都不满足这个条件，例如 题； 网络安全、机器人控制、智能游戏、智能接口等方面， 4)一个目标的集合，其中每个元素都是命题，且 随着智能规划的发展，这个问题变得越来越严峻，已 要求规划结束时这些命题都为真」 经成为智能规划发展的一个瓶颈.这个问题1995年 有效规划：设有一个动作的集合，其中的每个动 就被提出，直到2005年谷文祥和蔡增玉等人提出了 作都被指明执行的时间步，在同一时间步内执行的 规划图框架下可创建/删除对象的规划)，对象动态 任何2个动作都是不相冲突的，所有的问题目标在 可变的规划问题才部分得以解决，但是文献[8]中处 最后的时间步均为真，那么，就称这个动作的集合为 理的动作创建的新对象是可静态确定的，不能处理 一个有效规划 动作创建的对象不能确定的规划问题，而且采用的 NOOP动作：对命题不做任何改变的动作 是前向图扩展与逆向搜索有效规划方法，这使得规 规划图：规划图是一个有向图，由2种结点，3 划图规模庞大，无用节点过多，当初始状态中有大量 种边组成.2种结点是命题结点和动作结点，3种边 无关事实时，问题会更加严重，求解效率更低.文中 是前提条件边，添加效果边，删除效果边.边把命题 在文献[8]的基础上进行了扩展，提出了基于条件效 层的命题结点和动作层的动作结点连接起来 果的对象动态可变的图规划，引入了描述能力更强 条件效果：动作描述中与上下文相依赖的效果， 的动作表示形式.与文献[8]不同，文中创建/删除的 通常用when子句表示，when子句由前提和结论组 新对象依赖于上下文的描述，前提不同就会生成不 成，动作的前提是主前提，when子句的前提是次要 同的新对象，即要处理的问题是基于条件效果的.在 前提 现实世界中，这样的问题大量存在，如在产品配置方 要素扩展法处理条件效果的基本思想：把动作 面，用户的需求不同，生产的产品也不同；货物运输 所有的效果都条件化，每个效果产生一个动作元件」 方面，货物不同，组装生成的运输工具也不同等，以 引致：i层元件Cm引致元件Cn指Cm在i层 @1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
以来 ,与领域无关 ( domain2independent) 的智能规 划算法的效率得到了较大的提高 ,这是一个很好的 算法 ,它的高效性主要体现在 2 个方面 :一是有效利 用节点间的互斥关系进行解搜索 ,减少了搜索空间 , 从而提高搜索效率 ;二是在同一时间步尽可能地并 行执行多个非互斥动作 ,以保证找到的有效规划是 时间步数最短的规划. 图规划的提出使得人工智能 规划领域取得了革命性的进展 ,受到了研究者的广 泛关注 ,并在其基础上做了大量研究 ,已取得了大量 成果. 如 Weld 等人提出了基于条件效果的图规 划[3 ] ,Weld 和 Anderson 等人提出了不确定性规 划[4 ] ,Blum 等人提出了规划图框架下的概率规 划[5 ] , Eric Parker 提出了基于目标驱动的图规 划[6 ] , Hong J un 提出了基于图分析的目标识别[7 ] , 以及谷文祥和蔡增玉等人提出了规划图框架下可创 建/ 删除对象的规划[ 8 ] 等. 鉴于图规划良好的性能 , 目前国内外仍有许多著名的学者在做图规划框架下 的研究. 图规划有其独特的优越性 ,但也有一些局限 ,主 要的局限是它只能应用于 STRIPS 领域 ,规划问题 中的动作不能消灭对象也不能创造对象 ,对对象实 施某一动作的结果必须是能被静态确定的人或事. 图规划不能处理对象动态可变的规划问题 ,但是现 实生活中有很多规划问题都不满足这个条件 ,例如 网络安全、机器人控制、智能游戏、智能接口等方面 , 随着智能规划的发展 ,这个问题变得越来越严峻 ,已 经成为智能规划发展的一个瓶颈. 这个问题 1995 年 就被提出 ,直到 2005 年谷文祥和蔡增玉等人提出了 规划图框架下可创建/ 删除对象的规划[8 ] ,对象动态 可变的规划问题才部分得以解决. 但是文献[ 8 ]中处 理的动作创建的新对象是可静态确定的 ,不能处理 动作创建的对象不能确定的规划问题 ,而且采用的 是前向图扩展与逆向搜索有效规划方法 ,这使得规 划图规模庞大 ,无用节点过多 ,当初始状态中有大量 无关事实时 ,问题会更加严重 ,求解效率更低. 文中 在文献[ 8 ]的基础上进行了扩展 ,提出了基于条件效 果的对象动态可变的图规划 ,引入了描述能力更强 的动作表示形式. 与文献[ 8 ]不同 ,文中创建/ 删除的 新对象依赖于上下文的描述 ,前提不同就会生成不 同的新对象 ,即要处理的问题是基于条件效果的. 在 现实世界中 ,这样的问题大量存在 ,如在产品配置方 面 ,用户的需求不同 ,生产的产品也不同 ;货物运输 方面 ,货物不同 ,组装生成的运输工具也不同等 ,以 往的算法没有处理这类问题的能力. 又由于在现实 中 ,初始条件中会有很多与求解目标无关的事实 ,而 文献[ 8 ]不能区分这些事实 ,它会从初始条件出发 , 实例化许多与实现目标无关的动作 ,这严重增加了 规划图结构的宽度 ,同时大量时间会浪费在向规划 图中添加无用动作 ,无用效果 ,以及推导这些不相关 动作及命题的互斥关系上. 因此 ,文中采用了目标驱 动方法[6 ,9 - 10 ] ,提出了基于条件效果的对象动态可 变的规划图的扩展算法 ,并提出了新的前向搜索有 效规划算法. 这一方面的研究更加符合复杂真实的 世界状态 ,并在很大程度上提高了求得有效规划的 效率 ,具有很高的应用价值. 这一研究可广泛应用在 机器配置、商品生产、运输货物等方面 ,这进一步丰 富了规划理论并扩大了规划的应用范围. 1 研究基础 为了方便读者 ,这里对文中涉及到的几个基本 概念简要地加以介绍. 规划 :一个动作的序列称为一个规划. 一个规划问题涉及以下 4 个集合 : 1) 一个操作的集合 ; 2) 一个对象的集合 ; 3) 一个初始条件的集合 ,其中每个元素都是命 题 ; 4) 一个目标的集合 ,其中每个元素都是命题 ,且 要求规划结束时这些命题都为真. 有效规划 :设有一个动作的集合 ,其中的每个动 作都被指明执行的时间步 ,在同一时间步内执行的 任何 2 个动作都是不相冲突的 ,所有的问题目标在 最后的时间步均为真 ,那么 ,就称这个动作的集合为 一个有效规划. NO2OP 动作 :对命题不做任何改变的动作. 规划图 :规划图是一个有向图 ,由 2 种结点 ,3 种边组成. 2 种结点是命题结点和动作结点 ,3 种边 是前提条件边 ,添加效果边 ,删除效果边. 边把命题 层的命题结点和动作层的动作结点连接起来. 条件效果 :动作描述中与上下文相依赖的效果 , 通常用 when 子句表示 ,when 子句由前提和结论组 成 ,动作的前提是主前提 ,when 子句的前提是次要 前提. 要素扩展法处理条件效果的基本思想 :把动作 所有的效果都条件化 ,每个效果产生一个动作元件. 引致 :i 层元件 Cm 引致元件 Cn 指 Cm 在 i 层 第 3 期 谷文祥 ,等 :基于条件效果的对象动态可变图规划 ·13 ·
·14 智能系统学报 第2卷 的执行必然导致Cn的执行，如不执行Cn,则Cm也 (when(r∧s)可).动作B有前提g,2个效果h, 无法执行 (when st).这2个动作分别元件化： 对元件的抵制：通过否定元件的前提条件来阻 动作A分解成的元件是： 止元件的执行 ①A1有前提p,效果e: 2基于条件效果的对象动态可变的规 ②4，有前提p个q,效果f: ③43有前提py八s,效果y: 划问题 动作B分解成的元件是： 2.1 CECDOP问题描述 ①B1有前提g,效果h: 在文献[8]中己经介绍了创建/删除的对象是可 ②B2有前提q八s,效果1 静态确定的情况，文中研究的基于条件效果的对象 其中元件A1,A2,A3都来自动作A,它们是相 动态可变的规划问题，简记为CECDOP(conditional 关元件，同样元件B1,B?都来自动作B,它们也是 effects in creating or deleting object plan)问题， 相关元件.但是A1,A2,A3与B1,B2之间是无关元 CECDOP中创建/删除的对象是不可静态确定的， 件.动作A中，p是主要前提，q和(r八y)是次要前 动作的前提不同时创建/删除的对象也是不同的即 提，动作B中，q是主要前提，s是次要前提 效果是依赖于上下文的描述.因为现实世界是一个 与文献3]中的定义有所不同，文中对引致和元 动态复杂的世界，很多规划问题都会涉及到动作创 件抵制进行了改进： 建的对象是动态可变的情况，而且创建的新对象由 引致：i层元件Cm引致元件Cn指Cm在i层 前提而定，如运输问题，不同的货物对卡车的要求不 的执行必然导致Cn的执行，如不执行Cn,则Cm也 同，轻的货物用单排轮的卡车运输，重的货物则要用 无法执行 双排轮的卡车运输，这样运输货物的不同要求组装 具体要求： 生成的卡车也不同.由于文中规划问题的动作所产 ①cm和Cn是相关元件，有相同的变量约束； 生的效果是依赖于上下文的描述，在文献[3]的基础 ②Cm和Cn不互斥： 上引入了表达能力更强的动作描述形式： ③cn的否定前提在i-1层不能被满足 2.2CECD0P中操作的表达方式 对元件的抵制：通过否定元件的次要前提条件 文中讨论了基于条件效果的对象动态可变的规 来阻止元件的执行，这比文献[3]中的方法好，因为 划问题，对于所有动作都采用元件化思想，即动作产 这样可以减少很多不必要的循环 生的所有效果都对应一个动作元件，非条件效果的 文中的元件根据是否可以创建/删除对象分成 动作产生唯一一个元件.在文献[3]中所有的元件用 2类：普通元件，可创建/删除对象的元件(CDO元 “C”+1表示元件i,这不能表明元件来自哪个动作， 件，creat or delete object). 也不能表明哪些元件是来自同一动作的，在处理互 定义3一个元件可以创建/删除对象，称为创 斥时比较复杂，与文献[3]不同，文中的元件用Ac 建/删除对象元件，对它们的实例化称为CDO元件 tion+i表示来自动作Action的元件i,这样上面提 实例。 出的问题就会得到解决，这种描述方法即能表明元 定义4除了CD0元件都是普通元件，对它们 件来自哪个动作，也能表明哪些元件是来自同一动 的实例化称为普通元件实例 作的，这样在处理互斥时就可以减少许多不必要的 表示方式如下： 循环 CDO component: 为了表述问题更清楚，把元件进行了分类.文中 Component number 中的元件根据来源可分成2类： the set of parameter 定义1来自同一动作实例的元件称为相关元 (the set of common parameter 件】 the set of optional parameter 定义2来自不同动作实例的元件称为无关元 } 件」 the set of precondition 例1：动作A有前提p,3个效果e,(when qf), the set of effect 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的执行必然导致 Cn 的执行 ,如不执行 Cn ,则 Cm 也 无法执行. 对元件的抵制 :通过否定元件的前提条件来阻 止元件的执行. 2 基于条件效果的对象动态可变的规 划问题 211 CECDOP 问题描述 在文献[8 ]中已经介绍了创建/ 删除的对象是可 静态确定的情况 ,文中研究的基于条件效果的对象 动态可变的规划问题 ,简记为 CECDOP(conditional effects in creating or deleting object plan) 问题 , CECDOP 中创建/ 删除的对象是不可静态确定的 , 动作的前提不同时创建/ 删除的对象也是不同的 ,即 效果是依赖于上下文的描述. 因为现实世界是一个 动态复杂的世界 ,很多规划问题都会涉及到动作创 建的对象是动态可变的情况 ,而且创建的新对象由 前提而定 ,如运输问题 ,不同的货物对卡车的要求不 同 ,轻的货物用单排轮的卡车运输 ,重的货物则要用 双排轮的卡车运输 ,这样运输货物的不同要求组装 生成的卡车也不同. 由于文中规划问题的动作所产 生的效果是依赖于上下文的描述 ,在文献[3 ]的基础 上引入了表达能力更强的动作描述形式. 212 CECDOP 中操作的表达方式 文中讨论了基于条件效果的对象动态可变的规 划问题 ,对于所有动作都采用元件化思想 ,即动作产 生的所有效果都对应一个动作元件 ,非条件效果的 动作产生唯一一个元件. 在文献[ 3 ]中所有的元件用 “C”+ i 表示元件 i ,这不能表明元件来自哪个动作 , 也不能表明哪些元件是来自同一动作的 ,在处理互 斥时比较复杂 ,与文献[ 3 ]不同 ,文中的元件用 Ac2 tion + i 表示来自动作 Action 的元件 i ,这样上面提 出的问题就会得到解决 ,这种描述方法即能表明元 件来自哪个动作 ,也能表明哪些元件是来自同一动 作的 ,这样在处理互斥时就可以减少许多不必要的 循环. 为了表述问题更清楚 ,把元件进行了分类. 文中 中的元件根据来源可分成 2 类 : 定义 1 来自同一动作实例的元件称为相关元 件. 定义 2 来自不同动作实例的元件称为无关元 件. 例 1 :动作 A 有前提 p ,3 个效果 e ,(when q f ) , (when ( r ∧s) ﹁q) . 动作 B 有前提 q ,2 个效果 h , (when s t) . 这 2 个动作分别元件化 : 动作 A 分解成的元件是 : ①A1 有前提 p ,效果 e; ②A2 有前提 p ∧q ,效果 f ; ③A3 有前提 p ∧r ∧s,效果﹁q; 动作 B 分解成的元件是 : ①B1 有前提 q ,效果 h; ②B2 有前提 q ∧s,效果 t. 其中元件 A1 , A2 , A3 都来自动作 A ,它们是相 关元件 ,同样元件 B1 , B2 都来自动作 B ,它们也是 相关元件. 但是 A1 , A2 , A3 与 B1 , B2 之间是无关元 件. 动作 A 中 , p 是主要前提 , q 和 ( r ∧s) 是次要前 提 ,动作 B 中 , q 是主要前提 ,s 是次要前提. 与文献[3 ]中的定义有所不同 ,文中对引致和元 件抵制进行了改进 : 引致 :i 层元件 Cm 引致元件 Cn 指 Cm 在 i 层 的执行必然导致 Cn 的执行 ,如不执行 Cn ,则 Cm 也 无法执行. 具体要求 : ①Cm 和 Cn 是相关元件 ,有相同的变量约束 ; ②Cm 和 Cn 不互斥 ; ③Cn 的否定前提在 i - 1 层不能被满足. 对元件的抵制 :通过否定元件的次要前提条件 来阻止元件的执行 ,这比文献[ 3 ]中的方法好 ,因为 这样可以减少很多不必要的循环. 文中的元件根据是否可以创建/ 删除对象分成 2 类 :普通元件 ,可创建/ 删除对象的元件 (CDO 元 件 ,creat or delete object) . 定义 3 一个元件可以创建/ 删除对象 ,称为创 建/ 删除对象元件 ,对它们的实例化称为 CDO 元件 实例. 定义 4 除了 CDO 元件都是普通元件 ,对它们 的实例化称为普通元件实例. 表示方式如下 : CDO component : Component + number{ :t he set of parameter{ {t he set of common parameter} {t he set of optional parameter} } :t he set of precondition{ …} :t he set of effect { ·14 · 智 能 系 统 学 报 第 2 卷
第3期 谷文祥，等：基于条件效果的对象动态可变图规划 ·15 the set of object added 动作的前提或“有效结果”（在规划图中动作的结果 the set of object deleted) 被用来支持命题)；②沱们的有效结果集合完全相 the effect propositions) 同；③一个动作支持的命题与另一个动作支持的命 题两两互斥 2)两个命题逆向互斥，如果一个命题支持的所 Common component 有动作与另一个命题支持的所有动作两两互斥 Component number 由于文中采用目标驱动图扩展方法，规划图由 :the set of parameter{ 目标开始逆向产生，因此也要进行逆向推理和传播 :the set of precondition 互斥.但是与文献[11]不同，文中将处理3种互斥关 :the set of effect the effect proposition! 系：动作元件互斥，对象互斥，命题互斥 1)动作元件逆向互斥 2.3 CECDOP中对象的表达方式 2个动作元件Cm与Cn互斥： 在CDUOP中，一些动作能够创建新的对象或 ①静态互斥：2个元件Cm与Cn是无关元件， 删除已经存在的对象，对象在规划图中可动态地变 且元件Cm/Cn的结果删除另一个元件Cn/Cm的 化，在图规划中命题也有这样的性质，因此文中将延 前提或“有效结果”（在规划图中元件的结果被用来 用对象命题化8]思想，即用命题表示对象在某些规 支持命题)或②它们有效结果集合完全相同，或③ 划层的存在形式，采用alive+“对象名”表示方式. Cm与Cn支持的命题两两互斥，或④引致互斥：如 命题被分成了普通命题和对象命题， 果Cn引致Ck,Ck与Cm互斥，则Cn与Cm也互 斥 3 CECDOP规划 2)与对象命题有关的逆向互斥 3.1 CECDOP问题的组成 因为对象命题不支持元件，所以它们的互斥关 元件集包括普通元件和创建/删除对象元件 系不能通过后向传播得到，因此可以退前一步，当产 对象集 生1层动作元件时再判定1层的对象命题的互斥关 初始条件集由命题组成 系（目标出现的层是第1命题层，从目标往前扩展 目标集由命题组成，经过一系列操作，在规划 接着是第1元件层，以此类推)，1层与对象命题A 结束时这些命题为真 和B有关的逆向互斥，如果： 3.2 CECDOP规划图 ①层创建对象命题A的元件与创建对象命题 文中研究的CECDOP的规划图与图规划的规 B的元件通过逆向传播标记为互斥，则i层对象命 划图不同，它是由2种边和2种结点组成.CECDOP 题A与B互斥 的规划图的边由前提条件边、添加效果边组成，因为 ②如果i层中二对象命题A与B标记为互斥 是基于目标驱动构建规划图，所以图中没有删除效 且名字分别出现在i层的普通命题P和Q中，则普 果边.命题结点是由普通命题结点和对象命题结点 通命题P与Q互斥 组成，元件结点是由普通元件结点和创建/删除对象 3)普通命题逆向互斥 的元件结点组成.边把命题结点和元件结点相连，表 如果ⅰ层命题P支持的所有动作元件与命题Q 示了它们之间的关系.添加效果边把元件在前一层 支持的所有动作元件两两互斥，则普通命题P与Q 命题列的效果和元件相连，前提条件边把元件和下 互斥.互斥关系如图1所示 一层的命题列的前提相连 3.4图扩展算法 3.3逆向传播互斥 CECDOP算法包括扩展规划图和搜索有效规 以目标驱动方法扩展规划图时，规划图逆向产 划，这两部分交替进行.文中的规划图是从目标开始 生，这就要求逆向推理和传播互斥关系.在文献[11] 的，逐步向前扩展.这种扩展方法可以去除许多与目 中给出了逆向传播互斥关系的定义 标无关的命题与动作，规划图比较简单 1)2个动作逆向互斥，如果2个动作 3.4.1图扩展 ①静态互斥：如果一个动作的结果删除另一个 文中是以目标为导向进行规划图扩展的，算法 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
{the set of object added} {the set of object deleted} {the effect propositions} } } Common component : Component + number{ :t he set of parameter{ …} :t he set of precondition{ …} :t he set of effect{t he effect proposition} } 213 CECDOP 中对象的表达方式 在 CDUOP 中 ,一些动作能够创建新的对象或 删除已经存在的对象 ,对象在规划图中可动态地变 化 ,在图规划中命题也有这样的性质 ,因此文中将延 用对象命题化[8 ] 思想 ,即用命题表示对象在某些规 划层的存在形式 ,采用 alive +“对象名”表示方式. 命题被分成了普通命题和对象命题. 3 CECDOP 规划 311 CECDOP 问题的组成 元件集 包括普通元件和创建/ 删除对象元件 对象集 初始条件集 由命题组成 目标集 由命题组成 ,经过一系列操作 ,在规划 结束时这些命题为真 312 CECDOP 规划图 文中研究的 CECDOP 的规划图与图规划的规 划图不同 ,它是由 2 种边和 2 种结点组成. CECDOP 的规划图的边由前提条件边、添加效果边组成 ,因为 是基于目标驱动构建规划图 ,所以图中没有删除效 果边. 命题结点是由普通命题结点和对象命题结点 组成 ,元件结点是由普通元件结点和创建/ 删除对象 的元件结点组成. 边把命题结点和元件结点相连 ,表 示了它们之间的关系. 添加效果边把元件在前一层 命题列的效果和元件相连 ,前提条件边把元件和下 一层的命题列的前提相连. 313 逆向传播互斥 以目标驱动方法扩展规划图时 ,规划图逆向产 生 ,这就要求逆向推理和传播互斥关系. 在文献[11 ] 中给出了逆向传播互斥关系的定义. 1) 2 个动作逆向互斥 ,如果 2 个动作 : ①静态互斥 :如果一个动作的结果删除另一个 动作的前提或“有效结果”(在规划图中动作的结果 被用来支持命题) ; ②它们的有效结果集合完全相 同 ; ③一个动作支持的命题与另一个动作支持的命 题两两互斥. 2) 两个命题逆向互斥 ,如果一个命题支持的所 有动作与另一个命题支持的所有动作两两互斥. 由于文中采用目标驱动图扩展方法 ,规划图由 目标开始逆向产生 ,因此也要进行逆向推理和传播 互斥. 但是与文献[11 ]不同 ,文中将处理 3 种互斥关 系 :动作元件互斥 ,对象互斥 ,命题互斥. 1) 动作元件逆向互斥 2 个动作元件 Cm 与 Cn 互斥 : ①静态互斥 :2 个元件 Cm 与 Cn 是无关元件 , 且元件 Cm/ Cn 的结果删除另一个元件 Cn/ Cm 的 前提或“有效结果”(在规划图中元件的结果被用来 支持命题) 或 ②它们有效结果集合完全相同 ,或 ③ Cm 与 Cn 支持的命题两两互斥 ,或 ④引致互斥 :如 果 Cn 引致 Ck ,Ck 与 Cm 互斥 ,则 Cn 与 Cm 也互 斥. 2) 与对象命题有关的逆向互斥 因为对象命题不支持元件 ,所以它们的互斥关 系不能通过后向传播得到 ,因此可以退前一步 ,当产 生 i 层动作元件时再判定 i 层的对象命题的互斥关 系(目标出现的层是第 1 命题层 ,从目标往前扩展 , 接着是第 1 元件层 ,以此类推) , i 层与对象命题 A 和 B 有关的逆向互斥 ,如果 : ①i 层创建对象命题 A 的元件与创建对象命题 B 的元件通过逆向传播标记为互斥 ,则 i 层对象命 题 A 与 B 互斥 ②如果 i 层中二对象命题 A 与 B 标记为互斥 , 且名字分别出现在 i 层的普通命题 P 和 Q 中 ,则普 通命题 P 与 Q 互斥. 3) 普通命题逆向互斥 如果 i 层命题 P 支持的所有动作元件与命题 Q 支持的所有动作元件两两互斥 ,则普通命题 P 与 Q 互斥. 互斥关系如图 1 所示. 314 图扩展算法 CECDOP 算法包括扩展规划图和搜索有效规 划 ,这两部分交替进行. 文中的规划图是从目标开始 的 ,逐步向前扩展. 这种扩展方法可以去除许多与目 标无关的命题与动作 ,规划图比较简单. 31411 图扩展 文中是以目标为导向进行规划图扩展的 ,算法 第 3 期 谷文祥 ,等 :基于条件效果的对象动态可变图规划 ·15 ·
16· 智能系统学报 第2卷 可用前提集中)的元件Cs,如果它不与SC.!中己选 Pro.I com.I Pro.2 com.2 Pro.3 元件互斥，且不在SC.1中，则把Cs加入SC.1,并 alive 把Cs的效果加入i-1层可用前提集SP.1中 actl aliveB act.I aliveC act:1. act2 alive D 3)对于SC.1中的每一个元件Cs和Ct,考察 -In4 B alive Cs的引致元件Cm和Ct的引致元件Cn,如果Cm 与Cn互斥，则要选Cm和Cn之一进行抵制 component Proposition component Proposition 4)如果i=1,则SC.1,SC2,…,SC构成规 划解，否则i-1重复上面的步骤。 图1逆向传播互斥 3.5例子 Fig 1 Mutex inference backward 在A地有2个卡车车身(body),一组单排轮轮 胎(single tire,ST),一组双排轮轮胎(double tires, 描述如下 DT),一批木材(wood)和一批钢材(steel)还有一批 1)所有目标命题构成第1层命题层 2)构建第1层元件层 石板(flagstone),木材只需单排轮卡车就能运输，而 对于元件集中每一个元件，如果它的效果在目 钢材和石板则需双排轮的卡车才能运输，目标是把 木材和钢材运到C地 标集中出现，则把该元件实例化，并用上面判定互斥 的方法检查互斥，然后用效果边把元件和其对应的 给出一些操作：move,truck(创建一辆卡车)， 效果相连 load,unload 3)构建第1层命题层 对应的元件 ①向第1层中添加普通命题 movel:表示移动单排轮的卡车 首先通过持续边把i-1层的普通命题加入到i move2:表示移动双排轮的卡车 命题层，然后考察1-1层动作元件的前提，如果不 truck1:表示组装单排轮的卡车 在i命题层则加入，用上面判定互斥的方法检查互 truck2:表示组装双排轮的卡车 斥，并用前提条件边把元件和其对应的前提相连 loadl:表示装木材 ②往第i层添加对象命题 load2:表示装钢材 首先通过持续边把i-1层的对象命题加入到i load3:表示装石板 命题层，然后考察，当1层已添加的普通命题涉及到 unload1:表示卸木材 新对象A时，如果对象命题A不在i命题层则在i unload2:表示卸钢材 命题层中添加对象命题alive A. unload3:表示卸石板 ③如果在ⅰ命题层初始目标出现且不互斥，则 initial condition:(alive bodyl,alive body2, 开始搜索有效规划，否则继续扩展规划图 alive ST,alive DT,alive wood,alive steel,a- 4)构建第1层元件层 live flagstoneat bodyl A,at body2 A,at ST A. 对于元件集中每一个可行元件，如果它的效果 at DT A,at wood A,at steel A,at flagstone A} 在1层命题层出现，则实例化该元件，并用上面判定 components:movel,move2,truckl,truck2, 互斥的方法检查互斥，并根据本层的互斥确定1层 loadl,load2 load3,unloadl,unload2,unload3) 命题层中与对象命题有关的互斥，然后用效果边把 goals:at wood C,at steel C) 元件和其对应的效果相连 规划图如图2. 3.42搜索有效规划 其中truckS表示单排轮卡车，truckD表示双排 与以前的后向搜索有效规划不同，文中采用的 轮卡车 是前向搜索有效规划，算法如下： 到第5层时，初始目标出现且不互斥，开始前向 )i层为初始命题层，SP-{},其中SP,是i 搜索有效规划，最后的规划解是： 层可用前提集，初始时，把初始命题加入SP,中 step1 truckl 2)SC1},其中SC,-1是i-1层可执行元 truck2 件集，对于i·1层可实例化（元件的前提在i层的 step2:loadl 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 逆向传播互斥 Fig11 Mutex inference backward 描述如下 : 1) 所有目标命题构成第 1 层命题层 2) 构建第 1 层元件层 对于元件集中每一个元件 ,如果它的效果在目 标集中出现 ,则把该元件实例化 ,并用上面判定互斥 的方法检查互斥 ,然后用效果边把元件和其对应的 效果相连. 3) 构建第 i 层命题层 ①向第 i 层中添加普通命题 首先通过持续边把 i - 1 层的普通命题加入到 i 命题层 ,然后考察 i - 1 层动作元件的前提 ,如果不 在 i 命题层则加入 ,用上面判定互斥的方法检查互 斥 ,并用前提条件边把元件和其对应的前提相连. ②往第 i 层添加对象命题 首先通过持续边把 i - 1 层的对象命题加入到 i 命题层 ,然后考察 ,当 i 层已添加的普通命题涉及到 新对象 A 时 ,如果对象命题 A 不在 i 命题层则在 i 命题层中添加对象命题 alive A . ③如果在 i 命题层初始目标出现且不互斥 ,则 开始搜索有效规划 ,否则继续扩展规划图. 4) 构建第 i 层元件层 对于元件集中每一个可行元件 ,如果它的效果 在 i 层命题层出现 ,则实例化该元件 ,并用上面判定 互斥的方法检查互斥 ,并根据本层的互斥确定 i 层 命题层中与对象命题有关的互斥 ,然后用效果边把 元件和其对应的效果相连. 31412 搜索有效规划 与以前的后向搜索有效规划不同 ,文中采用的 是前向搜索有效规划 ,算法如下 : 1) i 层为初始命题层 , SPi ←{ } ,其中 SPi 是 i 层可用前提集 ,初始时 ,把初始命题加入 SPi 中. 2) SCi - 1 ←{} , 其中 SCi - 1 是 i - 1 层可执行元 件集 ,对于 i - 1 层可实例化 (元件的前提在 i 层的 可用前提集中) 的元件 Cs ,如果它不与 SCi - 1中已选 元件互斥 ,且不在 SCi - 1 中 ,则把 Cs 加入 SCi - 1 ,并 把 Cs 的效果加入 i - 1 层可用前提集 SPi - 1中. 3) 对于 SCi - 1 中的每一个元件 Cs 和 Ct ,考察 Cs 的引致元件 Cm 和 Ct 的引致元件 Cn ,如果 Cm 与 Cn 互斥 ,则要选 Cm 和 Cn 之一进行抵制. 4) 如果 i = 1 ,则 SCi - 1 ,SCi - 2 , ……,SC1 构成规 划解 ,否则 i - 1 重复上面的步骤. 315 例子 在 A 地有 2 个卡车车身(body) ,一组单排轮轮 胎(single tire ,ST) ,一组双排轮轮胎 (double tires , D T) ,一批木材(wood) 和一批钢材 (steel) 还有一批 石板(flagstone) ,木材只需单排轮卡车就能运输 ,而 钢材和石板则需双排轮的卡车才能运输 ,目标是把 木材和钢材运到 C 地. 给出一些操作 : move ,truck (创建一辆卡车) , load ,unload 对应的元件 : move1 :表示移动单排轮的卡车 move2 :表示移动双排轮的卡车 truck1 :表示组装单排轮的卡车 truck2 :表示组装双排轮的卡车 load1 :表示装木材 load2 :表示装钢材 load3 :表示装石板 unload1 :表示卸木材 unload2 :表示卸钢材 unload3 :表示卸石板 initial condition :{alive body1 ,alive body2 , alive ST , alive D T , alive wood , alive steel , a2 live flagstone ,at body1 A , at body2 A , at ST A , at D T A , at wood A , at steel A , at flagstone A} components: { move1 , move2 , truck1 , truck2 , load1 ,load2 ,load3 ,unload1 ,unload2 , unload3} goals:{at wood C ,at steel C} 规划图如图 2. 其中 truckS 表示单排轮卡车 ,truckD 表示双排 轮卡车. 到第 5 层时 ,初始目标出现且不互斥 ,开始前向 搜索有效规划 ,最后的规划解是 : step1 :truck1 truck2 step2 :load1 ·16 · 智 能 系 统 学 报 第 2 卷
第3期 谷文祥，等：基于条件效果的对象动态可变图规划 ·17· load2 从上面这个关于CECDOP例子中可以看出前 step3 movel 提不同时创建的卡车也不同，而且以目标为导向采 move2 用目标驱动方法扩展得到的规划图结构简单，如果 step4 unloadI 从初始条件开始扩展，则运输石板也要考虑，而这和 unload2 目标无关，因此对它的实例化是无用的 pro.1 com.I pro.2 com.2 pro.3 com.3 pro.4 com.4 pro.5 alive truckS alive truckS alve trucks alive truckS alive truckD -alive truckD alive truckD alive truck D alive body I alive bodyl alive body2 alive body2 alive ST -alive ST alive DT 、 alive DT truckl truck2 truck2 at truckS C movel at truckS A -movlel at truck S A- movel at truck SA at wood C-unloadl-in wood truckS-loadl- -at wood A loadl wood A loadl at wood A at steel C -unload2. in steel truckD-load2 -at steel A -load2 at sheel A load2 at'steel A at truckD C_ -move2 at truck D A- move2- at truch D A move2 at truchD A at bodyl A at bodyl A at ST A- at ST A at body2 A at body2 A Note:一前提条件边和添加效果边 at DT A- at DTA ◆带有n0-0p的边 图2卡车运输货物的CECDOP规划图 Fig 2 A planning graph created by CECDOP for the transportation problem using trucks 4结束语 造出何种对象或可能是哪几个对象中的一个.由于 现实中的绝大多数规划都是某一具体领域的规划， 文中在可创建/删除对象的图规划的基础上做 可能涉及到何种对象或可能是哪几个对象可预知， 了扩展，研究了基于条件效果的对象动态可变的规 目前主要讨论了第2类问题，其实第1类问题也是 划问题，提出了把所有动作元件化的方法，给出了可 值得研究的，因为此类问题在化学领域有着广泛的 创建/删除对象的动作元件的定义，提出了新的基于 应用.此外，由于现实世界具有动态多变性，也可以 目标驱动的扩展规划图算法及前向求解有效规划的 考虑把Flexible graphplan2和DCSp1的方法引 算法，并举例进行了说明.由于算法中的动作创建的 入文中.对对象动态可变问题的研究很有价值，这一 效果是依赖于上下文的描述，这更加符合现实需要， 方向的研究工作才刚刚开始，许多方面还有待于完 使处理的问题更接近于真实的世界状态，因而此算 善 法比以往的算法应用性更强，更具有现实意义 参考文献： 对于能创建/删除对象的规划问题，一般分成两 类，一种是创建的新对象的性质不可预知，即在规划 [1]BLUM A,FURST M.Fast planning through planning 搜索前不知道可能创造出何种对象，也不知道创建 graph analysis[A].In Proc 14th Int Joint Conf AI[C]. Montreal,Canada,1995. 的新对象有何性质，这就要求在创造新对象的同时 [2]BLUM A,FURST M.Fast planning through planning 把涉及到新对象的动作也加进来.另一种是创建的 graph analysis [J].J Artificial Intelligence,1997,90 新对象的性质可预知，即在规划搜索前知道可能创 (1-2):281-300 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
load2 step3 :move1 move2 step4 :unload1 unload2 从上面这个关于 CECDOP 例子中可以看出前 提不同时创建的卡车也不同 ,而且以目标为导向采 用目标驱动方法扩展得到的规划图结构简单 ,如果 从初始条件开始扩展 ,则运输石板也要考虑 ,而这和 目标无关 ,因此对它的实例化是无用的. 图 2 卡车运输货物的 CECDOP 规划图 Fig12 A planning graph created by CECDOP for the transportation problem using trucks 4 结束语 文中在可创建/ 删除对象的图规划的基础上做 了扩展 ,研究了基于条件效果的对象动态可变的规 划问题 ,提出了把所有动作元件化的方法 ,给出了可 创建/ 删除对象的动作元件的定义 ,提出了新的基于 目标驱动的扩展规划图算法及前向求解有效规划的 算法 ,并举例进行了说明. 由于算法中的动作创建的 效果是依赖于上下文的描述 ,这更加符合现实需要 , 使处理的问题更接近于真实的世界状态 ,因而此算 法比以往的算法应用性更强 ,更具有现实意义. 对于能创建/ 删除对象的规划问题 ,一般分成两 类 ,一种是创建的新对象的性质不可预知 ,即在规划 搜索前不知道可能创造出何种对象 ,也不知道创建 的新对象有何性质 ,这就要求在创造新对象的同时 把涉及到新对象的动作也加进来. 另一种是创建的 新对象的性质可预知 ,即在规划搜索前知道可能创 造出何种对象或可能是哪几个对象中的一个. 由于 现实中的绝大多数规划都是某一具体领域的规划 , 可能涉及到何种对象或可能是哪几个对象可预知 , 目前主要讨论了第 2 类问题 ,其实第 1 类问题也是 值得研究的 ,因为此类问题在化学领域有着广泛的 应用. 此外 ,由于现实世界具有动态多变性 ,也可以 考虑把 Flexible grap hplan [12 ] 和 DCSP [13 ] 的方法引 入文中. 对对象动态可变问题的研究很有价值 ,这一 方向的研究工作才刚刚开始 ,许多方面还有待于完 善. 参考文献 : [1 ]BLUM A , FURST M. Fast planning through planning graph analysis[ A ]. In Proc 14th Int Joint Conf AI[ C]. Montreal , Canada , 1995. [2 ]BLUM A , FURST M. Fast planning through planning graph analysis [J ]. J Artificial Intelligence , 1997 , 90 (1 - 2) :281 - 300. 第 3 期 谷文祥 ,等 :基于条件效果的对象动态可变图规划 ·17 ·
·18· 智能系统学报 第2卷 [3]ANDERSON C R,SMITH D E,WELD D S.Conditional [12]MIGUEL I,JARVIS P,SHEN Q.Flexible graphplan effects in graphplan[A].In Proc AI Planning Systems [A].In Proceedings of the Fourteenth European Confer- Conference[C].AAAI Press.Melo Park,1998. ence on Artificial Intelligence[C].Berlin,Humboldt U- [4]WELD D S,ANDERSON C R,SMITH D E.Extending niversity,2000. graphplan to handle uncertain and sensing actions[A ] [13]MITTAL S,FAL KEN HAIN ER B.Dynamic constraint In AAA198[C].Madison,Wisconsin,U S A,1998. satisfaction problems[A ]In Proc.of the 8th National [5]BLUM A L,LAN GFORD J C.Probabilistic planning in Conference on Artificial Intelligence [C].Boston,Mas- the graphplan framework [A ]AIPS98 Workshop on sachusetts,1990. Planning as Combinatorial Search [C].Pittsburgh, 作者简介： 1998. 谷文祥，男，1947年生，教授，博士 [6]PARKER E.Making graphplan goa-Directed [A ]In 生导师，主要研究方向为智能规划与规 ECP99[C].Durham,United Kingdom,1999. 划识别、形式语言与自动机、模糊数学 [7]HON GJ.Graph construction and analysis as a paradigm 及其应用.主持国家自然科学基金项目 for plan recognition[A].In Proc of AAAF2000:Seven 2项，参与国家自然科学基金项目1项， teenth National Conference on Artificial Intelligence[C]. 教育部重点项目2项，省科委项目1项， Austin,Texas,USA,2000. 发表论文百篇以上。 [8 GU Wenxiang,CAI Zengyu,ZHANG Xinmei,et al. Email :gwx @nenu.edu.cn. Extending graphplan to handle the creating or destroying objects panning[A].ICMLC2005[C].Guangzhou,Chi- na,2005. 杨永娟，女，1982年生，硕士研究生， [9]NEBEL B,DIMOPOULOS Y,KOEHL ER J.Ignoring 主要研究方向为智能规划与规划识别， irrelevant facts and operators in plan generation[A].In Proc 4th European Conference on Planning [C].Tou louse,France,1997. [10]XU Li,GU Wenxiang,ZHAN G Xinmei,et al.Goal- directed flexible graphplan [A].In Proceeding of 2005 International Conference on Machine Learning and Cy- 闫书亚，女，1982年生，硕士研究 bernetics[C].Guangzhou,China,2005. 生，主要研究方向为智能规划与规划识 [11]KAMBHAMPATI S,PARKER E,LAMBRECHT E. 别。 Understanding and extending graphplan[A ]In proceed- ings of the 4th European Conference on Planning Tou- louse[C].France,1997. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[3 ]ANDERSON C R , SMITH D E ,WELD D S. Conditional effects in graphplan [ A ]. In Proc AI Planning Systems Conference[C]. AAAI Press. Melo Park , 1998. [4 ]WELD D S , ANDERSON C R , SMITH D E. Extending graphplan to handle uncertain and sensing actions[ A ]. In AAAI98[C]. Madison , Wisconsin , U S A , 1998. [5 ]BLUM A L , LAN GFORD J C. Probabilistic planning in the graphplan framework [ A ]. AIPS98 Workshop on Planning as Combinatorial Search [ C ]. Pittsburgh , 1998. [6 ] PARKER E. Making graphplan goal2Directed [ A ]. In ECP99[C]. Durham , United Kingdom , 1999. [7 ] HON G J. Graph construction and analysis as a paradigm for plan recognition[A ]. In Proc of AAAI22000 : Seven2 teenth National Conference on Artificial Intelligence[C]. Austin , Texas , USA , 2000. [8 ] GU Wenxiang , CAI Zengyu , ZHAN G Xinmei , et al. Extending graphplan to handle the creating or destroying objects panning[ A ]. ICMLC2005 [ C]. Guangzhou ,Chi2 na , 2005. [9 ] N EBEL B , DIMOPOULOS Y , KOEHL ER J. Ignoring irrelevant facts and operators in plan generation [ A ]. In Proc 4th European Conference on Planning [ C ]. Tou2 louse , France , 1997. [10 ]XU Li , GU Wenxiang , ZHAN G Xinmei , et al. Goal - directed flexible graphplan [ A ]. In Proceeding of 2005 International Conference on Machine Learning and Cy2 bernetics[C]. Guangzhou , China , 2005. [11 ] KAMB HAMPA TI S , PAR KER E ,LAMBRECH T E. Understanding and extending graphplan[ A ]. In proceed2 ings of the 4th European Conference on Planning Tou2 louse[C]. France , 1997. [12 ] MIGU EL I , J ARVIS P , SHEN Q. Flexible graphplan [ A ]. In Proceedings of the Fourteenth European Confer2 ence on Artificial Intelligence[ C]. Berlin , Humboldt U2 niversity , 2000. [13 ]MITTAL S ,FAL KEN HAINER B. Dynamic constraint satisfaction problems[ A ]. In Proc. of the 8th National Conference on Artificial Intelligence [ C]. Boston , Mas2 sachusetts , 1990. 作者简介 : 谷文祥 ,男 ,1947 年生 ,教授 ,博士 生导师 ,主要研究方向为智能规划与规 划识别、形式语言与自动机、模糊数学 及其应用. 主持国家自然科学基金项目 2 项 ,参与国家自然科学基金项目 1 项 , 教育部重点项目 2 项 ,省科委项目 1 项 , 发表论文百篇以上. Email :gwx @nenu. edu. cn. 杨永娟 ,女 ,1982 年生 ,硕士研究生 , 主要研究方向为智能规划与规划识别. 闫书亚 ,女 , 1982 年生 ,硕士研究 生 ,主要研究方向为智能规划与规划识 别. ·18 · 智 能 系 统 学 报 第 2 卷