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