（计算机软件与理论专业论文）基于修补的重规划.pdf

中山大学硕士学位论文基丁修补的重规划 基于修补的重规划 专业：计算机软件与理论 硕士生：李国强 指导教师：姜云飞教授 摘要 智能规划是人工智能研究领域近年来发展起来的一个研究热点，在动态环 境中，为了处理变化了的情况，对于规划的修补要比重新进行规划有效的多。 随着规划技术的不断发展，规划修补技术也发展迅速。本文首先介绍了规划领 域中的基础知识，然后重点介绍了规划修补领域中的典型方法和关键技术，并 对基于规划图的修补算法进行了深入的分析和研究。 在图规划框架下，充分考虑了图的层次结构对规划修补的作用。对g p g 修 补算法进行了完善，增加了充分利用已有的修补结果的想法。针对于特定的变 化情况，给出了一种有效的修补算法，为了减小搜索空间，引入了后向扩展图 的思想，来提高修补的效率。最后在修补系统中实现了改进方法来验证算法的 有效性。 关键词：智能规划，规划图，规划修补 中山大学硕士学位论文 基于修补的重规划 r e p a i r - b a s e do i lr e p l a n n i n g 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 ：l ig u o q i a n g s u p e r v i s o r ：p r o f j i a n g y u n f e i 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 gh 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 i nd y n a m i c e n v i r o n m e n t s ，r e p a i r i n gap l a ni so f t e nm o r ee f f i c i e n tt h a np l a n n i n gf i r o ms c r a t c ht o d e a lw i t hc h a n g i n gs i t u a t i o n s p l a n n i n gr e p a i rt e c h n i q u e sa d v a n c e sa st h ep l a n n i n g t e c h n i q u e sd e v e l o p e dq u i c k l y w ef i r s ti n t r o d u c et h eb a s i ck n o w l e d g ea b o u tt h e p l a n n i n gd o m a i n , t h e ne m p h a s i st h ec 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 n p l a n n i n gr e p a i rd o m a i n a tl a s t ，w ef u r t h e ri n v e s t i g a t et h er e p a i ra l g o r k h mu s i n g p l a n n i n gg r a p h i nt h ef r a m eo ft h ep l a n n i n g g r a p h , w ep a ym o r ea t t e n t i o nt ot h eg r a p h i c h i e r a r c h yi np l a n n i n gr e p a i r w ep e r f e c tt h ea l g o r i t h mo fg p ga d d i n gt h ei d e ao f m a k i n gu s eo ft h er e p a i rr e s u l t st h a tw eh a v eo b t a i n e d w ep r e s e n tav a l i dr e p a i r m e t h o df o rak i n do fs p e c i a l s i t u a t i o n t oi m p r o v et h ee f f i c i e n c yo ft h er e p a i rw e i n t r o d u c et h eb a c k w a r dc o n s t r u c t i o no f t h e p l a n n i n gg r a p ht od e c r e a s et h es e a r c h i n g s p a c e i nt h ee n d ，e x p e r i m e n t a lr e s u k ss h o wt h a tt h em e t h o da b o v ei sv e r ye f f i c i e n t i np r a c t i c ei n - r e p a i r i n ga p l a n k e yw o r d s ：i n t e l l i g e n tp l a n n i n g ，p l a n n i n gg r a p h , p l a n n i n gr e p a k i i 中山大学硕士学位论文引言 1 1 研究的背景 第1 章引言 智能规划( a ip l a n n i n g ) 是近年来人工智能领域中的一个热门分支。其主要思 想是：对周围环境进行认识和分析，根据当前问题的初始状态和目标状态，对 若干可供选择的动作及所提供的资源限制进行推理，综合制定出实现目标状态 的动作序列，即规划。 人们对智能规划的研究最早可以追溯到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 ) 程序，这个系统采用了启发式信息和反向搜 索技术；随后他们设计的g p s 系统把领域知识与一般的搜索控制信息相分离， 被认为是世界上第一个智能规划系统。1 9 7 1 年，f i k e s 和n i l s s o n 设计的s t r i p s 系统【9 】在智能规划的研究中具有重大的意义和价值，他的突出贡献是引入了 s t r i p s 操作符的概念，使得原来很神秘的规划问题求解变得明朗清晰起来。然 而，由于当时智能规划的效率不高、应用不广，到1 9 9 0 年间，在人们发现新的 求解方法之前，对智能规划的研究陷入了低谷。到二十世纪8 0 年代后期，智能 规划在实际应用中的良好前景才吸引了众多研究者。尤其是近年来，不断有关 于智能规划的国际会议召开，有新的工作组的出现，而且人工智能规划和调度 协会还每两年举行一次国际智能规划竞赛。这一系列的动态促进了智能规划的 发展，使智能规划在理论和实践中都取得飞速的进步l l 】。 规划修补也是随着规划一起发展，它更适应环境经常变化的情况。现在研 究最多的就是当初始状态和目标状态发生变化时的情况。当初始状态或是目标 状态发生变化时，可以选择重新规划( r e p l a n n i n g ) ，也可以选择在原有的规划上 进行修补( p l a nr e p a i r ) 在实际应用中，当初始状态或目标发生变化时，在原有 规划上进行修补比进行重新规划效率要高，因为修补只要执行一定数量的改变 就可以解决这个改变后的新问题，在最坏的情况下才是进行重新规划。 中山大学硕士学位论文 基于修补的重规划 1 2 研究的内容 在总结已有的规划修补算法的基础上，利用规划图的结构，在充分利用历 史结果的基础上，引入了后向扩展图的规划算法思想来减小搜索空间，提高了 效率。而且针对于初始条件增加而目标增加或是改变的这一特定情况，给出了 一个比较有效的修补方法，并通过实验加以验证有效性。 1 3 论文的组织结构 本文后续章节的组织结构如下： 第2 章主要对智能规划基础知识和基于不同思想实现的规划器进行简要的介绍 以及对比，并对图规划方法进行较为详细的说明。接着介绍了已出现的规划修 补方法。 第3 章具体讲述了g p g 修补算法的思想，然后给出了本文对它的改进思想。并 且针对本文中提到的特定情况给出了修补方法的介绍及设计，及在实现过程所 采用的方法。 第4 章利用标准的测试数据，与g r a p h p f a n 和g p g 分别进行了对比，给出了详 细的比较结果并加以分析，得出实验总结。 第5 章是总结和展望。对本文所阐述的内容进行总结，并对下一步的研究工作 提出了展望。 2 中山大学硕士学位论文 智能规戈哇的概述 第2 章智能规划的概述 2 1 智能规划的主要思想 对周围环境进行认识与分析，根据自己要实现的目标，对若干可供选择的动 作及所提供的资源限制进行推理，从所给出的初始状态开始，综合制定出实现 目标的规划( p l a n ) 。 2 2 规划建模语言 早期规划领域理论的研究都采用纯逻辑的方法，这包括的情景演算 2 1 ，事件 演算1 3 1 和基于模态逻辑的动作理论 4 1 虽然用纯逻辑的方法能够精确的刻画动 作的语义并且能够证明领域理论的某些性质但实用的规划系统大多不直接采 纳，而是采用非形式化的方法，这些方法根源于s t r i p s 描述【5 1 2 2 1s t r i p s s t r i p s 语义比较直观：它把规划问题表示分成状态、动作、目标三部分考 虑f 5 】os t r i p s 的部分语法规则如下： 状态表示：s t r i p s 的一个状态表示为正文字的合取，既可以表示为命题文 字，也可以表示为一阶文字。其中状态中的文字必须是基项( g r o u n d ) ，采 用封闭世界假设，即一个状态中没有提及的条件被视为假。 目标表示：正文字的合取式。 动作表示：一个动作主要由其前提和效果来定义。只有满足前提，动作才 可以执行，动作执行后，效果就成立。效果里面可以包含增加的效果，也 可以包含删除效果。 举例为：r o c k e t w o r l d 里面的一个算子： ( o p e r a t o r l o a d ( p a r a m s ( c a r g ( r o c k e t ) ( p l a c e ) ) ( p r e c o n d s 3 中山大学硕七学位论文 基于修补的重规划 ( a t ) ( a t ) ) ( e f f e c t s ( i n ) ( d e la t ) ) ) 其中，在效果中( i n ) 是默认的增加效果，删除效果前面都加上 了d e l 标记。当对它的三个参数分别进行赋值，就完成了对此算子的实例化。 从这个算子可以看出，效果中可以出现负文字，但前提中只能出现正文字：前 提和效果中出现的所有变量都在参数表中；效果中的正文字集称为增加表，负 文字集称为删除表；一个动作的定义，由于参数值不同而代表不同的动作实例。 规划的过程，即不断重复地从一个状态s 1 ，执行一个动作后变成另一个状态s 2 。 比如在执行完这个动作后，o b j e c t 由状态( a t 匈b j e c t 就转变到了状态 ( i n ) 规划结果是行动的一个序列。 本文是在g r a p h p l a n 的基础上实现算法，采用的就是这种语法格式。 2 2 2a d l a d l 语言【6 l 提供了比s t r i p s 更强的表达能力：a d l 允许定义上下文依赖的 效果，全称量化的效果，否定式和析取式a d l 与s t r i p s 的区别在于以下几点： s t r i p s 的状态是正文字的合取；a d l 则可以包括负文字。 s t r i p s 采取的是封闭世界假设，即状态中没有提及的条件都视为假：a d l 采取的是开放世界假设，即没有提及的视为未知。 s t r i p s 的效果必须是合取；a d l 中允许是条件效果。 s t r i p s 目标中只有基文字；a d l 中可以包括量化变量。 s t r i p s 目标规定是合取；a d l 则可以是合取或析取。 a d l 新增支持等式谓词的功能。 a d l 的变量可以拥有类型。在s t r i p s 中，要声明一个变量是某个类型， 必须在前提中用谓词表示，例如a d l 的参数表里可以用r l ：r o c k e t 的方 式声明r l 的类型是火箭。但是在s t r i p s 中则要用r o c k e t ( r 1 ) 表示。 2 2 3p d d l 随着智能规划应用研究的开展，人们急切需要表达诸如时态推理、数值， 任务网络等的内容，于是涌现了大量扩展了s t r i p s 和a d l 的专门语言格式。 然而，它们的语义通常都非常模糊，不便于研究者进行交流。为了解决这一问 4 中山大学硕士学位论文智能规材的概述 题，专门设计了规划领域定义语言( p d d l ) 刀作为标准的领域描述语言。使用 p d d l ，可以非常方便的对不同的规划系统进行比较。在表达方面，最初的p d d l 基本与a d l 持平，但其后续版本大大增强了表达能力，这包括：p d d l 2 1 【8 1 增 加了时间的概念，p d d l 2 2 增加推导谓词和初始时间文字。在这些基础上，还 有其它很多的扩展。例如，p d d l 还可以表示不确定性和条件规划9 1 2 3 经典的规划方法 1 9 6 9 年，g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统【】“，这一系统被大多数的智能规划研究人员认为是第一个规划系统，原因 就在于他是第一个面向现实中的规划问题提出的规划系统；1 9 7 1 年，f i k e s 和 n i l s s o n 设计的s t r i p s 系统【l “。在智能规划的研究中具有重大的意义和价值，他 的突出贡献是引入了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 砌p s 、n o a h 、n o n l i n 等规划系统。在这十年间人们研 究智能规划的兴致比较高，普遍认为规划问题必须用定理证明的理论来解决， 直到c h a p m a n 设计的规划系统t w e a k 坦1 出现。c h a p m a n 详细全面地分析了利 用定理证明理论解决规划问题中的关键问题：模型与规划解的对应关系，提出 了著名的模态真值标准( m o d a lt r u t hc r i t e r i o n ) 理论。c h a p m a n 的分析使人们 认识到简单地利用定理证明的方法来解决规划问题是很难的，因此这以后到 1 9 9 0 年阃，在人们发现新的求解方法之前，对智能规划的研究陷入了低谷j 这 期间仅有s i p e 、a b t w e a k 和p r o d i g y 1 3 】等较少的智能规划系统出现。 2 4 非经典的规划方法 本文通过歹表的形式，将非经典规划方法的种类，其中的关键技术和方法， 及有代表性的规划系统进行了比较。非经典规划中搜索空间中的结点可以看作 是多个部分规划的集合，并不是出现在此结点中的每一个动作都会出现在解中， 而在经典规划中的每个结点就是一个部分规划，它当中的每个动作定会出现 在解中。( 指的是从该点出发能找到的规划解中) s 中山大学硕士学位论文基于修补的重规划 表2 - 1 规划方法比较 名称采用的关键技术代表系统 图规划方法利用幽规划算法，图规划在两个阶段交替 g r a p h p l a n l l 4 1 进行：图扩展) 阶段和解提取阶段。l g p l l 6 i b l a c k b o x i i p p l 1 6 1 在当前智能规划研究领域中无关的启发信 h s p 【”1 f f t l 8 , 1 9 1 息的抽取技术是基于实现目标的动作数 鬣，对要解决的问题p 放宽到一个比较简 m 1 p s t 2 0 2 1 1 单的问题尸，抽取技术就是基f p 来评 估。b o n e ! t 提出的向前搜索的一个放宽方法 就是将操作的删除边忽略，对于每个状态 基于启发式搜索 s ，得到在放宽了的问题p 的启发函数 h ( 就可以作为原有问题p 的启发函数 h + ( j ) 的下限，这样h ( s ) 就可以作为合适 的启发函数作用在原有问题p 上。 首先勾画出一个完整但义比较粗略的规划 s h o p 2 1 2 2 1 基于逐步细化的分层 解，然后逐步细化、逐步明确，直到足以 具体完成整个规划的每一步操作，层次规 规划 划方法实际上把不同性质的问题放在不同 层次上加以考虑 编译器首先猜测规划解的眭度，产生一个 b l a c k b o x 【i q 逻辑命题公式，如果逻辑命题公式是可满 足的，它蕴涵着规划解是存在的：符号表 记录了命题变量和规划实例之间的对应； 简化器运h ；j 较快( 通常为线性时间) 的技 约束可满足问题规划 术( 如单元子句法，纯文字消去法等) 来 方法 降低c n f 公式的规模；求解器运川系统或 统计的方法米找到一个满足的赋值；解码 器用符号表把赋值转换成一个规划解。如 果求解器发现公式是不可满足的，那么编 译器就会产生新的编码( 代表更长的规划 解) 。 它将一个系统模型跟逻辑需要进行比较， m 1 p s l 2 0 2 1 1 从而发现不一致性。 m 1 p s 主要结合了模型检测技术和放宽式 将规划问题转化为模 规划技术：采用了静态分析技术对状态编 型检测问题来求解的码进行优化，在象征或显式的模式数据库 ( p d b ) 内，采用放宽式规划技术来对搜索过 规划方法 程进行估值；根据动作集和利用因果结构， 采用路径分析来对生成有序的规划解进行 调度优化。 6 中山大学硕士学位论文智能规划的概述 针对本文的实验基础，重点讲解图规划方法的基本概念，及其工作原理。 2 4 1 基本概念 1 有效( v a l i d ) 规划解：规划问题的一个有效规划解是一个动作的集合和对 每一个动作发生时间的指定。 2 规划图( p l a n n i n gg r a p h ) ：是一个具有两类节点和三类边的有向、分层图。 规划图各层是命题层( p r o p o s i t i o n l e v e l s ) 和动作层( a c t i o n l e v e l s ) 交替出现的，命 题层包含命题节点( 标识为一些命题) ，动作层包含动作节点( 标识为动作) 。 规划图的第一层是命题层，包括规划问题初始条件下的所有命题。 3 第i 层两个动作实例( a c t i o n i n s t a n c e ) 满足以下三者中的任意一个时，我 们称之为具有互斥关系： l 、后件( 效果) 不一致( i n c o n s i s t e n t ) ：一个动作的后件是另一个 动作后件的否定。 2 、冲突( i n t e r f e r e n c e ) ：一个动作删除另一个动作的前件。 3 、竞争所需( c o m p e t i n gn e e d s ) ：两个动作具有i _ 1 层互斥关系 的前件。 4 第i 层的两个命题( p r o p o s i t i o n s ) 具有互斥关系，当： 4 、一个命题是另一个的否定或： 5 、不一致支持( i n c o n s i s t e n ts u p p o r t ) ：获得此命题的所有动作( 方 法) 都具有互斥关系。它们关系如图2 - 1 鋈) 蘸阁麴 i n c o n s i s t e n ti n t e r f e r e n c e e f f e c t s c o m p e t i n gn o d e s i n c o n s i s t e n t s u p p o r t 图2 1 动作问的互斥关系 7 中山大学硕士学位论文 基于修补的重规划 2 4 2 图规划原理 图规划在两个阶段交替进行：图扩展( g r a p he x p a n s i o n ) 阶段和解提取 ( s o l u t i o n e x t r a e t i o n ) 阶段。图扩展阶段正向扩展规划图直到目标状态的所有命题 都出现为止。解提取阶段反向搜索规划图以求出规划解。如图2 - 2 所示：黑圆 点代表命题节点，空白方框代表动作节点。 2 4 3 举例 图2 - 2 图规划的规划图 - ， - _ 。 给睡眠中的爱人准备一个惊喜，要求把垃圾( g a r b a g e ) 带出去，做好正餐 ( d i n n e r ) ，准备好一份礼物( p r e s e n t ) 。 初始条件：( a n d ( g a r b a g e ) ( c l e a n h a n d s ) ( q u i e t ) ) 目标： ( a n d ( d i n n e r ) ( p r e s e n t ) ( n o t ( g a r b a g e ) ) ) 表l 详细的动作描述 动作： ：前件( c l e a r d t a n d s )c a r r y ：前件 () ：后件( d i n n e r ) ：前件( q u i e t ) ：后件( p r e s e n t ) ：后件 ( a n d ( n o t ( g a r b a g e ) ) ( n o t ( c l e a n l a n d s ) ) ) d o l l y ：前件 () 8 ：后件( a n d ( n o t ( g a r b a g e ) ) ( n o t ( q u i e t ) ) ) 中山大学硕士学位论文智能规划的概述 o 2 u昧面 飞厕 图2 3 第一层扩展 动作c a t t y 与保持g a r b a g e 的动作具有互斥关系，因为它们的后件不一致：d o l l y 与w r a p 由于冲突而具有互斥关系；在第二层即命题层- iq u i e t 与p r e s e n t 具有互 斥关系。由于在第二层已经获得了所有的子目标，并且它们之间没有互斥关系， 因此下面可以进入图规划的第二阶段：即解提取阶段。依次考虑目标的各个子 目标，对第i 层的每一个子目标，图规划选择第i 1 层的获得此子目标的动作a ， 此处选择是一个回溯点：如果存在多于一个的动作能够获得此目标，那么图规 划为了保证其完整性必须考虑所有的动作，如果一个动作a 与其他的已经选择 的动作是一致( c o n s i s t e n t ) 的，那么图规划就继续进行其他的予目标，否则如果 没有这样的选择存在，图规划就回溯到前一个选择。当图规划器找到所有的实 现第i 层目标的动作后，它再把选择的动作的前件作为子目标，依次进行，直 到第零层，即初始条件为止，否则返回第一阶段继续进行图扩展阶段【l 】。 2 5 规划修补方法 2 5 1 规划修补的基础知识 在动态环境中，a g e n t s 要处理变化中的环境，即当初始状态或目标状态发生 变化时，修补一个规赳的效率通常要比从头进行规划要高。规划修补通常有两 9 中山大学硕士学位论文基于修补的重规划 个不同的操作组成：( 1 ) 移除动作，( 2 ) 增加动作。增加动作和规划是相似的，移 除动作是指将在规定时间内无法找到解的不一致动作删除掉。规划启发式同样 可以用于移除动作，称为：u n r e f m e m e n t 。 2 5 2 使用规划库的规划修补 将规划库用于修补过程中的求精阶段2 引，这个规划库中包含了在一定领域 中经常出现的一部分规划。主要用它来支持u n r e f i n e m e n t 策略，并且为了最小 的改变p o p r 系统，其中引入了m a c r o a c t i o n s ( 宏动作1 。宏动作不仅仅是一个 动作，而且表示了库中的一个规划。宏动作和普通的( 原子) 动作是一样的：有 所需的前件和所产生的效果。在求精( r e f i n e m e m ) 中，不是使用规划而是使用宏 动作，当宏动作被完全实例化后，并用它的前件得到满足和它不会与其它的链 冲突时，就可以被它表示的规划替代：移除宏动作，在规划库中检索相对应的 规划并插入。从而减小了搜索空间，提高了性能。规划的质量( 大小) 稍微有些 下降：在一些实例中，产生的结果有些差，但在其它实例中没什么不同。 宏动作生成的具体实例。在g r i p p e r 领域中，一个动作序列：p i c k - a c t i o n 是捡 起一个球，然后m o v e a c t i o n 移动到另外一个房间内，最后d r o p - a c t i o n 将球放 下。即为：将球从一个地方移动到另一个地方。这个规划就可以作为一个宏动 作： ( ：a c t i o nm a c i o p i c k m o v e - d r o p ：p a r a m e t e r s ( ? f r o m ? t o9 0 b j ? g r i p p e r ) ：p r e c o n d i t i o n ( a n d ( r o o m ? f r o m ) ( r o o m ? t o ) ( b a l l 9 0 b j ) ( g r i p p e r ? g r i p p e r ) ( a t - r o b b y ? f r o 神( a t ? o b j ? f r o m ) ( f r e e ? g r i p p e r ) ) ：e f f e c t ( a t 9 0 b j ? t o ) ) 这样，原来由三个动作组成的动作序列，现在只用一个动作就表示出来了。 2 5 3 基于修补规则的方法 由h a m m o n d 设计的c h e f 系统【2 4 1 中配置了一个规划修补规则的集合。每 一个这样的规划描述了具体的失败是如何修补的。当c h e f 碰到一个失败时， 1 0 中山大学硕七学位论文智能规划的概述 它就会给出一个此失败为什么会发生的解释，包括：( 1 ) 导致失败的所有的步，( 芍 导致失败的所有的状态，( 3 ) 这些步试图实现的目标。基于这些解释，选择一个 规划修补策略的集合并实例化具体的失败情况。然后选择一个最好的实例化修 补策略使用。 同样的，应用规划修补规则的系统还有o - p l a n 【2 5 1 它不采用失败的解释方 法。在执行过程中，系统确认每一个动作的效果。对于失败的效果，一些其它 的动作可以执行，这些动作是额外的，以修补规划的形式加入到规划中。这些 修补规划是预建立的来修补一定的失败情况。无论何是碰到一个错误情况，规 划都会停下来，一个修补规划被插入执行，待修补规划完成后，正常的规划继 续执行。对于修补失败，o p l a n 仅仅加入动作，因此它的执行中不存大 u n r e f m e m e n t 过程，也不需要历史。因此它是不完备的，因为不是所有的失败 都可以被恢复的。虽然w a n ga n dc h i e n t 2 6 】描述了搜索如何加入到o p l a n 中来 解决在没有修补策略可用的时候进行恢复的问题，但是他们也没有考虑移除动 作的过程，只是仅仅查找哪些动作需要来重新执行。 2 5 4 基于证明系统的方法 m r l ( k o e h l e r1 9 9 4 ) 2 7 1 将规划重用能力集成到一个推理规划器中，这个规划重 用基于重用过程的逻辑形式化，包括规划的修改，表示和检索。这个系统可以 自动的重用和修改序列化的、条件性的和重复的规划。规划库用带有规划逻辑 的知识公式来表示。它会自动的创建和维护这个规划库，而不需要用户的干预。 具体的规划重用步骤为： ( 1 ) 规划的确定：推理规划系统收到一个形式化的规划说明之后，规划重用过 程就去搜索规划库。库中包含了从解决前一问题中提取出来的“规划实体”。 一个规划实体提供了关于规划问题和其解的综合信息。比如：描述初始和目标 状态的说瞻。这个当前的规划说明作为搜索的关键字来确定一个合适的包含相 似规划说明的规划实体作为一个可重用的规划。 ( 2 ) 规划的解释：在此阶段中，当前的规戈l j 和可重用的规划说明进行语法比较， 这个比较的结果就是一个证明，来得至u 属于可重用规划说明的不用修改直接使 用的规划，或者是一个失败的证明以便于整修信息的提取。 中山大学硕七学位论文基于修补的霞规划 ( 3 ) 规划的整修：通过构造一个与证明结果一致的规划框架。这个框架是一个 规划公式，其中规划的元变量作为子规划中的占位符出现，在重整过程中必须 进行实例化。这个规划框架保持着许多动作，这些动作在证明中已经被证明为 是可重用的，并且从当前规划的说明中取得对象参数给动作中的变量进行实例 化。这个框架会通过替代每一个规划的元变量而扩展成一个正确的规划。 ( 4 ) 规划库的更新。在此过程中，一个新的规划实体通过当前的规划说明被构 建，它是通过修改一个现有的规划和在证明树中提取的信息生成的，这一证明 树是作为规划框架的扩展结果构成的。 2 5 5 利用层次任务网络的方法 r e p l a n ( b o e l l a & d a m i a n o2 0 0 2 ) 口8 】的重规划模型与层次任务网络中的规划 相似。一个任务网络描述为：通过完成一些子任务来完成任务的可能的路径。 对于每一个任务至少存在一个任务网络。通过对每一个选择的任务选择正确的 任务网络，直到每一个网络只有动作组成来生成一个规划。通过这个规划过程， r e p l a n 构造一个演绎树( d e r i v a t i o nt r e e ) ，它包括所有选择的任务并表示出一个 规划如何得来的。在r e p l a n 中的规划修补被称为p a r t i a l i s a t i o n 对于演绎树中无 效的叶子结点，包含此结点的( 最小的) 子树被移除掉。起初，这样的一个无效 的叶子结点是一个初始动作，对应的子树的根是包含这个动作的任务。之后， 对应这个任务一个新的r e f i n e m e n t 会产生。如果r e f i n e m e n t 失败了，新的一轮 接着开始：层次中任务子树的较高层被移除并且被重新生成。 直接在层次任务网络( h t n ) 规划基础上实现的重规划过程的是【2 6 1 ，并且还加 入了基于算子的规划方法。在这种结构下，把目标分为两类：活动目标和状态 目标。活动目标对应于可操作或是不可操作的活动，它可以通过h t n 规划技 术完成。状态目标对应于活动目标的前件和效果，可以通过基于算子的规划完 成。并将未完成的状态看作不可操作的。当所有的活动目标都为可操作的，所 有的状态目标都被实现的时候，规划才算是完整的。具体的重规划算法为： ( 1 ) 根据已执行的动作，找出有反映规划改变的效果的动作集 ( 2 ) 确定必须的状态目标继续进行规划，但是会因为未预见到的目标的改变而停 止。然后利用“r e s e t ”将每一个状态目标恢复为它的默认值 1 2 中山大学硕士学位论文智能规划的概述 ( 3 ) 最后，算法决定哪些已经执行过的动作需要重新执行。最终在尽可能多的利 用已有的结果的基础上找到新问题的解。 2 5 6 利用队列的方法 在 h a n k s & w e l d1 9 9 5 1 2 9 l 中，也明显的体现了修补的两个过程，利用一个队 列( 由宽度优先搜索来生成) 来选择下一个要工作的目标。在这个队列中的部分 规划或者是要被求精( r e f i n e ) 的( 标记为i ) 或者是要被u n r e f i n e 的( 标记为t ) 。对 于标记为l 的部分规划进行所有的求精，并将所得的都加入到这个队列。对于 标记为f 的部分规划p 被修改，并将结果也加入到队列中，仍然标记为f 。这 样标记结点可以避免在搜索空间中同一个结点被访问两次。这种方法是基于对 部分序规划的图的搜索，针对基于案例规划器的修改阶段设计的一个领域无关 的修补算法。与基于规划库的方法的不同在于，它所存储的规划，不一定是经 常被用到的，而是只要是在搜索过程中发现的，都包含在里面。所以在这个算 法是里面，就存在这样的一个问题：对这些生成的规划如何进行很好的检索， 如何进行索引。 2 5 7 利用启发式方法 在 3 0 1 3 1 1 提到了一个通用的规划修补启发式。这个启发式由新的u n r e f m e m e n t 策略组成，并且它可以利用现有的规划启发式提取( r e f i n e m e n t ) 算子。通过移除 一定的动作的集合，u n r e f m e m e n t 策略能以多种方式来恶化规划，然后规划启 发式被用来选择最好的候选者，作为初始的部分规划给规划器来进行提取。提 出如下的算法作为一个通用的框架，并且将r e p l a n , s p a ，g p g , 和s h e r p a 所用的 方法进行了对照。 a l g o r i t h mp l a nr e p a i r ( p , h ，h ) i n p u t ：ap a r t h lp l a np ap r o b l e mn a n dah i s t o r yh o u t p u t ：as o l u t i o n t o o r f a i l b e g i n i f c a n d i d a t e s ( p ) i se m p t yt h e n 中山大学硕士学位论文基于修补的霞规划 r e t u r nf a i l i f s o l u t i o n ( p ，r i ) r e t u r n sas o l u t i o ns t h e n r e t u r ns ： i f w ec h o o s et ou n r e f i n e dt h e n s e l e c tu n r e f m e m e ms t r a t e g yda n dg e n e r a t en e wp l a ns e t 2d ( p h ) e l s e s e l e c tr e f i n e m e n ts t r a t e g yra n dg e n e r a t en e w p l a ns e t 2r ( p h ) n o n - d e t e n n i n i s t i c a l l ys e l e c tac o m p o n e n tp i pa n dc a l lp l a n r e p a i r ( p i ， n h 0 ) e n d 在文中采用了称为“移除树”的结构来完成修补过程。移除树可以是前向的， 也可以是后向的。前向树的根是依赖于初始状态的动作。后向移除树的根是产 生无用效果的动作。树的高度决定了哪些动作会被选中：( 1 ) 一个动作0 ，或者 依赖于初始状态，或者产生无用的效果，这个移除树由0 本身组成，高度为1 ( 2 ) 对于依赖初始状态的动作0 ，0 的高度为n + l 的移除树定义为：由高度为n 的移除树上的动作产生，并且新树上动作依赖于这些动作。 ( 3 ) 对于产生无用效果的动作o ，o 的高度为n 十l 的移除树定义为：由高度为n 的移除树上的动作产生还有这些动作所依赖的动作。 在考虑整个规划都可能被移除的情况下，当移除树发生重叠时，先进行合并。 具体的u n r e f m e m e m 策略工作如下：从高度l 的移除树开始，利用规划启发式 来获得扩展规划为有效规划的代价，然后来选择最有前途的候选项，这一候选 项被传给r e f i n e m e n t 策略。如果这一候选项不行，则其它的候选项会被尝试， 直到此层中的所有候选项被移除。如果所有的候选项被移除，则递归的增加移 除树的高度并再次尝试，直到整个规划被舍弃，一个完全的重规划被执行。 2 5 8 利用规划模式库方法 在3 2 1 中规划修补中不需要额外的收集信息：例如增加步数的原因，但是需要一 个规划模式库。在重规划中使用一个可算框架，这个框架由资源和动作组成。 1 4 中山大学硕士学位论文智能规划的概述 利用动作和资源规划公式来表示a g e n t 的规划，引入了用于修改规埘的算子并 提出了重规划算法。其中，资源模式是具有同样属性的资源的集合，动作则以 规则的形式给出：a ：r s 2 一 ，其中a 是动作的名字，r s 2 是由a 产生的 资源模式。r s ，是由a 使用的资源模式，c 是在飚- 的约束。目标模式是资源模 式的扩展，表示为g s * - - 。规划模式则表示了一个a g e n t 所能提供的服务 即组织获得目标的动作集。 第一步：利用h o w t o 和o v e r l a p 两个算法将a g e n t 当前规划扩展成所有 可能规划模式。这样会产生一个部分规划的集合，第二步：从这个集合中选择 c h e a p e s t 的一个，并将它移除进行扩展，扩展的结果加入到第一次扩展的结果 中。递归的进行这两步，直到发现一个解为止。最后使用算法 r e m o v ea c t i o n s 将所得的规划化简。 2 5 9 仅使用求精策略 在【k o e n i g ，l i k h a c h e v ，& f u r c y2 0 0 2 中仅仅使用了求精( r e f i n e m e n t ) 策略， 其中用到的l p a l 算法，它是专门用于路径规划修补的一个算法，它首先快速 确定前一规划过程中对新问题不适应的部分，然后利用重规划方法对这些部分 来进行处理。对于给定的图中的结点，如果它们之间的边的代价发生变化，那 么这个算法会重复的得到它们之间的可达的最短路径。它采用后退搜索方法得 到一个与世界状态发生未知改变前具有相同启发式的值的部分规划。从这里开 始仅仅使用求精过程( r e f i n e m e n t ) 。但是s h e r p a 有局限性，它不能对所有的规 划修补问题都有效，仅适用在领域描述中动作被移除的问题中并且移除的动作 在以后的过程中永远都不会再用到的情况。 2 5 1 0 小结 在介绍了规划方法之后，总结了已有修补方法，针对不一致动作的解法各 自有一定的优点。随着规划技术的发展，在规划图的基础上进行修补表现出了 良好的修补效果。于是在图基础上实现规划修补，也可以进行深入的研究。这 也是本文所要做的工作。 1 5 中山大学硕士学位论文基于修补的重规划 2 6 规划问题复杂度 虽然人们对规划问题的研究已经五十多年了，到目前也已经提出了各种各样 的解决方案，但是由于规划问题是一个非常难解决的问题，所以现在能够解决 的规划问题还只是局限于一些像积木世界这样的小问题领域等，关于现实世界 中的一些大而复杂的规划问题仍然没有能够很好地解决，下面看一看前人对于 规划问题从理论上分析其计算复杂性的一些结论： 1 ) 1 9 8 5 年，j o h n c a n n y 证明了形式化的s t r i p s 规划问题是一个 p s p a c e 完全问题3 4 1 2 ) g u p t aa n d n a n 于1 9 9 1 年证明：不论采取什么样的形式化系统， 积木世界问题总是n p 难题( n p h a r d ) 3 5 1 。 3 1领域相关的规划问题至少是n p 完全的【3 6 m 刀。 4 )领域无关性的规划问题是p s p a c e 完全问题或更难，f 3 9 】。 5 1b e r n h a r d n e b e l 于1 9 9 4 年证明了规划问题是n p 难题 4 0 l 。 6 )s e l m a n 于1 9 9 4 年进一步指出：类似于规划的问题是n p 完全 的或更难的p ” 现在所能解决的规划问题还有很大的局限性，也正因如此，规划问题的研究才 具有很大的挑战性。 1 6 中山大学硕士学位论文 修补算法的改进与设计 3 1 动机 第3 章修补算法的改进与设计 3 1 1g p 6 修补算法介绍 在【f a s tp l a na d a p t a t i o nt h r o u g hp l a n n i n gg r a p h s ：l o c a la n ds y s t e m a t i cs e a r c h t e c h n i q u e s 1 4 2 1 1 4 3 1 咩i 提出了两个技术：局部搜索技术和系统搜索技术来进行规划 修改。首先介绍一下系统搜索。其中的a d j u s t - p l a n 算法如下： a l g o r i t h m ：a d j u s t - p l a n i n p u t ：ap l a n1 7 0 ，c o n t a i n i n gs o m ei n c o n s i s t e n c i e sw i t hr e s p e c tt oh ，a n dn c p u t i m el i m i tm a x - a d j n s t t i m e o u t p u t ：e i t h e rac o r r e c tp l a no rf a i l 1 l e t b et h ep l a no b t a i n e df r o mh ob yr e m o v i n gt h ea c t i o n st h a ta r en o t a p p l i c a b l ef o rs o l v i n g 1 7 0 2 i d e n t i f yt h ee a r l i e s tt i m es t e pii i l n c o n t a i n i n ga ni n c o n s i s t e n c y ：i ft h e r ei sn o s u c hat i