（计算机软件与理论专业论文）基于strips描述的规划宏动作的构造研究与应用.pdf

中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 基于s t r i p s 描述的规划宏动作 的构造研究与应用 计算机软件与理论 硕士生：王立坤 指导老师：姜云飞教授 摘要 本文提出了一种通过静态分析提取宏动作的方法。静态分析的对象是基动作 之间的关系。首先经过分析问题域，特定的选取些常量对动作实例化，得到一 些基动作。然后分析这些基动作得到矛盾谓词对，在此基础上将基动作之间的关 系进行分类，并根据基动作的之间的关系生成模式图。最终根据模式图提取出具 有实际应用价值的宏动作。 关键词：基动作，宏动作，矛盾谓词，模式图 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 r e s e a r c ha n d a p p l i c a t i o no ft h em a c r o o p e r a t o r b a s e do ns t r i p sd e s c r i p t i o n 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 ：w a n gl i k u n s u p e r v i s o r ：p r o f j i a n gy u n f e i a b s t r a c t i nt h i st h e s i s ，w ep r o p o s ean e wm e t h o df o rg e n e r a t i n gm a c r o o p e r a t o r st h r o u g ht h e s t a t i ca n a l y s i s t h eo b j e c t so ft h es t a t i ca n a l y s i sf o c u so nt h er e l m i o n so ft h eg r o u n d a c t i o n s f i r s t ，b ya n a l y z i n gt h ed o m a i n ，ac e r t a i nn u m b e ro fc o n s t a n t sa r es e l e c t e dt o p r o d u c eg r o u n da c t i o n s s e c o n d ，t h r o u g ha n a l y z i n gt h eg r o u n da c t i o n s ，c o n t r a d i c t o r y p r e d i c a t e sf o rt h ed o m a i na t ea t t a i n e da n dt h er e l a t i o n sb e t w e e nt h eg r o u n da c t i o n sa l e c l a s s i f i e d a c c o r d i n g l y t h e nt h ep a t t e r nm a p s a r e p r o d u c e d a tl a s t ，v a l u a b l e m a c r o 。o p e r a t o r sb a s e do nt h em a p sa r eg e n e r a t e d k e y w o r d s ：g r o u n da c t i o n s ，m a c r o o p e r a t o r s ，c o n t r a d i c t o r yp r e d i c a t e s ，p a t t e r nm a p s i i 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 1 1 研究的背景 第1 章引言 智能规划1 1j 是人工智能的一个很重要的领域，从6 0 年代开始就不断地发展 演变，很多相关领域的专家编写了各种各样的规划器，它们基于不同的理论，有 自己独特的一面，同时又有相同的相似的方法。另外一方面，为了进一步提高规 划器的效率。专家们继续做着各种尝试。每个专家都有其独特的见解，有些专家 提出的一些改进规划器的新方法可能是普遍适用的，但是如果要加入到每一种规 划器中，将会有许多琐碎的事情要处理。所以把各种规划器共性的部分，统一标 准，独立成块可以减少这些不必要的麻烦。统一标准，独立成块是一个很庞大的 项目，它需要各方面的科研工作者共同合作才能完成。本文的出发点就是把其中 的一小部分进行改进，做为各种规划器可以共同使用的部分。 利用抽象来提高规划器效率的方法，已经被很多科研人员应用到“自己的” 规划器中，而抽象技术很多时候并不依赖于特定的规划器。作为实验，本文通过 静态的分析问题域描述，得到具有应用价值的宏动作，然后通过合适的方法把得 到的信息传递给各种各样的规划器。如果哪个专家想通过静态分析问题域来提高 规划器求解效率，并不用特意修改这个规划器，它只需将输入事先经过统块 ( e n g i n e ) 的处理就可以了。如果哪个专家提出了一种普遍适用的提高规划器效率 的静态分析的预处理方法，它只需对统一块迸行改进而不需要大幅度的改变现有 的各种规划器。 1 2 研究的出发点 本文主要讨论的是在静态分析的基础上提取宏动作，描述了生成宏动作的一 种新方法。它是与具体问题无关的。现在有很多规划器通过各种各样的算法来生 成宏动作，而且也提高了规划器的效率，各种算法既有相同的地方也有不同之处。 特别是把智能规划与机器学习相结合的方法对智能规划的发展起到了很大的推 进作用，各方面的专家、学者在这方面的研究中也取得了不少成就。而本文是从 中山火学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 静态分析问题域的方法出发的，更像是一个预处理，与动态的学习有着各种各样 的区别。本文试图要寻找的是一种广泛适用的提取宏动作的方法。它只通过静态 的分析问题域的描述来寻找宏动作，从而其产生宏动作的方法不依赖于任何一种 规划器。本文的出发点是要把各种规划器的共性，独立成块。当然这是我们为之 努力的一个遥远的目标。在实际的运行过程中，本文提出的静态分析的方法将对 某类问题域通过静态分析，找出适当的宏动作，再通过合适的途径把这些信息传 递给各种规划器，从而提高规划器的效率。 将能够独立于规划器的某些宏动作的提取方法独立成块后，以后可以专注于 研究各种各样的通过静态分析来抽象的方法，而较少考虑所使用的是哪种规划 器。这样可以避免很多重复的工作，为以后研究或者实验带来便利。 1 3 方法的基本思想 本文提出了将规划器的预处理部分独立成块的设想，以及实现这种设想的一 些大概方法。并着重考虑从静态分析方面寻找共性，独立成块。意大利学者 g a r m a n o 2 引通过静态分析提取宏动作的方法在某些领域能够提高规划器的效 率，它是通过分析问题域中的动作描述，建立结点由动作组成，边能反映动作之 间的关系的一个图，根据图的性质来找到可以组合的宏动作。 本文与之不同的是分析的对象是基动作之间的关系。经过分析问题域后，特 定的选取一些变量对动作实例化，得到一些基动作。通过分析这些基动作之间的 关系，进而发现所有可能出现的基动作之间的关系，得出一般规律，提取出能够 提高规划器效率的宏动作。本文提出了一种新的分析基动作之间关系的方法，称 为模式提取法，它力图从少量的且能够反映普遍规律的基动作的分析出发，得到 能够实际提高规划器效率的宏动作。 1 4 解决问题的流程 输入一个问题域的p d d l i o i 描述文件后，我们试图编写的e n g i n e ，首先编译 并根据下文所述的方法来提取宏动作，然后经过宏动作组合以及后续处理，生成 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 新的p d d l 语言描述的问题域。如果需要可能是一个p d d l 扩展语言1 5 l 描述的问 题域。然后这个输出的文件与需要解决的问题再一起输入到任意一个接受这种语 言的规划器中，由规划器求解，得到结果。 我们要做的e n g i n e 在问题解决过程所处的位置，见下图。 图1 1e n g i n e 所处的位置 e n g i n e 内部的大概流程图： 图1 2e n g i n e 内部的流程图 1 5 本文的组织结构 本文将在第二章介绍矛盾谓词的概念；第三章以第二章为基础提出了矛盾序 列、完全独立的动作对、以及强可顺序执行序列的概念并介绍了它们的一些性质； 第四章在前两章的基础上介绍了组合两个基动作的方法，以及互补动作对的概 念；第五章与第六章通过分析基动作之间的关系，找出并生成宏动作的描述，第 七章是对本文的总结与展望。 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 第2 章矛盾谓词 2 1 矛盾谓词的提出 本文通过静态分析提取宏动作的方法，并不是通过直接分析动作的描述来获 得信息。本文所描述的方法是通过分析有限的基动作，提取它们之间的规律，并 用其来反映任意可能出现的基动作之间的规律。以木块世界为例，我们试图用有 限几个木块将动作实例化，从而产生关于这几个木块的基动作，进而通过分析它 们之间的关系来得到一个普遍适用的，并不是仅仅局限于目前几个木块的一般规 律，晟终得到我们想寻找的宏动作。目前算法主要针对只有a n d ，n o t 连接符且 动作前件中不含n o t 的问题域。首先引入的是矛盾谓词的概念。在引入这个概 念之前，先来看一个例子：u n s t a c k ( a ，b 1 与s t a c k ( b ，c ) 是木块世界中【1 l 】的两个基动 作。这两个动作的具体描述如下： a c t i o nu n s t a c k ( ab ) ：p r e c o n d i t i o n ( a n d ( o nab ) ( c l e a ra ) ( a r m e mp t y ) ) ：e f f e c t ( a n d ( h o l d i n ga ) ( c l e a rb ) ( n o t ( o nab ) ) ( n o t ( c l e a ra ) ) ( n o t ( a r m e m p t y ) ) ) a c t i o ns t a c k ( bc ) ：p r e c o n d i t i o n ( a n d ( c l e a rc ) ( h o l d i n gb ) ) ：e f f e c t ( a n d ( a r m e m p t y ) ( c l e a rb ) ( o nbc ) ( n o t ( c l e a rc j ) ( n o t ( h o l d i n gb ) ) ) 这两个动作在任何时候部是不能顺序出现在一个p l a n 中的。可是算法怎么 通过静态分析的方法来判断u n s t a c k ( a , b ) 后一定不能执行s t a c k ( b ，c ) 呢? 通过人 为的分析这两个动作的意义我们知道u n s t a c k ( a ，b ) 的后件中有一个谓词c l e a rb ， s t a c k ( b ，c ) 的前件中有一个谓词h o l d i n gb ，这两个谓词是不可能同时成立的，所 以任何情况下都不能执行完u n s t a c k ( a , b ) 后接着执行s t a c k ( b ，c ) 。可是电脑是不 能通过语义做出这样的判断的，我们必须通过特定的算法去发现它。 我们称c l e a rb 与h o l d i n gb 互为矛盾谓词。下面将介绍一种算法来发现这些 矛盾谓词。下面的算法经过适当的修改，就可以通过只分析动作的描述不用分析 4 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 基动作来得到矛盾谓词，不过我们还是选择了通过分析基动作来找出它们。以基 动作s t a c k ( bc ) 为例，算法试图通过静态分析来发现一些矛盾谓词对。 我们首先来分析s t a c k ( bc ) 的前件和后件。在s t a c k ( bc ) 的后件( 添加表) 中出 现了新的谓词( 前件中未出现过的) c l e a rb 。我们认为每个谓词的出现都是为了描 述某个变量的某个属性。那么b 木块的某个属性在执行完s t a c k ( bc ) 后一定发生 了变化从而导致出现了新的属性c l e a rb 。而在前件中出现的关于b 的谓词，在 执行完动作后又被否定的( 出现在删除表中) 只有h o l d i n gb 。于是得到下面的结 论：c l e a rb 与h o l d i n gb 是对b 的某个参数的描述，这个参数在执行了s t a c k ( bc ) 后发生了变化，当参数的取值不同的时候分别表现为c l e a rb ，h o l d i n gb 或者其 它的某个谓词。从而得到结论：c l e a rb 与h o l d i n gb 是一对矛盾谓词。 按照人们描述自然世界的习惯，当我们描述一个动作的时候，如果描述某一 变量的谓词在动作执行完后被否定了( 郎出现在删除表中) ，那么对应于现实世界 就是这个变量的某一属性发生了变化，并且我们用另一个关于这个变量的谓词去 描述这个变量的新出现的属性。于是得到这样的带些主观的结论： 对于任意一个基动作： n ) 如果前件中的一个描述某个变量的谓词在后件中被否定了，那么后件中 必然会有一个新的描述这个变量的谓词出现，并且它们之间是矛盾的。 ( 2 ) 如果后件中新出现了个描述某个变量的谓词，那么前件中必然有一个 描述这个变量的谓词且又在后件中被否定了，并且它们之间是矛盾的。 下面的例子稍微复杂了些，不过我们通过上面的两条结论我们还是能得到 一些矛盾谓词。 我们现在转而观察u n s t a c k ( a , b ) ，它的后件中第一个出现的新的谓词是 h o l d i n ga 。由( 2 ) 知道其前件中必然有一个谓词是关于a 的并且在后件中被否定 了。( 必然有一个，也可能有多个的情况) 。观察u n s t a c k ( a , b ) 的后件后发现这样 的谓词有两个：o i l a b 与c l e a r a 。在此需要说明的是0 1 0 a b 不一定是因为a 的 属性的改变而被否定的，它也许是因为b 的属性的改变而被否定的，也许是两 者兼有。我们用下面的图来描述刚才得到的结果： h o l d i n g a _ + o n a b ，c l e a r a 这个图表示h o l d i n ga 必然与花括弧中至少个谓词矛盾。可是我们现在还 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 不能确定任何矛盾谓词对。转而分析花括弧中的每一个谓词，利用结论( 1 ) 来试 图找到矛盾谓词对。首先分析花括弧中的o n a b ，在后件中新出现的旧词h o l d i n g a 与c l e a r b 可能与它矛盾。很遗憾h o l d i n g a 与o n a b 到底是否矛盾，通过这 样的分析是得不到结论的。不过分析花括号中的第二个谓词c l e a ra 的时候，发 现后件中只有h o l d i n g a 与a 有关，从而我们确定了h o l d i n g a 与c l e a r a 的矛盾。 2 2 矛盾谓词的寻找方法 上述情况看起来是顺利成章的，下面的寻找矛盾谓词的方法却让人觉得有些 冒险。为了尽可能准确地找出更多的矛盾谓词对，我们决定把寻找矛盾谓词的方 法，修改成如下： 分析一个基动作的后件，对于一个新出现的谓词p ，把那些在前件中出现的 且在后件中被否定( 即删除表中) 的谓词集合设为m ，集合m 中任意一谓词q ， 只要o 与p 有着相同的某个变量我们就认为p , q 是相互矛盾的谓词对。 也许我们这个决定过于激进了，不过实验得出的结论却比我们想象的要理想 的多，经实验发现相当多的问题域( 或许应该称它们为某一类问题域) 并没有因为 这个看起来很激进的决定，错误的发现本来不矛盾的谓词。读者可以用这种方法 分析一些问题域来验证这个算法。 这个方法看起来有点眉目了，别着急，还有两个特殊的情况需要算法做例外 处理。 例外处理( 一) 分析u n s t a c k ( a , b ) 的时候，出现了一个谓词a l t l l e m p t y ，而且它在后件中又 被否定了，通过我们上述的方法我们是不能找到任何与其矛盾的谓词的。其实这 样的谓词在某个特定的基动作中，它的变量被隐含了。就是说a h n - e m p t y 之所以 被否定还是与某个木块有关的。按照前面提出的结论，u n s t a c k ( a , b ) 的后件中必 有一个新出现的谓词的与其矛盾。而u n s t a c k ( a ，b ) 中新出现的谓词都有了自己的 “归宿”，没有哪个谓词没找到自己的“来源”的，那么我们这种情况下判断不 了a r m e m p t y 与哪个谓词是矛盾的。不过别着急，我们来看看木块世界中的另一 个基动作。 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 a c t i o np i c k u p ( a ) ：p r e c o n d i t i o n ( a n d ( c l e a ra ) ( o n t a b l ea ) ( a r m e m p t y ) ) ：e f f e c t ( a n d ( h o l d i n ga ) ( n o t ( c l e a ra ) ) ( n o t ( o n t a b l ea ) ) ( n o t ( ar m - e m p t y ) ) ) p i c k u p ( a ) 的后件中新出现的谓词只有h o l d i n ga ，它是所有被否定的谓词的 唯一的“归宿”，那么我们可以做出结论了：a r m - e m p t y 与h o l d i n g a 矛盾。其实 像a 1 一e m p t y 这样的谓词它的改变一定是因为某个木块，只不过这在谓词中没有 被体现出来。a r m e m p t y 的实际含义不正是：不存在一个木块它被机械手抓了起 来。与a l t n e m p t y 有关的确实是某一木块，不过算法不能轻易的发现出来，除非 有像p i c k u p ( a ) 这样的动作，给我们新的提示。 对于一个无参的谓词如果通过分析发现它可能的来源或者归宿只有一个，那 么就确立它与这个谓词是矛盾的。 a r m e m p t y 还隐含了一个变量就是机械手r ，同样的h o l d i n ga 也隐藏了这个 变量r ，本来如果两个谓词都不隐藏这个变量，因为两个谓词都含有变量r ，我 们通过最一般的方法直接就能发现它们的矛盾，何需我们再加这种特例呢。另外 我们如果仔细区分；其实木块a 的隐藏与机械手r 的隐藏还是不一样的。术块 a 的隐藏其实是一种存在谓词，我们可以在这个动作的其他谓词中找到a ，而r 的隐藏是因为机械手只有一个，只要涉及到a r m e m p t y 和h o l d i n g 都是指这个机 械手。在多机械手的情况下，随着动作定义方法的改变，将不再出现特例的情况。 如果哪个读者用我们这个方法加例外处理来分析木块世界，还会发现：h o l d i n g a ， h o l d i n gb 这样的谓词组合我们没有发现它们。对于类似这样的谓词名字相同， 只不过变量不同的谓词我们能不能发现它们之间的矛盾呢? 我们由此引入了例 外处理二。 例# t - 处理( - - 、 其实像h o l d i n g a ，h o l d i n gb 这种谓词名相同，但变量不同的谓词有的时候是 应该作为矛盾谓词来处理的，有的时候不能。在介绍例外处理( 二) 的时候，不得 不事先告诉大家h o l d i n ga ，h o l d i n gb 之间的矛盾仍然不能通过例外处理( 二) 来 发现它们。不过不用担心，如果它们真的是矛盾的，我们还可以通过h o l d i n g ( a ) 与a i m e m p t y 的矛盾，h o l d i n gb 与a r i n - e m p t y 的矛盾来间接发现h o l d i n ga 与 中山大学硕l l 学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 h o l d i n gb 之问的矛盾。不过这种处理是在试图判断强可顺序执行序列的时候做 的，在后面的章节我们将详细描述我们的做法以及这样做的原因。 有些远离话题了，还是以一个例子为开始，来介绍我们的例外处理( 二) 。首 先看g r i p p e r 问题域中出现的一个动作m o v e ，下面是它的某个基动作： a c t i o nm o v e ( r o o m a ，r o o m b ) ：p r e c o n d i t i o n ( a t r o b b yr o o m a ) ：e f f e c t ( a n d ( n o t ( a t r o b b yr o o m a ) ) ( a t - r o b b yr o o m b ) ) 先来观察它的后件：a t r o b b yr o o m a 与a t r o b b yr o o m b 没有一个共同的 变量把它们联系在起，可是我们会发现被否定的谓词只有一个：a t r o b b y r o o m a ，新出现的谓词只有一个：a t r o b b yr o o m b 。于是我们把它们看成矛盾 的谓词也是顺利成章的。它们之间如果不矛盾的，它们的“来源”或者“归宿” 还能是什么呢? 其实它们同样本不用当特殊情况来处理，a t r o b b y 把变量r o b b y 隐含掉了，不通过这样的方法是发现不了a t r o b b yr o o m a 与a t r o b b yr o o m b 之间的矛盾的。幸好，有m o v e 这样的动作给我们提供了更多的信息，让我们去 发现了这对矛盾谓词。下面的动作因为没有隐含卡车这个变量，我们直接用最常 规的方法就能找到它们之间的矛盾，因为它们之间有一个相同的变量t 。 a c t i o nd r i v e ：p r e c o n d i t i o n ( a n d ( a ttp 1 ) ( d r i v i n gdt ) ) ：e f f e c t ( a n d ( n o t ( a ttp 1 ) ) ( a ttp 2 ) ) ) 如果一个谓词在经过常规处理后，没有找到其“来源”或者“归宿”，并且 通过分析发现它的可能的来源或者归宿只有一个，那么就确立它与这个谓词是矛 盾的。 经过我们最常规的提取矛盾谓词的方法，加上特殊处理，使我们尽量找出所 有的矛盾谓词对，尽管它还不是完美的，还需要在判断两个基动作之间关系的时 候，因为类似h o l d i n g a 与h o l d i n g b 这样的矛盾谓词没有找出，而做一些特殊的 修补，可是我们用上述方法提取出的矛盾谓词，直到文章结束都扮演着不可或缺 的角色。我们将在接下来的一章详细介绍矛盾谓词的应用。 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 2 3 木块世界中矛盾谓词的寻找 在本章的最后以木块世界为例，通过静态分析提取矛盾谓词。前面的算法经 过简单的转化直接应用到了动作描述的分析上。算法通过逐步分析每一个动作， 从而寻找出矛盾谓词对。算法分析的对象虽然不再是基动作，但依据却是相同的。 ( ：a c t i o np i c k u p ：p a r a m e t e r s ( ? o h ) ：p r e c o n d i t i o n ( a n d ( c l e a r ? o b ) ( o n t a b l e ? o b ) ( a r m e m p t y ) ) ：e f f e c t ( a n d ( h o l d i n g ? o b ) ( n o t ( c l e a r ? o b ) ) ( n o t ( o n - t a b l e ? o b ) ) ( n o t ( a r m e m p t y ) ) ) ) 扫描p i c k u p 的后件，新出现的谓词有( h o l d i n g ? o b ) ，其含变量o b 。而p i c k u p 的删除表中的谓词涉及变量o b 的谓词有：( c l e a r ? o b ) ，( o n t a b l e ? o b ) 于是确定了 矛盾谓词对：( h o l d i n g ? o b ) 与( c l e a r ? o b ) ( h o l d i n g ? o b ) 与( o n - t a b l e ? o b ) 。 然后进行例外处理，p i c k u p 的后件的删除表中还有一个谓词( a r m - e m p t y ) ，因 为p i c k u p 后件中新出现的谓词只有( h o l d i n g ? o b ) ，根据例外处理能够发现矛盾谓 词对：( h o l d i n g ? o b ) - 与( a r m e m p t y ) 。于是经过以上分析得到如下三组矛盾谓词。 ( h o l d i n g ? o b ) - ( c l e a r ? o b ) ( h o l d i n g ? o b ) + _ ( o n t a b l e ? o b ) ( h o l d i n g ? o b ) + _ ( a r m - e mp t y ) ( ：a c t i o np u t d o w n ：p a r a m e t e r s ( ? o b ) ：p r e c o n d i t i o n ( h o l d i n g ? o b ) ：e f f e c t ( a n d ( c l e a r ? o b ) ( a r m - e m p t y ) ( o n t a b l e ? o b ) ( n o t ( h o l d i n g ? o b ) ) ) ) 扫描p u t d o w n 的后件新出现的谓词有( c l e a r ? o b ) ，( a r m e m p t y ) ， ( o n t a b l e ? o b ) 。 首先分析( c l e a r ? o b ) ，其涉及的变量只有o b ，而删除表中与o b 相关的谓词有 ( h o l d i n g ? o b ) 。于是确定了矛盾谓词对：( c l e a r ? o b ) 与( h o l d i n g ? o b ) 。 后件中新出现第二个的谓词是无参谓词( a r m e m p t y ) ，经过分析发现其可能 的“来源”只能是( h o l d i n g ? o b ) 于是确定了矛盾谓词对：( a r m - e m p t y ) 与 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 ( h o l d i n g9 0 b ) 。 后件中新出现的第三个谓词是( o n t a b l e o b ) ，其涉及的变量只有o b ，而删除 表中与o b 相关的谓词有( h o l d i n g ? o h ) 。于是确定了矛盾谓词对：( o n t a b l e ? o b ) 与( h o l d i n g ? o b ) 。于是经过以上分析得到如下三组矛盾谓词。 ( c l e a r ? o h ) 斗( h o l d i n g ? o b ) ( a r m - e m p t y ) + _ ( h o l d i n g ? o b ) ( o n t a b l e ? o h ) + _ ( h o l d i n g ? o b ) ( ：a c t i o ns t a c k ：p a r a m e t e r s ( ? o b ? u n d e r o b ) ：p r e c o n d i t i o n ( a n d ( c l e a r ? u n d e r o b ) ( h o l d i n g ? o b ) ) ：e f f e c t ( a n d ( a r m e m p t y ) ( c l e a r ? o b ) ( o n ? o b ? u n d e r o b ) ( n o t ( c l e a r ? u n d e r o b ) ) ( n o t ( h o l d i n g ? o b ) ) ) ) s t a c k 的后件中新出现的谓词有( ar m e m p t y ) ，( c l e ar ? o b ) ，( o n ? o b ? u n d e r o b ) 。 首先分析无参谓词( a r m e m p t y ) ，经过分析不能确定其“来源”。 后件中新出现的第二个谓词是( c l e a r ? o b ) ，其涉及变量是o b ，删除表中涉及 到o b 的谓词有( h o l d i n g ? o b ) ，因此确定矛盾谓词对( c l e a r ? o b ) 与( h o l d i n g ? o b ) 。 后件中新出现的第三个谓词是( o n ? o b ? u n d e r o b ) ，其涉及到的变量是 o b ，u n d e r o b 。删除表中与这个两变量有关的谓词有( c l e a r ? u n d e r o b ) ，( h o l d i n g ? o b ) ， 因此确定矛盾谓词对有：( o n ? o b ? u n d e r o b ) 与( c l e a r ? u n d e r o b ) ，( o r ? o b ? u n d e r o b ) 与( h o l d i n g ? o b ) 。于是经过以上分析得到如下三组矛盾谓词。 ( c l e a r ? o b ) + _ ( h o l d i n g ? o b ) ( o n ? o b ? u n d e r o b ) + _ ( c l e a r ? u n d e r o b ) ( o n ? o b ? u n d e r o b ) + + ( h o l d i n g ? o b ) ( ：a c t i o nu n s t a c k ：p a r a m e t e r s ( ? o b ? u n d e r o b ) ：p r e c o n d i t i o n ( a n d ( o n ? o b ? u n d e r o b ) ( c l e a r ? o b ) ( ar m e m p t y ) ) ：e f f e c t ( a n d ( h o l d i n g ? o b ) ( c l e a r ? u n d e r o b ) ( n o t ( o n ? o b ? u n d e r o b ) ) ( n o t ( c l e a r ? o b ) ) ( n o t ( a r m - e m p t y ) ) ) ) j 1 0 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 u n s t a c k 后件中新出现的谓词有( h o l d i n g ? o b ) ，( c l e a r ? u n d er o b ) 。 首先分析( h o l d i n g ? o b ，其涉及的变量只有。b 。在删除表中与o b 相关的谓 词有( o n ? o b ? u n d e r o b ) ，( c l e a r ? o b ) 。因此确定了矛盾对：( h o l d i n g ? o b ) 与 ( o n ? o b ? u n d e r o b ) ( h o l d i n g ? o b ) 与( c l e a r ? o b ) 。 分析 c t e a r ? u n d e r o b ) ，其涉及的变量只有u n d e r o b ，在删除表中与u n d e r o b 相关的谓词有( o n ? o b ? u n d e r o b ) ，因此确定矛盾谓词对：( c l e a r ? u n d e r o b ) 与 ( o n ? o b ? u n d e r o b ) 。 例外分析无参谓词( a r m - e m p t y ) ，经过分析不能确定与之矛盾的谓词。于是 经过以上分析得到如下三组矛盾谓词。 ( h o l d i n g ? o h j ( o n ? o b ? u n d e r o b j ( h o l d i n g ? o b ) 斗( c l e ar ? o b ) ( c l e a r ? u n d e r o b ) + 一( o n ? o b ? u n d e r o b ) 分折完这四个动作，在所获得的1 2 对矛盾谓词对中，去处重复共可以得到 如下5 对矛盾谓词。 ( h o l d i n g ? o b ) ( h o l d i n g ? o b ) 斗 ( h o l d i n g ? o b ) + 斗 ( o n ? o b ? u n d e r o b ) _ + ( o n ? o b ? u n d e r o b ) + 一 ( c e a f ? o b ) ( o n t a b l e ? o b ) ( a r m - e m p t y ) ( c l e a r ? u n d e r o b ) ( h o l d i n g ? o b ) 对于这些矛盾谓词对，在对变量实例化后生成对应的实例化的矛盾谓词对， 它们可以用来判断基动作之间的关系。在这个矛盾谓词的判定算法的基础上，我 们展开了第三章的讨论。 中山大学硕士学位论文 基于s t r i p s 描述的规划宏动作的构造研究与应用 第3 章强可顺序执行序列 某一问题域中的两个基动作a ，b 如果两个动作存在可以顺序执行的情况， 并且第一个动作为第二动作创造某些条件，那么我们认为a ，b 是强可顺序执行 序列。它的更为详尽的定义是什么呢? 首先我们介绍几个其它的概念。 3 1 矛盾序列 某一问题域中的两个基动作a , b 。我们说如果序列a , b 在任何情况下都不可 能顺序执行，那么我们称序列a b 是矛盾序列。我们通过下面的方法来判断a ，b 是矛盾序列。( a ，b 是矛盾序列，并不意味着b ，a 也是矛盾序列) 设b 的前件中所有的谓词集合为m 。 步骤：顺序扫描a 的后件与前件中的所有谓词： ( 1 ) m 中的某一个谓词p ，若在a 的后件的删除表中有p ，序列a , b 是矛盾序 列；算法停止。否则继续。 ( 2 ) m 中的某一个谓词p ，若在a 的后件的添加表中有一个或多个谓词与p 是 矛盾谓词对，序列a b 矛盾是矛盾序列，算法停止。否则继续。 ( 3 ) m 中的某一个谓词p ，若出现在了a 的后件的添加表中，那么在m 中删除 这个谓词p 。然后转( 4 ) 继续扫描a 的前件中的所有谓词。 ( 4 ) m 中的某- n 词p ，若在a 的前件中存在一个谓词o ，且p , q 是矛盾谓词 对，那么序列a ，b 是矛盾序列。 ( 5 ) 如果m 中的所有谓词经过( 1 ) ( 2 ) ( 3 ) ( 4 ) 判断后，都不能判断a , b 是矛盾序列。 则a b 不是矛盾序列。 算法的前两个步骤读者比较容易理解，因为a 的后件和b 的前件之间有谓 词是矛盾的，所以算法可以确定a ，b 是矛盾序列。可是后两个步骤做些什么呢? 首先举一个例子： 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 a c t i o np i c k u p ( a ) ：p r e c o n d i t i o n ( a n d ( c l e a ra ) ( o n t a b l ea ) ( a r m e m p t y ) ) ：e f f e c t ( a n d ( h o l d i n ga ) ( n o t c l e a ra ) ) ( n o t ( o n - t a b t ea ) ) ( n o t a r m e m p t y ) ) ) a c t i o np u t d o w n ( b ) ：p r e c o n d i t i o n ( h o l d i n gb ) ：e f f e c t ( a n d ( c l e a rb ) ( a r m e m p t y ) ( o n t a b l eb ) ( n o t ( h o l d i n gb ) ) ) 算法执行完步骤( 1 ) ( 2 ) 后并没有发现任何矛盾谓词。接下来执行步骤( 3 ) ，执 行完步骤( 3 ) 后，集合m 里还有h o l d i n gb ，在进行步骤( 4 ) 时发现了对矛盾谓词 a m 3 e m p t y 与h o l d i n gb 。这时候我们为什么根据这个对矛盾谓词就判断序列a ，b 是矛盾的呢? 我们在执行步骤( 4 ) 时，没有检验锄一e m p t y 是否在前一个动作的删除表里出 现，也不必进行这样的检验。 假设a l t n e m p t y 没有被否定( 即没有出现在删除表中) ，也就说在前一个动作 执行完后锄一e m p t y 仍然成立，我们发现了a r m e m p t y 与h o l d i n g b 这对矛盾谓词， a l t o e m p t y 与h o l d i n gb 不能同时成立，因此就有足够的理由认为动作a , b 是矛盾 的了。 假设a r m e m p t y 被否定了，那么它被否定后，必然会出现一个新的谓词，经 过步骤( 3 ) ，我们可以确定a l m e m p t y 被否定后不是出现了h o l d i n gb ，而是出现 了另外一个谓词( 实际是h o l d i n ga 不过算法并不关，p ) 。在前一个动作中设 a i m e m p t y 被否定后出现的新的谓词为p ，经过步骤( 3 ) 确认p 不是h o l d i n gb ，我 们有理由认为p 与h o l d i n gb 是a d j l e m p t y 经过不同的变化面转化成的，从而我 们也有理f h 认为p 与h o l d i n g b 是矛盾的，即a 后件中的谓词p 与b 前件中的谓 词h o l d i n gb 矛盾。从而我们认为序列a ，b 是矛盾序列。 如果a b 是如下两个动作： a c t i o np i c k u p ( a ) ：p r e c o n d i t i o n ( a n d ( c l e a ra ) ( o n t a b l ea ) ( a r m e m p t y ) ) ：e f f e c t ( a n d ( h o l d i n ga ) ( n o t ( c l e a ra ) ) ( n o t ( o n - t a b l ea ) ) ( n o t ( a r m e m p t y ) ) ) 中t lj 大学硕士学位论文基于s t r i p s 描述的规划宏动作的构造研究与应用 a c t i o np u t d o w n ( a ) ：pr e c o n d i t i o n ( h o l d i n ga ) ：e f f e c t ( a n d ( c l e a ra ) ( ar m e m p t y ) ( o n t a b l ea ) ( n o t ( h o l d i n ga ) ) ) m 集合中的h o l d i n g a 在步骤( 3 ) 中被删除掉了，从而步骤四检测不出任何矛 盾，丸b 这两个动作就不是矛盾动作了。 步骤( 3 ) ( 4 ) 正是为某些未能被检测出的矛盾谓词做的一个补充，打的一个补 丁。从而尽可能的找出那些不可能顺序出现在一个p l a n 中的两个基动作，并称 它们为矛盾序列。虽然理论上并不能保证上述方法一定可以将所有的不可能顺序 执行的序列找出。但是这个方法对很多问题域都能够完备找出所有不能顺序执行 的基动作序列，正是基于这一点，下文开始了更多的探索。 3 2 相互独立的基动作 某两个基动作a ，b 是相互独立的，就是指基动作a , b 的先后执行顺序无关。 既：a , b 两个基动作如果在某一p l a n 中顺序出现，则它们之间互换位置后p l a n 仍然是原来问题的解。 下面是判断a , b 是否相互独立的算法。 步骤( 1 ) 若a ，b 是矛盾序列，a ，b 不是相互独立的，退出。 步骤( 2 ) 若a 的后件中有一个谓词在b 的前件中也出现了， 立；的，退出。 步骤( 3 ) 若a 的前件中有一个谓词在b 的前件中也出现了， 把这个谓词又否定了。a b 不是相互独立的，退出。 否则，判断出a ，b 两个动作是相互独立的。 a ，b 不是相互独 且在b 的后件中 步骤( 1 ) 中矛盾序列的检验过程实际上可以与步骤( 2 ) 结合在一起进行。步骤( 3 ) 也可以融合到前两步中。 在保证矛盾序列检测方法正确的基础上，有如下定理。 1 4 中山大学硕士学位论文基于s t r i p s 描述的规划宏动作的杓造研究与应用 定理3 1 上述算法如果判断出a ，b 是相互独立的，那么b ，a 用这个算法也 一定自2 判断出是相互独立的( 算法的交换性) 。并且如果a ，b 若顺序出现在某一个 问题的某一个p l a n 中，将a ，b 的位置互换后p l