（计算机软件与理论专业论文）基于解释图剪枝算法的概率规划识别系统的研究及实现.pdf

摘要 规划识别是指规划识别器根据观察到的智能体( 一个或多个) 的片断的、琐碎的动 作，推测出在一定程度上具有合理因果关系的智能体将要执行的动作和欲实现的目标， 即推导出智能体正在执行的规划。但是，通常无二义性地确定一个规划假设是很困难的， 因为在许多领域，或者一个动作服务于多个目标，或者被识别域中存在多规划甚至是多 智能体多规划并行执行，而且，其中的许多领域仅仅是部分可观察的等等这些问题的 存在限制了许多规划识别方法的应用。比如，没有状态转移概率模型的复杂领域的大规 模特性使得抽象马尔可夫模型的应用变得困难；基于概率语法的方法无法处理多规划交 替并行实现的问题；采用语法分析的方法，虽然搜寻速度快，但无法处理时序约束等等。 g o l d m a n 和g e i b 于1 9 9 9 年提出了一种新的基于规划执行的规划识别模型，之后又于 2 0 0 5 年加以完善，其方法不仅可以识别偏序规划及多规划交替执行，还可以处理域的部 分可观察问题。但是，随着考虑的未观察动作在整个规划假设中所占比例的增加，其效 率将明显下降。 在本文中，我们提出了一种新的规划识别方法基于解释图剪枝技术的规划识别 算法，该算法在给出新的软时序约束和硬时序约束的概念的基础上，以高效的图搜索为 基础，以解释图的剪枝技术为核心，利用本文中定义的两种时序约束来推测未观察动作， 扩展解释图，并利用软时序约束对当前解释图进行剪枝，以精确目标假设集合，然后计 算各目标假设的概率，并以之对目标假设进行分级与选择，最后对所选目标假设子树进 行扩展，即可得到完整的规划假设。同时，本文还引入了支持程度的概念，以使规划识 别可以随着收集到越来越多的证据而合理地改变。该算法不仅可以有效处理域的部分可 观察问题和偏序规划及多规划交替执行等问题，还可以排除智能体的误导动作，这将在 网络安全及入侵检测等许多领域都有广阔的应用前景。 在给出算法的基础上，本文采用c + + 语言对该算法进行了实现，设计了基于解释图 剪枝技术的概率规划识别系统e g p p r ，并用实例对其性能加以测试，结果表明，该系 统完全可以达到理论预期效果，即不仅可以识别出智能体的目标和已经发生却未被观察 到的动作，还可以推测出智能体将要执行的动作，以及排除干扰动作等，这一性能将有 相当可观的应用价值，尤其是在敌对领域，推测出智能体将要执行的动作将是对敌方正 在执行的规划进行应对的至关重要的依据和基础。而且，由于目前国内尚没有一款公开 的成形的规划识别器，所以本文的e g p p r 系统将以其创新性而具有较大的研究价值与 可观的应用前景。 关键词：规划识别；解释图剪枝；硬时序约束；软时序约柬 a b s t r a c t p l a nr e c o g n i t i o nm e a n st h a tt h er e c o g n i z e ro b s e r v e st h ei m p o v e r i s h e da n df r a g m e n t e d d e s c r i p t i o no fa c t i o n sp e r f o r m e db yo n eo rm o g ea g e n t sa n dt h e ni n f e r sar i c ha n dh i g h l y i n t e n e h t e dd e s c r i p t i o n t h en e wd e s c r i p t i o nf i l l so u td e t a i l so ft h es e t t i n ga n dp r e d i c t st h e 9 0 a l sa n df i l t u r ea c t i o n so ft h ea g e n t b u ti t j su s u a l l yv e r yd i f f i c u l tt oc o n f i _ r l np l a n h y p o t h e s e su n i q u e l y , b e c a u s et h e r ei ss o m ed o m a i n si nw h i c ht h e r ee x i s t ss o m ea c t i o n st h a t c o n t r i b u t et om o r et h a no n eg o a l ，o ri nt h eo b s e r v e dd 咖a i n t h ea g e n tp u r s u e sm u l t i p l ep l a n s s i m u l t a n e o u s l y , a n df u r t h e rm o r e , s o m eo ft h e s ed o m a i n sa l eo n l yp a r t i a l l yo b s e r v a b l e t h e e x i s t e n c eo ft h e s ep r o b l e m sp r e v e n t st h ea p p l i c a t i o no fs o m ee x i s t e n tp l a nr e c o g n i t i o n m e t h o d st or e a lw o r l dp r o b l e m f o re x a m p l e , t h el a r g en u m b e ro fc o m p l e xd o m a i nf e a t u r e s , w i t h o u tp m b a b i l i s t i cs t a t et r a n s i t i o nm o d e l sm a k e su s i n ga na b s t r a c tm a r k o vm o d e l ( a m 啪 d i f f i c u l t ；m e t h o d sb a s e do i lp r o b a b i f i s f i cg r a m m a r sd on o th a n d l ec o n c u r r e n ta n di n t e r l e a v e d g o a l s ；a l t h o u g hi ts e a r c h e sf a s t , m e t h o d sb u s e do ng r a m m a rp a r s i n gc a nn o tt r e a to r d e r i n g c o n s t r a i n t s e t c g o l d m a n g c mh a v ep u tf o r w a r dad e wm o d e lo fp l a nr e c o g n i t i o nb a s e do n p l a ne x e c u t i o ni n1 9 9 9 , a n dt h e ni m p r o v e di ti n2 0 0 5 t h e i rm e t h o dc a n n o to n l yr e c o g n i z et h e p a r t i a l l yo r d e r e do fi n t e r l v e d , m a l f i # ep l a n s , b u ta l s ot r e a tt h ep a r t i a lo b s e r v a b i l i t yo ft h e d o m a i n s b u t , w i t ht h er a t i oo ft h eu n o b s e r v e da c t i o ni n t h ew h o l ep l a nh y p o t h e s e si n c r e a s i n g , t h ee f f i c i e n c yo ft h ea l g o r i t h mw i l ld e c r e a s es h a r p l y i nt h i sp a p e r , w eh a v ep u tf o r w a r dan o v e lp l a nr e c o g n i t i o nm e t h o d , t h ec o r eo fw h i c hi s e g p r u n i n g t h i sn e wa l g o r i t h m , i sb a s e do nt h ee f f e c t i v eg r a p hs e a r c h i n g , a n di n f e r st h e u n o b s e f y e da c t i o n su s i n gt h et w ok i n d so fo r d e r i n gc o n s t r a i n t sd c 缅e di nt h i sp a p e r t h r o u g h e x t e n d i n ge g , p r u n e st h ec u r r e n te gb ys o f to l d e r i n gc o n s t r a i n t sc h e c k i n gt om a k et h es e to f g o a lh y p o t h e s e sr e s t r i c t e d a n dt h e nc o m p u t e st h ep r o b a b i l i t i e so ft h eg o a th y p o t h e s e st o g r a d et h e m ，f i n a l l y , i te x t e n d st h eg o a lh y p o t h e s e ss u b - t r e e ss e l e c t e da c c o r d i n gt ot h e i r p r o b a b i l i t i e st oa t t a i nt h ew h o l ep l a nh y p o t h e s e s m e a n w h i l e ，w eh a v ei n t r o d u c e dt h ec o n c e p t o fs u p p o r t i n gd e g r e et om a k et h er e c o g n i t i o nc h a n g er e a s o n a b l ew i t hm o r ee v i d e n c ec o l l e c t e d p r o f i tf r o mt h e s es t e p s , o u rn e wa l g o r i t h mc l a r i f i e san u m b e ro fi s s u e st h a tw e r eo b s c u r e db y p r e v i o u sa p p m a c h e s i np a r t i c u l a r , i t 锄h a n d l ep a r t i a lo b s e r v a t i o no fd o m a i n s ，p a r t i a l l y o r d e r e dp l a n sa n dm u l t i p l e , i n t e r l e a v e dp l a n s f u r t h e r , i ti sa b l et oe l i m i n a t et h ea g e n t s m i s l e a d i n ga c t i o n s t h ei m p l e m e n t a t i o no ft h i sa l g o r i t h mw i l lh a v eav e r yc o n s i d e r a b l e p r o s p e c ti nc o m p u t e rn e t w o r ks e c u r i t ya n di n t r u s i o nd e t e c t i o n b a s e do nt h ea l g o r i t h mp r o p o s e da b o v e , w eh a v ei m p l e m e n t e dan e w p l a nr e c o g n i t i o n s y s t e m e g p p r ，w h i c hc a n n o to n l yr e c o g n i z et h ep l a na n dt h eg o a lt h ea g e n tb e i n gp e r f o r m e d e f f i c i e n t l y , b u ta l s oi n d i c a t et h ea c t i o n st h ea g e n tw i l lt a k e ，a n da l s oe x c l u d et h em i s l e a d i n g a c t i o n st o o m o r eo v e r , a st h e ei s1 1 0r e a d yp l a nr e c o g n i t i o ns y s t e mi n l a n d , s oo u re g p p r s y s t e mw i l lb es i g n i f i c a n tb o t h i nr e s e a r c ha n dp r a c t i c ed u et oi t sn o v e l t y k e yw o r d s ：p l a nr e c o g n i t i o n ；e g - p n m i n g ；h a r do r d e r i n gc o n s t r a i n t ；s o f to “i e r i n g c o n s t r a i n t h i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意 学位论文作者签名：日期：丝盈叁翌 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：塑：杰压7 指导教师签名： e t 期：诬盈：p 日 期： 学位论文作者毕业后去向； 工作单位： 通讯地址： 电话： 邮编： 引言 规划是人工智能中一个引趋相关学者极大兴趣的领域。一个原因是规划结合了我们 迄今为止已经讨论过的越的两个主要领域：搜索和逻辑也就是说规划器既能被视为 搜索解的程序，也能被视为( 构造性地) 证明解存在的程序。随着研究的深入，规划的应 用越来越广泛，目前，规划技术已经广泛应用于工厂的作业调度、宇宙航行以及车辆调 度等领域。特别是1 9 9 8 年底，美国的n a s a 发射的d e e ps p a c eo n e 宇宙飞船的燃料 自动控制系统使用了基于s a t 的规划方法，表明智能规划的研究已经走出实验室应用 于实际生产生活中。 规划识别1 1 l 是人工智能中与规划密切相关的另一个活跃的研究课题规划识别问题 是指从观察到的某一智能体的动作或动作效果出发，推导出该智能体目标，规划的过程 i 习早期的规划识别是基于规则推理的，研究者试图与推理规则保持一致，以此来掌握 规划识别的特性。如今很多推理技术都在规划识别中有所应用。但是，通常无二义性地 确定一个规划假设是很困难的，因为在许多领域，或者一个动作服务于多个目标，或者 被识别域中存在多规划甚至是多智能体多规划并行执行的情况，而且，其中的许多领域 仅仅是部分可观察的等等这些问题的存在限制了许多规划识别方法的应用，例如，没 有状态转移概率模型的复杂领域的大规模特性使得抽象马尔可夫模型1 3 l 的应用变得困 难；基于概率语法【4 l 的方法无法处理多规划交替并行实现的问题；采用语法分析1 5 j 的方 法，虽然搜寻速度快，但无法处理时序约束等等g o l d m a n 和g c i b 于1 9 9 9 年提出了一 种新的基于规划执行的规划识别模型嗍，之后又于2 0 0 5 年1 7 l 加以完善，其方法不仅可以 识别偏序规划及多规划交替执行，还可以处理域的部分可观察问题但是，随着考虑的 未观察动作在整个规划假设中所占比例的增加，其效率将明显下降 在本文中，我们提出了一种新的规划识别方法基于解释图剪枝技术的规划识别 算法( e g p p r ) ，并用c 年+ 对其加以实现，设计了e g p p r 规划识别系统。该系统不仅可 以保证在常规识别任务中的有效性与高效性，而且还在很大程度上突破了以上问题的限 制。 与g o l d m a n 和g c i b 的方法相似，我们的方法也可适用于部分可观察领域，可识别 偏序规划及交替执行的多规划，而且，也以层次( 任务分解) 规划作为规划表示，简便直 观。 与g o l d m a n 和g e i b 的方法不同的是，我们向层次图中加入了软时序约束和硬时序 约束两种时序约束信息，醴便有效推出未观察动作以快速精确目标假设范围，并且还向 图中引入了支持程度【8 l 等概念，使得规划的识别可以随着收集到的新证据而合理地加以 改变。与g o l d m a n 和g e i b 方法中的对智能体将采取的动作的前向推测相反，本算法更 1 侧重于对未观察动作的后向推理，并将规划识别问题转化为图搜索问题，通过剪枝技术 避免了推理过程中的组合爆炸，因而其效率更高。 2 第一章智能规划概述 这一章主要包括智能规划的基本概念、发展以及描述语言等虽然本文主要是研究 规划识别，但笔者认为加上介绍规划的一章仍然是必要的，因为欲对规划进行识别，必 先对规划有系统的了解，包括其概念、方法、发展及语言等，而且在规划识别过程中， 由于处理的对象仍是规划，所以要想所开发的算法及系统能够广泛应用，并易于扩展， 就必须使用规范的规划定义及描述语言。 1 1 智能规划的基本概念 智能规划起源于状态空间搜索、定理证明和控制理论的研究，以及机器人技术、调 度和其它领域的实际需要。它是一个多学科交叉的研究领域，涉及知识表达、知识推理、 非单调逻辑、情景演算、人机交互和知识挖掘等各方面的知识 在人工智能领域，规划目前还没有统一的定义，m c d e r m o t t 和j a m e sh e n d e l e r 认为 “规划就是设计某个( 组) 实体( e n t i t y ) 的动作序列，其结果被称之为规划解” 9 1 。 简单地说，提出能达到一定目标的行动序列的任务称为规划。 智能规划系统实际上是一个应用软件，当给定初始状态和目标状态以及可用的相关 操作后，该软件就可以给出从初始状态到达目标状态的规划解，也就是自动给出一个动 作序列，使得系统在初始状态下通过执行这个动作序列，就可以达到目标状态 一个规划问题( p l a n n i n gp r o b l e m ) 通常包括以下四个集合 1 0 1 ： 1 一个操作( o p e r a t o r s ) 的集合，包括可执行的操作 2 一个对象( o b j e c t s ) 的集合，给出该规划问题中涉及到的所有对象 3 一个初始条件( j n i t i a lc o n d i t i o n s ) 的集合，其中每个元素都是一个命题，给出问 题的初始状态。 4 一个目标( g o a l s ) 的集合，其中每个元素都是一个命题，而且要求规划结束时这 些命题必须是真命题，也就是规划结束时，这些目标必须实现。 面对这样一个规划问题，规划系统要解决的问题是：在初始条件下，给出一个动作 序列，也就是给出对对象实施怎样一些操作，才能使问题目标得以实现 通常情况下，我们都假设规划环境是完全可观察的、确定性的、有限的、静态的( 只 有当智能体行动时才发生变化) 以及离散的( 对于时间、行动、对象以及效果) ，这些被 称为“经典规划”( c l a s s i c a lp l a n n i n g ) 环境，例如地图着色问题、积木世界闯题等。现 在，许多研究者还在采纳此假定但是由于现实世界的复杂性，实际问题环境往往是部 分可观察的或随机的，被称为“非经典规划”环境。随着规划技术应用的逐渐推广，非 3 经典规划问题吸引着越来越多人的注意力 1 2 智能规划的发展 智能规划是人工智能领域的一个经典问题，其研究始于2 0 世纪年代，主要依据 两个已得到深入开发的技术：状态空间搜索和定理证明历经近半个世纪，智能规划的 发展是曲折而复杂的，下面我们就以各个阶段里程碑式的规划系统为参考点，来概括一 下智能规划的发展路线与趋势 s t r i p s ( f i k e s 和n i l s o n ，1 9 7 1 ) i n l ，作为s r i 的s h a k c y 机器人项目软件的规划部 分而设计，可以算为第一个主流规划器系统，其整体控制结构以g p s 为模型，采用了 o a 3 定理证明系统的一个版本作为用来确定行动前提的真值的子程序，解决了框架公 理问题，对推动规划技术的研究具有划时代的意义 t w e a k ( c h a p m a n ，1 9 8 7 ) 是当时规划研究的一个逻辑重建和简化工作：它的形式 化表示足够清晰，允许证明规划问题的各种不同形式化方法的完备性和不可操作性( n p 难题和不可判定性) ，但同时，它的出现也使人们认识到简单地利用定理证明的方法来 解决规划问题是很难的，因此，直到人们在1 9 9 0 年发现新的求解方法之前，对智能规 划的研究陷入了低谷，这期间仅有s i p e 、a b t w e a k 和p r o d i g y 等智能规划器出现。 9 0 年代，规划系统的研究达到高潮。 1 9 9 2 年，k a u t z 和s e l m a n 受到可满足性问题的贪婪局部搜索的意外成功的启发， 提出了可满足性规划和s a t p l a n 算法1 1 2 1 ，将规划翻译成命题可满足性加以解决 1 9 9 5 年，b l u n t 和f u r s t 提出的g r a p h p l a n 方法【1 3 10 4 1 ，使规划领域获得新生，它比 当时的偏序规划器快几个数量级。由于图规划算法的高效性，后来很多研究者都致力于 扩展g r a p h p l a n 来解决更多的问题，如口p 、c g p 、s g p 、t g p 以及p g p 等规划器都是 在此基础上发展而来的 1 9 9 6 年，d r e wm c d e r m o t t 的l i n p o p 程序成为状态空间规划再度兴起的先锋，这 是第一次提出基于忽略删除表的松弛问题的距离启发式 1 9 9 8 年，b o n e r 和g e f f e r 提出的启发式搜索规划1 1 5 l ( h s p ) 及其后来的衍生体( b o n e t 和g e f f c r ，1 9 9 9 ) 第一次将状态空问搜索应用于大规模规划问题到目前为止，最成功 的状态空间搜索器是h o f f m a n n ( 2 0 0 0 ) 的f a s t f o r w a r d 或称f f ，2 0 0 0 年a l i s 规划 竞赛的获胜者。f f 使用了一个简化规划图启发式和一个用新颖的方式把前向搜索与局 部搜索相结合的非常快速的搜索算法。 最近，人们对用二元决策表来进行规划表示产生了兴趣，c h n a t t i 等人于1 9 9 8 年提 出了基于该方法的规划器 自从规划搜索出现以来，它已经成为人工智能的中心问题之一，关于规划的论文是 主流人工智能期刊和会议的重要来源。也有专门的会议，例如“人工智能规划系统国际 会议”( i n t e r n a t i o n a l c o n f e r e n c e o n a i p l a n n i n g s y s t e m s ，a l p s ) ，“空间规划和调度国际 专题研讨会”( i n t e r n a t i o n a lw o r k s h o po np l a n n i n ga n ds c h e d u l i n gf o rs p a c e ) 以及“欧洲规 4 划会议”( e u r o p e a nc o n f e r e n c eo np h n n i n g ) 等 1 3 规划问题描述语言 规划问题定义是规划问题求解的前提，如果一个规划问题不能通过规划语言来表 示，则任何一个规划器都不能对它进行求解，所以说规划语言的发展是智能规划发展的 关键。 1 9 7 1 年，f i k e s 和n i l s o n 的s 1 r 口s 1 1 6 1 系统在智能规划的发展中具有划时代的意义， 但是其使用的行动表示要比它的算法方法更具有影响力，因为它使得规划可以非常容易 地进行描述和操作。从那时开始，几乎所有的规划系统都使用了s t r i p s 语言的一个或 另一个变种。不幸的是，变种的激增增加了比较中不必要的困难。而且，随着规划技术 的应用的逐渐推广，人们发觉s t r 口s 的表达能力非常有限，不能满足一些实际问题的 模型化要求，因此，设计一种能够刻画和模型化一个实际问题的规划问题定义语言便成 为了规划技术应用的关键。 随着时问的推移，人们对形式化方法中的局限与折中有了更好的理解，1 9 9 6 年 e p e d n a u l t | 1 7 l 提出了动作描述语言a d l 似c t i d e s c r i p t i o nl a n g u a g e ) a d l 除了具 有s t r i p s 的表达能力外，还放松了s t r i p s 语言中的一些限制，具有表达条件效果、 量化效果等语言特征，可以对更多实际问题进行编码 1 9 9 8 年，d r e wm c d e r m o t t i t s | 等提出了规划领域定义语言( p d d l ) ，并作为一种计 算机可分析的标准化语法被引入它不仅能够表示s t r i p s 、a d l 以及其它语言，还能 够刻画规划问题的时间和数值方面的属性，超过了现有的规划器所能处理的表达能力， 给规划器的发展提出了挑战，指明了发展的方向自1 9 9 8 年以来，p d d l 已经作为在 a i p s 会议上规划竞赛的标准语言使用 总之，从s t r i p s 到a d l 再到p d d l 语言，我们可以看出，规划语言的表达能力 越来越强，而且规划语言逐渐从实际应用的模型化角度来增强表达能力 5 第二章规划识别的研究与发展 2 1 规划识别概述 规划识别是人工智能中一个活跃的研究领域规划识别问题是指从观察到的某一智 能体的动作或动作效果出发，推导出该智能体目标，规划的过程 完成这种识别过程的软件或系统，被称为规划识别器 2 2 规划识别的发展 规划识别自从于1 9 7 8 年被s c h n l i d l ，s d d h a m n 和g d s 蚰作为一个独立的研究问 题提出来至今，已历经3 0 多年的发展，其方法日臻成熟 1 9 8 5 年，c h a r n i a k 和m c d e m o t t 提出溯因理论是进行规划识别的最好方式【删，唯 有以此方式才能推导出最合理的目标解释 1 9 8 6 年，k a u t z 和a l l e n 第一次形式化了规划识别理论闭，提出了基于限定理论和 最小化集合思想的通用框架，这是规划识别研究的一个里程碑 1 9 9 0 年，v i l a i n 以k a u t z 理论为基础提出了一种基于语法分析的规划识别理论【2 1 1 ， 该方法虽然有搜索速度快的优点，但是表达能力不如k a u t z 的方法，而且，如前文所述， 它也无法处理时序约束问题 同年，c a r b e r r y 将d e m p s t e r - s h a f c r 理论应用到规划识别中1 2 2 l ，通过多个证据来计 算规划假设的联合支持度 1 9 9 1 年，c h a r n i a k 和g o l d m a n 构建了规划识别的第一个概率模型l 珏2 4 l ，并将贝叶 斯网络应用到规划识别中，这使得规划识别方法向更广泛的应用又迈进了步 1 9 9 5 年，h o n gj u n 从b l u m 和f u r s t 提出的规划图中得到灵感，提出基于目标图的 规划识别闭，极大地提高了规划识别的速度。 1 9 9 9 年，g o l d m a n 和g e i b 提出了基于规划执行的规划识别算法闭，并将之用于入 侵检测系统田l 。该算法虽然能处理环境的部分可观察问题、多规划交替问题和支持多 目标的动作问题，但在考虑未观察动作的识别问题时，算法效率不高 2 0 0 2 年，姜云飞教授在一种基于规划知识图的规划识别算法中提出了一种新 的规划表示方法及规划知识图的概念，与目前规划识别领域广泛使用的k a u l z 方法相 比，新的规划表示方法更加简便直观，而且由于在规划知识图中增加了支持程度的概念， 使得规划的识别可以随着收集到的新证据而合理地改变【2 8 l 。 6 2 0 0 3 年，y mm i n g h a o 在h o n gj u n 目标图的基础上提出了利用回归图进行规划识 别。回归图由命题结点、动作结点和目标结点组成他将回归图中的结点分成确定的结 点和可能的结点以识别确定的目标和可能的目标该方法既保留了目标图分析的方法的 优点，又有自己独特的优势：能识别出确定的一致目标和可能的一致目标例。 同年，f r a n km u l d e r 和f r a n sv o o r b r a a k d 对战术规划识别进行了形式化描述，给出 规划识别过程中观察的不确定性观察的不确定性可以分为四种：可识别的观察，观察 中的动作以及动作的对象都可被唯一识别：不可识别的观察，可观察到动作，但识别不 了动作的对象；概率观察，观察者能够估计观察中某个变量的值；不确定的观察，观察本 身就是不确定的，每个观察都有一个信任程度刚。 由规划识别的发展历程，我们可以看出，随着新方法的不断提出，规划识别技术可 以处理的问题越来越多，越来越复杂，从而使其应用前景也越来越广泛 2 3 规划识别分类 根据不同的标准，规划识别有多种不同的分类方法，概括起来主要有以下几种p l l ； 2 3 1 根据智能体在规划识别中的作用分类 根据智能体在规划识别中的作用，对规划识别进行分类，是规划识别中最常用的分 类方法。最初这种分类中只包括两种识别：洞孔式规划识别和协作式规划识别，2 0 0 1 年，g e i b 和g o l d m a n 又在此基础上增加了对手式规划识别1 3 2 】。 1 洞孔式规划识别：智能体不关心或者不知道识别器正在对其规划或目标进行识 别，因此在识别器识别的过程中，智能体不会有意影响其工作，即既不会有意帮助，也 不会刻意阻碍。 2 协作式规划识别：智能体积极配合识别器的工作，智能体所做的动作有意让识 别器理解。 3 对手式规划识别：智能体会有意阻止或干扰识别器对它的识别 洞孔式的规划识别主要应用在生产监控和智能用户接口等领域，协作式规划识别则 主要应用于机器人足球、故事理解等需要双方协作的领域，而对手式规划识别则应用在 入侵检测和军事指挥等敌对的环境中 2 3 2 根据规划识别是否具有规划库分类 根据规划识别是否具有规划库，可将规划识别分为有库的规划识别和无库的规划识 别。 1 有库的规划识别：用分层任务网络、事件层、知识图或其他方式预先描述规划， 并用这些规划作为规划识别的依据。这些预先给定的规划就组成规划库 2 无库的规划识别：识别器不需要预先给定规划库就能给出识别结果。 7 目前大部分的规划识别方法都是有库的规划识别。这种方法最大的优点是直观、易 于理解，但是用这种方法进行识别前，需要做大量的建立规划库的准备工作，在搜索过 程中，常常又会消耗大量时间或空间 无库的规划识别突破了必须有特定规划库才能进行规划识别的限制，因此可以识别 出新的规划，比较适合入侵检测等敌对环境。但是，由于这种方法还不完善，不能判断 规划假设的优劣，因此其可应用领域还比较狭窄。现有的无库规划识别的方法很少，主 要是以h o n gj u n 的基于目标图分析的规划识别方法和y 缸t i n g h a o 的基于回归图的规 划识别方法为代表。 2 3 3 根据规划识别是否有完备的领域知识分类 据规划识别器所具有的领域知识的完备与否，可将规划识别问题分为有完备领域知 识的规划识别和无完备领域知识的规划识别。 1 有完备领域知识的规划识别：识别器完全掌握动作的前提、效果及动作的执行 概率等情况 2 无完备领域知识的规划识别：识别器不能完全掌握动作的前提、效果或动作的 执行概率等情况。 由于后者复杂度较高，难度较大，因此目前的规划器大都假设识别器具有完备的领 域知识。 2 j 4 根据所识别的动作序列是否完全可观察分类 1 完全可观察规划识别：智能体执行动作的情况对识别器来说是完全可观察的， 即识别器能够观察到所识别智能体的全部动作及动作的执行顺序 2 部分可观察规划识别：智能体执行动作的情况对识别器来说是部分可观察的， 即识别器不能观察到所识别智能体的全部动作 完全可观察的规划识别比部分可观察的规划识别要相对简单，通常情况下人们都是 假设所观察的动作序列是完全可观察的，以降低识别的难度但是，在现实生活中，尤 其是识别方与被识别方处于敌对关系的情况下，想要得到对方的全部动作信息基本上是 不可能的，因此部分可观察规划识别有更高的研究价值。 2 3 5 根据观察结果是否可信赖分类 1 观察结果可信赖的规划识别：所观察到的动作就是实际发生了的动作，对这些 动作所傲的规划识别就是观察可信赖的规划识别 2 观察结果不可信赖的规划识别：在这种识别中，所观察到的有些动作不能完全 肯定是否真实发生了，它们的发生带有一种可能性。这种动作通常都被赋一个可信度， 以确定该动作可信赖的程度。 由于识别器的疏忽或某些情况的干扰，识别器可能无法确定一些动作是否真实发 8 生，因此导致了观察不可信赖。为使问题求解更容易，或者某些领域不存在不可信赖的 动作，通常的规划识别都假设观察是可信赖的 以上只列出几种主要的分类方法，当然，规划识别还可有其它不同的分类方法，比 如根据所识别的规划是否有错误，又可分为无误规划识别和有误规划识别等 2 4 规划识别方法 就识别方法而言，规划识别可分为基于一致的规划识别和基于概率的规划识别。“一 致”主要是指与推理规则保持一致，而加入概率推理的即为基于概率的规划识别。本文 的工作主要是基于概率的规划识别。 2 4 1 基于事件层的规划识别 1 9 8 6 年，k a u t z 和a l l e n 第一次形式化了规划识别理论，提出了一种通用的规划识 别模型，其中，他们将动作和规划统称为事件，用事件层来表示已知的可能规划在事 件层中，根结点为高层动作，其他动作均依赖于高层动作。用e n d 表示具有独立意义、 不需要依赖于其它高层动作的动作或事件，抽象于e n d 的事件都是e n d 事件。事件层 中包括： 1 一元事件类型谓词集( h e ) 2 抽象公理集( h a ) 。 3 基本事件类型谓词集( i i 】茹 4 分解公理集( h d ) 5 通用公理集( h g ) 该规划识别模型还包含四种假设：穷尽假设( e x 、互斥假设( d j a ) 、使用部件假 设( c u 柚及最小基数假设( m c a ) 。前三种假设都以m c c a r t h y 的限定理论为基础。当观 察到某一动作序列时，根据这四种假设，识别器会对其中的每个动作都生成相应的解释 图( 解释图是表示由某一动作推导出的各种事件及事件问的关系的与或图) ，并找出这 些动作的所有可能的合并结果。最后，选择合并后e n d 事件最少的解释图或解释图集合 作为规划识别的输出。 这种规划识别方法具有丰富的表达能力，可以处理动作间的时序关系及不完全观察 动作序列，并能够很好的识别偏序规划。但由于识别中采用了最小覆盖模型，并认为所 有事件出现的可能性都是一样的，使得识别结果过于武断。该识别还要求所识别的智能 体不能犯错误，识别所依据的规划库是完备的，这在一定程度上影响了该识别方法的应 用【3 3 ，q 。 2 a 2 基于限定理论的规划识别 限定理论 3 5 3 q 是一种非单调推理方法，也是研究得最早的非单调推理方法之一， 9 是m c c a r t h y 在2 0 世纪7 0 年代末提出的，它的核心思想是：如果一个句子叙述一个命 题，那么它叙述的仅仅是这个命题，不能扩展和延伸例如，如果说书店卖书，那么就 意味着只有书店才卖书，其他任何可能的卖书场所或个人都不能被考虑。 k a u t z 的最小规划集的思想，虽然与限定理论的思想很相似，但由于限定理论包含 二阶逻辑，计算十分复杂，因此k a u t z 只是基于限定理论提出了上述三个假设，而并未 直接用限定的方法来求解规划识别问题。 2 0 0 2 年，姜云飞和马宁在k a u t z 规划识别的基础上，提出了基于限定理论的规划识 别问题求解的新方法闻，弥补了k a u t z 的方法的不足，增强了规划识别的容错能力。文 中，姜云飞和马宁根据k a u t z 的理论，提出了分解和枚举的概念：以溯因理论为基础， 给出了规划识别的模型，即一个规划识别问题是一个三元组tt ，g , p ，其中g 是原子 集，叫做观察集；p 是原子集，叫做规划集；t 是背景理论由一个观察g ( g g ) 识别 出的规划d p p ) 定义为： 1 t u d l g 。 2 t u d i _ f a l s e 3 d 是满足上述条件的极小集。 基于以上新概念及新模型，他们给出了自己的新算法，并且证明对观察到的现象做 限定获得的解集与由观察到的现象求出的最小规划集的结果是一样的 2 4 3 基于规划知识图的规划识别 2 0 0 2 年，姜云飞和马宁将k a u t z 的事件层改造为更简便更直观更易于操作的规划 表示方法规划知识图，并在此基础上提出了基于规划知识图的规划识别【3 8 1 规划知识图是一个非循环的与或图，其中的结点代表规划，结点问的连接符表示 事件之间的整体与部分、具体与抽象的关系，连接符上的数字表示子结点对父结点的支 持程度( 支持程度是指一个规划( 事件) 的出现使另一个规划( 事件) 出现的可能性) 。 在识别过程中，基于已观察到的动作，通常可能推出多种结果与k a u t z 选择e n d 事件最少的推理结果作为识别的最终结果相对，姜云飞等人则认为，根据支持程度来判 断识别的最终结果，会与实际情况更为接近，因为不同动作在满足条件的规划内的重要 程度是不一样的，所以规划出现可能性也不同 2 4 4 基于语法分析的规划识别 1 9 9 0 年，v i l a i n 以k a u t z 理论为基础提出了一种基于语法分析的规划识别理论他 并没有真正采用语法分析的方法来处理规划识别问题，而是通过减少规划识别的限制情 况来进行语法分析，用以研究k a u t z 理论的复杂度 2 0 0 0 年，p y n a d a t h 和w e l l m a n 扩展了上下文无关语法( p r o b a b i l i s t i cc o n t e x t - f r e e g r a m m a f 9p c f o ) ，提出了基于概率状态独立语法( p r o b a b i l i s t i cs t a t e - d e p e n d e n to r a m m a r , p s i ) g ) 的规划识别方法1 3 9 1 。p s d g 在继承了p c f g 的优点的基础之上，进一步要求产生 式的概率要依赖于规划智能体内部和外部状态的确切模型给定规划生成过程的p s d g 描述，通过利用p s d g 语法独立特性的推理算法，可以快速地识别出用户的提问，并给 出回答。虽然p s d g 模型的假设和推理算法缺乏一定的通用性，但是其模型中的约束限 制保证了算法应用的独立属性，同时也可阻止推理复杂化 2 0 0 2 年，m o o r e 和e s s a 将上下文自由语法( a g ) 扩充为随机上下文自由语法 ( s c f g ) i 鲫j ，并将其用于对视频中多任务活动的识别m o o r e 和e s s a 为c f g 中的每个 产生式规则( 如工一a ) 添加了一个概率p ( 记作p ( x a ) ) ，以此概率及语言模型中的 依赖关系，可以将语法分析分类，且删除不必要的分析，因此该方法特别适合基于规则 活动的识别而且m o o r e 和e s s a 采用e a r l e y - s t o l c k e 算法来决定最大可能的语义推理结 果。他们将错误分为三种：替换错误、插入错误和删除错误，并提出新的分析策略来进 行错误检测和恢复，以此来提高规划识别的成功概率 利用s c f 6 方法进行规划识别能够从多个对象和任务的长期行为序列中有效地提 取出高层行为。通过监控还可以对某一对象形成经验性评估，方便进一步