（计算机应用技术专业论文）基于规划知识图的概率规划识别系统的研究及实现.pdf

摘要 规划识别是人工智能领域近年来发展起来的一个重要分支。规划识别是指根据观察 到的智能体的片断的、琐碎的动作来推断智能体的目标及它的规划，从而预测智能体未 来的动作序列。一个规划识别器推出的规划不仅能补充一些我们未观察到而又实际发生 的现象，还可以预测未来合理地推出智能体未来可能采取的动作。规划识别在很多 领域具有广泛的应用，因此研究高效的规划识别算法有着重要的意义。 本文提出了基于规划知识图的概率规划识别算法( k g p p r ) ，使得对规划识别的解 释更加合理。在规划知识图的基础上，用分解和抽象两种关系来表示规划问题，分析了 规划知识图算法所存在的不足，对事件间的整体与部分及抽象与具体的关系进行了新的 规定，并利用支持程度对事件( 规划) 出现的可能性进行规定，给出计算规划出现概率 的方法和解图的算法描述，并进行相关算法的设计。 k g p p r 方法在结构表述上比较简单，采用与或节点的方法表示事件( 规划) 间的 抽象和具体、整体和部分的关系，并加入时序约束和概率信息，使得到的解图能够更好 的解释观察到的现象。在进行规划识别的过程中，充分利用时序约束信息和事件( 规划) 间的关系来推测智能体的动作，在计算规划出现的概率值的同时进行解图的扩展，生成 解图，减少了冗余节点的生成，同时，生成的规划就是最终的规划解，而不需要再进行 最小规划集的选取，提高了效率。文中提出的算法可以处理偏序规划和部分可观察环境 下的规划等问题，这在网络安全及入侵检测等许多领域有着广阔的应用前景。 本文在给出算法的基础上，采用c + + 语言对算法进行了实现，设计了k g p p r 规划 识别系统，并对系统进行了验证。实验证明该系统可以达到理论预期的效果，能够快速 有效地识别智能体的目标、各目标发生的可能性及其可能采取的操作。 关键词：规划识别：知识图；时序约束；支持程度 a b s t r a c t p l a nr e c o g 皿i o ni sa ni n l p 删_ t a n tr e s e a r c ha r e ai na n i f i c i a li m e l l i g e n c er e c e m l y p l a n r e c o 嘶t i o ni sn l ep r o c e s so fi l l l 钿曲g 血eg o a l 咖l l a 邶舶mo b s e r v a t i o 部o f 趾a g e n t s i i n p o v e r i s h e da n d 丘a g m e m e da c t i o 璐ap l a ni i l 】! e 仃e db yap l a i lr e c o 画z c rn o to i d yc 锄a d d s o m eu n o b s e e da c t i o n st h a tn i d tp 代s e mi n 也eo b s e r 、，a t i o ns 仃e 锄b l l tw e r ea c t u a l l ye x e c u t e d ， b u tc a np r e d i c tm e 如t u r ea c t i o n s 嬲w e l l i n f 打也ea c t i o n sw 1 1 i c h 也ea g c n tm a ya d o p t 矗j t l l r er e a s o n a b l y p l a nr e c o 龇i o ni sw i ( 1 e l yu s e di 1 1m a n y 丘e l d s ni ss i g i l i f i c a mt od e v e l o p e m c i e n tr e c o 鲥t i o na l g o r i t h i n s b a s e do np l a i ll 【i 】【0 w l e d g eg r a p h ，t h i sp a p e rp r e s e n t san e wa l g o 血i l i n 、) l ，：i l i c hp r o v i d e sa m o r er e a s o n a b l ee x p l a 胍t i o nf o rt l l eo b s e n ，e da c t i o i l s ，t l l a ti st h ep r o b a b i l i s t i cp l a nr e c o g l l i t i o n b a u s e d0 np l a nk n o w l e d g e 孕印h 哐g p p r ) i nt l l ea l g o r i t l l l n ，i tr e p r e s e 鹏t h ep l a nb yu s i n gt h e d e c o i l l p o s a b i l i t ya n da ：b s 删i o n na n a l y s i st h el 赫【o f 也ep l a nh l o w l e d g eg r a p ha l g o r i t h m a n dr e d e f m e s 廿l ea b s 仃a c t i o 玛s 1 ) e c i a l i z a t i o 玛w h o l ea n dp a r tr e l a t i o n s l l i p sb e 铆e e ne v e n t s i t g i v e s 廿l em e t h o do fc o m p u t i i 培t h ep l a l l sp r o b a _ b i l i s t i c 锄dt h ea l g 嘶m mo ft 1 1 es o l u t i o ng r a p h i t g i v e s 也ed e s 咖o f m ea l g o 珊1 1 n t h e 咖舳l r ed e s c r i p t i o no fk g p p ri ss 呻l e 趾di ta d o p t sa n 讹rn o d e sd e s c 曲吨位 r e l a t i o i l s h i po fp l a i l s na d d sm e 证f o m a t i o n0 fo r d e 血gc o 嬲呱缸a n dp r o b a b i l i s t i cs 0 嬲t o e x p l a i l l 也eo b s e r v e da c t i o ni nr e 嬲o n w h e n 也ep l a nr e c o g i l i t i o ni se x e c u t e d ，i ti sa ：b l et oi n f e r t t l ea g e n t sa c t i o n sb yu s i i 培也ep r o b d b i l is _ t i ca n d 也eo r d e r i r 玛i 1 1 f o m a d o n nc a nb u i l dn l e s o l u t i o n 伊a p hw i n l o u te x 仃a c t i l l g 也el e a s tp l a nw i - e nt h ep b a _ b i l i s t i ci s c o m p u t e d s oi t i m p r o v e s 也ee 伍c i e n c yo fp l a nr e c o g l l i t i o n nc a n 姗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 l l yo r d e r c dp l 锄sa n ds o0 n 1 1 1 ei m p l e n l e m a t i o no ft h i sa l g o r i 吐l i n 丽uh a v eav e 巧 c o i l s i d e r a 【b l ep r o s p e c ti nc o n q ) u t e r 咖r ks e c 啷r 觚di n t n l s i o nd e t e 以o n b a s e do n 也ea l g o r i t b l mp 哟l p o s e da b o v e ，w el l a v ei i n p l e m e n t e dan e wp l a nr e c o g i l i 廿o n s y s t i 锄- - k g p p r 砌c hc 趾n o t0 1 d yr e c o g n i z et h ep l 趾a n dm eg o a ln l ea g e n tb e i i l g p 晌n n e de 伍c i e n t l y ，b u ta i l s o 砌i c a t e 也ea c t i o 璐n l a t 也ea g e n t 谢l lt a k e t h er e s u no f 也e e x p e r i i n e mp r o v e st l 扭t 也ek g p p r i sr e a s o n a b l ea n de 伍c i e n t k 呵w o r d s ：p l a nr e c o 卿t i o n ；硒w l e d g e ( m l p h ；o r d e 血gc o n s t r a 【i m ；s u p p l o n i n gd e g r e e 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得 的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均已在文中作了 明确的说明。本声明的法律结果由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技术 信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 钟曰耋 东北师范大学硕士学位论文 第一章引言 智能规划与规划识别是人工智能领域近年来发展起来的一个热门分支。智能规划的 任务是在给定的初始条件下寻找一动作序列，通过这一动作序列的执行使得世界状态从 初始状态到达目标状态；而规划识别则是根据观察到的智能体的片断的、琐碎的动作来 推测智能体的目标及它的规划，从而预测智能体未来的动作序列n3 。一个规划识别器识 别出的规划不仅能补充一些我们未观察到而又实际发生的现象，还可以预测未来合 理地推出智能体未来可能采取的动作晗1 。 s c l l i n i d e t 在1 9 7 8 年第一次提出规划识别问题1 ，则在1 9 8 6 年第一次基于限 定理论和最小化集合的思想提出了规划识别的通用框架h 3 ，使智能规划识别的发展有了 很大飞跃。规划识别的应用领域非常广泛，早期的规划识别主要应用在自然语言理解( 谈 话分析、故事理解、机器翻译等) 和智能计算机接口等领域；现在规划识别的应用已扩 展到网络安全、入侵检测、智能用户接口、多a g e n t 的协作等领域睛1 1 。作为人工智能 研究领域的一个重要分支，规划识别的重要性由于其越来越广泛的应用而日益突显。目 前有许多著名的学者专注于该领域的研究，如美国华盛顿大学的k a u t z ，霍尼韦尔科技 中心( h o n e y w e l lt e c l l i l o l o g yc 蹦衙) 的g e i b 和g - 0 l d m a n ，南加利福尼亚大学的p y n a d 砒， 密歇根大学的w e 1 1 m 趾等。 传统的规划识别方法是根据观察动作建立规划库，根据一定的搜索和匹配机制来获 取规划解。但是由于所观察到的动作往往是不全面的，且同样的动作经常出现在不同的 规划中，因而确定一个无二义性的规划通常是困难的。因此，研究者们提出了很多方法 来解决此问题，其中有基于溯因理论的规划识别阳3 ，但是它不能利用抽象和具体类型事 件间的共享；c h a m i a k 和g o l 提出一种基于贝叶斯网络的规划识别模型饽1 ，但当知 识库和证据集合增加时，贝叶斯网络的大小会快速增加，不适用于比较复杂的问题领域； h o n gj 强在规划图的基础上，提出利用目标图进行规划识别n0 3 ；m 崦h a 0 在h o n g j u n 的目标图的基础上提出了利用回归图进行规划识别n2 1 ，但这两种方法只是对观察到 的动作进行解释，并不能对未来的动作进行预测，也不能表示动作间抽象与具体及整体 与部分的关系。k a u ：t z 则在限定理论的基础上提出了事件( 规划) 层次结构方法口4 1 ，该 方法具有丰富的表达能力，是规划领域最著名最具影响力的规划识别方法，但它也有其 局限性，本身比较复杂，使用起来比较难。 姜云飞教授在k a u t z 方法的基础上，将k a u t z 的规划识别框架转化为一种非循环的 与或知识图雎3 ，采用信任度量的方法，选取出现可能性最大的规划作为规划解，由于考 虑到了规划在客观条件下出现的可能性及事件对规划的支持程度，所以它比龇方法 所求得的解更可信。但是采用知识图方法不能很好的解释观察到的现象，并且无法处理 不存在于规划表示中的新的规划类型。在阐述事件间整体与部分、具体与抽象的关系时， 东北师范大学硕士学位论文 规划知识图方法也只是简单规定子节点对父节点的影响，而没有考虑父节点对子节点的 影响。同时，在计算规划出现的可能性时，也只是单纯地计算可能性值，只在最后，当 识别出的多个规划无关时，才利用可能性值的乘积进行最小规划的选取。 在分析现有规划识别方法及其研究现状的基础上，本文提出了基于规划知识图的概 率规划识别算法。首先，给出事件( 规划) 间抽象与具体及整体与部分这两种关系，并 分析了规划知识图算法所存在的不足。在此基础上，利用支持程度对事件( 规划) 出现 的可能性进行规定，并给出计算规划出现概率的方法。之后，给出解图的算法描述，并 进行相关算法的设计。最后，给出k g p p r 识别系统，并用c + + 语言进行了规划识别系 统的实现，给出实验结果。 本文提出的k g p p r 方法，在结构表述上比较简单，采用与或节点的方法表示事件 ( 规划) 间的抽象和具体、整体和部分的关系。在进行规划识别的过程中，充分利用时 序约束信息和事件( 规划) 间的关系来推测智能体的动作，在计算规划概率值的同时进 行解图的扩展，生成解图，减少了冗余节点的生成，同时，生成的规划就是最终的规划 解，而不需要再进行最小规划集的选取，提高了效率。我们的方法可适用于部分可观察 领域，可识别偏序规划等。 针对研究的内容，本文的结构安排如下： 第一章为引言，概述了本文研究的背景和意义，以及规划识别的发展现状，本文的 主要工作等。 第二章为智能规划概述，主要介绍了智能规划的基本概念，智能规划的发展以及智 能规划的主要应用。 第三章为规划识别概述，主要介绍了规划识别的基本概念，规划识别的发展，规划 识别的方法，规划识别的应用等方面。 第四章为基于规划知识图方法的规划识别算法，在这一章里，主要介绍了龇的 规划识别方法和基于规划知识图的规划识别算法。 第五章为本文的主要工作，提出了基于规划知识图的概率规划识别算法，即l m p r 算法。在这一章里，给出了事件( 规划) 间的两种关系，分析了规划知识图算法所存在 的不足，并利用支持程度对事件( 规划) 出现的可能性进行规定。给出计算规划出现概 率的方法。在此基础上给出相关识别算法及算法设计。最后给出k g p p r 识别系统，对 其进行实现，给出实验结果。 2 东北师范大学硕士学位论文 2 1 智能规划的概念 第二章智能规划概述 智能规划虽然是人工智能中较早的研究领域之一，但目前人工智能领域对规划还没 有一个统一的定义。规划过程是一种问题求解方法，一个规划系统我们可以认为就是一 个问题求解系统，若用它求解比较复杂的问题，可求得一个动作序列( 串行、并行或串 并行混合) ，依次执行此动作序列可以完成某一特定的具体任务，最终达到一个特定目 标。简单的讲，智能规划是一种问题求解技术，它从规划问题的初始状态出发，构造一 个能够到达问题目标状态的动作或操作序列。如果一个实体在初始状态下经过一个动作 序列，最后到达目标状态，我们就称这个动作序列为一个规划。 一个智能规划问题( p l 咄p r o b l e m ) 通常涉及以下四个集合n 4 1 ： 1 一个操作( o p 咖s ) 的集合，给出智能体可执行的操作； 2 一个对象( o b j e c t s ) 的集合，给出规划问题中涉及到的所有对象； 3 一个初始条件( 嘶t i a lc o n d i t i o n s ) 的集合，给出问题的初始状态，其中每个元素 都是一个命题； 4 一个目标( g o a l s ) 的集合，其中每个元素都是一个命题，而且要求规划结束时 这些命题必须是真命题，也即规划结束时，这些目标必须实现。 规划系统要解决的问题是：在初始条件下，对对象实施怎样一些操作，才能使问题 目标得以实现。 目前研究的较多的是经典规划问题n5 1 。在经典规划问题中，有以下假设： 1 智能体能够感知它周围的环境和它的动作的效果； 2 智能体的动作效果是完全确定的； 3 环境状态的改变完全是由智能体的动作效果造成的。 地图着色问题、积木世界问题等都是经典的规划问题。由于现实世界的复杂性，实 际问题往往并不能满足上述条件，因此一部分学者正在致力于放宽这一假设，研究部分 可观察的或随机的环境下的规划问题，也即在“非经典规划 环境下研究规划问题。 求解智能规划问题的系统实际上是一个应用软件，给定初始状态、目标状态以及可 用的相关操作后，该软件就可以给出从初始状态到达目标状态的规划解，也就是自动给 出一个动作序列，使得系统在初始状态下通过执行这个动作序列，可以达到目标状态。 东北师范大学硕士学位论文 2 2 智能规划的发展 智能规划是人工智能的个重要领域，也是人工智能中研究较早的一个领域，它的 研究最早可以追溯到2 0 世纪5 0 年代后期，1 9 5 7 年n e w e l l 和s 妇o n 的问题求解程序 ( g p s ) 、1 9 6 9 年g r e e n 的q a 3 系统口引。1 9 7 1 年f 赫和n i l s s o n 的s t i s 系统n 刀在智 能规划领域中具有划时代的意义，它引入了s 彻s 操作符的概念，使得规划可以非常 容易地进行描述和操作，使得原来很神秘的规划问题求解变得明朗清晰起来。此后到 19 7 7 年先后出现了h a c k e r 、w a r p l a n 、i n t e 如l a n 、a b s t i 己d s 、n o a h 、n o n l l n 等规划系统。这个十年间人们研究智能规划的兴致比较高，普遍认为规划问题必须用定 理证明的理论来解决，直到c h a p m a n 设计的规划系统t w e a k 出现。由于c b a p m a n 的 分析，使人们认识到简单地利用定理证明的方法来解决规划问题是很难的，因此这以后 到1 9 9 0 年间，在人们发现新的求解方法之前，对智能规划的研究陷入了低谷，这期间 仅有s m e 、a b r v e a l 【和p r o d i g y u 刚等较少的智能规划器出现。 1 9 9 2 年k a u t z 等把规划问题求解转化为可满足( s a t ) 问题u ，一反定理证明式求 解方法，利用在约束可满足问题算法上的突破，有效地解决了部分规划问题。1 9 9 5 年 b l u m 和f u r s t 提出了图规划的方法u4 1 ，这种方法第一次采用图的方式来解决规划问题， 开辟了规划求解的新途径，使智能规划领域取得了革命性进展。用这种方式解决规划问 题，能使一些动作并行执行，大大提高了执行效率。图规划为智能规划技术提供了一种 快速优雅的求解方式，它拥有许多重要属性，包括健壮、稳定、合理、高效、且建立规 划图的计算复杂度是多项式时间和多项式空间等。后来很多算法都采用了图规划的方 法，比较著名的规划器b 1 a c k b o x 、f f 、l g p 、s g p l 雒都或多或少地采用了图规划的技 巧。1 9 9 8 年b o n e t 和g e 伍l e r 提出了启发式规划方法，这种方法利用启发式函数来指导 状态空间搜索，实践证明采用启发式的规划器比没有采用启发式的规划器表现出了更强 的问题求解能力，比较典型的规划器如f f ，h s p ，g r t ，a i ，t a i t ，m m s 和s 1 都 采用了启发式搜索的思想。另外，需要关注的是，1 9 9 8 年，国际规划竞赛首次召开， 再一次掀起了规划研究的热潮，大赛为规划器的优劣提供了测试平台，对智能规划的理 论研究起到了巨大的推动作用。 进入2 1 世纪以来，到目前为止国际规划竞赛又成功地召开了三届，不断涌现出杰 出的规划器，在理论上也取得了很多重大突破。目前，规划系统对时序和数值问题的求 解能力已引起人们的普遍关注，最新的规划系统大都考虑了对资源约束的处理。由于智 能规划研究的难度大、应用广，未来此领域无疑将继续成为个富有挑战性的国际研究 热点和人工智能领域中最活跃的分支之一。 2 3 智能规划的应用 智能规划在问题描述和问题求解两方面得到了新的突破，极大地扩展了智能规划的 4 东北9 币范大学硕士学位论文 应用领域，近年来智能规划的理论和应用研究有了长足的进展。目前智能规划应用在自 动系统中使得自动化系统的灵活性、健壮性和适应性得到提高。其主要应用研究领域有： 机器人、智能企业和商业软件。智能规划的一个重要应用领域是航天航空，在该领域中 取得最好效果的是美国宇航局的a s p e n( a u t o 删腑ds c h c d u l i i l g 锄dp l 础g e n v 的衄e n t ) 规划系统啪3 。a s p e n 获得了1 9 9 9 年美国宇航局的软件比赛优秀奖并且 广泛用在进行外太空任务的宇航器上。在机器人领域中，智能规划的应用主要有环境的 模型化描述、机器人能力的模型化描述、目标的模型化描述和实时的输入响应。不同于 其它规划研究领域，机器人领域的规划研究主要在于当处于有噪音的环境模型中，机器 人通过感应器和交流信道得到的信息都存在噪音，这样它就需要将感应和执行整合来进 行直接规划。目前主要研究领域包括路径规划、感知规划、任务规划、规划交流。另外 智能规划在智能化工厂中也有应用心。目前主要研究领域包括生产流程规划、生产安排 规划和调度。智能规划在商业中应用也很广泛，目| j 的研究领域主要有网络信息集成口2 】 和运输规划。 东北师范大学硕士学位论文 3 1 规划识别的概念 第三章规划识别概述 从规划识别的概念上来看，我们可以把规划识别的过程理解为智能规划过程中提取 有效规划的逆过程。智能规划的任务是在给定的初始条件下寻找一动作序列，通过这一 动作序列的执行使得世界状态从初始状态到达目标状态；而规划识别则是根据观察到的 智能体的不完整的、琐碎的动作来推断智能体的目标及它的规划，并预测智能体未来的 动作序列。一个规划识别器推出的规划可以补充一些我们未观察到的现象，还可以预 测智能体未来可能采取的动作唯3 。 3 2 规划识别的发展 规划识别理论是人工智能研究领域中一个相当活跃的研究方向。它已经被广泛地应 用于自然语言理解、知识理解和情景演算等计算机系统的许多方面。 s c h 武d e t 在1 9 7 8 年第一次提出规划识别问题口1 。规划识别问题属于心理学和人工 智能交叉领域的问题，它涉及到知识表达、知识推理、非单调逻辑、情景演算、人机交 互和知识挖掘等方面知识。经过了三十多年的发展，出现了许多规划识别模型及方法。 龇在1 9 8 6 年第一次基于限定理论和最小化集合的思想提出了规划识别的通用 框架h 1 ，使智能规划识别的发展有了很大的飞跃。1 9 8 7 年k a u 亿提出了规划识别的形式 理论，这是规划识别研究的一个里程碑。它的主要思想是建立一个事件( 规划) 的层 次结构，通过将观察到的动作与这个层次结构相匹配来进行规划的识别。 1 9 9 0 年l l a i l l 提出了一种基于语法分析的规划识别理论腩1 ，该理论以k a u t z 理论为 基础。同年，c a 恸将d e m p s t e r - s h a 矗玎理论应用到规划识别中皿引。随后c h a n l i a l 【和 g o l d m 肌构建了规划识别的第一个概率模型阳2 圳，并将贝叶斯网络应用到规划识别中， 这使得规划识别向更广泛的应用又迈进了一步。1 9 9 9 年，g o l d l l l 趾等人又提出了基于 规划执行的规划识别方法晗5 1 ，该方法从一个新的角度出发来解决规划识别问题。之后的 几年里，g o l d n ：m 等人对这种方法不断修改，并将其应用到了多种领域，特别是敌对 环境下的规划识别。1 9 9 5 年b l u m 和f u r s t 提出利用规划图进行快速规划，h o n gj 强从 规划图得到灵感，提出基于目标图的规划识别n 。 2 0 0 2 年姜云飞教授提出了一种新的规划表示方法口1 ，将的规划识别框架转化 为一种非循环的与或知识图，以此来表示规划，与舭方法相比，这种规划表示方法 更加简便、直观。它采用信任度量的方法，选取出现可能性最大的规划作为规划解，由 6 东北师范大学硕士学位论文 于考虑到了规划在客观条件下出现的可能性及事件对规划的支持程度，所以它比k a u t z 方法所求得的解更可信。 2 0 0 3 年m i n g - h a o 在h o n gj u i l 目标图的基础上提出了利用回归图进行规划识别 的方法n 羽。回归图中的节点被分为确定的节点和可能的节点，通过这两种节点进行目标 的识别，其中目标又分为确定的目标和可能的目标。该方法既保留了目标图分析方法的 优点，又有自己独特的优点：能识别出确定的一致目标和可能的一致目标。 2 0 0 3 年f 捌【l l 【m u l d e r 和f 删1 sv 0 0 r b r a a k d 在对战术规划识别进行形式化描述时给出 规划识别过程中观察的不确定性啪，。 规划识别从提出到现在经过了近3 0 年的发展历程，其方法也日趋成熟。随着新方 法的不断提出，其应用前景也越来越广泛。 3 3 规划识别的方法 规划识别的方法有很多种，概括起来主要有下面一些口7 | ： 1 基于事件层次结构的规划识别方法 基于事件层次结构的规划识别即基于k a l l t z 理论的推理方法。1 9 8 6 年k a l l t z 和灿1 e n 提出了一种通用的规划识别模型h 3 。这是规划识别的第一个形式化理论。该理论的主要 思想是建立一个事件( 规划) 的层次结构，并由动作的不同抽象来组成。这个层次结构 用来组成规划库。在进行规划识别时，将观察到的动作与规划库中的规划进行匹配。该 方法具有丰富的表达能力，但是使用起来比较困难。 2 基于语法分析的规划识别方法 1 9 9 0 年l 血以龇的理论为基础提出了一种基于语法分析的规划识别理论聆1 。 他通过减少规划识别的限制情况来进行语法分析，用以研究k a u t z 理论的复杂度。2 0 0 0 年p ) ，n a d 砒和w e l h 孤提出了基于概率状态独立语法的规划识别方法啪3 。该语法扩展 了概率上下文无关语法( p r o b a b i l i s t i cc o m e ) 【t 五陀eg 阳m m a rp c f g ) 。由于p c f g 较同期 的语法有更多的独立假设，因此能够支持更广泛的问题领域，并能支持有效的语法分析 算法。2 0 0 2 年，m o o r e 和e s 姚将上下文自由语法( c f g ) 扩充为随机上下文自由语法 ( s c f g ) 啪1 ，并将该方法用于对视频中多任务活动的识别。 3 基于溯因理论的规划识别方法 溯因理论哺1 是一种逆推理归纳，它是一种由结论成立而推出前提以某种置信度成立 的归纳方法。这种方法的一般模式是：若h 为真时，则h e 必为真；观察到e 成立， 则h 以某种置信度成立。l i n 和g o e b e l 发现了溯因理论和规划识别之间的联系，可以 将溯因理论运用到规划识别中，当观察到一个结论时，会寻找它发生的原因作为该结论 产生的解释。 4 基于限定理论的规划识别方法 限定理论是研究的最早的非单调推理方法之一。m c c a 一h y 在2 0 世纪7 0 年代末提 出了限定理论“3 2 1 。传统的逻辑语言可用来形式化非单调逻辑，而规划识别问题通常为 7 东北师范大学硕士学位论文 非单调的逻辑推理问题，因而可以将限定理论与规划识别问题相结合。 k a u t z 的规划识别问题就是求解观察动作的最小规划集，这与限定理论的思想很相 似。但由于限定理论包含二阶逻辑，计算十分复杂，因此，k a u t z 只是基于限定理论提 出了三个假设( 穷尽假设、互斥假设、使用部件假设) ，并没有直接用限定的方法来求 解规划识别问题。2 0 0 2 年，姜云飞和马宁在k a l | t z 规划识别的基础上，结合以上两种 方法，提出了基于限定的规划识别问题求解的新方法n 3 1 。根据规划识别，姜云飞、 马宁给出了分解和枚举的概念，并给出了限定求解规划识别问题的算法。 5 基于规划知识图的规划识别方法 2 0 0 2 年，姜云飞、马宁在k a l l t z 规划识别的基础上提出了基于规划知识图的规划 识别算法乜1 。它把龇的事件层次结构图框架转化为一种非循环的与或图，图中节点 代表规划( 事件) 。事件之间具有整体与部分、具体与抽象的关系。 他们在规划知识图中添加了支持程度的概念，并通过计算各事件在现实生活中出现 的可能性来判别候选规划。姜云飞等人认为，不同动作对规划出现可能性的支持程度是 不同的，因此，根据支持程度来计算规划出现的可能性，进而判断识别的最终结果，会 与实际情况更为接近。 在知识图方法的基础上，谷文祥、李杨等人又提出了一种带标记的反向搜索的规划 识别算法3 l 。该方法修改了知识图算法中对支持程度和可能性的部分计算，并采用了从 下往上动态生成解图的方法，解决了动态增加新节点的问题。 6 基于缺省推理的规划识别方法 缺省理论是在知识不完全的情况下使推理得以继续下去的一种非单调推理理论。缺 省推理的核心是在默认或假设某些命题成立的前提下进行推理。c a r b e n y 根据对自然对 话的分析以及对人类推理的心理研究提出了一个基于默认推理的规划识别模型1 。它的 主要思想是通过支持适当的默认推理来延迟无根据的结论直到进一步的证据出现，从而 逐步地更新用户规划的系统模型。 7 基于动态概率关系模型的规划识别方法 1 9 9 9 年，f r i e d i i l 孤等人在贝叶斯网络的基础上提出了概率关系模型口朝，它的基本 目标是模型化领域对象属性的不确定性。概率关系模型允许某一对象的属性与该对象本 身的其它属性有概率依赖关系，还允许某一对象的属性与其相关对象的属性有概率依赖 关系。2 0 0 3 年，s l l a n g l l a i 等人在概率关系模型的方法的基础上提出了动态概率关系模 型( d p 蹦) 汹3 。动态概率关系模型在每个时间片上都有一个概率关系模型，且每一个 时间片上的状态都依赖于前一个时间片的状态。 另外，还有基于解释图剪枝技术的规划识别算法，在该算法中，以解释图剪技术为 核心，扩展解释图时利用软时序约束对当前解释图进行剪枝，以精确目标假设集合。计 算各目标假设的概率后，对目标假设进行分级与选择，最后对所选目标假设子树进行扩 展，然后即可得到完整的规划假设。该算法不仅可以有效处理域的部分可观察问题和偏 序规划及多规划交替执行等问题，还可以排除智能体的误导动作。 除上述方法外，规划识别的方法还有很多，比如基于因果网络的攻击规划识别7 勰1 ， g 东北师范大学硕士学位论文 基于目标图分析的目标识别n 仉3 9 3 ，基于动态贝叶斯网络的规划识别4 ，基于隐马尔 可夫模型的规划识别h 羽，基于回归图的规划识别n 2 3 等。 3 4 规划识别的应用 “ 规划识别在很多领域中都有所应用，早期广泛应用在自然语言理解、智能用户接 口及用户模型等方面。目前其应用已扩展到网络安全、入侵检测，战术规划识别及工业 控制等领域晗7 1 。 入侵检测，通俗的说是指对入侵进行识别并做出响应的过程，它是网络安全中二个 重要的研究领域。将人工智能的方法加入到入侵检测系统，可以促进入侵检测的进一步 发展。在军事应用中，特别在利用感知数据进行决策时，采用规划识别方法有其重要的 价值。2 0 0 5 年，s u z i c 提出了规划识别的一种通用模型h 驯，并将其用于威胁评估。在敌 意规划领域，智能体需要有效的识别出对手现行的规划与目标并预测出对手未来的规划 与目标，然后再针对识别与预测内容进行有效的应对。敌意规划的识别与应对在国家信 息安全等计算机安全问题上有着非常重要的研究价值和应用前景，也有不少学者对该领 域进行了研究h4 蜘。在工业生产中，规划识别方法可以识别出机器操作的目标，根据该 目标与初始目标的比较来判断生产过程是否有错误发生，以完成监控及诊断的任务啪3 。 规划识别能够增强用户接口。通过接口来监视用户的行为，从接口交互中对用户目标和 规划进行识别，推断出其目标和规划，为用户提供智能辅助。m i c r o s o r 公司的。伍c e 助手就是利用了规划识别的方法来对用户进行智能辅助的h 。另外，规划识别在其他方 面也有广泛的应用。 9 东北9 币范大学硕士学位论文 第四章基于规划知识图的规划识别算法 4 1k a u t z 的规划识别表示 龇的规划识别理论是一个形式化的理论n 1 ，它对现实生活中的事件实例用形式 化方法进行表述，k a u t z 的表示由于其形式化和丰富的表达能力而成为规划识别领域最 著名的一种表示方法n ，2 1 。 把规划识别中的事件( 规划) 表示为一个层次结构。这个结构中主要有两类 表达式：抽象表达式和分解表达式。分解表达式用来说明一个事件是由几个子事件组成 的。如图4 1 所示：在k a u t z 的m a k e p a s t a - d i s h 规划中，m a l 【e p a s t a - d i s h 可以分解为3 个子事件：m a k e - n o o d l e s ，b o i l w a t e r 和m a k e s a u c e 。抽象表达式说明事件( 规划) 间 的i s a 关系，例如：m a k e f e t t l 】c i n i m a 血a r a 抽象于m a l 【e p 姗d i s h ，这表明 m a k e f e t t u c 越m a r i n a r a 是m a k e p a s t a - d i s h 的一个具体实例，换言之， m a k e f e t t l 】c “m a 血a r a 应当继承m a l 【e p 嬲协d i s h 的所有特征，即它也可分解为以上说 明的3 个子类型事件。这两种形式用一阶逻辑可以分别表示为： 搬胁船触一d 括3b d 玎一耽幼0 3 ) 胁肛 b d 砒如1 ) 肱旆p 一勋“c 如2 0 嘞 吐幺眈一凡抛c 加i 一施，砌口阳( x ) 3 肋矗妇一只嬲胁一d 括办( x ) 其中s l ，s 2 ，s 3 是步骤函数，表明整体和部分之间的映射关系。 k a u t z 把所有的规划分为两类：一类是不具有独立意义的规划，它们总是表示成其 他规划的一部分，也是需要进一步推导的规划，例如图4 1 中的( m a k e _ n o o d l e s ) 。另 一类是具有独立意义的规划，即规划推导的终端，例如图4 1 中的( m a k e m e a l ) 。这两 种类型的规划都抽象于一个特殊的规划a n y 。为了区分这两类规划，k a u t z 引进了一个 特殊的符号e n d ，凡是抽象于e n d 的规划都是具有独立意义的规划，也就不需要进一 步的推导，以此作为推导的控制机制。 k a u t z 认为规划识别的解集应当是能够推出观察到的现象的最小规划集。这与 m c c 鲫时限定理论的思想很相似。据此，k l u t z 提出一个基于限定求解规划识别的框架。 这个框架的核心是k a u _ t z 提出的4 个假设，其中第4 个假设是选择具有最少规划的规划 集作为解集。而其他3 个假设，k a _ u t z 证明了根据它们所求得的解满足限定理论。这3 个假设是：穷尽( e x h a u s t i v e n e s s ) 假设、互斥( d i s j o 砷n e s s ) 假设、使用部件( c o m p o n e 删憾e ) 假设。以这3 个假设为基础所建立的规划识别框架( 如图4 1 所示) 是以层次结构的形 式来组织的。不同的规划安置在结构中的不同位置。k a u ：t z 提出的算法就是在这个结构 上进行搜索，找出满足条件的规划集，然后再借助第4 个假设最终确定规划识别的解集。 l o 东北师范大学硕士学位论文 做饭，做面团，烧水，做面条，做调味汁，做大蒜番茄酱意大利面条，做大 蒜番茄酱白脱奶油面，做意大利面条，做白脱奶油面，做大蒜番茄酱 图4 1 一个分层规划 4 2 基于规划知识图的规划识别表示 k a u 忆方法具有丰富的表达能力，但它也有其局限性，本身比较复杂，使用起来比 较难。姜云飞教授在龇方法的基础上，将k a u t z 的规划识别框架转化为一种非循环 的与或知识图阻3 ，采用信任度量的方法，选取出现可能性最大的规划作为规划解。 4 2 1 规划知识图方法 规划知识图方法是在龇提出的层次结构规划识别方法的基础上架构的，它把 k a u t z 的事件层次结构图框架转化为一种非循环的与或图，图中节点代表规划( 事件) ， 节点间均由连接符连接。事件之间具有整体与部分、具体与抽象的关系，这两种关系在 规划识别中用抽象表达式和分解表达式表示。 规划知识图中有两类节点：与节点和或节点。每一个节点是与节点还是或节点是相 对于其父节点而言的。具体地说，如果一个父节点的后继是此父节点的具体化，即当此 父节点与其后继节点之间是抽象与具体的关系时，这些具体化节点称为或节点。如果一 个父节点的后继是一组组成部分节点，即当此父节点与其后继节点之间是整体与部分的 关系时，这些组成部分节点称为与节点。在规划知识图中用圆弧标出。将k a u t z 的 1 1 东北师范大学硕士学位论文 m a k e p a l s 协d i s h 层次规划图改写成的规划知识图，如图4 2 所示。其中节点中的带括号 的数字代表时间片。 图4 2 规划知识图 4 2 2 规划知识图算法 在k a u 亿层次结构图中定义了两个特殊的规划类型a n y 和e n d ，并且规定只有抽 象于肿的规划才具有独立意义，以此来控制整个搜索算法。但是对一个系统来说， 什么样的规划可以抽象于d o 却是一个棘手的问题，在知识图中则没有用a n y 和e n d 这两个特殊的规划类型，而是采用为每个规划提供一个支持程度的方法来确定可识别的 候选规划。通过这种方式，可以把求解的过程控制在任何层次上，从而找到可能性比较 高的一个，而不是最抽象或最庞大的一个规划。 在进行解图搜索时，规划知识图采用与或图的宽度优先搜索策略，一次性产生整个 解图s g 。知识图的解图s g ( s o l u t i o n 刚) 是指由观察到的现象规划知识图中的 节点出发，找到的一个包含这些节点的子图。原来的规划知识图为g ，那么解图s g 如 下规定： ( 1 ) 观察到的现象节点m 在s g 中； ( 2 ) 咒在s g 中，如果珂有一组o r 后继节点，那么有且只有一个o r 后继节点 在s g 中； ( 3 ) 刀在s g 中，如果玎有一组心m 后继节点，则所有的珂的a n d 后继节点 都在s g 中； ( 4 ) 由观察到的现象节点聊出发，可能性最大的o r 节点在s g 中； ( 5 ) 无其他的在g 中的节点所在s g 中。 当观察到的节点为m a k e f e t t u c i n e ( 1 ) 、m a k e m 面n a r a ( 2 ) 时，利用该算法所得到的 解图如图4 3 所示。 1 2 东北师范大学硕士学位论文 图4 3 一个规划知识图产生的解图 1 3 东北师范大学硕士学位论文 第五章基于规划知识图的概率规划识别算法的研究 由于规划知识图方法考虑到了规划在客观条件下出现的可能性及事件对规划的支 持程度，所以它比k a u t z 方法所求得的解更可信。但是采用知识图方法不能很好的解释 观察到的现象，并且无法处理不存在于规划表示中的新的规划类型。在阐述事件间整体 与部分、具体与抽象的关系时，规划知识图方法也只是简单规定子节点对父节点的影响， 而没有考虑父节点对子节点的影响。同时，在计算规划出现的可能性时，也只是单纯地 计算可能性值，只在最后，当识别出的多个规划无关时，才利用可能性值的乘积进行最 小规划的选取。 在本章我们提出了k g p p r 算法，对事件间的相互关系作了修改，对支持程度作了 不同于规划知识图的规定，并给出计算规划出现概率的方法和生成解图的算法。在计算 规划出现的概率值的同