（计算机软件与理论专业论文）基于规划图中动作选择策略的快速向前规划方法.pdf

中山人学硕= l 学位论文2 0 0 5基于规划图中动作选择策略的快速向前规划方法 基于规划图中动作选择策略的快速向前规划方法 计算机软件与理论 硕士生：梁丹然 指导教师：姜云飞教授 摘要 智能规划是人工智能研究领域近年来发展起来的一个热门分支。通用的规划 方法是为了解决一般的规划问题而设计的，在具体应用下效率则比较低。为了提 高通用规划方法在求解具体领域问题时的效率，本文研究了通用规划方法结合领 域知识来求解具体领域问题的方法，把领域知识表示为动作选择策略，介绍了一 种基于规划图的动作选择策略指导规划的方法和把它与f f 规划器结合形成的基 于规划图中动作选择策略的快速向前规划系统p i f f ，然后对国际智能规划大赛上 的积木世界领域和仓库领域抽取领域知识，输入至o p i f f 中来求解这两个领域上的 问题。实验结果表明，在这两个领域上，p i f f 可以方便地增加领域知识，其效率 比f f 有了很大提高，求得的规划解的质量也有所提高。 关键词：规划，动作选择策略，p i f f ，积木世界领域，仓库领域 中山人学硕学位论文2 0 0 5 肇十规划目中动作选择策略的快速向前规划方法 a c t i o ns e l e c t i o ns t r a t e g i e si n t e g r a t e df a s tf o r w a r d p l a n n i n ga l g o r i t h m c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：d a n r a nl i a n g s u p e r v i s o r ：p r o f y u n f e ij i a n g a b s t r a c t r e c e n t l yi n t e l l i g e n tp l a n n i n gi sav e r yh o tb r a n c hi na i s i n c et h em o s tp l a n n e r s i na na i i p u r p o s ep l a n n i n gm e t h o da r ed e s i g n e dl b rg e n e r a lp l a n n i n gp r o b l e m s t h e y d on o ts c a l et or e a l - w o r l dp r o b l e m si nt h i sp a p e rw ep r e s e n ta na p p r o a c hb a s e do n p l a n n i n gg r a p ht ou s oa c t i o ns e l e c t i o ns t r a t e g i e st oh e l pg u i d ep l a n n i n g w ea p p l y t h i sa p p r o a c ht of fp l a n n e r ，a n df o r mo u rp o l i c yi n t e g r a t e df a s tf o r w a r dp l a n n i n g s y s t e m ( p i f f ) p i f fw a st e s t e do nb o t ht h eb l o c k sw o r l da n dd e p o t sd o m a i n s t h e r e s u l t ss h o wt h a ti nb o t hd o m a i n s ，p i f fc a ni m p r o v et h ee f f i c i e n c ya n de n r i c h d o m a i n - d e p e n d e n tk n o w l e d g ee a s i l ya n d m o r ep r a c t i c a l l y k e yw o r d s ：p l a n n i n g ，a c t i o ns e l e c t i o ns t r a t e g i e s ，p i f kb l o c k sw o r l dd o m a i n ， d e p o t sd o m a i n 中山大学硕士学位论文2 0 0 5基于规划图中动作选择策略的快速向前规枷方法 第1 章引言 近年来，智能规划( a ip l a n n i n g ) 重新得到人工智能研究学者们的重视， 成为人工智能研究领域上的一个热点。在这七年来，通过a i p s ( a r t i f i c i a l i n t e l l i g e n c ep l a n n i n ga n ds c h e d u l i n gc o n f e r e n c e ) 举办的四次规划大赛 ( 1 9 9 8 ，2 0 0 0 ，2 0 0 2 ，2 0 0 4 ) ，使得世界各国规划研究学者们有一个用来测试规划 系统的交流平台( 统一的规划描述语言和标准的测试用例) ，为智能规划的理论 和应用研究起到很大的推动作用。 尽管目前智能规划的研究主要集中在与领域无关( d o m a i n i n d e p e n d e n t ) 的通用规划算法或通用规划系统上面，但是普遍认为发掘领域知识是提高规划系 统效率的关键部分，领域相关规划( d o m a i n - d e p e n d e n tp l a n n i n g ) 也是将智能 规划从理论研究推向实际应用的必经之路。著名学者、知识工程创始人 f e i g e n b a u m 教授一直希望从知识之门来打开一条通向人工智能之路。一般的 规划问题的复杂度都是p s p a c e 1 2 ，3j ，而通用规划系统都是为了解决普通的规划 问题设计，必须考虑所有的应用领域，在搜索过程中必须考虑所有的路径、谓词 的所有可能的组合。但是在应用领域中，有时实际问题中存在羞一些领域知识， 这些领域知识能提高规划系统的表达能力和求解效率。这样，通用规划系统没有 考虑在具体领域中利用具体的领域知识( d o m a i n d e p e n d e n tk n o w l e d g e ) ，因此 它们在具体应用下效率很难提高。 我们在研制解决具体问题的实用规划系统时，也遇见过同样问题，下载了 在世界规划大赛获奖的规划系统，用在应用领域上对具体问题求解的过程中发觉 它们的效率很低，只能解决很简单的实用规划问题。在总结经验时，我们觉得利 用跟领域密切相关的知识仍然是提高规划系统效率的一个主要方向，同时也是智 能规划从理论研究走向实际应用的道路”“。因此我们决定将跟领域密切相关的知 识添加到目前世界上优秀的通用规划系统上，使得它成为领域相关规划，从而能 够较好地解决实际应用的问题。但是，如果这些领域知识过强，规划系统退化为 一个按照固定的步骤来执行的程序，失去了普遍应用的意义，那它也就只能成 为一个专门的专家系统“有其实际的应用价值，但是缺乏研究的价值” 本文研究了通用规划方法结合领域知识来求解具体领域问题的方法，把领 中山人学硕i ：学位论文2 0 0 5 基十规划倒中动作选择策略的快速向前舰划方法 域知识表示为动作选择策略，介绍了一种基于规划图的动作选择策略指导规划的 方法和把它与f f 规划器结合形成的基于规划图中动作选择策略的快速向前规划 系统( p o l i c yi n t e g r a t e df a s tf o r w a r dp l a n n i n gs y s t e m ，p i f f ) ，然后对国际 智能规划大赛上的积木世界领域和仓库领域抽取领域知识，输入到p i f f 中束求 解这两个领域上的问题。实验结果表明，在这两个领域上，p 1 f f 可以方便地增 加领域知识，其效率比f f 有了很大提高，求得的规划解的质量也有所提高。 中山大学硕f ：学位论义2 0 0 5摹于规划图中动作选择策蝽的快速向前规划方法 第2 章智能规划概述 智能规划( a ip l a n n i n g ) 是近年来人工智能研究领域中的一个热门分支。 其主要思想是：对周围环境进行认识与分析，根据当前问题的初始状态和目标状 态，对若干可供选择的动作及所提供的资源限制进行推理，综合制定出实现目标 状态的动作序列，即规划( p l a r 1 ) 。而智能规划的目的就是建立一个控制算法， 使得a g e n t 能够从当前给定的某个状态通过一系列可执行动作后达到所要求的 目标状态。这个控制算法就是我们所说的规划算法。 智能规划的研究开端可追溯到二十世纪5 0 年代。1 9 5 7 年由g w e r n s t 和 a n e w e l l 等人研制的通用问题求解系统g p s ( t h eg e n e r a lp r o b l e ms o l v e r ) 被认 为是世界上第一个智能规划系统。而后在1 9 6 9 年，以著名人工智能专家n i l s s o n 为首的斯坦福研究院人工智能研究组提出了斯坦福研究院问题求解系统s t r l p 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 i l ls o l v e r ) ，这个系统的知识表示方法 和推理方法对后来的规划系统具有深刻的影响。 然而，由于当时智能规划的效率不高、应用不广，智能规划的研究陷入了一 个发展缓慢的阶段。直到二十世纪8 0 年代后期，智能规划在实际应用巾的良好 前景吸引了众多研究者。尤其是近年来，不断有关于智能规划的国际会议召丌， 有新的工作组的出现，而且人工智能规划与调度协会还每两年举行一次国际智能 规划竞赛等。这一系列的动态促进了智能规划的发展，使得智能规划在理论和实 践中都取得飞速的进步。 在理论研究方面，首先是智能规划算法的效率得到了很大的提高，三种新的 规划生成方法尤显突出：图规划法，可满足规划法，以及启发式搜索规划法。其 中各种方法的代表规划器有g r a p h p l a n ( b l u m f u r s t1 9 9 7 ) 、s a t ( k a u t z a n d s e l m a n1 9 9 2 ) 、h s p ( b o n e r ，l o e r i n c s ，6 e f f e r1 9 9 7 ) 以及f f ( h o f f m a n n2 0 0 0 ) 等。其次，规划算法对动作描述语言的处理能力也得到了很大的扩展，包括对更 具解释性语言的处理、加入简易的时间标或复杂的时态因素、以及考虑上简单或 复杂的因素等。此外，为了能更好地表述现实世界的事物，便于与实际应用数值 相联系，还有学者对规划的动作描述语言作研究，j z b a d l 、p d d l 、p d d i 。+ 等。 中山人学碳l j 学位论文2 0 0 5基十枷划幽中动作选择策略的快速向前规划方法 在实际应用当中，智能规划同样有着喜人的成绩。如：获得9 7 年世界计算 机合约桥牌冠军的b r i d g eb a r o n 系统，它就是使用了一个具有预定任务分解特点 的规划算法来生成多种策略，并为每种策略估算其启发式值；美国海岸巡逻队( u s c o a s tg u a r d ) 则使用了一个规划器s i p e - 2 来为发生海上飘油故障时规划出适当 的回应，如要使用的设备以及人员配备等；规划器s i p e 一2 还被用在 d c p e ( d i s t r i b u t e dc o n t i n u a lp a n n i n ga n de x e c u t i 0 1 3 ) 系统中，用来生成空军 作战计划；欧洲空间署( e u r o p e a ns p a c ea g e n c y ) 应用了一个规划系统进行对 宇宙飞船的装配、合成以及检测等项目的管理；n a s a 把规划系统d p l a n 运用在远 空f 、白j 通讯网络中：此外，还有基于规划思想的路径规划( r o u t ep l a n n i n g ) 以及 证明规划( p r o o fp l a n n i n g ) 等应用。 近年来，智能规划在问题的描述和问题求解两方面得到了新的突破，因此 本章接下来简要地介绍一下这两方面的主要研究成果 2 1 规划问题描述语言 经典的智能规划问题表示包括三个部分：初始状态、目标状态和操作集合 初始状态和目标状态是规划问题的起点和终点，操作集合是把一个状态变成另 一个状态的动作的集合操作主要由三部分组成：操作名称、操作的前提条件和 操作结果，有时出于对费用的考虑还要加上动作的丌销等等一个从初始状态 到目标状态的操作队列就称为一个规划非经典的智能规划问题是为了跟实际 情况更加符合，增加进去了不确定因素、时序逻辑和目标优化要求等信息 2 1 1s t r i p s 语言 s t r i p s 语言是最先描述规划问题的语言，它以“s t a n f o r d r e s e a r c h i n s t i t u t e p l a n n i n gs y s t e m ”这个学术机构的名字来命名。一个s t r i p s 规划问题由这样的 一个四元组 组成。p 表示允许的状态空间，通常是一系列的谓词 集合。i 表示初始状态集，即问题的初始条件。g 表示目标状态集，即从初始状 态开始，经过一系列的状态转变，所要到达的结束状态。o 表示可操作的动作集。 一个动作( a c t i o n ) 由前件和后件组成，前件又被称为前提条件( p r e c o n d i t i o n ) ， 只有当动作的前提条件在某个状态中全部为真时，我们称这个动作相对于这个状 态是可应用的( a p p l i c a b l e ) ：动作的后件( p o s t c o n d i t i o n ) 也被称为效果( e f f e c t ) ， 中山大学碗，t 学位论文2 0 0 5基于规划图中动作选择策略的快速向前 | ! l ! 划方法 表示动作对状念的改变，一般分为增加效果( a d de f f e c t ) 和删除效果( d e l e t e e f f e c t ) 。增加效果会对原来的状态空间增加些新的谓词，而删除效果则会删除 原有状态空间的一些谓词。一个规划问题的求解就是要找到一个动作序列，使得 求解问题可以从初始状态转换到目标状态，如下面的例子：积木块世界。 初始状态目标状态 图2 1 积木块世界( b l o c k w o r m ) 的一个例子 我们假设“抬起x ”这个动作用p i c k u p ( x ) 来表示，“放下x ”用p u t d o w n ( x ) 来表示，“把x 放在y 上面”用s t a c k ( x ，y ) 来表示，“把x 从y 上面拿起来”用 u n s t a c k ( x ，y ) 来表示，那么按次序地执行表2 一l 的动作序列，我们就可以从图2 一l 的初始状态到达图2 一l 的目标状态。 表2 1 步骤数 动作 1 u n s t a c k ( a ，c ) 2 p u t d o w n ( a ) 3 p i c k u p ( b ) 4 s t a c k ( b ，c ) 5 p i c k u p ( a ) 6 s t a c k ( a ，b ) 2 1 2p d d l ( p l a n n i n gd o m a i nd e f i n a t i o nl a n g u a g e ) 语言 p d d l ”，”是用作智能规划问题设计的标准语言。最早的版本是由m c d e r m o t t 定义，用在1 9 9 8 年规划大赛上。在2 0 0 2 年规划大赛上，p d d l 2 1 对其进行扩充， 增加时序逻辑的内容，即对动作延续时间的描述和时间流逝对动作的影响。 p d d l 2 1 包括五个层次： 第一层：相应于m c d e r m o t t 定义的p d d l l 7 中的命题和a d l 层相容，这是为 了保证p d d l 向下兼容性，没有进行新的添加和修改。 中山大学顺 一学位论业2 0 0 5 茉十规划图中动作选择策略的快速向前规划方i 土 第二层：在第一层的基础上增加了数值变量，并且能够对这些数值变量的值 进行即时的测试和更新，并对m c d e r m o t t 的提议稍微作了修订。 第三、第四层：在第二层的基础上增加了持续的动作，持续的动作定义为： 在动作开始执行后要经过一段时间爿能得到动作的效果。第三层和第四层的区别 在于：在第三层上描述的动作没有持续的影响，而在第四层上描述的动作就可以 有持续的影响。因为持续动作被限定在它影响的变量上，故第四层简化了在实际 时问领域的模型。 第五层：是第四层的一个自然扩展，增加了表示任意实际时间、复杂的度量 领域，目的是为以后研究者们设计规划问题描述语言p d d i 寺旨明方向。 2 0 0 4 年第4 届规划大赛“”语言p d d l 2 2 m 1 是在p d d l 2 1 ( 更准确地，p d d l 2 1 的前三个层次) 的基础上形成。像p d d l 2 1 一样，p d d l 2 2 被分为三个层次，分 别对应于a d l 、数值和连续规划，而且在p d d l 2 1 语言的特征之上，增加两个新 的，相对较小的构成：派生谓词( d e r i v e dp r e d i c a t e s ) 和定时的初始文字 ( t i m e di n i t i a ll i t e r a l s ) ，这是为了能更加贴切的描述现实当中的问题。 2 2 规划问题求解方法 本文讨论的是将领域知识添加到领域无关规划系统上，使得它成为领域相关 规划，从而能够较好地解决实际应用的问题。因此以下两节先分别介绍几种主要 的领域无关规划系统和领域相关规划系统。 2 2 1 领域无关规划( d o m a i n i n d e p e n d e n tp l a n n i n g ) 一、 图规划( g r a p h p l a n ) 图规划算法“3 主要由两个阶段交替进行来得到规划：图扩展阶段和解抽 耿阶段。图扩展阶段f 向扩展规划图直到获得规划存在的必要条件为止。解抽取 阶段反向搜索规划图以求出规划解。 为了下面更好地理解图规划的原理，我们先柬了解有关的基本定义。 中山大学硕l 学位论文2 0 0 5 基于规划图中动作选择策略的快速向前规划方法 1 规划图和两元互斥关系 首先，我们按照文献 的定义给出规划图模型。 【定义2 1 】规划图是个具有两类结点和三类边的有向分层图。规划图是 命题层( p r o p o s i t i o nl e v e l s ) 和动作层( a c t i o nl e v e l s ) 的交替出现。命题 层包含命题结点( 标识为一些命题) ，动作层包含动作结点( 标识为动作) 。规划 刚开始时，规划图中仅包含0 层命题结点层，也就是规划问题初始条件下的所 有命题结点集。以后每扩展一轮就依次增加两层，动作层和新命题层，因此偶数 层为命题层，奇数层为动作层。 如图2 2 所示，黑色圆点代表命题结点，空白方框代表动作结点。 0 t ：= = ：l + 、_ 。- 图2 - 2 ：规划图由命题层和动作层交替组成。连接两命题层的水 平连接虚线称为”维持动作”，表示该命题状态能维持至下一命题 接下来，我们介绍一个重要概念两元互斥关系“。互斥关系是算法判断 是否满足进入解抽取阶段的一个依据，并且解的提取也要依赖互斥关系的指导。 【定义2 2 】两元互斥关系分为两个动作结点间的互斥和两命题结点间的互 斥。我们说在同一层中的两个动作结点具有互斥关系，如果没有一个合法规划能 包含这两个动作结点；类似的，如果没有一个合法规划能使同层的两个命题结点 同时为真，则这两个命题结点是互斥的。 两动作结点间的互斥有三种类型：不一致效果( i n c o n s i s t e n te f f e c t ) 、冲 突( i n t e r f e r e n c e ) 、竞争所需( c o m p e t i n gn e e d s ) 。我们说第i 层的两个结 点是互斥的，若它们满足下列条件中的一个： 不一致效果：一个动作的后件是另一个动作后件的否命题( 见图2 3 ( a ) ) ； 冲突：一个动作删除另一个动作的前件( 见图2 3 ( b ) ) ： 竞争所需：两个动作的前件在第i - 1 层中是互斥的( 见图2 3 ( c ) ) 。 两命题结点间的互斥有两种：两命题结点互为否定，或者它们是不一致支持 中山人学硕士学位论文2 0 0 5基于规划豳中动作选择策略的快速向前规划方法 ( i n c o n s i s t e n ts u p p o r t ) 的，即所有获得该两命题的动作结点对都是互斥的 ( 见图2 3 ( d ) ) 。 n ：o n i 扫l 电州 日t e c - l s 鞫器r 0 1x 垤) o 塑 c o 硼p b 俯l g r l c o r l a i s l e r l ! n e 目d 5s t 印o ( a )( b )( c )( d ) 图23 ：同层动作结点对的互斥关系和两命题结点问的不一致支持 明确了两元互斥关系，我们就可以介绍图规划的基本原理了。图规划是在图 扩展和解抽取两个阶段交替进行的。 2 图扩展阶段 在图扩展阶段中，算法的主要过程是：从初始命题结点集开始，根据可供选 择的动作扩展一层动作层和一层命题层；然后根据两元互斥关系标出规划图中的 所有互斥结点对：检查是否满足规划存在的必要条件，若是，则进入解抽取层， 否则进行新轮的扩展。 其中，规划存在的必要条件根据文献 1 1 可归纳为： 目标的所有文字都出现在当前的命题层，并且 这些文字相互之间不存在互斥关系。 若当前考虑的命题层满足以上条件，那么算法就进入解抽耿阶段。具体实例 请参考文献 1 1 。 3 解抽取阶段 解抽取的过程为：当算法进入此阶段，当前规划图的最后一层命题层( 设为 第i 层) 也就包含了所有目标文字。此时逐个考察单个子目标文字( 设为p i 。，即 第i 层第m 个命题) ，为其在第i - i 层中选择一个能获得该文字的动作( 设为a 1 ， 即第i 一1 层第f 1 个动作) ，如果a ”1 。与已选定的动作集合a 1 。1 ( a ”1 中的元素为第 i 层命题所选定的第卜1 层动作) 中的元素存在互斥关系，则重新选定a 。一。，直 中山大学醐十学位论文2 0 0 5基于规划图中动作选择策略的快速向前规划方法 到a 1 。与a 1 1 的元素不存在互斥关系或找不到合适的a ”1 。若是前者则将a 1 。加 入a 。中，然后考虑下一个子目标；若是后者则需对前一个目标文字( p 1 ，1 ) 重 新选定动作。 当第i 层的子目标都已获得时，就将圹1 的所有元素的前提条件加入第i - 2 层目标集中，并对该层做类似上述的查找过程，直到i = o ，即已到达第0 层，规 划问题得解；否则查找失败，需要重新扩展规划图，返回图扩展阶段。具体实例 请参考文献 1 1 。 二、 可满足规划s a t ( p l a n n i n g a ss a t i s f i a b l i t y ) 起初s a t p l a n “”是h e n r yk a u t z 和b a r ts e l m a n 深入地分析了传统的基于理 论证明的规划以后提出来的完全不同于以往演绎技术的一种特殊的规划系统，它 克服了传统规划系统的异常( 每一个模型不一定对应一个有效的规划解) 情况， 使得每一个正确模型都有一个有效的规划解与其相对应。 图2 - - 4s a t 规划的体系结构 d e c o d e fl 旦鸳 s a t 规划3 的体系结构如图2 4 所示，编译器( c o m p i l e r ) 的输入是规划 问题( 包括初始状态、目标状态和动作集合) ，它首先猜测规划解的长度，产生 一个逻辑命题公式，如果逻辑命题公式是可满足的，它蕴涵着规划解是存在的； 符号表( s y m b o lt a b l e ) 记录了命题变量和规划实例之间的对应；简化器 ( s i m p l i f i e f ) 运用较快( 通常为线性时间) 的技术( 如单元子句法，纯文字消 去法等) 等柬降低c n f 公式的规模：求解器( s o l v e r ) 运用系统或统计的方法来 找到一个满足的赋值；解码器( d e c o d e r ) 用符号表把赋值转换成一个规划解。 如果求解器发现公式是不可满足的，那么编译器就会产生新的编码( 代表更长的 规划解) 。 由基 二s a t 的规划的体系结构可以看到，这种规划方法关键在于两个环节， 一个是编码方式，另一个是求解方式。有关第一个问题的研究取得了一系列的进 展，如”中综合叙述了几种普遍的编码方式，由于基于s a t 的规划算法是基于 s a t 算法来实现的，所以第二个问题其实就是选择好的s 盯算法，而可满足性 中山太学颀一i ：学位论文2 0 0 5皋十燃划圈中动作选择策略的快速向前规划方法 ( s a t ) 问题是人工智能研究领域中的一个基本理论问题，最近几年束，每年都 有新的s a t 算法问世，人们设计各种各样的技术来提高解决s a t 问题的效率。 三、启发式搜索规划h s p 基于启发式搜索规划法的结构大致由三大部分组成：主体算法、启发式值 估算、以及剪枝技术。其中主体算法大多是最佳优先法、爬山法及其变体等一一些 搜索算法。剪枝技术则有很多类型，如：失败记忆、有用动作集、删除过早出现 的目标等。 在规划问题中，通常利用放宽式问题p 来获得原问题p 的启发式信息， h s p ”。就是将操作的删除边忽略，对于每个状态s ，得到在放宽了的问题p 的启 发函数( s ) 就可以作为原有问题p 的启发函数h + ( s ) 的下限，这样纠( s ) 就可以 作为合适的启发函数作用在原有问题p 上。 实质上，初始状态和操作可以理解为一个定义了的节点有向图，对于每个操 作印都有一条由其前提条件节点指向正效果节点的边，这样从初始状态到达节 点p 的开销就可以计算。从状态s 到节点p 的开销g ( s ) 递归定义为： ，、0 f p s 器 卜1 m i n 卿f 1 + g 册呱硼】。胁p 肿船 o ( p ) 表示添加效果为p 的操作集，就是p a a a ( o p ) 。矾( p r e c ( o p ) ) 是从状 态s 到操作o p 前提条件节点的计算。 b o n e r 对上面的盛( p ) 提出更为简单的向前计算过程，首先初始化图上各个 节点：当p s ，令g ，( p ) 为0 ：否则令既( p ) = 0 ( 3 。这样，每一次操作o p 作用在 状态s 上，每个添加效果节点p a d d ( o p ) 添加到s ，& ( p ) 更新为： g 。( p ) = m i n g 。( p ) ，l 十g 。( p r e c ( o p ) ) 这个计算g 。( p ) 的过程一直到譬。( p ) 不再改变为止，明显这个过程在节点数目 一定的情况下，时问复杂度是多项式的。 这样，节点集c 的估算g 。( c ) 可以由在这节点集c 里面每个节点估算来得到。 那么，同理h ( s 1 定义为： d u i h ( s ) = g 。( g ) g 。( c ) 可以定义为三种估算：节点集c 中所有节点估算值的和、节点集c 中 中山人学硕l 学位论业2 0 0 5皋千规划幽中动作选择策略的快速向前规划方法 节点最小估算、节点集c 中节点最大估算。在l i s p “”中，b o n e t 主要采用两种估 算： a ) g ，( c ) 为节点集中所有节点估算值的和，称作添加启发函数 。： 或( c ) = g ，( ，) ，“ b ) g ，( c ) 为节点集c 中节点最大估算，称作最大启发函数h 一： g ，( c ) = m a x g ，( ，) 启发式搜索规划法的另一个代表f f 将在4 2 1 节中介绍。 2 2 2 领域相关规划( d o m a i n d e p e n d e n tp l a n n i n g ) 一、基于逐步细化的分层规划系统s h o p 2 以s h o p 2 “为代表的层次规划方法思想是：首先勾画出一个完整但又比较 粗略的规划解，然后逐步细化、逐步明确，直到足以具体完成整个规划的每一步 操作，层次规划方法实际上把不同性质的问题放在不同层次上加以考虑 s h o p 2 “3 是一个分层任务网络规划系统跟在一般的规划需要组目标不 一样，取而代之是s h o p 2 需要一个半序的任务序列去执行，为了解决一些领域 上的规划问题，s h o p 2 需要一些基于领域知识的方法，这些方法来将一个任务分 解为一组半序的子任务为了得到合法的规划，s t t o p 2 将问题变形：它递归地将 任务分解为子任务，直到它到达能被规划操作直接执行的原始的任务 跟大多数分层任务网络规划系统不一样，s i t o p 2 是从初始状态向前规划：给 出几个任务需要分解，s l t o p 2 按他们同一执行顺序来得到规划在规划过程中的 每个点上，s h o p 2 已经知道在这个点之前所执行的操作，故s h o p 2 了解当前状态 这种技术使得s h o p 2 的预处理估计机制相当强大，s t o p 2 预处理方法和操作可以 包含逻辑推理、复杂数值计算和外接程序 s h o p 2 比s h o p 成功的地方在于它的预处理过程，s h o p 需要他的任务是全序 结构，然而s t l o p 2 只需要它的任务是半序结构，因为s h o p 2 可以插入不同的子任 务，一些领域知识在s h o p 2 比s t l o p 更容易表示 二、t l p l a n n e r 中山大学硕士学位论史2 0 0 5 幕于规划图中动作选择策略的快速向前规划方法 f b a c c h u s 和f k a b a n z a 在文 2 0 提出了表示和利用领域控制知识的一种 方法：用时序逻辑表示领域依赖搜索控制知识，然后用来有效地控制一个向前链 规划器。这个方法有几个优点，包括：搜索控制知识的说明性语义；高度模块化 ( 新的搜索控制知识可以被加入而不影响以前的控制知识) ；这种知识与规划算 法细节之间的独立性。t l p l a n 系统实现了这个方法，并在广泛的规划领域中表 现出它的卓越的性能。 具体地，文 2 0 采用阶线性时序逻辑( l t l ，f i r s t o r d e rl i n e a rt e m p o r a l l o g i c ) 来表达搜索控制用到的时序知识，它是在标准一阶逻辑( l ， s t a n d a r d f i r s t o r d e rl o g i c ) 上的扩展，这样扩展得到的时序逻辑语言l t 。l t 以状态为 可能世界，以状态的演变次序关系为可能世界问的可到达关系。在文 2 0 中，讨 论的时序逻辑是确定的，即状态演变次序为一线序，所以简称线性时序逻辑为时 序逻辑，它只考虑“现在状态”和“将来状态”，不考虑“过去状态”。 时序知识容易添加到一个规划问题中，它的表示独立于动作、初始状态和目 标状态的表示。在t l p l a n n e r ”0 1 中，时序知识使用是有效的，采用下面四种时序 算子： 1 、 口称为a l w a y s 算子，口f 表示“永远有f ”。 2 、称为e v e n t u a ll y 算子，f 表示“有时有f ”。 3 、o 称为n e x t 算子，o f 表示“在下状态( 时刻) 有f ”。 4 、u 称为u n t i l 算子，f ，u 疋表示“一直有f 。，直到有厶”。 模型化表示l t 可以为m = ，m 是一系列“时刻”，通常采用这一 系列“时刻”m 来作为时间线，每个“时刻”w 是一个对一阶逻辑扩展后的时序 逻辑状态。 为了形式化描述，给出下面的几个定义：令w ，为在时间线m 上的第i 个时刻， v 是一个赋值函数，根据领域d 来将l t 中的变量赋值，f ，和f 。是l t 中的表达式。 定义如下： 1 、如果f 是个原予表达式，那么 0 【工，当且仅当， 旺z 。 2 、 qv x _ ，当且仅当， q 一，对于所有d d ， v ( x d ) 是个赋值函数x = d 。 3 、 c c y ，当且仅当，可i ， 和v k ， i k j ，有 o 【一，即f 。为真直到厶为真。 4 、 o f , ，当且仅当， do f , ，即f ，在下一个状态 ( 时刻) 为真。 5 、 伐嘶，当且仅当，可i ， o rz ，即f 最终会为 真。 中山大学硕i ：学位论文2 0 0 5 基千规划图中动作选择策略的快速向前规划方法 6 、 仪口i ，当且仅当，w i ， z ，即f 一永远为 真。 三、t a l p l a n t a l p i a n “是一个向莳链规划器，它使用领域依赖知识来控制状态空间中的 搜索，这些状念空问通过动作调用产生。领域依赖控制知识、背景知识、规划和 目标全部使用时态逻辑t a l 中的公式表示。t a l 已经被独立地开发成为描述a g e n t 并进行推理的一种形式方法。在t a l p i a n 和t l p l a n 两个系统中，搜索控制公式以 类似的方式被用来修剪搜索空削，不同之处在于，t l p l a n 币u 用公式前进，而 t a l p i a n 的高效版本利用公式评价同一些优化技术结合。这些技术允许把部分搜 索控制信息从搜索控制公式移到操作符的前提。这显著地提高性能，因为在规划 器甚至尝试调用一个操作符之前控制规则冲突可以被检测，这些规则在操作调用 之前被评估，因此像前提控制信息一样有效率。最后，除了它不错的性能外， t a l p l a n n e r 还有的优点是：它已经被扩展来处理并发动作，有时间依赖效果的动 作和资源的配置“。 四、h f c p j s i e r r a s a n t i b d f i e z 描述了基于领域知识的规划的一种特别方法，并据 此用p r o l o g 实现了一个启发式向前链规划器( h f c p ) “，该方法基于动作选择策 略这种领域知识的说明性形式化。在文 2 3 中，动作选择策略( s t r a t e g yr e j a c t i o n # e j e c t i o n ) 是一组一致的动作选择规则。一个动作选择规则( a c t j o n s e l e c t i o nr u j e ) 是一个隐合式，它的前项是一个情景演算公式，而后项可以 取以下形式之一：g o o d 囟，b a d 囟或b e t t e r 向向。这些谓词的直 观解释是：在状态s 执行动作a 是好的( g e e d 、坏的( b a 0 9 或比执行动作b 好( b e t t e r ) 。h f c p 的动作选择机制运作如下：( 1 ) 如果对当前状态有一个g o o d 动作，那么它搜索的状态只限于应用这个动作到当前状态产生的状态能生成的状 态子树。( 2 ) 如果对当前状态没有g o o d 动作，那么它搜索应用非b a d 动作到当 前状态能生成的状态子树，并使用由谓词b e t t e r 建立的偏序关系来指导它的搜 索过程。 五、d c i p s 基于模型检测的智能规划是当今通用的智能规划研究的热点，它的求解效 率比较高但是，目前的基于模型检测的智能规划系统没考虑到利用领域知识 中山大学硕上学位论文2 0 0 5皋十规划圉中动作选择策略的快速向前规划方法 来提高描述能力和求解效率为此，d c i p $ ”“研究了增加领域约束的基于模型检 测的智能规划方法，并据此建立了基于模型检测的领域约束规划系统d c i p s ， 它主要考虑了领域知识在规划中的应用，将领域知识表示为领域约束添加到规 划系统中根据”规划= 动作+ 状态”，d c i p s 将领域约束分为三种：对象约束、 过程约束和时序约束，采用对象约束来表达状态中对象之间的关系：采用过程 约束来表达动作之问的关系：采用时序约束表达动作跟状态中对象之间的关系 通过在2 0 0 2 年智能规划大赛a i p s 0 2 上关于交通运输领域的三个例予测试，实验 结果表明，利用领域约束的d c i p s 可以方便地增加领域知识，更加实用化，其 效率也有了相应的提高 2 3 智能规划的应用 目前智能规划应用在自动系统中，使得自动化系统灵活性、健壮性和适应性 得到提高主要应用研究领域有：机器人、智能企业和商业软件 在i j c a i o l 的智能规划讨论会上，会议主题是“资源约束规划”目标是为 实际应用上的规划研究学者提供一个交流的平台，会议上的规划系统都是在计 算机实际应用系统中得到广泛使用的规划系统，例如：美国宇航局的a s p e n 规 划系统、马里兰大学的c i r c a 、美国宇航局的e u r o p a 、华盛顿大学的l p s a t 规划 系统和爱丁堡大学的o - p l a n 规划系统等等这次会议主要讨论内容有：混合规 划系统、整合规划系统、赘源约束上的推理技术、时序规划、智能规划和调度、 优化目标规划和有关规划的模型、问题领域和实验结果 2 3 1 在机器人中应用的规划系统 规划在机器人中的应用主要有：环境的模型化描述、机器人能力的模型化描 述、目标的模型化描述和实时的输入响应机器入规划研究跟其他规划研究领域 不一样，主要在于机器人处于有噪音的各类部分的环境模型中，它通过感应器 和交流信道得到的信息都存在嗓音，这样机器人就需要将感应和执行的整合来 进行宜接规划 目前主要研究领域包括：1 、路径规划：指在机器人从一个开始的位置如何 走到目标位置的控制机制，并且要满足动态的约束2 、感知规划：主要是有关 如何采集外部和内部信息的规划，例如：辨别物体，确定机器人位置，对环境 的观察3 、任务规划：跟传统的规划问题相似，不过更加注重时间和资源的分 中山大学颧1 ：学位论文2 0 0 5基于规划圈中动作选择策略的快速向前规划方法 配，在动态的环境、不确定的或部分已知的状态知识的条件下进行规划4 、规 划交流：多个机器人之问和人与机器人之间如何进行信息交换，包括询问信息 和反馈信息两大部分 a s p e n 机器入规划在实际应用中，取得最好效果的是美国宇航局的a s p e n ( a u t o m a t e ds c h e d u li n ga n dp l a n n i n ge n v i r o n m e n t ) 。1 规划系统a s p e n 获得 了1 9 9 9 年美国宇航局的软件比赛优秀奖，并且广泛用在进行外太空任务的宇航 器上，包括c i t i z e ne x p l o r e r 、m a r s 0 1 和d s t 等宇航器，目前对外也有其商 业版本出售 在宇航器中，智能规划的应用主要是将较高层次的科学研究和工程操作指 令转化为较低层次的宇航器执行指令a s p e n 结合了宇航器操作约束、飞行规范、 宇航器硬件模型、科学实验目标和操作过程来自动生成较低层次的宇航器操作序 列通过自动生成宇航器操作序列和结合了相关的领域知识，a p s e n 使得宇航任 务可以由一个小分队来控制，这样，降低了开销 2 3 2 在智能工厂中应用的规划系统 智能规划在智能化工厂中的应用。”是指从生产设计到生成产品，监测生产 的系列过程，它不止包括单个企业，还可以处理多个企业之间的关系，例如： 供应链和虚拟企业主要采用资源约束的方法进行求解“，目前主要研究领域 包括： l 、生产流程规划：在一个功能化的工厂中，将一个生产要求转变为一组详 细的操作指令许多基于知识工程的软件在这方面取得了较好的效果，先将现 实生产流程转化为知识库中信息，然后再根据相应的生产要求来转化 2 、生产安排规划和调度：将生产安排用来迎合客户的需求，按时交货，即 我们通常说的e r p 作业调度 2 3 3 在商业中应用的规划系统 在商业中，智能规划的应用更加广泛对原有的经典规划作了更大的扩充 目标状态可以不是明确的，只是满足某个条件目前主要研究领域有： 一、网络信息集成 网络信息集成”1 的过程是根据领域本体的内容，从互联网上采集信息，并 中山夫学硕l 学位论文2 0 0 5麸于规划陶中动作选择策略的快速向前规划方法 将信息集成到领域本体中，网络信息集成的实质意义是为网络信息提供一种重 新组织和理解的机制目前研究主要集中在查询规划中查询规划可以定义为： 把对信息对象框架的查询转化成只对信息源作访问的操作序列在规划的执行 过程中，有时需要将信息源返回的结果台并起来分析，以作出下一步的规划 所以，信息的合并是查询规划中的一个重要环节我们把信息的合并定义为： 合并两个残缺信息对象的框架，即将两个属性值对集结合成一个属性值对集 合并的依据是信息源之间的相关链接目前，查询规划已经扩展到生物信息查 询上，较好的有在i b m 公司的d i s c o v e r y l i n k 系统上的应用o 二、运输规划 在目前物流应用问题中，根据动态的不断改变的运输要求而对一队交通工 具进行实时规划( 行程调整和计划安排) ”这些交通工具可以是：在一个房子 早边的移动机器人、在一个城市道路上的的士，甚至是经典的电梯问题然而在 这个问题中，存在着很多的制约条件来使得运输规划变得复杂，例如时间限制 ( t i m ew * n d o w ) 、最终期限、运输能力、行程时问、资源优化，更多的是象交通 状况、天气状况、车辆中