第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 ]