（计算机软件与理论专业论文）基于灵活图规划的规划识别算法研究及其实现.pdf

摘要 智能规划与规划识别是人工智能领域近年来发展起来的非常热门的分支。智能规划 的任务是在给定初始条件下寻找一动作序列通过这一动作序列的执行使得世界状态从 初始态到达目标状态；而规划识别是根据观察到的a g e m 的片断的、琐碎的动作来推断 a g e t 的目标及它的规划，从而预测a g e n t 未来的动作序列。i 姐m i g u e l 在2 0 0 0 年提出了 灵活规划器，它引入了一种称为“软”限制的方法，使得能处理经典图规划不能处理的 一些现实问题。另一方面，基于图规划方法的识别方法也倍受关注，根据规划图的建立 和搜索过程，2 0 0 0 年h o n gj u n 提出的目标图可以在图规划框架下解决规划识别问题取 得了很好的效果，由于它是根据规划图的思想建立的，因此目标图的识别方法与传统的 规划识别方法有显著不同，尤其是它无须规划库就可蛆识别出目标的优点。但由于目标 图的识别方法是在经典的图规划的理论基础上，因而它也不具备识别出灵活规划中具有 “软”限制动作或目标的能力。 本文旨在结合灵活规划方法和目标图方法的基础上，深入研究在灵活规划图下的规 划识别方法。在灵活规划框架下根据已观察到的a g e n t 动作、初始条件和目标条件建立 灵活目标图，在灵活目标图的基础上，首先用已观察动作的因果连接进行剪枝，然后使 用已观察动作的满意度进一步剪枝，这两个方法的使用大大降低了灵活目标图的规模， 同时限定了a g e n t 可能采取的规划的范围。 本文考虑由于灵活规划可以得到多个规划解的特性，在剪枝后仍可能存在多个符合 条件的规划解，因此，我们的算法可以得到并存储规划解集合，并在得出的规划解集合 中进一步限定a 眵n t 可能采用的规划。从实验结果表职，本文所介绍的识别方法是切实 可用的，可以解决由于灵活规划的提出，对基于规划图理论框架下的规划识别问题。 关键词：灵活规划；规划识别；人工智能；智能规划 a b s t r a c t n o w a d a y s ，i n t e l l i g e n tp l a n n i n ga n dp l a n n i n gr e c o g n i t i o na r ev e r yb o ib r a c hi na r t i f j c i a l i n t e l l i g e n c e ，t h em a i nt a s ko fi n t e l l i g e n tp l a n n i n gi sf i n do u tas e r i a la c t i o s t h es e r i a la c t i o n s c a nc h a n g et b es t a t eo fw o r l df r o mt h ei n i t i a l i z a t i o nt oi h eg o a l ih o w e v e r ，p l a n n i n gr e c o g n n i o n i su s e dt od e d u c et h eg o a la n dt h ep l a n n i n gt b a tt h ea g e n tu s e ，b a s e do no b s e r v e di n c o m p l e t e a c t i o n s i n2 0 0 0 ，l a m i g u e lb u i l df l e x i b l ep l a n n i n g ，h e 蛔p o nt h e “s o f t ”c o 璐缸缸呲i n t og r a p h p l a n i l i n g ，t l l i s1 e a dt 1 1 ea b i l i t y0 fn e x 王b l ep l a 肌i n gh a v ea 1 0 ti m p r o v ei nd e a lw i t t lt h e 掣o _ b l e m s 证t h er e a lw o d d o nt h eo t h e rh a d ，l o t so ff o c u si sm a d eo nt l l er e c o g n i t i o nb a s e d o nt h eg r a p hp l a 衄i i l g b a s e do nt w op r o c e d u r e so ff a s tp l a l l i l i n g ，b u i l dp l 趾n i n g 伊a p ha n d s e a r c hp l a n ，h o n gj u nm a d et l l eg o a lm e t h o dt os o l v et h er e c o g i l i t i o np r o b l e mi ng r a p h p l a n i l i n gp r o b l e mf h m ea n d9 0 cs u c c e s s t l l i sm e t h o d ，c o m p a r et ot h eo m e rr e c o g n i t i o n m e t h o d s ，h a v ea 伊e a te x c c l l 即c et 1 1 a ti tn e e dn o tt h ew a r e h o u s eo fp l a n s b u tg o a lg r 印hb u i l d b a s i so nt h et h e o r yc l a s s i c a lg r 印hp l a l l 1 1 l e r e f o r ei tc a nn o td e a lw i t ht h e “s o f t ”c o n s t r a i n t a c t i o na n dt a r g e t t h i sp a p e ri si n t e 笋a t e dt h em e t h o d0 fn c x i b l ep l a i l n i n g 趾dg o a l 冒a p h ，a n dr e s e a r c ht h e m e t h o do fp l a n n i n gr e c o g n i t j o n u n d e rt h ef r a m eo fn e x i b l ep l a n n i n g ，w eb u n dt h en e x b l eg o a l g r a p hb a s i s0 no b s e r v e da c t i o n ，i n i t i a lc o n d i t i o n sa n dg o a lc o n d “i 蚰s b a s i s0 nf l e x i b l eg o a l g r a p h ，w eu s et h ec a u s a l j t yt op r u n eb r a n c h e sf i r s t ，u s et h eo b s e r v e da c t i o n st oc u tm o r eb r a n c h e s u s et h e s et w om e t h o d sw i l lr e d u c et h es c a l ef l e x i b l eg o a lg r a p h ，a n dl i m “t h er a n g eo fp l a n st h a t a g e n tc a na d o p t f l e x i b l ep l a n i l i n gc a ng e tm 蛐yp l 柚n i n gr e 蛐l ta ts a m et i m e ，i ts t i 珏h a v em a n yp o s s i b l e r e s u l t sl e f t ，w h e nt h ec u tm e m o dd o n e s 0w ed i s c u s st h em o t h o dt h a tc a l lr e n g n i z et h ep l a n o fa g e n tm a yb ed o t h er e s u l t so fe x p e r i m e n ts h o w st h a tt h ea r i m m e t i ci se 饪e c t i v ei nt h i s p a p e r ，a n dc a ns o l v et h en 铡p r o b l e mu n d e rt h e 盘a m eo f n e x i b l ep l a n i l i n g 。 k e y w o r d s ：f 1 e x i b l ep l a n n i n g ；p 1 a n n i n gr e c o g n i t i o n ；a i ；i n t e l l i g e n tp l a n n i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：日期： 歹口。j y ，卯 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在解密盾适用本授权书) 学位论文作者签名：壅噍蜂指导教师签名： 日期：2 竺：! ：堡日期： 学位论文作者毕业后去向 工作单位： 通讯地址： 电话： 邮编： 引言 在人工智能的研究中规划问题是较早的研究领域之一，近年来，国际上对规划的研 究越来越热，a a a i 和u c a i 中有大约1 4 规划方面的文章从9 8 年开始，u c a l 每两 年举行一届智能规划与调度竞赛。在应用方面，规划技术广泛应用于工厂的作业调度 ( j o bs h 叩s c h e d u l 血g ) 、宇宙航行、车辆调度等领域。m u r p y 等人1 9 9 6 年为美国联邦 太平洋铁路建立了基于规划的自动调度系统【1 】，k h o b i o c k 等人用规划方法解决q u e r v p l 啪i n g 问题，是规划技术在i n t e m e t 上的成功应用【2 】o1 9 9 8 年底，美国的n a s a 发射的 d e e ps p a c eo n e 宇宙飞船的燃料自动控制系统使用了基于s a t 的规划方法1 3 】，这些表明 智能规划的研究已经走出实验室应用于实际，在人工智能领域形成了智能规划这一当前 研究热点。 i a nm i g i l e l 在图规划基础上最早在2 0 0 0 年提出的灵活规划器【2 0 1 ，后又多次对其进 行完善，它除了可以很好处理原始的图规划中的全部问题外，还可以处理许多现实世界 的问题。灵活规划图的特点：( 一) 加入了满意度的概念，从而能够处理原始规划器不 能处理的“软”限制问题，同时也使得具备了度量规划解优劣程序的方法；( 二) 使用 了先进的搜索技术灵活动态限定可满足方法；( 三) 细化了记忆集的概念使搜索更快。 h o n gj u n 在分析了b l u m 和f u r s t 的规划图基础上，建立了基于目标图的规划识别方法。 该方法不需搜索整个规划空间，而是先构造目标图，进而在对目标图的分析完成识别过 程。 如灵活规划图中所描述的，对于相同的问题产生具有不同满意度的多个规划解，对 于每个满意度，仅产生一个与其对应的规划解，而考虑用目标图的方法处理灵活规划的 识别问题时，需要通过对已观察的a g e m 的部分动作识别后续动作和规划，灵活规划图 产生的规划解是不能满足问题的需求的。因此在本文中我们对于相同的满意度得到全部 的规划解，对于这多种规划解，通过对满意度和规划解优劣程序进一步分析，对a g e n t 的规划进行识别。 基于上述思想，本文组织如下，首先对规划问题和灵活规划问题进行了介绍，第二 章在对规划识别的方法和算法做了简单回顾后，重点对h o n gj u n 提出的基于目标图的 规划识别算法进行了分析，在第三章在讨论了基于灵活规划识别算法的必要性后，详述 了基于灵活规划器的规划识别算法思想，在第四章给出基于此算法的例子和实验结果， 最后我们指出未来的工作和发展方向。 1 1 智能规划问题 第一章灵活规划问题 1 1 1 智能规划问题的基本概念 规划过程是一种问题求解方法，一个规划系统我们可以认为就是一个问题求解系 统，若用它求解比较复杂的问题，即可求得一个动作序列( 串行、并行或串并行混合) ， 依次执行此动作序列可以完成某一特定的具体任务，最终达到一个特定目标。 一方面，智能规划是一个多领域交叉的研究领域，它涉及知识表达、知识推理、非 单调逻辑、情景演算、人机交互和知识挖掘等各个方面。在人工智能领域，规划目前还 没有一个统一的定义，m c d e r m o t t 和j a m e sh e n d e l e r 。1 认为“规划就是设计某个( 组) 实体( e n t i t y ) 的动作序列，其结果被称之为规划解( p l a n ) ”。一个规划解实质上就是 一个动作序列，此序列能够实现某一目标，智能规划就是设计这个动作序列的过程，也 就是说它主要解决怎么样做，而不解决为什么。 一般地，我们在做规划之前，大多做以下的假设： 1 规划是动作的序列。 2 动作的执行前件是确定的。 3 动作的执行后件( 效果) 是确定的。 通常，我们把满足以上假设的规划称之为“经典的规划”( c l a s s i c a lp l a n n i n g ) ， 例如地图着色问题、积木世界问题等都是经典的规划问题。现在，大多数研究者还在采 纳此假定，但是由于现实世界的复杂性，实际问题往往并不能满足上述条件，因此也有 一部分人正在研究放宽此假定，研究在环境不断变化情况下的规划问题，不满足此假定 的规划问题称之为“非经典的规划”( n o n c l a s s i c a 卜p l a n n i n g ) 。 由上面的讨论可以发现，规划问题由于其自身的特点，它至少应包括三个部分：初 始状态、目标状态和动作集合。初始状态和目标状态是规划问题的起点和终点，动作是 可能由初始状态到达目标状态的一系列可以执行的动作，定义了状态空间的传递方法。 初始状态和目标状态属于状态的描述，一般用一阶逻辑或命题逻辑来表示。动作( 又称 操作) 主要包括三部分：动作名称、动作前件( 前提条件) 和动作后件( 添加效果) 。 q i a n gy a n g 旧把s t r i p s “1 域下的规划问题定义为一个三元组： ， 其中，i n i t 是初始状态文字的集合，即初始世界模型；g o a l 是目标状态文字，即目标 状态模型；o 是规划操作( 动作) 的集合，也有的称之为域理论。 1 1 2 智能规划的发展 人们对智能规划的研究已经有半个世纪了，最早可以追朔到1 9 5 6 年n e w e l l 、s h a w 2 和s i m o n 设计的逻辑理论家( l o g i c t h e o r i s t ) 程序，这个系统采用了启发式信息和反 向搜索技术，随后他们设计的g p s 系统把领域知识与一般的搜索控制信息相分离，上述 两个系统特别是g p s 在人工智能领域中具有非常重要的地位，但它们还不是真正面向规 划问题研制的智能规划系统。 1 9 6 9 年g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统”3 ， 这一系统被大多数的智能规划研究人员认为是第一个规划器，原因就在于它是第一个面 向现实规划问题提出的规划系统；1 9 7 1 年f i k e s 和n i l s s o n 设计的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 、n o a h 、n o n l i n 等规划系统。由于c h a p m a n 的分析， 使人们认识到简单地利用定理证明的方法来解决规划问题是很难的，因此这以后到1 9 9 0 年间，在人们发现新的求解方法之前，对智能规划的研究陷入了低谷，这期间仅有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 ) 问题，一反定理证明式求解 方法，利用在约束可满足问题算法上的突破，有效地解决了部分规划问题。后来，基于 此理论的b 1 a c k b o x 规划器“”在第一届智能规划器的比赛( 参见附录a ) 中表现了非凡 的解决问题能力，一举夺魁，开辟了解决规划问题的又一新途径。1 9 9 5 年a v r i mb l u m 等设计的图规划系统g r a p h p l a n 。”第一次采用图的方式来解决规划问题，并且提出了用 于规划的规划图的概念。后来很多规划系统都借鉴了图规划系统的方法，参加第一届智 能规划比赛的规划器除委内瑞拉的h s p 外，其它四个规划器s g p 、b l a c k b o x 、i p p 和s t a n 都或多或少地采用了图规划的某种( 些) 技巧，并且对图规划做了相应的扩充：s g p 加 入了用户互操作界面；b 1 a c k b o x 则综合了基于规划图的快速规划扩展和基于s a t 的快 速规划验证的优点；i p p 扩充了图规划的问题描述语言，支持a d l 规划描述语言，它能 够处理条件效果等，这样它的表达能力比图规划器要强大；s t a n 在减少搜索和构造规 划图的费用上做了扩充。这些规划算法都是部分序或非线性的通用规划器，此次比赛表 明部分序方法在规划求解中具有举足轻重的地位。两年以后，在第二属规划比赛上，部 分序规划被人们广泛关注。在参加比赛的十六种规划器中采用启发式知识的有十一个， 并且采用启发式知识的规划器比没有采用启发式知识的规划器得到的规划解效果好：例 如比赛评委评选出的最佳规划器t a l p l a n n e r 和f f ，以及排名其次的s t a n 、h s p 2 、m i p s 和s y s t e mr 都是采用启发式知识的规划器，在此次比赛中采用启发式知识的规划器表 现出很强的问题求解能力，而第一届比赛的冠军b 1 a c k b o x ( g r a p h p l a n + s a t ) 则由于没有 采用启发式知识在此次比赛中表现不如人意。 综上所述，规划问题求解从最初的定理证明方法到s t r i p s 方法是问题求解方法上 的转变，然后又发展了非线性规划器，采用目标导向的方式来生成规划：一方面使得规 划的生成速度大大提高；另一方面，由于是目标导向的生成方式，因此生成规划的质量 比较好。现在人们又在此基础上加入了启发式信息，进一步提高规划求解的效率和质量。 3 1 2 图规划问题描述 l - 2 1g r a p h p l a n 规划器 图规划在两个阶段( p h a s e s ) 交替进行：图扩展( g r a p he x p a n s i o n ) 阶段和解提取 ( s o l u t i o ne x t m c t i o n ) 阶段。图扩展阶段正向扩展规划图宜到目标状态的所有命题都出现 为止。解提取阶段反向搜索规划图以求出规划解。其中的有关定义如下： 规划图( p l a n i l i n gg m p h ) ：是一个具有两类节点和三类边的有向、分层图。规划图 各层是命题层( p r o p o s i t i o n1 e v e l s ) 和动作层( a c t i o nl e v e l s ) 交替出现的，命题层包含命题 节点( 标识为一些命题) ，动作层包含动作节点( 标识为动作) 。三类边是前提条件边 ( p r e c o n d i t i o ne d g e ) ，添加效果边( a d de d g c ) 和删除效果边( d e l e t ee d g c ) 。规划图的 第一层是命题层，包括规划问题初始条件下的所有命题。 有效( v a l i d ) 规划解：规划问题的一个有效规划解是一个动作的集合和对各个动作 发生顺序的指定。 1 2 2 规划图扩张阶段 如上所述，g r a p h p l a 的实现依靠于一种称为规划图的图结构，规划图的扩张阶段 就是建图的过程，简单描述这一方法和过程如下： 我们用一个 四元组来表示g m p h p l a i l 图结构，其中i 、o 、g 、s 分别 为初始条件集合，操作集合，目标集合，当前世界状态集合。图在初始化时给定初始条 件i 、操作o 、目标g 这三个集合。 第一步：把初始条件i 作为图扩张的第一层( 命题第一层) ，把这一层填入s 中， 第二步：在第一层的基础上对0 中的操作逐一的进行实例化，实例化后的操作称 为动作，动作的效果产生为命题，命题记入下一层的命题层，并标记互相冲突的动作和 相互冲突的命题节点。 相互冲突的动作定义为在第i 层两个动作实例( a c t i o ni i l s t a n c e ) 满足以下三者中的 任意一个时，我们称之为具有冲突关系： 1 1 后件( 效果) 不一致( i n c o n s i s l e n t ) ：一个动作的后件是另一个动作后件的否定。 2 ) 冲突( i m e r f e 坤n c e ) ：一个动作删除另一个动作的前件。 3 ) 竞争需要( c o r n p e t i n g c e d s ) ：两个动作具有i 1 层互斥关系的前件。 相互冲突的命题定义为在第i 层的两个命题( p r o p o s i t i o s ) 在以下两种情况下具备 冲突关系： 一个命题是另一个的否定： 不一致支持( i n c o n s i s t e ms u p p o r t ) ：获得此命题的所有动作( 方法) 都具有互斥关 系。 除上述的动作和命题外，规划图还定义有一种称为n o o p 动作的节点，即维持当前 4 的世界状态到下一命题层。 图1 1 规划图层示例 。 。 如上图所示，实心点代表命题节点，空心方框表示动作节点，而虚横线表示n o o p 动作。 第三步：重复第二步的过程，直到g 中的目标全部出现并没有冲突，则此次规划 图扩张阶段结束，进入规划图提取阶段。 1 2 3 有效规划提取阶段 若时间步n 的命题层中包含了所有的目标命题，并且没有一对是互斥的，则停止规 划图的扩张，进入从时间步n 的命题层开始的有效规划搜索阶段。 在时间步n 的命题层中，取定一个目标命题，考察在时间步n 一1 的动作层中以这个 命题为添加效果的动作，从中选定一个，如动作1 。再从余下的目标集合中取定一个命 题，考察在时间步n 一1 的动作层中支持它的动作，从中取定动作2 ，要求动作1 和动作 2 不互斥。如果动作1 和动作2 互斥，则重新选择一个与动作1 不互斥的动作替换动作 2 。依次类推，最后假定从时间步n 1 的动作层中取定动作n ，它支持目标集合中的最后 一个命题，并且它与已经取定的动作1 ，动作2 ，动作n 一1 均不互斥。把动作1 ，动 作2 ，动作n 的前提条件都放在一起，构成一个新的命题集，叫做时间步n 1 的次 目标集。 对于时间步n 1 次目标集合，采用对时间步n 的目标集合选取动作集合的方法，确 定在时间步2 的动作集合和次目标集合，如此前向搜索，如果某个时间步的次目标集 合恰好是初始条件的子集，则找到有效规划，停止搜索。 1 3 灵活图规划 1 3 1 灵活规划发展历程 i a nm i g u e l 在2 0 0 0 年在欧洲第十四次人工智能会议上的论文f l e x i b l eg r a p h p l a n 【2 0 】 第一次提出，在2 0 0 1 年又在它的基础上加入了d c s p 等算法在人工智能工程应用上 得以发表1 ，在2 0 0 2 年的第四届软限制国际会议上由原基础上加入了模糊技术得以发 表，作者又在2 0 0 3 年对得到的结果进一步扩展而引入了f l l z z yr r d f c s p 【2 6 】等技术而发表 在人工智能杂志上。 从上述的灵活规划的简单发展历程上看，它取得了相当大的成功，并将不断向前发 展。 1 3 2 灵活规划解决的问题 场 在现实世界中经典会遇到如下图所示的问题， 1 i 两个包的价值不同( p 1 p 2 ) 2 道路的优劣有异( m 1 ，m 2m i n o r o a d ) 3 因为包的价值不同，从而要求贵重包( p 1 ) 在装载和卸载过程中要求有卫兵在 图1 2 灵活规划图例 由于经典规划器对限制的处理是布尔型的，命题和动作需要定要满足或不满足， 这使得对上面的问题不能对道路进行区分，同样在经典的规划方法也不能对数值进行处 理，在此问题中即不能对包的价值进行，对不同的包进行同等的处理。 综上所述，i a nm i g l l e l 发现此算法有如下的几点不足，即经典图规划方法对处理现 实世界问题过程中的几个限定： n 1 目标全部满足或全部不满足； ( 2 1 应用一个操作是布尔类型的，即全部满足或全都违背，且生成的命题和动作也 是布尔类型的，只能描述确定性的世界状态； ( 3 ) 限制是强制性的( “硬”限制) ； f 4 ) 只提供一个有效规划解。 针对这些不足，i a l lm i g l l e l 提出了灵活图规划方法。 6 1 3 3 灵活规划问题对经典规划的修改 1 规划形式化描述 灵活规划问题仍然表示为和经典规划相同的四元组 ，其中元组的定 义和图规划是相同的，但对操作0 和目标g 的内部表示做了修改，对规划中所用的操 作根据满足在不同情况下不同条件加入了衡量指标满意度( s a t i s f a 嘶o n ) ，相对于动作的 满意度，为规划中命题节点赋值相应真值度。 2 对经典规划方法的修改 ( 1 1 下图中给出了灵活规划器中用到的操作和目标，在目标和操作中都加入了可供 选择的参数( p r e f e r e n c e s ) ，使得操作和目标在多种条件下可以被实例化，降低了原有规 划的强制性限制，如在图1 2 的问题中的运输问题中当包的价值较高时，在没有卫兵在 场时同样可以进行装卸，但操作的满意度会降低，而同样目标在不同的条件下也可以到 达，如包运到不同的城市都可以认为达到不同的目标，且目标具有不同的真值度。 i o p 许砒 o 辔t n 瑚恤“l 辨r d m 2 ，j 吼：h 印( p 健c 明曲巩，吼：) ( e 噍由i 户i 。产b l ( 1 硼咖州o nl ) ( g 嘲 t 训1 e 村日 ( - i t k h c t i o nl ；) t w h 巳( 靠咀啪c n o nb i 图1 3 灵活操作和灵活目标 ( 2 ) 操作描述( 目标的描述和操作基本相同) 一个灵活操作，o 0 ，用前提条件空间映射到全序的满意度l 和一个灵活效果命 题的模糊关系描述。l 由有限的成员量度1 上，u ，1 2 ，1 t 组成。两个端点l 上，1 t 分 别表示不满足和完全满足。o p 动作是特别的具有满意度t 的动作。 灵活操作包含析取条件从旬集合。每个6 是一个三元组( ，r ，1 ( i 分别表示灵 活前提的合取，一个灵活效果命题的合取和给予这些前提的满意度。每个o 的形式 为( p ，巾1 ，巾2 ，巾i t k ) ，其中t 是带参数集合k 的前提操作。允许的前提操 作可以是布尔值，可以是真值之间的连续范围和离散的真值度集合。每个6i 映射一个 前提空间集合到一个特定的效果集合和在l 中的满意度。 ( 3 ) 真值度( t m t hd e 掣e e ) 描述 与每一个命题和动作相联系的真值度是集合k = ( k 上，k 1 ，k 2 ，姐) 中的一 个元素，其中两个端点表示命题为假和命题为真。 ( 4 ) 真值度和满意度计算方法 实例化操作时，对不同的前提条件对应于不同的满意度，所得的满意度即是动作的 满意度，在一个命题中具有多个动作可达时，取动作的最大满意度为命题的真值度，这 个计算方法出于两方面的考意，命题节点相当于动作节点的或运算结果，任个动作节 点都可以到达个命题，因此对动作的满意度取或( 上确界) 的结果就把最大满意度的动作 设为命题的真值度。 1 3 4 灵活图规划执行过程 灵活图规划和图规划( g r a p h p l a l l ) 一样都分为扩张和搜索两个阶段，图结构的定 义和g r a p h p l a 没有区别，规划的执行过程同样分为扩张和搜索两个阶段： ( 1 ) 扩张阶段 如下表所示为灵活规划的扩张过程对原始图规划的扩张过程的区别。 过程比较 图规划( g r a p h p l a l l )灵活图规划 ( f l e x i b l cp 1 a n i l i i l g ) 初始初始条件放于第o 层命题层初始条件放于第o 层命题层 实例化 从第i 层的命题层提取命题与从第i 层的命题层提取命题 操作的前提比较后，把可以实与操作的前提比较，以所有 例化的操作的效果加入第i + 1可能性实例化操作，并把实 命题层例化的操作效果加入第i + 1 命题层 动作冲突计算1 不致的效果1 不一致的效果：两个动作 2 冲突：一个动作的效果命题有相互冲突的效果 是另一个动作的前提的否定2 冲突：一个动作有一个效 命题果命题和另一个动作需要 3 竞争需要 的前提表达不同的真值度 3 竞争需要：动作有相互冲 突的前提 命题冲突 创建一个命题的所有方法与 1 同g r a p h p l a n 创建另一个命题的所有方法 2 两个灵活命题包含的核 都冲突( 两个命题不能包含于心命题( c o r ep r o p o s i t i o n ：在 一个有效规划中)灵活规划中，与g n p h p l a i l 的命 题相同，不具有真值度的命题1 表达不一致的真值度 扩张终止条件 当全部目标到达，就进行下一1 只要一种目标集到达，就 步规划提取阶段 开始进行一次有效规划提 取，并记录这次规划的整体 满意度 2 这种灵活规划的扩张方 法又加入了一个剪枝过程， 即当已有规划解1 i 存在时， 后面的扩张在命题或动作 低于l i 时，就不需实例化这 个命题或动作 8 ( 2 ) 经丌1 ) f c s p ( r e s t r i c t i o n sa i l dr e i a x a t i o n sd y i l a m i cf 1 e x i b l ec s p ) 的灵活规划抽取 ( f 1 e x i b l ep l a ne x t r a c t i o nv i ar r d f c s p ) 当图扩展到某一层，这层中包含有能在某种程度上( 即满意度) 满足灵活规划目标 的一组命题集合时，就开始灵活规划提取的过程。从灵活规划图提取一个规划可以视为 在原始g r a p h p l a n 框架下的般提取过程。在灵活规划中，如果仅包含两种满意度，1 上，l t ( 布尔值) 和相应的两个真值度，k 上，k t ，那么解决的问题就完全和g r a p h p l a n 处理的问题一样，事实上从这个角度来看，完全可以认为灵活规划是g r 印h p l a n 的一个 扩展。 同d c s p 问题致，由于规划提取阶段是从当前层向初始层逐层找到满足支持目标 的变量和值，而灵活规划又包含不同满意度的动作和不同真值度的命题，而规划的目的 是得到又短又好的规划解，从这个目的出发，在灵活规划提取时加入了如下的启发式信 息： 1 )在相同条件下，目标集出现的层数较小且满意度较高的规划解认为比其它的 解更优； 2 )在多个动作支持一个命题时，具有较高满意度的动作优先考虑。 通过加入这两条启发方法，就使得较满意的规划解被先找到的目的。 s u k p r o b l e i n s o l u t 孙n 8 d 娟n 棼 8 u h p b l e m 8 e q u e n c e sa t h en l 搿( tl e v l e i 圈1 4 灵活规划求解顺序 ! ! d i l 鼍! c t o no f ! 黔& n d 醚 ：s o l u t i a 飘 ! e x 董r 8 c t i o n 在n d f ( 笃p 不像基于活动限制的d c s p 求解过程，它预先并不知道问题将怎样改 变，而总是使用前面解决问题的结果去解决后面的问题，从而这种方法可以有效按顺序 把前面解决问题的结果。 r r d f c s p 使用如图1 5 所示的l o c a lc h a n g e s ( l c ) 算法来解决。l c 算法定义三个 变量池，v 1 中的变量分配已经固定( 触e d ) ，v 2 中存放的变量已经分配了值，但没有 固定值，v 3 中的变量是未分配的变量，在不断的为v 1 中分配值和三个变量池的交互 过程使得问题得以解决。 r r i ) f c s p 使用了l c ，使得它在规划提取过程中有两个优势： 1 假如在第g 层和在第g 1 层子问题有某些交集，它能重用这些相似处用以解决当 9 前问题； 2 同样，在规划提取过程中，失败的尝试也能在规划的扩展过程中和之后的规划 提取过程中得到重用； 另外，灵活规划较之经典g r a p h p l a l l 相比，为了增加规划提取速度还添加了些其 它的技术：强迫弧一致、记忆功能、记忆集回传( p m p a g a t e dm e m o s e td i s c o v e r y ) 等技术。 黾。z b = l 配l 玎 | h 瓯 姆，u ，砩瓠，n l = 辑3 ，e 毗 l n i t i ：i 黜挣，斯崩，籼描u # i 篇“m 籼t i m 监 b b 兰缸l ，船，秘，瓤 憾业p # ，* 6 s 龇tt b h ( h i 柑竹d ，靴 弭+ - x v 吣i 喃( q ，夯a x 邶_ # n 掣 地h 诲耸扣l ，靳，瓤l ，h 兰仕3 轴k 科芒h ( 抽捌撕c 【霉】t 黜k c 缸籼# 】 a i i 捌两s t l r 峙舾卅o i 枷，f ( 辩。辩) # 辆r 蚓。强n 鞴卜n v “i 蛔# f 蛳，蛳) a 忡牡# # 竺 邬 t 兰协l ，卿，列 | 婚揣扣时 鲰i 辩t 瑚e 蚝x 蚶d 舯r 和l 蛳k d 掷，* 翻卜圪黜- l ，v d g 睫c ( 辩、端) 董“r 酬 瓤- 抖s u o o 蝉幽 = b 均霄秘 靴。蝴，潮， k h 掣缸$ l 孙i 树张eb 踟i m d 村c c 觏。黼) ，c ( “，# 0 挪- 肘v b h t 鼎r 扭6 。# d ) c 陬辫 ：c h 删划t 5 h 尝 孙k 坞兰协i ，珊，黜b 地盘恤如o 1 3 5 灵活规划图中用到的其它技术 i 且，n d i = x ，气目却，仉= h 钟 翱l 钟t # 皂u t h l d 吖c 社l ，嚣 ，f 睁，# kr 妞，螂l a i i 样械卵i n 删协稍o c ( 辩，摊k 粕诹f h 树m 辫杠，v i 幽t 嘴州辫，摊 q 钟 h t k 惶。 卫】，- ，“ ，h = 忙5 蛳i 婶。掷eh c h e d 舯，轴k d ￥5 ，# 嚣- 扣一x 斟+ - 州_ 哺。陋籼 心铷缸骶耐 粕 聍v i 0 1 咖如乳f ) c h 饿黜 h 兰 l ，茧b k 砘兰 # i 蜘，蛳b 讹竺仕 8 蝻鼬芒h 轴耐d 竹c ( t ) 。c 睁# b ) 2 a + 一p ，卜l ， 卜j vv 栖i 协c f 鹞，瓤 # th6 * 甜 # 4 一茸目 剐# 心 轴h n h i ! # 。抒，赳l ，料崔趣$ 篇，舶= 转，勰富j 图1 5l c 说明图 1 强迫弧一致( e n f o r c i n ga r cc o n s j s t e n c y ) 强迫弧一致的方法思想：如果d i 和d j 两个值域之间存在一个给定的限制“x i ，x j ) ， 要对其成功分配值，则在d i 中的一个元素d i 满足在d j 中至少有一个元素d j 满足限制， 所有不满足这个原则的元素必须从d i 中删除。 这种强迫弧一致可以认为是二元一致，一般在第i 层中的n 命题如果存在有效规划 则一定是k 元一致的，即这个命题可以有值同时分配，而要解决多元一致的问题是 n p 问题。 因而在灵活规划的提取规划时首先对二元致进行了处理，进行了初步的剪技过 程，去掉了一些域中的元素并记忆了这些元素的删除原因，这提高了搜索有效规划的速 度。 1 0 2 甚 乙功能 强迫弧一致没能处理所有的冲突( 仅是二元不一致) ，留下的问题仍需用搜索方法解 决，因此在搜索过程中加入一定的剪枝方法是必要的，而原有图规划中的记忆功能是非 常有限的，因此在灵活规划解决问题时同样也实现了一种新的记忆功能。 记忆功能是记录不支持的集合的过程，这种集合我们称作记忆集( m e m o s e t s ) 。当同 样的记忆集在同层再次遇到就可以迅速对其剪枝，记忆分为两种： 1 ) 当强迫弧致删除元素时的记忆删除的节点； 2 ) 在搜索过程中发现一个“死胡同”( d e a de n d ) 时，当前变量域的所有元素是与当 前的部分任务分配是不匹配的，形成一个“冲突集”。 由于冲突集可能发生多次比较和遍历，因此要求它要尽量的小，它的规模比较小， 将导致更快的速度，因此在记忆集的记录过程中又进行了无关的变量的测试。 无关变量：如果删除冲突集中的某变量，则冲突集仍然是冲突的，因此它的存在 对冲突集没有作用，称为无关变量。 轴b _ p m b l 舯 图1 6 冲突集中的无关变量 如上图所示，在图中x 1 ，x 2 ，x 3 已经是冲突的，x 4 就没有加入冲突集的必要，当 没有可以删除的变量时，我们就说最终的冲突集为微问题( m i c r o - p d 0 b l e m ) 。 3 记忆集回传( p r o p a g a t e dm e m o s e td i s v e r y ) 生成的第i 1 层记忆集可以由动作回溯到第i 层，这样的方法对第i 层的进一步提 取是有益的，但由于一般情况下一个动作有多个效果命题，所以可以对这些效果命题选 取出与当前的目标命题集交集最大的子问题。这黏方法可以找出最有可能导致记忆集的 变量集，从而再次限定搜索范围。 4 关注搜索( f b c u s i l l gt h es e a r c h ) 在解决限定可满足问题时，提早发现失败的分配可以大大提高搜索效率，同样提早 发现“死胡同”也可以达到有效的剪枝。优先找到小的子问题可以达到最有效的减枝效 果。 在灵活规划搜索过程中总是优先选择具有较小r 柚k 值的变量，将会更快的提升搜 索速度。变量r a n k 的计算是采用了累加产生它的上层节点数。计算后的r a n k 同样可以 在强迫弧一致过程中使用，在弧一致问题的解决过程中优先选择那些r 剐【l k 值较小的限 制会加快速度，限制的m k 值是与它相关的两个域变量的m n k 值的和。 第二章图规划框架下的规划识别算法 2 1 规划识别概述 规划识别是根据观察到的片段琐碎的现象，推出具有合理的因果联系的完整而全面 的规划描述的过程。一个规划识别器得出的规划能补充一些我们未观察到而又实际发生 的现象，同时还可以预测未来合理地推出a g e n t 未来可能采取的动作。 一般认为，一个规划识别问题有以下部分组成： 一个动作描述集合； 一个有限的、动态世界的对象集合； 一个称为初始条件的命题集合： 一个目标描述集合( 详细说明可能的目标) ； 一个已观察到的动作集合，它们可能局部有序； 一个明确的分离的时间步集合。 如下图所示，假设我们观察到j o h n 做好了调味汁，现在正在烧水。那么，基于如 图2 1 所示的规划，有理由相信j o l l n 的目标是做p a s t a ，同时可以预测他下一步是煮面 条，而且已经做好面条。 o 暇虑凡槲l 瓤绦，回撇翻袈 融溯味 回烧水，回谶嘲袭a 稚醒舟 图2 1 做面条的规划识别例子 规划识别的应用领域很广泛，规划识别主要应用在故事理解、自然语言识别、谈话 分析、心理学模型和智能计算机接口等领域，随着规划识别的发展，它的应用领域也逐 渐地在扩展。 2 2 规划识别的分类 规划识别根据被推理的a g e n t 在规划识别中的作用可以分为两类： 1 _ 洞孔式规划识别( k e y h o l er e c o 弘i t i o n ) ： 这种识别在识别过程中，被观察和推 理的a g e n t 不影响规划识别过程，通过不引人注目的观察来推断a g e n t 的目标，而a g e n t 只管做它自己的事。 2 有意的规划识别( i i l t e n d e dr c c o g n i t i o n ) ：这种识别