（计算机软件与理论专业论文）智能规划中基于遗传算法的动作模型学习.pdf

论文题目：智能规划中基于遗传算法的动作模型学习 专业：计算机软件与理论 硕士生：赖志锋 指导教师：姜云飞教授 摘要 智能规划是人工智能研究领域近年来发展起来的一个热门分支，理论 研究和实际应用都成为人工智能当前的热点。本文首先分析研究目前智能 规划领域中的典型方法和关键技术，并对规划中的学习，特另q 是动作模型 学习的研究进行了深入讨论。 在中间状态未知的假设下学习动作模型在很多现实的应用中有重要的 研究意义。本文正是在这假设下，利用遗传算法，从不完整的领域描述和规 划实例中学习动作模型，并且设计了a m l s g a 系统来具体实现这一思想。 我们为每一个部分描述的动作构建一个可能谓词集，这个谓词集覆盖了动 作前提表、增加表和删除表中的所有文字。并且用二进制鳊码的形式，把动 作模型编码成g a 搜索空间中的一个假设，学习过程是在标准的遗传算法框 架下进行的。 我们把学习结果的正确性定义为尽可能多的解释规划实例，并且通过 实验的方法对比了学习到的模型与专家预定义模型之问的差别。结果表明， 算法能在较短的时间内，学习到一个逼近专家描述的动作模型。 关键词：智能规划；遗传算法；规划中的学习；动作模型学习；规划 实例；动作约束；规划约束 t i t l e ： m a j o r ： n a l n e ： s u p e r v i s o r ： l e a r n i n ga c t i o nm o d e l i na ip l a n n i n gb a s e do n g e n e r i ca 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 z h i f e n gl a i y u n f e ij i a n g ，p r o f e s s o r a b s t r a c t i n t e l l i g e n tp l a n n i n g1 1 a sr e c e n t l yb e c o m eah o tt o p i ci na if i e l d r m e a r e hw o r kb o t h i nt h e o r ya n da p p l i c a t i o nm a l c e si tn m c hn l o r en l a t m e w ef i r s ts u r v e yc l a s s i c a lm e t h o d sa n dc r i t i c a lt e c h n i q u e si na ip l a n n i n ga n df u r t h e ri n v e s t i g a t el e a r n i n gi np l a m f i n g ， p a r t i c u l a r l yl e a r n i n ga c t i o nm o d e la s p e c t i nr e a lw o r l da p p l i c a t i o n ，i ti so fs i g n i f i c a n c et ol e a r na c t i o nm o d e lw h e ni n t e r - m e d i a t es t a t e sa r eu n a v a i l a b l e u n d e rt h i sa s s u m p t i o n ：t h i sp a p e rp r e s e n t sam e t h o d t ol e a r na c t i o nm o d e lf r o mi n c o m p l e t ed o m a i nd e s c r i p t i o na n dp l a ne x a m p l e so nt h e g e n e r i ca l g o r i t h mf r a m e w o r k ，a n dd e v e l o p sas y s t e mc a l l e da m l s - g a ( a c t i o nm o d e l l e a r n i n gs y s t e mb a s e do ng e n e r i ca l g o r i t h m ) a sa e s t b e df o rt h i sm e t h o d ，i tb u i l d sa p o s s i b l ep r e d i c a t es e tf o re a c hp a r t i a ld e s c r i b e da c t i o n ，m i l c hc o v e r sa l lp o s s i b l el i t e r a l s i np r e c o n d i t i o n a d dl i s ta n dd e l e t el i s to ft h ea c t i o n i te n c o d e st h ea c t i o nm o d e la s ah y p o t h e s i si ng as e a r c hs p a c ee x p l o i t i n gb i n a r yc o d i n gt h ew h o l el e a r n i n gp r o c e s s i su n d e rt h es t a n d a r dg e n e r i ca l g o r i t h mf r a m e w o r kp r o p o s e db yp r o f e s s o rh o u a n di n m i c h i g a nu n i v e r s i t y w ed e f i n et h ev a l i d i t yo ft h i sm e t h o da se x p l a i n i n gm o r ep l a ne x a m p l e s a n dn l a k e c o m p a r i s o nb e t w e e nt h el e a r n e dm o d e la n dt h em o d e ld e s c r i b e db ye x p e r t s e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea l g o r i t h mc a l ll e a r na na c t i o nm o d e ld o s et oe x p e r tf o r m a l i s mi n 】j m i t e dt i m e k e y ：i n t e l l i g e n tp l a n n i n g ，g e n e t i ca l g o r i t h m ，l e a r n i n gi np l a n n i n g 1 e a r n i n ga c t i o n m o d e l ，p l a ne x a m p l e ，a c t i o nc o n s t r a i n t ，p l a nc o n s t r a i n t i i i 第一章引言 智能规划f a ip l a n n i n g ) 是近年来人工智能研究领域中的一个热门分支。其主要思 想是：对周围环境进行认识与分析，根据当前问题的初始状态和目标状态对若干可供 选择的动作及所提供的资源限制进行推理，综合制定出实现目标状态的动作序列即规 划( p l a n ) 。 智能规划的研究开端可追溯到二十世纪5 0 年代。1 9 5 7 年由g w e r u s t 和a n e w e l l 等人研制的通用问题求解系统g p s ( t l mg e n e r a lp r o b l e ms o h e r ) 被认为是世界上第一 个智能规划系统。而后在1 9 6 9 年，以著名人工智能专家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 i r s t i t u t e p r o b l e ms o l v e r l ，这个系统的知识表示方法和推理方法对后来的规划系统具有深刻的 影响， 然而，由于当时智能规划的效率不高、应用不广，智能规划的研究陷入了一个发展 缓慢的阶段。直到二十世纪8 0 年代后期，智能规划在实际应用中的良好前景才吸引了众 多研究者。尤其是近年来，不断有关于智能规划的国际会议召开，有新的工作组的出现 而且人工智能规划与调度协会还每两年举行一次国际智能规划竞赛。这一系列的动态 促进了智能规划的发展，使德智能规划在理论和实践中都取得飞速的进步。 智能规划系统需要被提供动作模型、初始状态和目标状态来作为输入。在规划界， 存在着许多动作建模语言，像著名的s t r i p s f i k e sa n dn i l s s o n ，1 9 7 1 1 和p d d l g h a l l a b e ta 1 ，1 9 9 8 。有了这些语言，领域专家就可以写下完整的领域动作表示，为规划系统产 生规划提供输入。然而，从零开始来构建一个动作模型即使对于专家来说，也是一件很 耗时的困难任务。 由于这种困难的存在，许多研究者已经探索了许多方法 c a r b o n e l la n dg i l 1 9 9 0 g i l ，1 9 9 2 ，1 9 9 3 ，1 9 9 4 ，w a n g ，1 9 9 5 ，w a n ga n dc a r b o n e l l ，1 9 9 4 w a n g ，1 9 9 4 b e n s o n ，1 9 9 5 b e n s o na n dn i l o n ，1 9 9 3 1 ，目的在于自动地从不同的例子中学习动作模型。这些早期的 工作有一个共同的特征，它们必须先知道每个动作发生前后的状态，然后才能用统计的 或推理的方法来学习动作的前提和效果。然而，在诸如对象追踪和规划监测等现实应用 领域，很多情况下a g e n t 无法获知中间状态的任何信息。如果要手工为每个规划实例的 中间状态来做注释，则代价可能是非常高的。 因此，在中间状态未知的假设下学习动作模型的任务就变得非常迫切。基于这 一假设，本文在遗传算法的框架下，从不完整的领域描述和规划实例中学习动作模 型，并且设计了一个称为a m l s g a ( a c t i o nm o d e ll e a r n i n gs y s t e mb a s e do ng e n e r i c 中山大学硕士学位论文 a l g o r i t h m ) 的系统具体实现这一想法。我们指的规划实倒包括初始状态、目标状态和带 有参数列表的动作名序列，动作间的中间状态完全不知。我们的目标是找回动作前提 表、增加表和删除表中缺失的文字。假设能为a m l s g a 提供一些规划实例那么它将 构建出一个尽可能多解释规划实例的动作模型。这个动作模型不保证完全正确，但是我 们希望它能为领域专家设计出个正确的模型提供一个基础。 在下一章我们将对智能规划的理论基础、研究方法、遇到的问题和基于不同思想 实现的具体规划器进行简要地介绍。而规划中的学习问题将在第三章中阐述，包括动作 模型学习现有研究和一个集成了规划、学习这两方面的系统p r o d i g y 的介绍，以及其 它学习方面的研究。第四章回顾了遗传算法的一些主要议题，阐明了其基本原理和算法 要素，同时带过了遗传算法的理论基础、算法特点和应用。第五章是本文工作的核心 首先介绍了研究的动机和问题的假设，接下来用一个具体的实例来陈述要处理| 试题最 后具体地讲解了学习系统a l s - g a 的总体设计、算法框架、软件体系结构还有其它方 面的算法细节。实验的结果和分析在第六章中讨论。最后一章总结了全文的研究工作， 并对这个问题的未来工作进行了展望。 2 第二章智能规划概述 2 1 形式化基础 通常来说一个规划问题包括以下要素： 用形式化语言描述的领域动作( 领域理论) ； 关于世界初始状态的描述； 对预期目标的描述。 在以下各小节，我们将列举出一些定义规划问题各要素的重要方法。 2 1 1 规划领域的形式化 领域形式化的目标是提供一个领域理论以刻画a g e n t 动作的语义，通常领域理论用 状态迁移系统来表示。在状态迁移系统中，状态( 情景) 是描述世界在某个特定时问点的 快照，而动作用于把一个状态转换成另一个状态。一般，状态被定义为基原子公式( 原 子) 的集合，那些会随着时问改变其值的原子称为f l , 。e n t ，而那些不会改变的称为状态不 变量。 早期领域理论的研究都采用纯逻辑的方法这包括 m c c a r t h y 1 9 6 3 1 的情景演 算，【k o w a l s k ia n ds e r g o t ，1 9 8 6 的事件演算和 g i o r d a n oe ta 1 ：1 9 9 8 1 基于模态逻辑的动 作理论。虽然用纯逻辑的方法能够精确的刻画动作的语义并且能够证明领域理论的某 些性质。但实用的规划系统大多不直接采纳，而是采用非形式化一定的方法，这些方法 多数根源于 f i k e sa n dn i l s s o n ，1 9 7 1 1 的s t r i p s 描述。s t r i p s 通过指明前提表、增加表 和删除表来定义一个动作，它们都表示为原子的合取式。其语义也比较直观：仅当当前 世界状态满足前提表，一个动作才可适用。在动作执行之后增加表中的原子加到世界 状态( 数据库) 中，而删除表中的原子从世界状态中移去。a d l i i 吾言 p e d n a u l t ，t 9 9 4 提供 了比s t r i p 更强的表达能力：a d l 允许定义上下文依赖的效果、全称量化的效果、否定 式和析取式。 随着智能规划应用研究的开展，人们急切需要表达诸如时态推理、数值，任务网络 等的内容，于是涌现了大量扩展了s t i u p s 和a d l 的专门语言格式。然而，它们的语义 通常都非常模糊，不便于研究者进行交流。为了对付这一问题，f g h a l l a be ta 1 ，1 9 9 87 专 门设计了规划领域定义语言( p d d l ) 作为标准的领域( 问题) 描述语言。使用p d d l ，可 以非常方便的对不同的规划系统进行比较。在表达方面最初的p d d l ( p d d l i 2 ) 基 本与a d l 持平，但其后续版本大大增强了表达能力这包括：p d d l 2 1f f o xa n dl o n g 3 中l h 大学硕士学位论文 2 0 0 3 1 增加了时间的概念，p d d l 2 2 增加推导谓词和初始时间文字。在此基础上还有其 它很多的扩展，例如，【b e r t o l ie ta 1 ，2 0 0 3 1 使得p d d l 可以表示不确定性和条件规划。 2 1 2 初始世界的形式化 初始世界只不过是领域理论定义的世界状态之一。对于所有关注初始世界的方法 来说其中心议题是哪些原子可以被认为在初始世界状态中为真。经典的智能规划方法 假设初始世界状态的定义提供了完整的描述，即闭世界假设( 任何在状态数据库中没有 被显式表明的事实都为假) 。但是，对于像机器人或w e b 服务计算领域等真实世界的运 用，这样简化的假设是不合理的。事实上我们将会面临如下的问题： 不完整的信息：初始世界的定义没有详述与规划任务相关的所有信息； 错误的信息：一些被定义为真的原子可能在现实中是假的( 反之亦然) ： 模糊的信息：一些原子只在一定的概率下才为真。 为了处理以上的诸种困难，有必要区分两类动作：改变世界的动作和影响a g e n t 知 识的动作，后者被称为感知动作。s a d l g o l d e n ，1 9 9 7 在a d l 的基础j ：增加了对不完整 信息和感知的支持：类似地o p t m c d e r m o t t ，2 0 0 2 1 在p d d l 的框架上增加了知识效果 和可学习项。 2 1 3目标的形式化 大多数经典的智能规划方法都把目标表示为需要在预期世界状态( 目标状态) 成立 的属性集通常以文字( 正原予或负原子) 的台取式、析取式的形式出现而变量被认为 是存在量化的。规划器需要定下一个解f 规划动作序列) ，当这个解在初始世界状态中 执行后，会产生一个目标状态来满足这个目标。 但是，对于现实世界的规划领域，这样的目标描述还是不足够的，文献中提及过的 对目标描述的需求包括： 需要时态信息：一些复杂的目标不能摘单的表示为单一最终状态的属性。例如对 于一个从广州到北京往返航程的规划，不能表示为目标状态上的一个条件因为 目标状态将会等于初始状态( a g e n t 直在广州) ； 处理不确定性的策略：一个动作的执行没有达到预期的结果应该如何处理； 安全属性：并不是所有能够达到目标的解都是符合要求的。例如，可以生成一个最 终使信用卡余额为正的规划，但中间状态可能会因为透支过大而不符合要求。像 这类存在受保护f l n e n t 的问题称为资源约束问题； 信息目标和完成目标的区别：许多问题需要这样的区分，因为信息目标只能由 感知动作完成。例如，给a g e n t 分配一个去查明指定的积木块是否为红色的任 务，a g e n t 就不能使用改变颜色的动作： 4 第二章智能规划概述 用户对各种可能解的偏好( 偏好乘飞机而非火车，用信用卡付款而不是现金) 和其 它对于解的用户约束( 如果飞机票能打七折就买飞机票，否则买火车票) 。 对于以上问题的各种处理方法，将会在2 3 小节详细讨论。 2 2 基本规划方法 2 2 1基于状态空间的规划 一个状态空问包括一个有限的状态集s 一个有限的动作集a ，一个描述动作怎样 把一个状态映射到另一个状态的状态转移函数1 和一个代价函数c ( d s ) 0 用来度量 动作。作用到状态s 上的代价 f i k e sa n dn i i s s o n ，1 9 7 1 。一个带有初始状态s o 和目标状态 集的扩充状态空问称为一个状态模型盼m ：t hc lor f m ，2 0 0 1 b 。 基于状态空间的规划器通过搜索能够达到预期状态的动作序列来求解规划问题。 根据搜索起点的不同，我们可以把搜索方法区分为前向状态搜索( p r o g r e $ i o n ) 和反向 状态搜索f r e g r e s s i o n ) 。不管哪一种情况，其目标都是要找出一个动作序列，当其作用 于初始状态时，会导向目标状态。更形式一点地说，一个状态模型的解是一个动作序 列n o ，0 1 a 由它们可以产生一个状态轨迹s 0 s l = ( s o ) ，s 。，t = ，( s 。) - 使得每 一个动作仉都可适用于s 。，而s 。+ 1 是一个目标状态，即l a ( s 1 ) 8 n - i - i s g 【b o n e ta n d g t ：m l “2 0 0 l b l 。 原则上，任何的搜索算法都可以用于状态空间搜索。但是，在基于状态空闻搜索的 方法中，一个动作可选的状态数如此之多以致于基本的规划器效率都很低为了提高 效率，研究者通常沿着两条不同的思路，一条是缩减状态空闯，另一条是使用启发式函 数。最早尝试缩减状态空间的是s t r i p s 算法。但它是不完备的，即使问题存在一个解， 它也不能保证一定能把它找出来。 另外一种处理状态空间数目巨大的思路是使用启发式函数，其设计可以是领域相关 的，也可以是领域无关的。u n p o p m c d e r m o t t ，1 9 9 6 1 是- - 个使用领域无关启发信息的 规划器，它采用了一种称为反向匹配图的结构。h s p ( h e u r i s t i cs e a r c hp l a m m r ) 【b o n e t 一 ( j - f h v ，1 9 9 9 1 j 芑- 个采用爬山式前向搜索的规划器。它的累加启发函数h 。d d 定义一 个原子集合g 的代价为g 中每一个原子代价的和。也就是说，它假设子目标是相互独立 的。h s p 采用的另外一种技术是，用一个放宽的问题来获取启发性的评估值。h s p 的后 继版本是h s p 2m ( 1m i t lg t l l h e r ，2 0 0 1 a ，它和h s p 采用相同的启发函数h 。d d ，但它采 用的是最好优先搜索而不是爬山式搜索。 快速前向规划器( f a s tf o r w a r d ，f f ) i l h | f i = m 2 0 0 1 1 更进一步的利用领域无关的 启发式信息来做规划。像h s p ，f f 在放宽问题上评估目标距离作为启发式信息，从而使 5 中山大学硕士学位论文 得它能够快速的在状态空间作前向搜索。然而f f 在图规划算法( 2 2 2 4 , 节) 的基础上， 使用更加复杂的方法来提取启发信息值m e t r i c f f 是f f 的个扩展降州| m 一2 0 0 2 l ， 它能够处理p d d l 2 1l e v e l 2 所规定的数值变量和约束的问题。 虽然在放宽问题上提取启发信息的方法在很多领域上取得成功但在某些领 域f f 和h s p 这类规划器表现得非常差劲，因为放宽是建立在忽略负效果的基础上的 这将会失去太多的有用信息。快速反向规划器( f a s td o w n w m ( 1 ) i h e h n e l ta n dr i c h t e r 2 0 4 1 是为了对付这一问题而设计的跟f f 和h d p 不同的是它采用称为因果图( c a u s a l g r a p h ，c g ) 的数据结构而不是放宽了的规划图。 2 2 2图规划 有关图规划的所有算法都是基于一个称为规划图的紧致结构。在状态空问图中，规 划是图上的一条贯穿路径，而在规划图中，规划是图中的流( 在网络流的意义上) f b l u m a n df u r s t ，1 9 9 7 。 一个规划图是一个有向的分层图。它包括两类结点：动作结点和命题结点。这些结 点被组织成命题结点层、动作结点层这样交替的层次结构，每一层都关联了一个时问 步。规划图的第一层是命题层层中每一个结点代表初始状态的一个命题。第二层是动 作层，层中的结点是那些前提表中的命题都在第一层出现的动作。第三层又是命题层 包括了所有前一层动作效果的命题。当两个相邻的命题层相同时规划图的构造停止。 可以证明，这种情况肯定会发生，这保证了该扩展过程的终止性。构建一个规划图的复 杂性是动作和命题数量的低阶多项式。 假设第 一1 和i + l 层是命题层，第i 层是动作层。如果一个文字从第i 一1 层保存 到第i + 1 层，但没有连接它们的动作结点那么我们就会在它们之间加一个持续动作 ( p e r s i s t e n c ea c t i o n l 结点。【b l u ma n df u r s t 、1 9 9 5 定义了动作之间以及命题之间的互斥 关系。动作之间可能的互斥关系包括：( 1 ) 不一致效果，一个动作否定了另一个动作的 效果：( 2 ) 冲突，一个动作的效果是另一个动作前提的否定：( 3 ) 竞争需要，一个动作的 前提和另一个动作的前提互斥。同一层两个命题之间具有互斥关系，如果一个命题是另 一个命题的否定或者所有可能到达它们的动作都是互斥的 r , w s e l la n ( 1n o r v i g 2 0 0 2 1 。 第一个使用规划图结构的规划器是g i n p h p l a n 。g r a p h p l a n 算法的核心在 一个大循环中两个交替的主要步骤：图扩展和解提取。图扩展阶段如上所述，直到 出现这样的一个命题层，所有目标命题都在这个命题层出现，且它们之间两两不互 斥。这是规划存在的一个必要但不充分的条件。解提取阶段用于找出潜在的规划 解。g r a p h p l a n 采用反向的策略和逐层的方法以最大的利用互斥关系的约束 b l u m a n d f u r s t + 1 9 9 7 。给定时间( 层) 的一个目标集合，g r a p h p l a n 会确定时间一l 的一 个动作集合，这些动作把目标当成它们的效粜。每一步只有那些和规划中现有动作不 6 第二章智能规划概述 互斥的动作才会被考虑进来。如果失败，g r a p h p l a n 进行回溯并尝试不同的动作集。 如果没有找到一个规划并且规划图还没有完全展开，g r a p h p l a n 就继续图扩展的过 程，直到出现另一个有希望找到解的命题层。 除了性能的优势外g r a p h p l a n 的优越性更体现在像台理性、完备性、最短规划 产生和不可解问题终止性这类理论特性。然而原始g r a p h p l a n 算法还存在很多的 局限性：( 1 ) 它的表示语言只能为纯s t r i p s 不允许有条件和量化的效粜；( 2 ) 如果太 多不相关的信息包括在规划任务的描述中那么g r a p h p l a n 的性能就会急剧下降。 i p p 规划器 k o e h l e re ta 1 ，1 9 9 7 1 扩展了g r a p h p l a n 以处理条件和全称量化了的 效果。另个基于g r a p h p l a n 并且在不断进化的规划器是s t a n 它在做规划之前先 对规划领域进行预处理分析( s t a t ea n a l y s i s ) ，使用了在 f o xa n dl o n g 1 9 9 8 1 中描述的 类型推导模块。s g p v c e l de ta 1 ，1 9 9 8 是g r a p h p l a n 的另外一个扩展它不仅支持条 件效果，而且能够处理不确定效果和不确定的初始状态。 2 2 3 半序规划 半序规划( p a r t i a lo r d e rp l a n n i n g ，p o p ) 把规划问题描述成为在部分规划空问中的 搜索而不是状态空间的搜索，即搜索空问的结点不是状态而是规划结点之问的弧不是 动作的执行关系，而是规划的精化关系。p o p 规划器通常产生的是部分规划，即规划中 的动作没有固定的顺序，一个规划可能有不同的线性化但它们都能达到相同的结果 一个半序规划( 在比较旧的文献中称为任务同络) 可以表示为一个四元组= ，包括： s 是规划步的集合，即动作实例； 0 是序约束的集合，每一个序约束都具有形如s i s j 的结构，表示步骤岛在步骤s ；之 前执行。如果某个规划7 r 至少存在两个规划步s 。和岛，使得0 既没有约束s 。 8 6 ，也 没有约束s 6 8 a 那么我们称7 r 为一个部分规射； 嚣是动作实例参数列表中变量绑定的约束；每一个变量约束都具有形如u n r = z 或口d r z 的形式。其中“n r 是某个规划步的变量x 是一个常量或者是一个其它 规划步变量的的引用。如果只用到基规划步，那么8 = 吼 c 是因果链的集合。因果链被用于说明为什么要把一个规划步引入到一个规划，并 且阻止其它规划步干扰它的引入。如果规划步s ；能达成一个命题p 并且p 满足s ，的 前提，那么就把因果链s 。与s j 加入到c 。 除了上述基本的记号外，半序规划还引入了其它些派生的集合：o c 是规划开放 前提的集合。如果p 是8 前提的一个文字，并且c 中没有形如岛三s 的因果链，那么就把 开放前提三z 加入到凸c 中。换句话说，开放前提是当前规划还没有处理的规划步的前 提；“c 是不安全链的集合。一个因果链岛与s ，称为是不安全的，仅当存在一个规划 7 中i 【i 大学硕士学位论文 步s s 使得：( 1 ) 、p 是s k 效果中的文字；( 2 ) s 。一 “ s ， 在d 中是相容的。在这种 情况下，s k 被称为是因果链s 。与s j 的一个威胁。一个规划z 所有开放前提和不安全链的 并被称为是规划“的瑕疵集f ，即，= o c ( ”) u “( z ) 。一个没有瑕疵的规划称为是完成 的。 半序规划中包含两个特殊的动作s h ，t 和f i n i s h 。s t a r t 动作没有前提且将规划问题 初始状态中的所有文字作为其效果，f i n i s h 动作没有效果睦将规划问题的目标文字作 为其前提。初始规划只包括s 加，1 和f i n i s h ，约束s t a r t f i n i s h 并且将f i n i s h 动作的 所有前提当作开放前提。p o p 算法从初始规划开始从目标反向搜索在满足b 和c 的条 件下通过不断添加规划步来达成每个子目标。直到得到一个完整的、一致的规划。 n o a h s a c e r d o t i ，1 9 7 5 ，1 9 7 7 规划器开刨了半序规划的工作，t a t e 的n o n l i n t a t e 1 9 7 7 1 系统对此进行了深入的研究，n o n l i n 同时也是第一个清楚地给出在一个部分 规划中如何判定一个条件是否为真算法的规划器。t w e a k c h a p m a n ：1 9 8 7 是一个 通用的半序规划系统，c h a p m a n 给出了系统的详细分析，包括完备性的证明和复杂 性的分析。s n l p 算法 s o d e r l a n da n dw e l d ，1 9 m 是 m e a l l e t e ra n dr o s e n b h t t ，1 9 9 1 描 述的规划器的一个具体实现。u c p o p p e n b e r t h ya n dw e l d ，1 9 9 2 t 是针对a d l 表达的 问题的第一个规划器，它比s n l p 稍快，但是由于像s a t 和g r a p h 之类更快的方法出 现在2 0 世纪9 0 年代对基于半序规划方法的研究冷淡了下来。然而，n g u y e na n d k a m b h a m p a t i ，2 0 提出的r e p o p 规划器从规划图中提取出精确的启发信息，其性能 比g r a p h p l a n 提高了很多。 2 2 4 基于命题可满足性的规划 传统上，使用逻辑来傲规划采用的是演绎的方法，即找出一个从初始条件、领域公 理( 定义动作的语义) 和动作序列能够推导出目标状态( 表示为逻辑表达式) 的证明。只 要证明的过程是任一有效的逻辑定理实例，那么动作序列就能从这一实例中提取出来。 k a u t z7 a n ds e l m a n 1 9 9 2 提出了通过可满足性检验来做规划的方法。在这种方法 中规划问题不是一个要证明的定理，而是带有如下属性的公理集：任何公理集的模型 代表着一。个有效的规划。要达到这个目的必须精巧地构造公理以排除不合理的模型。 公理不包括量词和项，所有谓词都在末尾加入一个表示时间步的参数。例如，在著 名的积木块世界中，从初始状态o n ( a b ) a o n ( b ，t a b l e ) 要达到目标状态o n ( b ，a ) 的规划 问题可以表示为： o n ( a b 1 ) ao n ( b ，t a b l e ，1 ) ad e a r ( a ，1 ) ao n ( b ，a ，3 ) 动作r o 佻的语义( 前提和效果1 可以表示为 8 第二章智能规划概述 妇，y ，。，i m o v e ( z ，y ，z ，i ) d ( c l e a t ( z ，i ) ac l e a r ( z ，i ) ao n ( x ，t ) ) 另外还必须加上一些公理以保证每一时间步只采用一个动作。在这个例子中唯一 满足公理化规划问题的模型是： m o v e ( a ，b ，t a m e ，1 ) ，m o v e ( b ，t a b l e ，a ，2 ) ) 这是预期的模型它能够被当作a g e n t 的规划。可以通过使用像d a v i s p u t n a m 或随 机过程g s a t s e h n a ne ta l ，1 9 9 2 1 等可满足性判定过程来构建模型。另一个著名的随机 可满足性判定过程是、a h i k s a t s e l m a ne ta l ，1 9 9 3 ) 。也称为w s a t 。 基于命题可满足性的规划器有s a t p l a n 【k a u t za n ds e l m a n ，1 9 9 2 1 和其后继版 本b l a c k b o x 【k 砒i t za n ds e l m a n ，1 9 9 8 1 ，它兼有s a t p l a n 和g r a p h p l a n 的优点。 s a t p l a n 和b l a c k b o x 在国际智能规划大赛中都表现出色。另一个采用命题可满足 性的系列是l g p g e r e v i i f ia n ds e r i n a ，2 0 0 2 1 7 r 1 其后继版本l g p t d g e r e v i n ie ta 1 ，2 0 0 4 。 它们都基于w a l k s a t ，但l g p t d 采用最优优先搜索算法和规划图作为启发式信息。 除了性能外，基本s a t 的规划器还有另外一个优势：在这个框架下，状态是显式建 模的，因此，很容易加入对状态的需求。这对于表示在2 1 3 小节讨论的复杂目标很有帮 助。 2 3 带控制知识的规划 虽然上- d , 节讲到的很多规划器性能都不错，然而，有很多研究者认为，有必要为 规划器提供领域或任务相关的控制知识，以提高它们在现实世界领域中的性能。 2 3 1 层次任务网络规潮 h t n 规划提供了一种层次抽象，这种抽象是处理现实世界复杂规划领域的种 有效策略。像其它的规划方法，h t n 规划包含了一个动作的集合，当这些动作在执行 之前前提成立，它们就会达到特定的效果。除了动作( 在h t n 规划中称为原任务) 之 外，h t n 还支持方案( m e t h o d ) 的概念每一个方案描述了怎样把一些任务分解成子任 务。这些方案描述代表了通用的领域知识。 根据 e r o le ta 1 ，1 9 9 4 h 的定义，在h t n 规划中有三种类型的任务：( 1 1 目标任务， 包括最终状态的预期属性集；( 2 ) 原任务；( 3 ) 复合任务，原任务或目标任务的组合。 基于h t n 的规划系统把预期的任务分解成一个子任务的集合，这些子任务再分解成予 任务，直到只包括原任务，它们能够通过调用原子动作直接执行。在每一轮的任务分 9 中山大学硕士学位论文 解，h t n 都会检测一些给定的条件是否被违背。如果预期的任务能够被分解成原任务 集并且没有违背任何的给定条件，我们就称规划问题成功地被解决了。 第一次介绍层次任务网络( h i e r a r ( - h i c mt a s kn e t w o r k ，h t n ) 规划的是a b s t m p s f s a c e r d o t i 1 9 7 3 1 规划系统，n o a h 和其它一些规划器也分别介绍了这种规划方法 它的形式语义在 e r o le l ；a 1 1 9 9 4 a b 1 中给出。最近的一个研究热点是称为有序任务 分解( o l d e r e dt a s kd e c o m p o s i t i o n ) 的规划方法，它是h t n 规划的变形。在这种规划 中，a g e n t 分解任务的顺序和它们将被执行的顺序相同，这极大地降低了规划问题的复杂 性。基于这种原则的规划器有s h o p ( s i m p l ef l i e r a r c h i c a lo r d e r e dp l a n n m ) f n a ue ta l ： 1 9 9 9 】。 2 3 2 基于模式检测的规划 基于模型检测的规划方法( p l a m f i n gb m o d e lc h e c k i n g p b m ) 能够处理不确定 性、部分可观察和扩展目标等问题。在p b m 中，规划领域被描述成为一个非确定性的状 态迁移系统，动作能够把系统从一个状态转化到一个可能的后续状态集。和其它的规划 方法一样规划目标能够被表示成为预期目标状态上的约束。除此之外，在p b m 中，还 可以通过叙述规划本身的属性对e l 标进行扩展，这种叙述可以使用c t l ( c o m p u t a t i o n t r e el o 百c ) 时态公式【e n l e r s ( 1 n1 9 9 0 】或者壤近提出的e a g l e 语言 l a g oe ta 1 ，2 0 0 2 。 p b m 方法的基本思想是通过确定目标公式在一个模型中是否为真来产生规划。通 常，模型被表示成为k r i p k e 结构。考虑一个规划领域= f s 1 一) 其中s 是一个有限 的状态集合，a 是一个有限的动作集合，而7 ：s a 一2 3 是非确定性的状态迁移函数。 一个有效的p b m 产生规划 ( 也称为规划领域的策略) 是( s n ) 对的集合其中s s ， 而a a 。对于任意的状态s 要求至多只能有一个动作n 使得( s o ) 口。 由于p b m 领域允许非确定性，p b m 中解的定义和经典规划方法中解的定义不同： 弱解是可以达到目标但不保证这样傲的解。强解能保证达到目标而不管领域的非确定 性性质，强循环解在公平假设1 前提下保证会达到目标。 因为实际问题涉及到的模型包括的状态数会很多，这些算法的实现通常会借 助于符号模型检测( s y m b o l i em o d e lc h c c k i n g ) b u t c he ta l ，1 9 9 2 k 存符号模型检测 中，k r i p k e 结构的可能状态集合和状态问的转移关系都被符号化，通常使用变量矢量 来表示状态命题的真值。通过搜索状态集来进行规划而不是单独的状态，规划本身被 表示为公式。符号模型检测的表示和推理都在二元决策图( b i n a r yd e c i s i o nd i a g r a m s b d d s ) 上展开。 基于模型检测的规划方法在 c i m a t t ie t 川i 11 9 9 7 1 中第一次被系统提出。一个具体实 现的规划器是m i p s e d e l i c a m pa n dh e h n e r t 2 0 0 1 l ，它用到的底层结构是b d d s 。m i p s 的 1 解摄终会从进入的循环中跣出。 1 0 第二章智能规划概述 主要强处是它的预编译阶段，它能确定下隐式的领域知识，即状态不变量。如果能够合 适的将状态不变量进行编码，那就能极大地缩减状态描述的长度。其它对于确定领域 的p b m 实现有p r o p l a n f o u r m n n ，2 0 0 1 和b d d p i a n h s l l d o b l e ra n ds t s r r ，2 0 0 0 ，然而它 们的性能都比m i p s 差。 不同于m 1 p s 、p r o p l a n 和b d d p i a n ，规划器m b p ( m o d e lb a s e dp l a n n e l ) 【b e r t o l i e ta 1 2 0 0 1 1 和u m o p ( u n i v e r s a lm u l t i a g e n to b d d b a s e dp l a n n e r ) l j e i l ；e na n dv e l o s o 2 0 0 0 l 用于处理不确定的环境它们很好地利用了模型检测的关键好处。m b p 能够处理 初始状态、动作效果的不确定性使用自己韵动作描述语言n u p d d l ( p d d l 2 1 s j 。 个变形l 。类似地u m o p 也使用自己的领域描述语言n a d l ( n o n d e t e r m i n i s t i ca g e n t d o m a i nl a n g u a g e ) ，n a d l 问题和领域描述被转化成用o b d d s 表示的符号k r i p k e 结 构 b r y a n t ，1 9 s 6 。 2 3 3时态规划 “时态规划”不是指一种特殊的规划技术，而是指规划器能够处理规划领域时态方面 的问题。时态方面的问题包括： 持续动作：在经典的规划方法中动作被看成是瞬时完成的。然而在很多现实的 领域中动作持续时间的信息发挥着重要的作用； 命题有效的时段：在经典的规划理论中。命题一旦成立就保持着，直到a g e n t 显式 地用动作去改变它。但在现实世界，很多f l u e n t 的值是依赖时间的。例如，访向某 种w e b 服务是有时间限制的时间一到链接就自动断开； 并行动作：经典的规划理论假设，规划序列是串行的，一次只能执行一个动作。半 序规划好像是个例外，但是，它并不是为动作的并行性而专门设计的，它只是意味 着某些动作之间相互独立，最终还是给出线性化的规划。然而，有一些问题就是要 求两个或两个以上的动作必须同时执行，无论把它们怎样线性化都不能达到预期 的目的； 时态扩展目标 b a c e l