（计算机软件与理论专业论文）智能规划中目标谓词排序算法的研究.pdf

智能规划中目标谓词排序算法的研究摘要 智能规划中目标谓词排序算法的研究 专业：计算机软件与理论 硕士生：黄英持 指导教师：吴向军副教授 摘要 智能规划是人工智能的一个重要分支，它的研究最早可以追溯到六十年代。 虽然人们很早就开始了对它的研究，但由于规划本身是一个非常复杂的问题，所 以研究的进展一直很缓慢，甚至在八十年代陷入了低谷。直到九十年代，一些新 的问题描述方法以及求解策略的提出才重新激发起人们对智能规划的研究热情。 其中比较有影响力的求解策略包括图规划、启发式搜索、将规划问题转换为约束 可满足问题和模型检测等4 种规划求解策略。这些方法在小规模问题求解上相对 于传统方法都具有相当大的优势。但对于稍大规模的问题，同样会陷入求解效率 低下的困境。为了提高效率研究人员提出按照子目标的实现顺序将较大规划问题 分解成若干个较小规模的子问题，并分别求解各个子问题的策略。这种策略的核 心是子目标的排序算法。在2 0 0 0 年k o e h l e r 等人首次严格定义了子目标之间的 顺序关系，并提出了基于规划图和基于启发式的两种目标排序的算法，其中第二 种算法被运用到包括i p p 、f f 以及s g p i a n 等规划器上，这些规划器都在智能规 划大赛中取得过优异的成绩。 本文在深入研究基于启发式的目标谓词排序算法的基础上，利用模式化方法 以及领域知识对该算法进行改造。原算法在目标排序的过程中需要对同一谓词的 不同实例进行多次判断，而本文提出的基于模式的目标谓词排序算法则在谓词模 式的层次上进行谓词的排序，所以能有效减少相似的重复比较，提高了排序的效 率。实验数据表明，我们的算法相对于原算法具有更大的优势。 关键词：智能规划、目标排序、领域知识、模式化 智能规划中目标谓词排序算法的研究 a b s t r a c t r e s e a r c ho nt h es o r t i n ga l g o r i t h mf o rg o a lp r e d i c a t i o n s i na ip l a n n i n g m a j o r ：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 ：h u a n gy i n g c h i s u p e r v i s o r ：w ux i a n g j u n a b s t r a c t t h ea ip l a n n i n gi sa ni m p o r t a n tb r a n c ho fa r t i f i c i a li n t e l l i g e n c e t h er e s e a r c ho n i tc a nb et r a c e db a c kt ot h es i x t i e s b e c a u s et h ea ip l a n n i n gi t s e l fi sav e r yc o m p l i c a t e p r o b l e m , a l t h o u g ht h es t u d yo ni tw a sb e g i n n i n gv e r ye a r l y , t h ep r o g r e s so f t h es t u d y h a sb e e ns l o wa n de v e ns t o p p e di nt h ee i g h t i e s u n t i lt h en i n e t i e ss o m en e wm e t h o d f o rd e s c r i b i n ga n ds o l v i n gp r o b l e mw e r ep r o p o s e d t h e s em e t h o d si n s p i r e dp e o p l e s e n t h u s i a s mo na ip l a n n i n ga g a i n t h ep l a n n i n g - g r a p h ，h e u r i s t i cs e a r c h ，s a ta n d m o d e lc h e c k i n ga r et h ef o u rm o s ti n f l u e n t i a lm e t h o d s t h e s ef o u rm e t h o d sc a nd o b e t t e ri ns m a l lp r o b l e mt h a no t h e rt r a d i t i o n a lm e t h o d s b u tt h e ya r ei n e f f i c i e n ti n s o l v i n gl a r g ep r o b l e m i no r d e rt os o l v el a r g ep r o b l e mm o r ee f f i c i e n t ，s o m e r e s e a r c h e r sp r o p o s ean e wm e t h o d i nt h i sn e wm e t h o dp l a n n e rp a r t i t i o n sal a r g e p l a n n i n gp r o b l e mi n t os o m es u bp r o b l e m s ，e a c hw i t ho w ns u bg o a l s t h ec o r eo ft h i s m e t h o di st h es o r t i n ga l g o r i t h m i n2 0 0 0 ，k o e h l e rg a v eas t r i c td e f i n i t i o no ft h eo r d e r r e l a t i o nb e t w e e ng o a l sf o rt h ef i r s tt i m e ，a n dg a v et w om e t h o d st oc o m p u t et h eg o a l o r d e r i n g s ，t h ef i r s tm e t h o di sb a s e do np l a n n i n gg r a p ha n dt h eo t h e ri sb a s e do nf a s t h e u r i s t i c t h el a t t e rm e t h o dw a su s e di np l a n n e r si n c l u d i n gi p p f fa n ds g p i a n t h e s ee n t i r ep l a n n e r sa c h i e v e dg o o dr e s u l t si ni n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n t h i st h e s i sf i r s ts t u d i e st h ef a s th e u r i s t i cm e t h o d ，a n dt h e nc o m b i n e st h em o d e l m e t h o da n dd o m a i nk n o w l e d g ei n t of a s th e u r i s t i cm e t h o dt og e tan e wm e t h o dc a l l e d g o a lo r d e r i n g sc o m p u t i n ga l g o r i t h mb a s e d o nm o d e l t h ef a s th e u r i s t i cm e t h o dc h e c k s p r e d i c a t i o ni ni n s t a n t i a t i o nl e v e l ，s oap r e d i c a t i o nm a yb ec h e c k e df o rm a n yt i m e s o u rm e t h o dc h e c k sp r e d i c a t i o ni nm o d e ll e v e l ，s oi td o e s n th a v et oc h e c kp r e d i c a t i o n f o rm a n yt i m e s ，w h i c hc a ni m p r o v et h ee f f i c i e n c y t h ee x p e r i m e n t ss h o wt h a to u r a l g o r i t h mc o m p a r e dw i t ht h eo r i g i n a la l g o r i t h mh a sg r e a t e ra d v a n t a g e k e yw o r d s ：a ip l a n n i n g ，g o a lo r d e r i n g ，d o m a i nk n o w l e d g e ，m o d e l 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：蓣荚掎 日期：q 年f 月叫日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名： 导师虢欤勿屏 日期：钆少年j - 月2 ，日 智能规划中目标谓词排序算法的研究引言 己i 言 j -口 规戈1 ( p l a n n i n g ) 是关于动作的推理，它是一种抽象的、清晰的深思熟虑过程， 这个过程通过预测动作的期望效果，选择和组织一组动作，其目的是尽可能好地 实现一些预先给定的目标。在人工智能的研究范围内，智能规划阻ip l a n n i n g ) 实 际上是从计算上研究这个深思熟虑过程的一个领域【l 】。由于在现代社会里，规划 问题无处不在，因此智能规划的应用非常广泛，从车间的生产调度到军队的后期 支援计划再到宇航船使用的规划调度系统都可以找到智能规划使用的影子。虽然 智能规划的应用范围广泛，但是智能规划问题的求解本身是一个非常复杂的难 题。为了降低求解的难度，研究人员会对规划进行许多理想化的假设，这就构成 了经典的智能规划。 在经典的智能规划里面，问题的状态被描述成谓词的集合，而动作则被表示 成3 个部分，分别是名字、前提和效果。其中动作的前提和效果都是谓词的集合。 如果动作的前提在某个状态中得到满足，那么就可以执行这个动作。在执行动作 后就可以用动作的效果去修改当前状态并产生新的状态。解决经典的规划问题就 是要求出可以从初始状态到目标状态的动作序列。根据常识知道，在规划的过程 中如果知道目标的完成顺序，就能加快规划的速度。同样，在智能规划里如果知 道了目标集合中各个谓词在规划过程中的先后顺序，就可以提高生成规划解的速 度。为了对目标谓词进行排序，研究人员已经做了许多有意义的工作。 1 9 9 4 年k n o b l o c k 等人针对p r o d i g y 系统【2 】提出用来提取抽象公式间的顺序 关系的a l p i n e 方法【3 】。该方法基于谓词公式之间的层次关系来进行排序，所以 能对不同的谓词进行排序，但对于同一谓词的不同实例则无法判定它们的顺序关 系。2 0 0 0 年k o e h l e r 等人第一次严格给出了目标间顺序关系的定义，并提出了两 种重要的排序算法1 4 。这两种算法与a l p i n e 方法有明显的区别：它们都是对实 例化的谓词进行排序，而不是对谓词公式进行排序。所以算法的复杂度与实例化 的谓词个数有关。 本文在k o e h l e r 等人的工作的基础上，对以下内容进行了创新性的研究： 结合其他目标谓词排序算法的特点，本文提出种改进的算法：基于模式的 智能规划中目标谓词排序算法的研究 引言 目标谓词排序算法。该算法在谓词模式以及动作模式的层次上使用启发式方法结 合领域知识求出谓词模式实现后可执行的动作模式，并利用这些动作模式求出实 例化的谓词之间的顺序关系。算法不但克服了a l p i n e 方法不能求同一谓词不同 实例之间的顺序的缺陷，还克服了基于启发式的目标谓词排序算法随问题规模增 长而激增的缺陷。 本文先对智能规划进行简单的介绍，分析目前智能规划的研究现状和发展情 况，然后深入研究两种重要的目标谓词排序算法。在对目标谓词排序算法深入研 究的基础上，提出基于模式的目标谓词排序算法。作者将按以下思路组织本文： 引言，交待本文的研究背景和作者的主要贡献，这是论文研究工作的出发点； 第l 章，介绍智能规划的历史，研究现状以及规划问题的描述语言；第2 章，介 绍图规划求解方法，为研究目标谓词排序算法提供必要的预备知识；第3 章，介 绍两种重要的顺序提取算法以及议程驱动的规划方法，这是论文的基础；第4 章， 重点阐述基于模式的目标谓词排序算法以及相关的理论，这是论文研究的核心成 果。最后，对论文工作进行扼要的总结，并提出进一步的研究思想。 2 智能规划中目标谓词排序算法的研究第1 章智能规划概述 第1 章智能规划概述 智能规划是人工智能的一个重要分支，目前几乎每本人工智能的书籍都对智 能规划进行介绍。在智能规划研究过程中，一个规划问题需要包含三类基本信息： 初始状态、目标状态以及规划动作。使用什么形式来表达这些信息就成为智能规 划需要解决的第一个问题。本章首先将回顾智能规划的研究历程以及研究现状， 然后详细介绍智能规划的描述语言，其中重点介绍被视为规划领域和规划问题的 标准描述语言一p d d l 。 1 1 智能规划研究的历史 智能规划是人工智能中研究较早的一个领域。早期的研究方法主要为定理证 明和逻辑推理。它的研究最早可以追溯到1 9 5 6 年n e w e l l 、s h a w 和s i m o n 设计 的逻辑理论家( l o g i ct h e o r i s t s ) 程序和通用问题求解器( g p s ) 【5 1 。这两个系统在人 工智能领域中具有非常重要的地位，但它们还不是真正面对规划问题研制的智能 规划系统。1 9 6 9 年g r e e n 提出适用定理证明的方法来进行规划求解，并结合此 理论实现了问题解答系统q a 3 t 6 1 。由于它是第一个面向现实问题提出的规划系 统，所以被大多数的智能规划研究人员认为是第一个规划系统。但情景演算方法 存在两大问题：推理效率问题和框架公理问题。推理的效率会因推理过程陷入组 合爆炸而大大降低，而推理过程中需要的框架公理也会因规划问题复杂度的增加 而增多。由于在效率上不能达到研究人员的要求，这种方法不久就被人们舍弃了。 1 9 7 1 年f i k e s 和n i l s s o n 设计了问题求解系统s t r i p s ( s t a n f o r dr e s e a r c h i n s t i t u t ep r o b l e ms o l v e r ) 0 7 1 。它是智能规划历史上最具影响力的规划系统之一。他 们的突出贡献是引入了s t r i p s 操作符的概念，使得原来神秘的规划问题求解变 得清晰明朗起来。在s t r i p s 系统中，用原子谓词集合描述状态，把动作描述为 前提条件、增加表和删除表等三大部分。若在某个状态中，动作的前提条件得到 满足，那么就可以执行该动作，并用动作的增加表和删除表来修改当前状态。此 后到1 9 7 7 年，先后出现了h a c k e r 、w a r p l a n 、i n t e r p l a n 、a b s t r i p s 、 智能规划中目标谓词排序算法的研究第1 章智能规划概述 n o a h 、n o n l 烈等规划系统。这些规划器的出现大大推动了研究人员的研究热 情，研究人员普遍认为规划问题可以用定理证明的方法解决。直到1 9 8 7 年 c h a p m a n 详细分析了利用定理证明的方法来求解规划问题中的关键问题：模型与 规划解的对应关系问题【8 】。该问题的提出让人们意识到简单地利用定理证明的方 法来求解规划问题是很艰难的。因此这以后到九十年代，在没有发现新的求解方 法之前，智能规划的研究陷入了低谷。这期间仅有s i p e 、a b t w e a k 和p r o d i g y 等少数几个智能规划系统出现。 九十年代智能规划的研究呈现出新的发展，研究者提出许多新的求解方法， 这些方法使得规划系统的效率得到明显提高。智能规划逐步重新成为人工智能研 究的热点之一。 1 9 9 2 年k a u t z 等把规划问题求解转化为可满足( s a t ) 问题1 1 ，改变以往使 用定理证明求解的方法，利用约束可满足问题的算法来求解规划问题，有效地解 决了部分规划问题。基于此方法的规划器b l a c k b o x 规划系统在第一届的智能规 划比赛中表现突出，证明了s a t 方法具有一定的优越性。不过此方法也存在很 大的缺陷，哪怕对一些小规模的规划问题，编码空间也可能达到几兆甚至几百兆 空间。编码问题很大程度上制约了该方法的发展，但该方法为解决规划问题开辟 出一条新的途径。 1 9 9 5 年，a b l u m 等人提出了图规划方法以及相关理论，并根据这些理论设 计出规划系统g r a p h p l a n 1 2 1 。图规划方法的提出引起了整个智能规划界的关注， 受到许多学者的强烈推荐。这种方法将规划问题转化为能用路径发现求解的规划 图结构。用这种方式解决规划问题，能使一些动作并行执行，大大提高了求解效 率。后来许多规划系统都借鉴了图规划系统的方法，其中比较出名的有b l a c k b o x 、 i p p 、f f 0 3 】、l p g 、s g p l a n 等规划器。这些规划器在一定程度上都采用了图规划 的某些技巧，并对图规划做了相应的扩充。 1 9 9 8 年由b o n e t 和g e f f n e r 提出使用启发式搜索策略【1 4 】来指导空间的搜索。 实践证明采用启发式的规划器比没有采用启发式的规划器表现出了更强的求解 能力。经典的规划器如f f 、h s p 、l g p 、g r t 、a l t a l t 和s a p a 都采用了启发 式搜索的思想。启发式搜索的基本思想是：人为给定一个评估函数，对每个搜索 状态进行计算，得到每个状态的启发值，从而决定哪个状态较好。启发式搜索的 4 智能规划中目标谓词排序算法的研究第1 章智能规划概述 重要因素包括搜索的方向、搜索算法和启发信息。其中搜索的方向可以是：正向、 反向和双向三种。著名的规划器f f 就是采用前向搜索。而搜索算法主要是爬山 法、贪心算法和a 木算法。启发式搜索最关键的在于如何确定启发信息。规划器 要解答各种领域的问题，不同领域的启发信息不同，要实现较高的求解效率，规 划器就需要有能根据规划领域自动提取启发信息的能力。 2 0 0 0 年s e d e l k a m p 等提出了基于模型检测的规划策略，并基于该策略实现 了规划器m i p s ( m o d e lc h e c k i n gi n t e g r a t e dp l a n n i n gs y s t e m ) 。系统中适用二元 判定图b d d ( b i n a r yd e c i s i o nd i a g r a m s ) 来表示规划问题的状态，采用静态分析技 术对编码进行优化，从而缩小了命题和实例化动作之间的编码空间。m i p s 是首 次将模型检测的技术用到规划问题求解中。在智能规划大赛中m i p s 规划器是唯 一在全自动规划组能对所有比赛用例产生出规划解的规划器，并夺得了表现优秀 奖。当前模型检测的规划方法被认为是智能规划领域的研究热点之一。 综上所述，规划问题求解从最初的定理证明方法发展到s t r i p s 方法，之后 又出现了图规划、启发式搜索、模型检测等规划求解方法。这些规划求解方法使 规划系统在求解效率和质量上都有了大幅度的提高。规划器可以解决的问题规模 逐步在加大，从原来的小规模问题向现实问题转变。 1 2 智能规划研究的现状 近年来，智能规划研究在规划领域的描述语言和问题求解方法两个方面都有 了长足的进步。在规划领域的描述方面，在九十年代后期出现了p d d l ( p l a n n i n g d o m a i nd e s c r i p t i o nl a n g u a g e ) t 1 6 - 1 9 】描述方法。此后p d d l 逐步取代其他描述方法 被广泛使用在规划领域的研究当中，后来成为智能规划研究中问题描述的标准语 言。最早的版本是由m c d e r m o t t 定义，用在1 9 9 8 年规划大赛上。目前最新版本 是p d d l 3 0 。在前面的版本中，p d d l 2 1 对原有s t r i p s 描述的一个较大突破， 不仅涵盖了s t r i p s 和a d l 语言的描述能力，还增加了数值、持续性动作等描 述能力，而p d d l 2 2 和3 0 是在2 1 的框架上作进一步的扩展，增加了派生谓词 和状态轨迹约束等的描述能力。新的领域特征被描述出来使所描述的规划领域更 接近于具体的应用领域。在求解策略上，一些新的高效规划求解方法使规划系统 的求解效率和规划质量有了大幅度的改善，这些新的求解方法扩充了规划器对数 智能规划中目标谓词排序算法的研究 第l 章智能规划概述 字化推理、并行计算、与用户交互、解决资源约束的能力，使得设计出具有实用 价值的规划系统变成现实。 鉴于智能规划研究的理论意义和实用价值，国外成立了一些专门研究智能规 划的项目以及相关会议【2 0 1 。其中比较著名的有：美国国防部高级研究计划局 d a r p a ( t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 和r o m e 实验室的 d a r p a r o m ep l a n n i n gl n i t i a t i v e ( a r p i ) 计划。该计划针对军事中空军规划问题进 行研究，目前总投资已经超过7 千万美元。另外美国国家航空和宇宙航行局也投 入大量人力、物力开展关于智能规划的研究，并把相关的研究成果运用到宇宙飞 船等航空器上。在欧洲主要有p l a n e t 计划，该计划开始于1 9 9 8 年1 0 月1 日， 有e s p r i t 基金资助，参与的国家达1 4 个之多。同时英国的国家航空和宇宙航行 局也赞助了e u m e t s a t 项目。在学术会议方面，主要有两年一届的国际智能规 划与调度研讨会a i p s ( a r t i f i c i a li 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 g ) 、欧洲智能规 划研讨会e c p ( e u r o p e a nc o n f e r e n c eo np l a n n i n g ) 、美国国家航空和宇宙航空局举 办的n a s a p s 以及i j c a i ( i n t e m a t i o a n lj l i n tc o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ) 。 智能规划的另一个重要学术交流活动是国际智能规划大赛，该项活动每两年 举行一次，至今已经成功举办了六届【2 1 。2 6 】。该项规划活动给研究人员提供了一个 测试规划算法的平台，促进了研究人员之间的交流，大大推动了智能规划的发展。 目前参与过规划比赛的规划器已经达到了数十种之多。 研究者除了努力完善智能规划的理论外，还积极推动智能规划在实际问题上 的应用。随着规划系统求解效率的提高以及规划领域的实用化，规划系统已经逐 步可以运用到求解实际问题上。在解决实际问题上，“与领域有关 的规划器比 “与领域无关 的规划器有更好的表现。这主要是因为前者能更好地利用领域中 特定的知识。一些著名的应用型规划系统有：d a r t 、a s p e n 、r a x p s 、h s t s 和m a c h i n e 等。其中d a r t 是美国国防部计划局主持开发的用于后勤支援的系 统。a s p e n ( a u t o m a t e ds c h e d u l i n ga n dp l a n n i n ge n v i r o n m e n t ) 是美国宇航局开发 的，用于执行外太空任务的调度和规划系统。r a x p s 同样也是用于太空宇航船 的规划和调度控制系统。h s t s 是为哈勃太空望远镜提供调度计划的规划系统。 m a c h i n e 是一个基于操作自动化的非线性规划器，它能为制造系统产生出一系列 的控制序列，这些序列可以方便转换为真实的生产程序。馀了以上在军事、航空 6 智能规划中目标谓词排序算法的研究第1 章智能规划概述 领域的运用外，研究人员还探索将智能规划的算法运用到解决供电故障恢复问 题、管道输送问题、钢厂调度问题和港e l 调度等问题上【2 7 1 。 1 3 规划问题的描述语言 智能规划主要是研究如何解决规划问题，因此首先要解决的一个问题就是知 识表达的问题，即需要有一种精确严密的形式语言，以方便我们对实际的规划问 题进行有效建模【2 8 】。在一个规划问题里面，通常需要知道三类基本信息：初始状 态、目标状态和规划动作，不同的表示方法都是力求能准确且简单地描述这些信 息。下面分别介绍在智能规划发展过程中有影响的描述方法。 1 3 1 情景演算表示方法 早期的智能规划主要使用情景演算来描述规划问题。情景演算是一种表示动 态世界变化的二价逻辑语言。在情景演算中，规划问题的状态用情景表示，所谓 情景就是一阶逻辑项的集合。而状态的变化都是由于执行了某一动作而产生的结 果。变化的结果还是情景。例如将某个动作a 作用于情景s ，那么可以用d o ( 口，曲 表示动作a 执行后的情景。 由于动作的前提得到满足才能执行，所以要求在情景演算中能表示动作的前 提是否满足。在情景演算中，动作的前提条件被表示为前提条件公理，并引入谓 词符号p o s s ，用表达式p o s s ( a ，s ) 表示在情景j 下，动作a 是可以执行的。例如 p o s s ( p i c k u p ( r , x ) 譬) 3 ( v z ：- - 4 a o l d i n g ( r , z , s ) ) o n - t a b l e ( x , s ) 表示，意思是在情景s 下，动 作p i c k u p ( r , x ) 可执行则必须满足在情景s 下机器人不拿其他任何物体，并且被拿 起的物体x 必须在桌面上。动作的前提得到满足就可以执行动作，而动作的效果 在情景演算中同样是通过公理的形式来表示，称为效果公理。 通过将动作的前提和效果用公理化的形式来描述，规划问题就被转化为在给 定初始情景和目标情景的情况下，根据动作的前提和效果公理化框架，找到合适 的动作序列，使得状态能从初始情景演算为目标情景。因此，在情景演算的描述 方法下，规划过程就变成了个定理证明的过程。 虽然情景演算描述方法具有很强的描述能力，但将规划问题转化为定理证明 不见得就是一种很好的策略，历史证明这种方法具有很大的局限性，因此研究人 7 智能规划中目标谓词排序算法的研究第1 章智能规划概述 员很快就放弃了这种描述方法，并创造出新的更方便的描述方法。 1 3 2s t r i p s 描述方法 为了解决情景演算描述方法中的框架公理问题，1 9 7 1 年f i k e s 和n i l s s o n 在 问题求解系统s t r i 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 ms o l v e r ) 7 】中使用了新的 描述方法，后来的研究人员称这种方法为s t r i p s 描述方法。 在s t r i p s 描述方法里面，用逻辑原子集合表示状态。初始状态和目标状态 都被表示成合取公式的形式，这和情景演算方法类似。不同的是动作描述为前提 条件、增加表和删除表等三个部分，一个动作o 可以表示成以下形式： p r e ( o ) - - - a d da d d ( o ) d e ld e z ( o ) 其中p r e ( o ) 是动作的前提表，a d d ( o ) 是增加表，d e t ( o ) 是删除表。它们都是逻 辑原子集合。在某个状态s 下，假如动作0 的前提条件得到满足，即p r e ( o ) c s ， 就可以执行动作。动作的效果分为增加效果和删除效果，增加效果会在原来的状 态基础下增加所有在增加表的事实命题，而删除效果则根据动作的删除表将原来 的状态下的事实命题删除。用r e s u l t ( s ，d ) 表示动作执行后的状态，那么有 r e s u l t ( s ，d ) ：书u 域d ) x c l e l ( o ) 与情景演算方法相比，s t r i p s 方法的不同之处在于：首先后者不需要对动 作的前提条件和动作的效果进行公理化描述，而是取代为用增加表和删除表的形 式来描述；其次s t r i p s 方法可以避免在情景演算中的大量框架公理，从而提高 求解的效率；最后在s t r i p s 方法下，规划问题本质上被视为一个状态空间中搜 索目标状态的搜索问题。 1 3 3a d l 语言 随着智能规划研究的深入，求解问题的复杂度也在增加，出现了s t r i p s 描 述语言很难描述的一些规划问题。s t r i p s 描述方法要求动作的前提是命题的合 取，动作的效果也是命题的合取，效果必须是确定的且具体的。对于那些动作效 果不确定的规划问题，s t r i p s 就很难描述了。 为了解决以上问题，1 9 8 9 年p e d n a u l t 提出了动作描述语言a d l t 2 9 1 。a d l 是 在s t r i p s 的基础上进行了扩充，除了具有s t r i p s 的描述能力外，还能表达动 8 智能规划中目标谓词排序算法的研究第1 章智能规划概述 作的条件效果和量化效果。条件效果指的是动作的效果与上下文有关，不同情况 下动作会产生不同的效果，般用w h e n 子句来表示。w h e n 子句由两个部分组 成：前提和结论。当w h e n 子句的前提得到满足，就会用子句的结论部分来修改 当前状态。而量化效果则允许在动作的效果描述中使用全称量词和存在量词。 1 3 4p d d l 描述方法 p d d l 是规划领域描述语言( p l a n n i n gd o m a i nd e s c r i p t i o nl a n g u a g e ) 的简称， 是现代智能规划问题描述的标准语言。最早的版本是p d d l i 2 ，是由m c d e r m o t t 定义【例，并用在1 9 9 8 年规划大赛上，目前最新的版本是p d d l 3 o r l6 1 。p d d l 是 在吸取了s t r i p s 和a d l 的基础上发展起来的，因此p d d l 的表达能力覆盖了 s t i u p s 和a d l 两者。 在p d d l 里，一个规划问题由领域定义和问题描述两部分组成，并且这两个 部分通常以文件的形式独立存在。由于将定义和问题分开，所以一个领域定义可 用于多个规划问题。在领域定义部分主要是动作的描述，动作都是抽象定义的， 可以称其为动作模式( a c t i o ns c h e m a ) 。通常包括三个部分：参数列表、前提和效 果。参数列表包含在动作模式里面用到的变量。这些变量可以有类型说明也可以 没有，这要根据领域定义里面对表达能力层次的要求。前提部分和效果部分用谓 词、项和逻辑谓词组成的逻辑公式来表示。如果领域定义里有更高的表达能力说 明，那么还可以包含量词、函数和时态等。 p d d l 包含了领域定义对表达能力要求的语法描述，可以通过r e q u i r e m e n t s 标签来表达特定问题对于领域描述能力的要求。规划器可以根据标签快速判定是 否具有处理该问题的能力。 由于p d d l 描述语言本身不是我们研究的主要内容，所以下面仅对p d d l 中最重要的部分进行介绍。有关p d d l 的详细内容可以参考文献 1 6 1 9 。p d d l 语法用e b n f 表示，这里先简单介绍e b n f 的些定义。 ( 1 ) 每个规则的定义形式是： ：- 表达式； ( 2 ) 单独使用“ ，表示在此使用规则； ( 3 ) 方括号“口”表示其中的内容可选； ( 4 ) 当方括号上方有r e q u i r e m e n t s 标签时，表示在领域定义里声明了该标签 9 智能规划中目标谓词排序算法的研究第1 章智能规划概述 时，方括号里面的内容才是可选的，否则不被包含在领域定义里： ( 5 ) 星号“木”表示“零或以上；加号“+ ”表示“一个或以上”； ( 6 ) 在规则定义时可以带参数，用空格分开。例o l ：x 木，其中x 是参 数，可以替换成其他文字或者规则。 1 3 4 1 规划领域的定义 p d d l 定义的规划领域主要部分的e b n f 范式描述如下： ：= ( d e f i n e ( d o m a i n ) 【 】 ：t y p m g 【 】 【 】 【 】 ) 下面分别对各个描述子句进行说明： ( 1 ) 规划领域的名称说明子旬 ( d e f i n e ( d o m a i n ) 本子句的主要作用是声明规划领域的名称，其中n a m e 是字符串，表示下文 将要定义的领域。 ( 2 ) 规划领域的需求说明子句 【 】：- ( ：r e q u i r e m e n t s ) 本子句用来说明当前的规划领域对于p d d l 描述能力的层次要求。如果在领 域定义时没有定义本子句，则默认为“：s t r i p s 需求标签。随着p d d l 的发展， 可供使用的需求标签不断增加，下表是p d d l 3 o 【1 6 】中可供使用的标签。 表1 1 规划领域的需求符及其含义 规划领域的需求符含义 ：s t r i p s 基本的s t r i p s 类型，包含增加以及删除效果 ：t y p i n g 在定义变量时允许类型 1 0 智能规划中目标谓词排序算法的研究 第1 章智能规划概述 ：n e g a t i v e p r e c o n d i t i o n s 在定义目标时允许n o t ：d i s j u n c t i v e p r e c o n d i t i o n 在定义目标时允许o r ：e q u a l i t y 支持“= ”谓词作为内嵌谓词 ：e x i s t e n t i a l p r e c o n d i t i o n 在定义目标时允许存在量词 ：u n i v e r s a l p r e c o n d i t i o n s 在定义目标时允许全称量词 ：q u a n t i f i e d - p r e c o n d i t i o n s：e x i s t e n t i a l p r e c o n d i t i o n + ：u n i v e r s a l p r e c o n d i t i o n s ：c o n d i t i o n a l - e f f e c t s 允许w h e n 作为动作效果 ：f l u e n t s 允许定义函数及在动作效果中使用赋值和算术操作 ：s t r i p s + ：t y p i n g + ：n e g a t i v e p r e c o n d i t i o n s + ：a d l ：d i s j u n c t i v e - p r e c o n d i t i o n + ：e q u a l i t y + ：q u a n t i f i e d p r e c o n d i t i o n s + ：c o n d i t i o n a l e f f e c t s ：d u r a t i v e a c t i o n s允许定义持续性动作 ：d e r i v e d p r e d i c a t e s 允许用公式来定义谓词的真值 ：t i m e d i n i t i a l 1 i t e r a l s 允许在初始状态中指定在某个时刻点文字为真值 ：p r e f e r e n c e s 允许在动作前提和目标中使用喜好 ：c o n s t r a i n t s 允许在领域定义和问题定义中使用限制域 ( 3 ) 类型说明子句 ：= ( ：t y p e s ) ：= x 幸i ：t y p m g x + 一 ：= l ( e i t h e r + ) 假如在需求子句中定义t ：t y p i n g 标签，就可以在类型说明子句中定义领域中 用到的类型。类型之间允许有继承关系，用连接符“表示这种关系，其中位 于右边的是父类型。如果没有类型说明，则默认的类型是o b i e c t 。 ( 4 ) 常量说明子句 ：= ( ：c o n s t a n