（计算机软件与理论专业论文）基于规划图的对手规划识别方法.pdf

p 靠 兮 _ 一 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指 导下独立进行研究工作所取得的成果。据我所知，除了 特另t l ；h f i 以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明 的法律结果由本人承担。 学位论文作者签名：丞l 盏 日期： 学位论文使用授权书 本学位论文作者完全了解东：l k n 范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：碰 日期： 丝f ! ：l 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日期： 电话： 邮编： 1 ( r 一。1 r 1 ， r r t 7-t 卜 ， v 一 摘要 近年来，规划识别技术作为人工智能领域的重要分支，得到了长足发展。规划识别 技术是指依据观察到的智能体的片断的、琐碎的动作来推断智能体的目标及其所执行的 规划。一个规划识别器求解出的结果能够发现很多我们没有观察到但却实际存在的结 果，还可以提供结果发现智能体可能出现的轨迹。规划识别众多方面得到使用，使 得研究成果具有重大意义。 本文通过使用基于规划图的对手规划识别算法，在原有理论上，采用分解和抽象方 法描述规划算法，舍弃已有计算方式的缺点，对智能体的总体与局部、抽象与具体进行 重新确定，并利用“测试”方程对动态序列轨迹出现的可能性进行测试，获得算法以及 解题的算法描述，并进行算法设计。 本文的算法结构简单，采用与或节点的方法表示事件( 规划) 间的抽象和具象、总 体和局部的关联，这样做的好处是得到的结果能够更好的说明具体表现。在进行求解的 过程中，充分使用已有算法来推测智能体的运行轨迹，在获得结果的同时，不断扩充算 法，获得结果集，减少重复推测的过程。本文中所使用的算法可以广泛使用在其他类似 须处理规划的业务领域，同时，在网络防护、智能接入测试、医学检测等领域得到广泛 的应用和推广。 本文在经过深入研究基础上，得到了规划算法，并使用c 语言进行了设计，开发出 一套规划识别系统业务模型，并对此业务模型进行了比较测试，结果证实达到了设计要 求，可以计算出智能体的动态运行轨迹、运行目标、可能的运行方式及相应的应对动作。 关键词：智能规划：规划识别；规划图；对手规划 a b s t r a c t i nr e c e n ty e a r s ，p l a nr e c o g n i t i o nt e c h n o l o g ya sa l li m p o r t a n tb r a n c ho fa r t i f i c i a l i n t e l l i g e n c e ，h a sm a d ec o n s i d e r a b l ep r o g r e s s p l a nr e c o g n i t i o nt e c h n o l o g yi sb a s e do nt h e o b s e r v e da g e n t s f r a g m e n t s ，a n df r i v o l o u sa c t i o n st oi n f e ra g e n t so b j e c t i v e sa n di t s o p e r a t i n gt r e n d s ，w h i c hd e s c r i b et h es e q u e n c eo fi t sd e v e l o p m e n tp a t h s o l v e dap l a n r e c o g n i z e rc a nf i n dm a n yo fo u rr e s u l t sa r en o ta w a r et h a tt h e r ea r er e a lr e s u l t s ，c a na l s o p r o v i d er e s u l t s 一一a g e n tm a yb ef o u n di nt h et r a c k i d e n t i f i e db yt h eu s eo fm a n y a s p e c t so fp l a n n i n g ，s or e s e a r c hi so fg r e a ts i g n i f i c a n c e i nt h i sp a p e r , b a s e do np l a n sr i v a lp l a nr e c o g n i t i o na l g o r i t h m s ，i nt h et o w np l a n ， b a s e do nt w ok i n d so fr e l a t i o n s h i p sw i t ht h ed e c o m p o s i t i o na n da b s t r a c t i o nt oe x p r e s s p l a n n i n gp r o b l e m s ，a n a l y s i so fp l a n sa l g o r i t h mw e a k n e s s e s ，t h ei n c i d e n to fo v e r a l la n d p a r t i a la n da b s t r a c ta n dt h es p e c i f i cr e l a t i o n s h i pb e t w e e nt h en e wp r o v i s i o n sa n du s eo f t e s t ”f u n c t i o no ft h ee v e n t ( p l a n n i n g ) a p p e a r st h ep o s s i b i l i t yo fd e t e c t i o n ，g i v e nt h e p r o b a b i l i t ym e t h o do fc a l c u l a t i n gt h er e c o n c i l i a t i o np l a ne m e r g e dg r a p hd e s c r i p t i o no ft h e a l g o r i t h ma n da s s o c i a t e da l g o r i t h md e s i g n t h i sp r e s e n t a t i o ng i v e nb yt h ea l g o r i t h mi sr e l a t i v e l ys i m p l ei ns t r u c t u r e ，u s i n gt h e m e t h o dw i t ho rn o d e s ，s a i de v e n t ( p l a n n i n g ) b e t w e e nt h ea b s t r a c ta n dc o n c r e t e ，t h e r e l a t i o n s h i pb e t w e e nw h o l ea n dp a r t , s ot h a tt h es o l u t i o nm a pt ob eb e t t e ra b l et oe x p l a i n t h eo b s e r v e dp h e n o m e n a i d e n t i f i e d d u r i n gt h ep l a n n i n gp r o c e s s ，f u l l yr i v a lp l a n r e c o g n i t i o nd a t a b a s et os p e c u l a t ea g e n tm o v e sa p p e a ri nt h ec a l c u l a t i o no ft h ep r o b a b i l i t y o ft h ev a l u eo fp l a n n i n gs i m u l t a n e o u ss o l u t i o no ft h ee x p a n s i o np l a n , g e n e r a t es o l u t i o n p l a n s ，r e d u c i n gt h eg e n e r a t i o no fr e d u n d a n tn o d e s i nt h i sp a p e r , t h ea l g o r i t h mc a nd e a l w i t ho p p o n e n t so fp l a n n i n ga n dp a r t i a l l yo b s e r v a b l ee n v i r o n m e n t ，p l a n n i n ga n do t h e r i s s u e s ，w h i c hi nn 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 na n dm a n yo t h e rf i e l d sh a v ea b r o a da p p l i c a t i o np r o s p e c t s i nt h i sp a p e r , t h ea l g o r i t h mi sg i v e nb a s e do nt h eu s eo f c + + l a n g u a g ea l g o r i t h mt o a c h i e v et h ed e s i g no ft h ep l a nr e c o g n i t i o ns y s t e m ，a n ds y s t e mv a l i d a t i o n e x p e r i m e n t p r o v e dt h a tt h es y s t e mc a l la c h i e v et h ed e s i r e dr e s u l t st h et h e o r yc a nb eq u i c k l ya n d e f f i c i e n t l yi d e n t i f yt h ea g e n t sg o a l s ，o b j e c t i v e so ft h el i k e l i h o o da n dp o s s i b l ea c t i o nt o t a k e 玎 _ 一 f y 产 ， 嚼 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 nr e c o g n i t i o n ；p l a n s ；a d v e r s a r i a lp l a n n i n g 1 1 1 目录 摘要i a b s t r a c t i i 目录i v 引言1 第一章智能规划问题2 1 1 智能规划的概念2 1 2 规划问题表示2 1 3 智能规划的发展与应用3 第二章规划识别6 2 1 规划识别概述6 2 2 规划识别的方法6 2 3 规划识别的分类7 2 4 规划识别的应用8 第三章规划图1 0 3 1 规划图的概念1 0 3 2 规划图的算法1 0 第四章基于规划图的对手规划识别方法1 3 4 1 对手规划识别库。1 3 4 2 基于规划图的对手规划识别算法1 4 4 3 对手攻击检测1 7 结论2 0 参考文献2 1 i v 东北师范大学硕士学位论文 引言 规划识别是人工智能研究中一个十分重要的领域。规划识别是指观察者从被观察 到的自主体的动作集合推导出该自主体的目标，可能的下一步动作或完整的规划方案 的推理活动。初期的规划识别皆基于规则推理，研究人员试图根据推理规则来掌握规 划识别的特性。而如今已经有很多推理技术应用在规划识别中。经过多年的发展，规 划识别技术已经在众多的领域中得到广泛的应用。 随着对智能规划技术研究的不断开展，在实际工业生产中的使用也不断增多，当 然，这其中也包括带有安全防护行为的领域。在这些领域内，攻击性行为会威胁到业 务的使用，因此规划识别和防范攻击性行为的是研究的一个重要课题。 自1 9 7 8 年将规划识别作为新的研究问题提出后，出现了应用于不同领域的多种 的规划识别方法。1 9 8 6 年，k a u t z 和a 1 l e n 提出的一种基于事件层的规划识别理论， 形成了规划识别的理论基础。1 9 9 1 年，c h a r n i a k 又将贝叶斯网络应用到规划识别中， 提出了一种基于贝叶斯网络的规划识别模型，让规划识别得到了更加广泛的使用。在 1 9 9 9 年，g o l d m a n 等人又提出了基于待定集( p e n d i n gs e t ) 的规划识别方法，这是 全新的规划识别方法，主要应用于为用户提供智能辅助系统。2 0 0 2 年，姜云飞和马 宁结合限定理论和k a u t z 规划识别的相似性，提出了一种基于限定的规划识别问题求 解的新方法。早期的规划识别方法不仅在交通监控、计算机辅助教学以及危机管理等 领域的应用取得了不错的成果，更被广泛应用于自然语言理解、智能用户接口及用户 模型等领域，目前正向包含竞争、敌对等因素的复杂领域发展。 东北师范大学硕士学位论文 第一章智能规划问题 在人工智能中有一个重要的研究方向就是智能规划。所谓智能规划就是指根据想 要实现的目标，在分析与认识了周围环境的基础上，对可以进行的动作进行推理，归 纳出可以实现其最终目标的一系列动作，即规划( p l a n ) n 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 规划问题表示 对规划问题进行符合事实的形式化描述，是规划问题得以正确求解的前提条件。 任一个规划器对规划问题求解，都必须将规划问题进行规范描述，否则不可能求解。 因此，规划语言的发展是智能规划长足进步的重中之重。1 9 7 1 年，在智能规划发展 中具有划时代意义的一年，在f i k e 和n i l s o n 的s t r i p s 系统中规划可以方便的进行 描述和操作。但是，随着规划的在不同领域中的使用，人们发现s t r i p s 能力仍然存 在非常大的不足，它满足不了很多实际应用的模型化表达。此时，作为规划技术应用 的前提，设计可以描述和模拟一个实际应用的规划定义语言成为亟需解决的问题。 1 9 9 6 年e p e d n a u l t 提出了动作描述语言a d l ( a c t i o nd e s c r i p t i o nl a n g u a g e ) b 3 ，a d l 除具备s t r i p s 的描述能力外，同时还能够描述量化效果和条件效果等特征。 1 9 9 8 年d r e wm c d e r m o t t 提出了规划领域定义语言( p d d l ) h 3 ，它逐渐地成为公认的 国际智能规划比赛( i n t e r n a t i o n a lp l a n n i n gc o m p e t i t i o n ，i p c ) 的标准语言。p d d l 语言同时提供了规划问题定义的语法和规划的定义。p d d l 语言强大的表达能力，超 出了当时规划器发展的水平，极大的促进了规划器的发展。规划语言是规划领域交流 和沟通的标准，对于不同的规划器我们可以通过它们对同种语言表示的规划问题的 2 东北师范大学硕士学位论文 处理来进行性能比较哺3 。 采用a d l 表达的第一个规划器是u c p o p 。a d l 的扩展让更多的实际问题能够使用 规划方法进行编码。 a d l 语言和s t r i p s 语言的区别主要有以下几点： ( 1 ) a d l 在状态中正、负文字都有，而s t r i p s 在状态表示中只有正文字。 ( 2 ) a d l 认为未被提及的文字是未知的，采用开放世界假设，而s t r i p s 则认为 未被提及的文字均为假，采用封闭世界假设。 ( 3 ) 在a d l 中p a q 表示增加p 和一q 并删除一p 和q ，而s t r i p s 中则意味着增 加p ，删除q 。 ( 4 ) a d l 的目标中包含有更利于表达的量化变量，而s t r i p s 的目标中只包含基 本文字。 ( 5 ) a d l 中变量可以具有类型，而s t r i p s 中不支持类型定义。 ( 6 ) a d l 中允许包含条件效果，s t r i p s 的效果则要求用合取表达式。 ( 7 ) a d l 中包含等式谓词，s t r i p s 中不支持等式。 智能规划的发展关键是规划语言，在规划理论的发展上有着重大的意义。由于当 前的规划器还不能够完全处理一些规划语言所能表达的问题，所以说规划语言的发展 为规划的发展指出了方向。可以看到的是，从s t r i p s 域到a d l 语言再到p d d l 语言， 规划语言的表达能力已经越来越强。 1 3 智能规划的发展与应用 1 智能规划的发展 智能规划识别理论在知识理解、情景演算及自然语言理解等方面已经有了广泛的 应用，是人工智能研究领域中十分活跃的一个研究方向。规划识别是指根据对一些现 象的观察来进行分析，进而推测出智能体将会进行规划。 规划识别问题是由s c h m i d e t 在1 9 7 8 年首次提出的，属于多学科交叉领域，包含 了心理学及人工智能等方面的知识，涉及的层面包括知识表达、知识推理、非单调逻 辑、情景演算、人机交互及知识挖掘等。历经二十几年的发展，已经有了许多规划识 别的模型及方法。 规划识别的通用框架由k a u t z 于1 9 8 6 年在限定理论和最小化集合的基础上提出 的，此框架的提出使智能规划的发展迈出了一大步。此种方法的表达能力十分突出， 是到目前为止最具影响力、最著名的表示及处理规划识别的方法之一。第二年，k a u t z 进一步提出了规划识别的形式化理论，其主导理论是以层次结构来描述一个规划，在 进行规划识别时将构建的层次结构与已经观察到的动作相匹配，以此试图建立用户的 高层目标规划。每观察到一个新的动作，识别器就将与该动作冲突的规划消除掉，并 将该动作加入到与它保持一致的规划中。 在此之后b l u m 和f u r s t 又引入规划图的概念，使规划识别可以更加快速的进行， 3 东北师范大学硕士学位论文 h o n gj u n 在规划图的基础上又提出了基于目标图的规划识别。此方法在识别过程中 不需要在整个规划空间中进行搜索，也不需要规划库，只需要先构建一个目标图，根 据对目标图的分析来识别目标及有效规划。此种方法适合用于软件的咨询系统、数据 查询优化系统及故事理解等方面。好处是构造及分析目标图的算法都是时间和空间的 多项式，并且识别目标的准确率较高。 姜云飞教授在2 0 0 2 年发表的一种基于规划知识图的规划识别算法文章中提 出了规划知识图的理论，在当前流行的k a u t z 提出的层次结构图的基础上，将其转换 为另一种规划识别图，并通过与或图的宽度优先算法来求解能够观察到的规划集。 殷明浩于2 0 0 3 年在目标图的基础上指出使用回归图的方式对规划进行识别。回 归图的组成部分有命题节点、动作节点和目标节点。其指导思想为将回归图中的节点 分为两类，确定的或可能的节点。以此来识别当前目标是确定的目标或是可能的目标。 此种方法即将目标图中分析方法的优点保留了下来，又发掘出了自身独特之处：能够 将确定的一直目标与可能的一直目标区分开。 2 智能规划的应用 智能规划在问题描述和问题求解的领域取得的突破，使之成为人工智能领域中的 一个热门方向。由于研究的对象和方法发生了变化，使智能规划的应用领域得到了极 大的扩展，因此在近几年来智能规划的理论及应用方面的研究得到了更好的发展。目 前，由于智能规划技术应用到了自动系统中，极大幅度的提高了自动化系统的灵活性、 健壮性和适应性。 ( 1 ) 航天领域 1 9 9 9 年美国宇航局软件比赛优秀奖得主a s p e n ( a u t o m a t e ds c h e d u l i n ga n d p l a n n i n ge n v i r o n m e n t ) ，目前正广泛应用在外太空作业的宇航器上。 ( 2 ) 机器人领域 在机器人领域规划的主要应用为对环境、机器人能力及目标这三方面的模型化和 实时的输入响应。因为机器人所处的环境模型通常都有噪音干扰，所以机器人领域的 规划研究与其他领域的主要区别就在于机器人需要将环境感应和执行直接规划融合 到一起。 在机器人学中智能规划的具体应用方向有：控制知识的表示、路径规划、环境模 型的描述、任务规划、含有不确定时的规划、装配规划、基于传感信息的规划、非结 构环境下的规划等。 ( 3 ) 智能化工厂 智能化工厂是指将智能规划应用到从生产设计到产品的生成、生产过程的监测等 一系列的过程，不仅可以应用在单个的企业中，还能在同一时间协调多个企业之间的 关系。在智能化工厂中，智能规划主要使用资源约束的方式求解有效规划。 例如，在工厂作业电镀规划问题中( j o bs h o ps c h e d u l i n g ) ，描述的是在加工资 源( 如刨床、车床、钻床等) 受到限制的情况下，根据现有的零件加工顺序对整套生 产线安排和规划出一套有效合理的生产程序，可以使完成所有工作的时间最短，并且 4 东北师范大学硕士学位论文 每台加工机器的等候时间也是最短。相同生产条件下，智能规划理论的引入使得作业 调度更加合理，为企业带来了更高的经济效益。 ( 4 ) 商业应用 在商业领域中，智能规划技术的应用更为广泛，主要的方向有运输规划及网络信 息集成。 运输规划即为规划问题在物流行业中的应用，由于运输要求会随时发生变化，因 此可以根据这些动态的要求来对交通工具安排计划和调整行程。交通工具可以是一辆 出租车、一部电梯或是在房间里移动的一个机器人。在此类问题中存在了很多使规划 变得复杂的约束条件，如最终期限、时间限制、运输的能力、资源的优化，更多的条 件来自于天气状况、交通情况、车辆在中途受损等不可预知的事件，这些变化让预先 制定好的执行顺序不能正常运行，此时引入智能规划方法，在复杂的环境中对交通运 输工具实时的进行规划，可以让物流系统的运行效率得到高效的运行。 网络信息集成是以领域本体为依据，在互联网内搜集信息并将信息与领域本体融 合为一体，从本质上来说就是提供一种重新理解和组织网络信息的机制。查询规划是 目l j 的主要研究方向。 东北师范大学硕士学位论文 2 1 规划识别概述 第二章规划识别 规划识别是依据发现的动作、现象来推断具有合理、完整而全面的因果联系的规 划描述的过程。作为心理学和人工智能研究的一重要个分支，规划识别涉及到信息表 述、行为推演、逻辑学、情景演算、人机交互、信息挖掘以及心理学等多个学科。 规划识别问题的解有：与已发现的动作相一致的目标，与己识别的目标或部分识 别的目标相对应的动作组成的有效规划序列。 2 2 规划识别的方法 1 9 7 8 年，规划识别作为一个研究问题出现。s c h m i d t 、s r i d h a r a n 和g o o d s o n 。 把心理学实验与c o h e n 等人的提供人类行动证据的实验h 1 相结合，用于推理其它智能 体的规划及目标。随后，其他一些关于规划识别的理论方法陆续出现。 1 基于事件层次的规划识别 在k a u t z 理论的推理方法基础上出现了基于事件层次结构的规划识别。1 9 8 6 年 k a u t z 和a 1 l e n 第一次提出了通用的规划识别模型理论，这是也是规划识别发展过程 中的第一个形式化理论，在规划识别研究历史中具有重要的意义。该理论提出了规划 库的概念，所谓规划库就是建立一个由动作的不同抽象组成的层次结构。在对规划进 行识别的过程中，将发现到的动作同规划库中的规划进行对比，每发现一个动作，识 别器就将与该动作冲突的规划删除掉，并将发现的动作添加到一致规划中，以此来建 立用户高层目标的规划。 2 基于限定理论的规划识别 m c c a r t h y 于2 0 世纪7 0 年代末提出了限定理论，它是最早进行研究的非单调推 理方法之一，其主要思想是：如果一个句子描述了一个命题，那么它描述的仅仅是这 个命题而不能进行扩展和延伸。如，文具店卖笔，那么就表示只有文具店才卖笔，其 他任何可能的卖笔的个人或场所都不能被考虑。 k a u t z 所提出的最小规划集，与限定理论相似，但由于限定理论的运算十分复杂， 包含了二阶逻辑，因此k a u t z 并没有用限定方式直接对规划进行求解，而仅仅提出了 三个假设。 在k a u t z 的规划识别理论上，姜云飞和马宁于2 0 0 2 年提出了基于限定理论的求 解规划识别问题的新方法，增强了k a u t z 方法中规划识别的容错能力。文中提出了枚 举和分解的概念，并在溯因理论的基础上构建了规划识别的模型。 6 东北师范大学硕士学位论文 3 基于语法分析的规划识别方法 v i l l a i n 于1 9 9 0 年在k a u t z 理论的基础上提出了一种基于语法分析的规划识别 方法。他对k a u t z 理论中的复杂度进行分析的方式是减少规划识别的限制条件。十年 后，p y n a d a t h 和w e l l m a n 又提出了基于概率状态独立语法的理论。此法扩展了上下 文概率无关语法。因为该语法具有更多的独立假设，所以可以在更广泛的问题领域中 进行应用，同时能够支持有效的语法分析算法。 4 基于概率方法的规划识别 在纯粹的逻辑框架基础上会产生不止一个的规划假设，虽然每个假设被执行的可 能性不尽相同，但在基于逻辑的规划识别框架中得到的对待是等同的。因此有人提出 引入不确定性来对规划假设排列顺序，进而选出最优解作为被识别出的规划解。 c h a r n i a k 和g o l d m a n 提出贝叶斯推理，b a u e r 提出证据理论。 c h a r n i a k 和g o l d m a n 把规划识别当作是一种特殊的推理，并提出了一种由发现 的动作构建可能的解释图的规划识别方法，这就是基于贝叶斯网络的规划识别模型。 此模型主要功能是生成贝叶斯网络，根据已知的知识库及给定的动作来组成规划识别 贝叶斯网络集合，而后采取反向链式规则开始推理。此方法的问题主要在知识库与证 据集合增多时，贝叶斯网络的规模会快速的扩大，因此它不适合于复杂的问题领域。 贝叶斯方法是对一个解释的可能性采取概率中的贝叶斯理论进行评估的一种方 法。此方法下的规划识别理论是将所有可能的解释全部生成，而后用贝叶斯理论对各 个解释进行评估，选出最有可能的一个。与贝叶斯网络方法的不同之处在于：贝叶斯 网络方法是利用贝叶斯网络来表示规划库中的因果关系，并利用新出现的条件进行推 理，而贝叶斯方法则是使用贝叶斯推理来评估每个规划出现的概率，然后选取机会最 大的作为最优解。 5 基于回归图的规划识别 殷明浩，谷文祥在随1 目标图的基础上提出了规划识别的另一种图形表示回归 图。这种识别方法也是无库识别的一种方法。回归图的方法既有自己独特的优点，又 保留了目标图能够识别出可能的一致目标及确定的一致目标的优点。由三类节点组成 了回归图，分别是动作节点、命题节点和目标节点，在回归图里这三类节点是交替出 现的。 回归图中的节点划分为确定的或可能的节点，这两类节点分别对确定的目标及可 能的目标进行识别，其中确定的节点描述观察到的动作，而可能的节点描述领域知识。 此方法中识别器观察到一个动作就添加一个确定节点到途中，同时后退一步，删除剩 余的根据领域知识生成但与观察到的动作相互冲突的动作及命题接待你，利用这种回 退的方式来识别确定及可能的目标。 2 3 规划识别的分类 在规划识别的发展过程中出现了非常多的方法，现将这些规划识别方法进行分 7 东北师范大学硕士学位论文 析： 1 根据识别系统是否具有规划库 分为有库的规划识别( w i t hp l a nl i b r a r y ) 和无库的规划识别( w i t ho u tp l a n l i b r a r y ) m 。 我们可以预先描述可能被执行的规划，通过事件层、分层任务网络、知识图等其 他方式来作为规划识别的依据。大部分规划识别都是通过现有的规划库进行推理、判 断、观察等方法直观的得出被识别的规划。但前提是必须建立规划库，而且会浪费大 量的空间、时间来执行搜索过程。如果被识别的规划不在库中，则识别率通常偏低。 另外为了能够识别新出现的规划，规划库还需要经常更新。这种方式为有库识别。 无库识别是指在识别过程中可以不用创建规划库，在这种情况下仍然能识别出智 能体的规划。目前比较典型的采用无库的识别方法的有殷明浩的基于回归图的规划识 别方法和j u nh o n g 的基于目标图分析的规划识别方法。没有规划库的识别方法适合 用在军事对抗、入侵检测等比较灵活的范围中，能够识别出从未发现过的新的规划。 2 根据被识别智能体在规划识别中的作用： 可以划分为洞孔式规划识别( k e yh o l er e c o g n i t i o n ) 及有意的规划识别 ( i n t e n d e dr e c o g n i t i o n ) 。 洞孔式在识别过程中，a g e n t 只负责完成自己的动作，不会刻意阻碍识别器对其 进行识别，也不会为识别器提供帮助，而是在不引起别人注意的情况下来观察和推测 a g e n t 的目标，此时的a g e n t 不会影响规划识别过程。 有意的识别方法中，a g e n t 会对整个的识别过程产生两种截然不同的影响：阻碍 识别过程或帮助识别过程。阻碍识别过程，通常在军事战争中会出现这种情况，如果 智能体发现自己的规划被敌对方观察和预测时，它会采取各种有效的行动来干扰规划 识别的过程；帮助识别过程主要应用在协作规划环境中，a g e n t 尽量传递它的规划， 有意让识别器理解其执行的动作，如机器人足球、对话系统、程序理解等研究范围。 3 能否完全观察到被识别的动作 能够完全观察动作的规划识别( o b s e r v e dc o m p l e t ea c t i o n s ) ：被识别a g e n t 的全部动作在这种识别方法下都能被观察到，并且这些动作之间的完全执行顺序也能 观察到。 能够观察部分动作的规划识别( o b s e r v e ds e g m e n ta c t i o n s ) ：被识别a g e n t 执 行的动作中能被观察到的只有部分动作，这种结果可能是由于智能体在识别过程中隐 藏了某些动作，或在识别过程中诱导智能体而使某些动作而被漏掉。 2 4 规划识别的应用 规划识别技术在很多的领域中都得到了广泛的应用，如智能用户接口、自然语言 理解、入侵检测及军事对抗等领域。 1 在智能用户接口中可以通过规划识别技术来关注用户的动作，同时在合适的时 8 东北师范大学硕士学位论文 刻为用户给予帮助，或在识别出用户的最终目标后直接为用户完成目标，减轻负担。 在本领域内多分为两类形式：智能帮助系统，多智能体交互协作。在智能帮助系统中 应用规划识别技术可以帮助观察用户的动作，并识别出用户正在进行的操作目标，从 而给出帮助。多个智能体交互协作通常发生在较为复杂的应用环境中，任务的完成需 要多个智能体之间互相通信，除了了解自身的任务和目标外还需要掌握其他智能体的 任务及目标。此时应用规划识别技术可以让每个智能体了解其他智能体的最终目标及 现有规划，从而调整自身的规划，更好的相互合作完成任务。 2 入侵检测是网络安全中很活跃的一个研究领域，很多专家都表示入侵监测系统 如果想发展的更好，就必须将人工智能方法加入到其中。规划识别的原则是从已发现 的动作来预测未发生的动作，与入侵监测系统的目的一致。g e i b 和g o l d m a n 在2 0 0 1 年将规划识别技术应用到入侵检测领域中，采用了基于规划执行的方法，此方法没有 过多的设置限制性假设，可以处理更多的规划识别问题。 3 在军事对抗环境中，引入规划识别技术有着重要的意义，特别是需要根据侦察 到的各种信息做战略决策的时候。军事指挥这需要及时了解战场情况，预测战争未来 的走势，这就需要规划识别快速、高效、准确的给出敌方规划。在1 9 8 6 年，j e r o m e a z a r e w i c z 等就将规划识别技术在空运战术中进行了应用，称之为战术规划识别方 法。此后，又给出基于模板，并可以应用于多种智能体共存的环境中的战术规划识别 方法。1 9 9 8 年m u l d e r 给出了另一种通用任务模型，这种模型主要是用来识别敌方的 规划，打破了早期不能识别未经确认的观察结果的限制。2 0 0 3 年，f r a n km u l d e r 和 f r a n sv o o r b r a a k 有对战术规划识别做了形式化的描述，他们指出对敌方被观察对象 一致性的识别是尤为重要的。因为我们不知道在战术规划识别中观察到的动作是否来 自于同一个对象，所以，战术识别器只是生成规划假设是不够的，还需要将规划假设 进行赋值，根据这些赋值来判定动作是否来源于同一对象，这种方法能够较好的识别 出相似的敌对智能体。 9 东北师范大学硕士学位论文 第三章规划图 我们将在下面的章节中将介绍规划图的相关概念、原则及其扩张过程的每一个基 本步骤。以图的形式来描述规划问题能够更直观更透彻的表示出规划问题的实质性。 3 1 规划图的概念 对于任意一个规划问题( p l a n n i n gp r o b l e m ) 通常会涉及到下列四个集合：操作 集、对象集、初始条件集、目标集。对于任意一个规划图，通常会涉及到以下五个概 念： 1 动作 一个完全实例化的操作叫做动作n 们。规划的任务就是在一定的初始状态下对某个 具体的对象执行了一系列的动作，最终实现了这个问题的目标。 2 n o o p 动作 我们把一种对命题不作任何改变的动作就叫做n o o p 动作n 0 1 。执行一个操作后， 可能会产生某些新命题，也可能某些真命题被变为假命题；常规状态下，想要执行一 个操作，必须在几个命题同时真的情况下才可以。而对于n o o p 动作，他的前提条件 可以是任意一个真命甩而它被执行后命题依然为真。 3 规划图 由三类边、两类节点组成的经典图就是规划图3 。其中三类边分别是添加效果边 ( a d d e d g e ) 、前提条件边( p r e c o n d i t i o ne d g e ) 和删除效果边( d e l e t ee d g e ) 。两 类节点是命题结点( p r o p o s i t i o n n o d e ) 和动作结点( a c t i o nn o d e ) 。 4 规划图的稳定 所谓的规划图的稳定状态是指在扩张阶段，对于时间步来讲，出现一个时间步n ， 如果在n 后的任意一个时间步m 都能得到，两个时间步的命题集合、动作集合、互斥 关系都是相同的n 训。 5 有效规划 要将一个动作集合称为有效规划的前提是该动作集合中，每一个相同时间步下执 行的任意两个动作都均不互斥，每一个动作的时间步都被明确的指出，并且在最后的 时间步上所有的问题目标都是真值。 3 2 规划图的算法 规划图算法在扩张阶段和提取规划阶段之间交替执行。规划图的扩张阶段分为正 反两个方向，其中正向的扩张的目标状态为全部命题均出现同时每两个命题之间不互 斥，也可以是规划图扩张到稳定状态。提取规划阶段是对规划图进行逆向搜索，从而 1 0 东北师范大学硕士学位论文 得出规划解。 1 扩张规划图 首先，将所有在初始条件中出现的命题划为时间步1 的命题列，每个节点表示一 个命题。 其次，观察操作集合中的每一个对象，如果该对象的所有前提都在命题列中，那 么就可以将该对象实例化，随着每个对象的实例化就得到一系列的动作节点，这样就 可以得到时间步1 的动作列。并用前提条件边将动作节点和它的前提条件节点进行连 接。 第三步，生成i + l 时间步的命题列。i + l 时间步的命题列由i 时间步的包括n o o p 动作在内的所有动作的添加效果组成。其做法为：用添加效果边将每个对象的 动作节点与它添加效果后的命题节点连接起来，用删除效果边将每个对象的动作节点 与他删除效果后的命题节点连接起来。同时将命题之间存在互斥关系的进行标识。判 断两个命题是否互斥的依据为命题一的任意一个支持动作与命题二的所有动作均发 生冲突，这时我们说两个命题之间是互斥关系。 第四步，判断目标集合中的对象是否已经都在命题列中出现，同时任意两个对象 是否都不互斥。如果对象已经全部出现，并任意两个不互斥，那么结束规划图的扩张， 开始反向查找有效规划；反之，生成i + l 时间步的动作列。 生成i + l 时间步的动作列时，需要判断操作集合中的每个对象是否所有前提都存 在于i + l 时间步的命题列中，同时注意每个命题都不可以互斥，此时就能把这个对象 实例化，得到一个动作节点。在所有对象都进行实例化以后，就可以得到i + l 时间步 的动作列。 2 提取规划 在第2 个时间步以后，每个命题列出现后，就可以在当前命题列中查找目标的集 合。查找结果分两种情况：一是最后一个时间步的问题目标集合中的命题还有尚未出 现的，此时需要对规划图继续进行扩张；二是最后一个时间步的问题目标集合中所有 命题都已经在命题列中，且每两个都是不冲突的，此时可以开始查找有效的规划。 稳定的规划图，必定是以时间步t 的命题列作为结束列，在目标集中取定任意一 个命题，观察在前一个时间步中该命题的支持动作，从它的支持动作中选定一个动作， 称为动作1 。再从剩余的问题目标集中选出一个命题，观察该动作在t - i 时间步中的 支持动作，选定动作2 ，选取的过程中要注意动作1 与动作2 不可以互相冲突。根据 此种方法继续将剩余的动作3 ，动作4 ，动作n 选出。 把动作1 ，动作2 ，动作3 ，动作n 的所有前提都放到一起，形成次目标 集，该集合由t - i 时间步命题列的所有命题构成。假设次目标可以在t - 1 个时间步内 实现，那么原始目标集完全能够在t 个时间步内实现。次目标集的生成过程称为目标 集合创建步。 重复此过程，如果若干步以后的次目标集是初始条件命题集的子集，那么我们就 找到了有效规划。如果在查找动作的过程中发现某个时间步中支持目标的任意一个动 1 1 东北师范大学硕士学位论文 作都与已经取定的动作冲突，此时应该后退一步，但是不等同于没有有效规划，可以 从支持动作的其他选法继续进行下去。 1 2 东北师范大学硕士学位论文 第四章基于规划图的对手规划识别方法 从这一章起，我们开始介绍本文的重点工作。由涉及到的对手规划知识库，得出 规划图，并介绍基于该图的对手识别方法，最终总结出识别检测的方法。 4 1 对手规划识别库 由于在对手范畴内，敌对方经常隐藏自己的最终目标和规划，有些时候更会进行 一系列诱导或迷惑的动作来误导我们，妨碍我们进行正确的识别。因此，我们的规划 器能否及时、正确的生成有效的应对规划其中的规划识别器起着重要的作用。 本文主要利用目标分解的方法，对于背景知识的表述采用分层知识树来进行，从 高层抽象目标开始逐层分解，一直分解到能够用利用抽象动作直接表述低层抽象目标 为止。正常状况下，每个高层目标的分解形式不仅仅有一种。图4 1 是分层知识树的 一个结构图。 图4 1 分层知识树 图4 1 的分解过程为：将a 1 分解为b 1 、b 2 和b 3 ，b 1 分解为c 1 、c 2 ，c 1 分解为 d 1 、d 2 ，c 2 分解为d 3