第2卷第1期 智能系统学报 Vol.2 Ne 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 规划识别的研究及其应用 谷文祥，李丽，李丹丹 (东北师范大学计算机学院，吉林长春130117) 摘要：规划识别是人工智能研究领域的一个重要分支.由于近年来的广泛应用，规划识别的重要性被越来越多的 学者所认同.对规划识别领域的大量文献进行广泛而深入研究，从整体上阐述了规划识别问题，较为全面地介绍了 规划识别的发展历程分类、方法以及应用，并着重介绍了规划识别目前较为流行的技术方法和热门应用，公开了几 个未解决的问题 关键词：人工智能：规划识别：智能规划 中图分类号：TP18文献标识码：A文章编号：16734785(2007)01-0001-15 Research and a pplication of plan recognition GU Wemxiang,LI Li,LI Dandan (School of Computer,Northeast Normal University,Changchun 130117,China) Abstract:Plan recognition is an important part of artificial intelligence.As its extensive application in re- cent years,plan recognition has been focused by more and more researchers.Based on the comprehensive and profound research on large numbers of references in the domain of plan recognition,this paper expati- ates on the problem of plan recognition in the mass,and introduces the development,classification,ap- proaches and application.Moreover,the popular techniques and hot application of plan recognition are em- phasized at present.Finally,several open problems unsettled are provided. Key words:artificial intelligence;plan recognition;intelligent planning 规划识别是人工智能中一个活跃的研究领域。 一种基于语法分析的规划识别理论s1.同年，Car 规划识别问题是指从观察到的某一智能体的动作或berry将Dempster-Shafer理论应用到规划识别 动作效果出发，推导出该智能体目标/规划的过 中6，通过多个证据来计算假设规划的联合支持度. 程口.早期的规划识别是基于规则推理的，研究者试 1991年，Charniak和Goldman构建了规划识别的 图与推理规则保持一致，以此来掌握规划识别的特 第一个概率模型7】，并将贝叶斯网络应用到规划 性.而如今很多推理技术都在规划识别中有所应用. 识别中，这使得规划识别方法向更广泛的应用又迈 Schmidt,Sridharan和Goodson在l978年第 进了一步.1999年，Goldman等人又提出了基于规 一次将规划识别作为一个研究问题提出).他们把 划执行的规划识别方法山，该方法从一个新的角度 心理学实验与Cohen等人的提供人类行动证据的 出发来解决规划的识别问题.之后的几年里，Gold 实验)相结合，用于推理其他智能体的规划及目标. man等人对这种方法不断的修改，并将其应用到了 Charniak和McDemott在1985年提出进行规划识 多种领域，特别是敌对环境下的规划识别. 别的最好方式是溯因).他认为这样才能推导出最 规划识别从提出到现在经过了近30年的发展 合理的目标解释.1986年，Kautz和Allen第一次形 历程，其方法也日趋成熟.目前，规划识别已经成为 式化了规划识别理论！，这是规划识别研究的一个 人工智能中比较热门的研究方向之一 里程碑.1990年Vilain以Kautz理论为基础提出了 1 规划识别分类 收稿日期：20060722. 规划识别有多种分类方法，概括起来有如下几 基金项目：国家自然科学基金资助项目(60573067,60473042) 种 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 规划识别的研究及其应用 谷文祥 , 李 丽 , 李丹丹 (东北师范大学 计算机学院 ,吉林 长春 130117) 摘 要 :规划识别是人工智能研究领域的一个重要分支. 由于近年来的广泛应用 ,规划识别的重要性被越来越多的 学者所认同. 对规划识别领域的大量文献进行广泛而深入研究 ,从整体上阐述了规划识别问题 ,较为全面地介绍了 规划识别的发展历程、分类、方法以及应用 ,并着重介绍了规划识别目前较为流行的技术方法和热门应用 ,公开了几 个未解决的问题. 关键词 :人工智能 ;规划识别 ;智能规划 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0120001215 Research and application of plan recognition GU Wen2xiang , L I Li , L I Dan2dan (School of Computer , Northeast Normal University , Changchun 130117 , China) Abstract : Plan recognition is an important part of artificial intelligence. As its extensive application in re2 cent years , plan recognition has been focused by more and more researchers. Based on t he comprehensive and profound research on large numbers of references in t he domain of plan recognition , t his paper expati2 ates on t he problem of plan recognition in the mass , and introduces t he development , classification , ap2 proaches and application. Moreover , t he pop ular techniques and hot application of plan recognition are em2 p hasized at present. Finally , several open problems unsettled are provided. Keywords :artificial intelligence ; plan recognition ; intelligent planning 收稿日期 :2006207222. 基金项目 :国家自然科学基金资助项目(60573067 ,60473042) . 规划识别是人工智能中一个活跃的研究领域. 规划识别问题是指从观察到的某一智能体的动作或 动作效果出发 ,推导出该智能体目标/ 规划的过 程[1 ] . 早期的规划识别是基于规则推理的 ,研究者试 图与推理规则保持一致 ,以此来掌握规划识别的特 性. 而如今很多推理技术都在规划识别中有所应用. Schmidt , Sridharan 和 Goodson 在 1978 年第 一次将规划识别作为一个研究问题提出[2 ] . 他们把 心理学实验与 Cohen 等人的提供人类行动证据的 实验[ 3 ]相结合 ,用于推理其他智能体的规划及目标. Charniak 和 McDemott 在 1985 年提出进行规划识 别的最好方式是溯因[3 ] . 他认为这样才能推导出最 合理的目标解释. 1986 年 , Kautz 和 Allen 第一次形 式化了规划识别理论[4 ] ,这是规划识别研究的一个 里程碑. 1990 年 Vilain 以 Kautz 理论为基础提出了 一种基于语法分析的规划识别理论[5 ] . 同年 ,Car2 berry 将 Demp ster2Shafer 理论应 用到规划 识别 中[6 ] ,通过多个证据来计算假设规划的联合支持度. 1991 年 ,Charniak 和 Goldman 构建了规划识别的 第一个概率模型[7 - 8 ] ,并将贝叶斯网络应用到规划 识别中 ,这使得规划识别方法向更广泛的应用又迈 进了一步. 1999 年 , Goldman 等人又提出了基于规 划执行的规划识别方法[1 ] ,该方法从一个新的角度 出发来解决规划的识别问题. 之后的几年里 , Gold2 man 等人对这种方法不断的修改 ,并将其应用到了 多种领域 ,特别是敌对环境下的规划识别. 规划识别从提出到现在经过了近 30 年的发展 历程 ,其方法也日趋成熟. 目前 ,规划识别已经成为 人工智能中比较热门的研究方向之一[9 - 10 ] . 1 规划识别分类 规划识别有多种分类方法 ,概括起来有如下几 种 :
·2 智能系统学报 第2卷 1.1根据智能体在规划识别中的作用 全掌握动作的前提、效果或动作的执行概率等情况， 这是规划识别最常用的分类方法.Cohen,Per 由于无完整领域知识的规划识别复杂度较高， rault和Allen在1981年提出了规划识别的这种分 目前的规划器大都假设识别器具有完整的领域知 类方法，当时的分类中包括2种识别，分别为洞 识 孔式规划识别和协作式规划识别.2001年Geib和 1.4 根据所识别的规划是否有错误 Goldman又在此基础上增加了对手式规划识别2]. 1)对无误规划的规划识别：识别器所识别的智 1)洞孔式规划识别：智能体不关心或者不知道 能体在进行规划的过程中，所执行的每一个动作对 识别器在观察它的动作.在识别器识别的过程中，智 于到达目标都是必要的 能体不会为识别器提供帮助，也不会刻意阻碍识别 2)对有误规划的规划识别：识别器所识别的智 器对它进行识别 能体在进行规划的过程中，执行了一些错误动作这 2)协作式规划识别：智能体积极配合识别器的 些错误动作，或者是智能体本身能力限制造成的，或 识别，智能体所做的动作有意让识别器理解 者是智能体为了干扰识别器对它的识别而特意执行 3)对手式规划识别：智能体所做的动作对识别 的干扰性动作」 方造成了威胁，破坏了识别方的正常规划，而且智能 所识别的规划是否是有误规划，还要依据识别 体还会阻止或干扰识别器对它的识别. 背景及经验来判断.与实际情况更接近的是假设所 这3种规划识别都有其自身的特点，因此它们 识别的规划存在错误.但为了简便，目前大多数的规 的应用领域也不尽相同.洞孔式的规划识别主要应 划识别方法都是在假设所识别的规划为无误规划的 用在生产监控、智能用户接口等领域.协作式规划识 前提下进行的。 别主要应用在机器人足球、故事理解等领域：对手式 1.5根据所识别的动作序列是否完全可观察 规划识别则应用在入侵检测、军事指挥等敌对的环 1)完全可观察规划识别：识别器能够观察到所 境下.在这3种规划识别中，较为常用的是洞孔式规 识别智能体的全部动作及动作的执行顺序 划识别 2)部分可观察规划识别：识别器不能观察到所 1.2根据规划识别是否具有规划库 识别智能体的全部动作.这可能是由于识别器遗漏 1)有库的规划识别：用分层任务网络、事件层、 了，也可能动作本身是不可观察的.这种情况通常用 知识图或其他方式预先描述规划，并用这些规划作 动作的效果来进行识别 为规划识别的依据 完全可观察的规划识别比部分可观察的规划识 2)无库的规划识别：识别器不需要根据预先给 别要相对简单，通常情况下人们都是假设所观察的 定的规划就能给出识别结果 动作序列是完全可观察的，以降低识别的难度.但 目前大部分的规划识别方法都是有库的规划识 是，在现实生活中，很多情况是无法完全观察到的， 别.该方法直观、易于理解，但用这种方法进行识别 尤其是识别方与被识别方是敌对关系的情况下，想 前，需要做大量的建立规划库的准备，在搜索过程中 要得到对方的全部动作信息更是无法做到，因此，部 常常会消耗大量时间或空间.无库的规划识别突破 分可观察规划识别有更高的研究价值.从某种角度 了必须有特定规划库才能进行规划识别的限制，现 来看，完全可观察规划识别是部分可观察规划识别 有的基于无库规划识别的方法很少，主要是以Jun 的特例 Hong的基于目标图分析的规划识别方法.41和 1.6根据观察是否可信赖 Minghao Yin的基于回归图的规划识别方法1s]为 1)观察可信赖的规划识别：所观察到的动作就 代表.无库规划识别方法可以识别出新的规划因此 是实际发生了的动作，对这些动作所做的规划识别 很适合入侵检测、战术规划识别等智能体处于敌对 就是观察可信赖的规划识别。 状态的规划识别问题.但是，由于这种方法还不完 2)观察不可信赖的规划识别：在这种识别中，有 善，不能判断规划假设的优劣，可应用领域还比较狭 些动作不能完全肯定是否真实发生了，它们的发生 农 带有一种可能性.这种动作通常都被赋予一个可信 1.3根据规划识别是否有完整的领域知识 度，以确定该动作可信赖的程度 1)有完整领域知识的规划识别：识别器完全掌 由于识别器的疏忽或某些情况的干扰，识别器 握动作的前提、效果或动作的执行概率等情况 可能无法确定一些动作是否真实发生，因此导致了 2)无完整领域知识的规划识别：识别器不能完 观察不可信赖.为使问题求解更容易，或者某些领域 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
111 根据智能体在规划识别中的作用 这是规划识别最常用的分类方法. Cohen , Per2 rault 和 Allen 在 1981 年提出了规划识别的这种分 类方法[11 ] ,当时的分类中包括 2 种识别 ,分别为洞 孔式规划识别和协作式规划识别. 2001 年 Geib 和 Goldman 又在此基础上增加了对手式规划识别[ 12 ] . 1) 洞孔式规划识别 :智能体不关心或者不知道 识别器在观察它的动作. 在识别器识别的过程中 ,智 能体不会为识别器提供帮助 ,也不会刻意阻碍识别 器对它进行识别. 2) 协作式规划识别 :智能体积极配合识别器的 识别 ,智能体所做的动作有意让识别器理解. 3) 对手式规划识别 :智能体所做的动作对识别 方造成了威胁 ,破坏了识别方的正常规划 ,而且智能 体还会阻止或干扰识别器对它的识别. 这 3 种规划识别都有其自身的特点 ,因此它们 的应用领域也不尽相同. 洞孔式的规划识别主要应 用在生产监控、智能用户接口等领域. 协作式规划识 别主要应用在机器人足球、故事理解等领域 ;对手式 规划识别则应用在入侵检测、军事指挥等敌对的环 境下. 在这 3 种规划识别中 ,较为常用的是洞孔式规 划识别. 112 根据规划识别是否具有规划库 1) 有库的规划识别 :用分层任务网络、事件层、 知识图或其他方式预先描述规划 ,并用这些规划作 为规划识别的依据. 2) 无库的规划识别 :识别器不需要根据预先给 定的规划就能给出识别结果. 目前大部分的规划识别方法都是有库的规划识 别. 该方法直观、易于理解 ,但用这种方法进行识别 前 ,需要做大量的建立规划库的准备 ,在搜索过程中 常常会消耗大量时间或空间. 无库的规划识别突破 了必须有特定规划库才能进行规划识别的限制 ,现 有的基于无库规划识别的方法很少 ,主要是以 J un Hong 的基于目标图分析的规划识别方法[13 - 14 ] 和 Minghao Yin 的基于回归图的规划识别方法[15 ] 为 代表. 无库规划识别方法可以识别出新的规划 ,因此 很适合入侵检测、战术规划识别等智能体处于敌对 状态的规划识别问题. 但是 ,由于这种方法还不完 善 ,不能判断规划假设的优劣 ,可应用领域还比较狭 窄. 113 根据规划识别是否有完整的领域知识 1) 有完整领域知识的规划识别 :识别器完全掌 握动作的前提、效果或动作的执行概率等情况. 2) 无完整领域知识的规划识别 :识别器不能完 全掌握动作的前提、效果或动作的执行概率等情况. 由于无完整领域知识的规划识别复杂度较高 , 目前的规划器大都假设识别器具有完整的领域知 识. 114 根据所识别的规划是否有错误 1) 对无误规划的规划识别 :识别器所识别的智 能体在进行规划的过程中 ,所执行的每一个动作对 于到达目标都是必要的. 2) 对有误规划的规划识别 :识别器所识别的智 能体在进行规划的过程中 ,执行了一些错误动作. 这 些错误动作 ,或者是智能体本身能力限制造成的 ,或 者是智能体为了干扰识别器对它的识别而特意执行 的干扰性动作. 所识别的规划是否是有误规划 ,还要依据识别 背景及经验来判断. 与实际情况更接近的是假设所 识别的规划存在错误. 但为了简便 ,目前大多数的规 划识别方法都是在假设所识别的规划为无误规划的 前提下进行的. 115 根据所识别的动作序列是否完全可观察 1) 完全可观察规划识别 :识别器能够观察到所 识别智能体的全部动作及动作的执行顺序. 2) 部分可观察规划识别 :识别器不能观察到所 识别智能体的全部动作. 这可能是由于识别器遗漏 了 ,也可能动作本身是不可观察的. 这种情况通常用 动作的效果来进行识别. 完全可观察的规划识别比部分可观察的规划识 别要相对简单. 通常情况下人们都是假设所观察的 动作序列是完全可观察的 ,以降低识别的难度. 但 是 ,在现实生活中 ,很多情况是无法完全观察到的 , 尤其是识别方与被识别方是敌对关系的情况下 ,想 要得到对方的全部动作信息更是无法做到 ,因此 ,部 分可观察规划识别有更高的研究价值. 从某种角度 来看 ,完全可观察规划识别是部分可观察规划识别 的特例. 116 根据观察是否可信赖 1) 观察可信赖的规划识别 :所观察到的动作就 是实际发生了的动作 ,对这些动作所做的规划识别 就是观察可信赖的规划识别. 2) 观察不可信赖的规划识别 :在这种识别中 ,有 些动作不能完全肯定是否真实发生了 ,它们的发生 带有一种可能性. 这种动作通常都被赋予一个可信 度 ,以确定该动作可信赖的程度. 由于识别器的疏忽或某些情况的干扰 ,识别器 可能无法确定一些动作是否真实发生 ,因此导致了 观察不可信赖. 为使问题求解更容易 ,或者某些领域 ·2 · 智 能 系 统 学 报 第 2 卷
第1期 谷文祥，等：规划识别的研究及其应用 。3 不存在不可信赖的动作，通常的规划识别都假设观 20世纪70年代末提出的.人类和智能计算机常常 察是可信赖的 需要得出这样的一些结论：某些具有特定属性或关 2规划识别方法 系的对象是仅有的满足这些关系的对象.McCarthy 的限定理论就形式化了这种推理.由于限定理论是 就规划识别方法而言，规划识别可分为基于一 在一阶逻辑上添加一些限定规则，因此，可以用传统 致的规划识别和基于概率的规划识别.“一致”主要 的逻辑语言来形式化非单调逻辑.而规划识别问题 是指与推理规则保持一致，而加入概率推理的即为 通常为非单调的逻辑推理问题，因而可以将限定理 基于概率的规划识别.下面介绍一些目前较为流行 论与规划识别问题相结合. 的规划识别方法 Kautz的规划识别问题就是求解观察动作的最 2.1基于事件层的规划识别 小规划集，这与限定理论的思想很相似.但由于限定 1986年Kautz和Alen提出了一种通用的规 理论包含二阶逻辑，计算十分复杂，因此，Kautz只 划识别模型，.这一模型几乎囊括了规划识别的所 是基于限定理论提出了3个假设（穷尽假设、互斥假 有子任务，是规划识别的第一个形式化理论.在该理 设、使用部件假设)，并没有直接用限定的方法来求 论中，每一个被观察动作都是一个或多个高层规划 解规划识别问题. 的一部分，规划识别任务是最小化这些高层动作，并 由于McCarthy限定理论难于计算，许多学者 用这些高层动作来解释观察动作集合· 在其计算方面都做了深入的研究.Lifschitz根据看 他们将动作和规划统称为事件，用事件层来表 待谓词最小化的角度不同，提出了逐点限定.Doher- 示已知的可能规划.在事件层中，根节点为高层动 ty和Lukaszewicz提出了一种将二阶限定公式降为 作，其他动作均依赖于高层动作.用End表示具有 逻辑等效的一阶公式的新方法，用逐点限定的一阶 独立意义、不需要进一步推导的规划，抽象于End 形式直接计算限定，该方法简化了限定计算的难度 的事件都是End事件.事件层中包括： 2002年，姜云飞和马宁在Kautz规划识别的基 1)一元事件类型谓词集(H); 础上，结合以上2种方法，提出了基于限定的规划识 2)抽象公理集(HA); 别问题求解的新方法2o,.根据Kautz规划识别，姜 3)基本事件类型谓词集(H); 云飞、马宁给出了分解和枚举的概念，并给出了限定 4)分解公理集(H); 求解规划识别问题的算法.以溯因理论为基础，他们 5)通用公理集(HG). 给出了规划识别的模型，即一个规划识别问题是一 该规划识别模型还包含4种假设：穷尽假设 个三元组,其中G是原子集，叫做观察 (EXA)、互斥假设(DIA)、使用部件假设(CUA)及 集；P是原子集，叫做规划集；T是背景理论.由一个 最小基数假设(MCA).前3种假设都是以McCar- 观察g(g∈G识别出的规划D(D三P)定义为 thy的限定理论为基础的.当观察到某一动作序列 1)T UD =8: 时，根据4种假设识别器会对其中的每个动作都生 2)T UD false: 成相应的解释图（解释图表示由某一动作推导出的 3)D是满足上述条件的极小集」 各种事件及事件间的关系)，并找出这些动作的所有 根据限定与规划识别的关系，他们给出定理，用 可能的合并结果.最后，选择合并后End事件最少 以说明对观察到的现象做限定获得的解集与由观察 的解释图或解释图集合作为规划识别的输出。 到的现象求出的最小规划集是一样的， 这种规划识别方法具有丰富的表达能力，可以 姜云飞等借鉴Kautz的规划识别方法，首次提 处理动作间的时序关系及不完全观察动作序列，并 出了用限定直接求解规划识别问题，弥补了Kautz 能够很好地识别偏序规划.但由于识别中采用了最 规划识别的不足，增强了规划识别的容错能力 小覆盖模型，并认为所有事件出现的可能性都是一 2.3基于规划知识图的规划识别 样的，使得识别结果过于武断.该识别还要求所识别 2002年，姜云飞、马宁在Kautz规划识别的基 的智能体不能犯错误，识别所依据的规划库是完整 础上提出了基于规划知识图的规划识别2)，他们将 的，因此也就缩小了该识别方法的应用范围6.1」 Kautz的事件层改造为更简便，更直观，更易于操作 2.2基于限定理论的规划识别 的规划表示方法—规划知识图.规划知识图是一 限定理论18.1是一种非单调推理方法，也是研 个非循环的与或图，由代表规划的节点集合组成.节 究得最早的非单调推理方法之一，是McCarthy在 点间由连接符连接，表示事件之间的整体与部分、具 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
不存在不可信赖的动作 ,通常的规划识别都假设观 察是可信赖的. 2 规划识别方法 就规划识别方法而言 ,规划识别可分为基于一 致的规划识别和基于概率的规划识别.“一致”主要 是指与推理规则保持一致 ,而加入概率推理的即为 基于概率的规划识别. 下面介绍一些目前较为流行 的规划识别方法. 211 基于事件层的规划识别 1986 年 Kautz 和 Allen 提出了一种通用的规 划识别模型[4 ] . 这一模型几乎囊括了规划识别的所 有子任务 ,是规划识别的第一个形式化理论. 在该理 论中 ,每一个被观察动作都是一个或多个高层规划 的一部分 ,规划识别任务是最小化这些高层动作 ,并 用这些高层动作来解释观察动作集合. 他们将动作和规划统称为事件 ,用事件层来表 示已知的可能规划. 在事件层中 ,根节点为高层动 作 ,其他动作均依赖于高层动作. 用 End 表示具有 独立意义、不需要进一步推导的规划 ,抽象于 End 的事件都是 End 事件. 事件层中包括 : 1) 一元事件类型谓词集( HE) ; 2) 抽象公理集( HA ) ; 3) 基本事件类型谓词集( HEB ) ; 4) 分解公理集( HD ) ; 5) 通用公理集( HG) . 该规划识别模型还包含 4 种假设 :穷尽假设 ( EXA) 、互斥假设 (DJ A) 、使用部件假设 (CUA) 及 最小基数假设 (MCA) . 前 3 种假设都是以 McCar2 t hy 的限定理论为基础的. 当观察到某一动作序列 时 ,根据 4 种假设识别器会对其中的每个动作都生 成相应的解释图(解释图表示由某一动作推导出的 各种事件及事件间的关系) ,并找出这些动作的所有 可能的合并结果. 最后 ,选择合并后 End 事件最少 的解释图或解释图集合作为规划识别的输出. 这种规划识别方法具有丰富的表达能力 ,可以 处理动作间的时序关系及不完全观察动作序列 ,并 能够很好地识别偏序规划. 但由于识别中采用了最 小覆盖模型 ,并认为所有事件出现的可能性都是一 样的 ,使得识别结果过于武断. 该识别还要求所识别 的智能体不能犯错误 ,识别所依据的规划库是完整 的 ,因此也就缩小了该识别方法的应用范围[16 - 17 ] . 212 基于限定理论的规划识别 限定理论[18 - 19 ]是一种非单调推理方法 ,也是研 究得最早的非单调推理方法之一 ,是 McCart hy 在 20 世纪 70 年代末提出的. 人类和智能计算机常常 需要得出这样的一些结论 :某些具有特定属性或关 系的对象是仅有的满足这些关系的对象. McCart hy 的限定理论就形式化了这种推理. 由于限定理论是 在一阶逻辑上添加一些限定规则 ,因此 ,可以用传统 的逻辑语言来形式化非单调逻辑. 而规划识别问题 通常为非单调的逻辑推理问题 ,因而可以将限定理 论与规划识别问题相结合. Kautz 的规划识别问题就是求解观察动作的最 小规划集 ,这与限定理论的思想很相似. 但由于限定 理论包含二阶逻辑 ,计算十分复杂 ,因此 , Kautz 只 是基于限定理论提出了 3 个假设(穷尽假设、互斥假 设、使用部件假设) ,并没有直接用限定的方法来求 解规划识别问题. 由于 McCart hy 限定理论难于计算 ,许多学者 在其计算方面都做了深入的研究. Lifschitz 根据看 待谓词最小化的角度不同 ,提出了逐点限定. Doher2 ty 和 Lukaszewicz 提出了一种将二阶限定公式降为 逻辑等效的一阶公式的新方法 ,用逐点限定的一阶 形式直接计算限定 ,该方法简化了限定计算的难度. 2002 年 ,姜云飞和马宁在 Kautz 规划识别的基 础上 ,结合以上 2 种方法 ,提出了基于限定的规划识 别问题求解的新方法[ 20 ] . 根据 Kautz 规划识别 ,姜 云飞、马宁给出了分解和枚举的概念 ,并给出了限定 求解规划识别问题的算法. 以溯因理论为基础 ,他们 给出了规划识别的模型 ,即一个规划识别问题是一 个三元组 ,其中 G 是原子集 ,叫做观察 集; P 是原子集 ,叫做规划集; T 是背景理论. 由一个 观察 g ( g ∈G) 识别出的规划 D ( D Α P) 定义为 1) T ∪D| = g; 2) T ∪D| ≠false ; 3) D 是满足上述条件的极小集. 根据限定与规划识别的关系 ,他们给出定理 ,用 以说明对观察到的现象做限定获得的解集与由观察 到的现象求出的最小规划集是一样的. 姜云飞等借鉴 Kautz 的规划识别方法 ,首次提 出了用限定直接求解规划识别问题 ,弥补了 Kautz 规划识别的不足 ,增强了规划识别的容错能力. 213 基于规划知识图的规划识别 2002 年 ,姜云飞、马宁在 Kautz 规划识别的基 础上提出了基于规划知识图的规划识别[21 ] . 他们将 Kautz 的事件层改造为更简便 ,更直观 ,更易于操作 的规划表示方法 ———规划知识图. 规划知识图是一 个非循环的与或图 ,由代表规划的节点集合组成. 节 点间由连接符连接 ,表示事件之间的整体与部分、具 第 1 期 谷文祥 ,等 :规划识别的研究及其应用 ·3 ·
4 智能系统学报 第2卷 体与抽象的关系 加了一个概率p(记作p(x→)，用此概率及语言 他们在规划知识图中添加了支持程度的概念 模型中的依赖关系，可以将语法分析分类，或删除不 支持程度是指一个规划（事件）的出现使另一个规划 必要的分析.该方法特别适合基于规则活动的识别 (事件)出现的可能性.由己观察到的动作，可能推出 Moore和Essa采用Earley-Stolcke算法来决定最 多种结果.Kautz会选择End事件最少的推理结果 大可能的语义推理结果.他们将错误分为3种：替换 作为识别的最终结果；姜云飞等则认为，不同动作在 错误插入错误和删除错误，并提出新的分析策略来 满足条件的规划内的重要程度是不一样的，所以对 进行错误检测和恢复，以此来提高规划识别的成功 规划出现可能性的支持程度也不同，因此，根据支持 概率.Moore和Essa以二十一点牌为例，描述了对 程度来判断识别的最终结果，会与实际情况更为接 视频中多任务活动的识别过程 近 利用SCFG方法进行规划识别能够从多个对 由于该方法添加了支持程度的概念，因此，与 象和任务的长期行为序列中有效地提取出高层行 Kautz规划识别相比，其结果更合理；方法中对知识 为.通过监控还可以对某一对象形成经验性评估，方 图采用了宽度优先搜索，比Kautz规划识别更简捷. 便进一步的识别 在基于规划知识图的规划识别方法之上，谷文 2.5基于规划执行的规划识别 祥、李杨等人又提出了一种带标记的反向搜索的规 1999年Goldman,Geib和Miller在文献[1]中 划识别算法2].该方法修改了规划知识图算法中对 给出了一种规划识别的新模型基于规划执行的 支持程度和可能性的部分计算，并采用了从下往上 规划识别.该模型的主要用途是向用户提供智能辅 动态生成解图的方法.在有多个或节点存在时，他们 助 对节点做了标记，使得动态增加新的观察现象时不 Kautz的规划识别是以规划图为核心，它要求 用完全重新生成解图.该方法解决了动态增加新节 确定动作的最小集合，其最终是一个图覆盖的问题， 点的问题 对比Kautz的规划识别，Goldman等人提出的这 2.4基于语法分析的规划识别 新模型是以规划执行为核心的，并加入了概率推理 1990年Vilain以Kautz理论为基础提出了一 用概率的方法替代了最小动作集合的方法，使识别 种基于语法分析的规划识别理论).他并没有真正 结果更合理，增强了规划识别的准确性】 采用语法分析的方法来处理规划识别问题，而是通 这一模型采用与或树作为规划库，相对于 过减少规划识别的限制情况来进行语法分析，用以 Kautz规划识别的事件层而言，更易于应用到计算 研究Kautz理论的复杂度 机上.该模型可以处理规划识别中遇到的多方面的 20o0年Pynadath和Wellman提出了基于概率 问题，包括：考虑世界状态的影响，利用否定证据，识 状态独立语法(probabilistic state-dependent gram~ 别中采用干预理论，对偏序规划的识别，处理重载动 mar,PSDG的规划识别方法21.该语法扩展了上 作及由自身原因触发的动作，并能识别交错规划， 下文无关语法(probabilistic context-free grammar, Goldman等人认为规划的执行是动态的，智能 PCFG.由于PCFG较同期的语法有更多的独立假 体可以选择执行任何已被激活的动作.因此，每一时 设，因此能够支持更广泛的问题领域，并能支持有效 刻智能体都会有一个装载着被激活动作的待定集 的语法分析算法.PSDG正是在继承了PCFG的这 合，智能体可以从当前待定集中选取任一动作来执 些优点之上，进一步要求产生式的概率要依赖于规 行.随着事件的进行，智能体会反复执行一个操作， 划智能体内部和外部状态的确切模型.给定规划生 即从当前待定集中选取动作执行，并生成新的待定 成过程的PSDG描述，通过利用PSDG语法独立特 集，再从新生成的待定集中选取动作执行，同时生成 性的推理算法，可以快速地识别出用户的提问，并给 新的待定集，如此反复.不同的选取方式会产生不同 出回答.PSDG模型的假设和推理算法缺乏一定的 的动作选取序列.一个解释对应一个待定集合的动 通用性，但是PSDG模型的约束限制保证了算法应 作选择序列，即一个解释记录了每一时刻从待定集 用的独立属性，同时也可阻止推理复杂化 合中选择的动作及这些动作执行的先后顺序，由于 2002年，Moore和Essa将上下文自由语法 待定集中待选动作的选取方式不唯一，在识别过程 (CFG)扩充为随机上下文自由语法(SCFG)24),并 中会生成很多种解释，每种解释本质上是一种对智 将该方法用于对视频中多任务活动的识别.Moore 能体所执行规划的猜想.Goldman等人在他们的模 和Essa为CFG中的每个产生式规则（如x→W添 型中加入了概率推理，这使得每种解释都具有一定 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
体与抽象的关系. 他们在规划知识图中添加了支持程度的概念. 支持程度是指一个规划(事件) 的出现使另一个规划 (事件) 出现的可能性. 由已观察到的动作 ,可能推出 多种结果. Kautz 会选择 End 事件最少的推理结果 作为识别的最终结果 ;姜云飞等则认为 ,不同动作在 满足条件的规划内的重要程度是不一样的 ,所以对 规划出现可能性的支持程度也不同 ,因此 ,根据支持 程度来判断识别的最终结果 ,会与实际情况更为接 近. 由于该方法添加了支持程度的概念. 因此 ,与 Kautz 规划识别相比 ,其结果更合理 ;方法中对知识 图采用了宽度优先搜索 ,比 Kautz 规划识别更简捷. 在基于规划知识图的规划识别方法之上 ,谷文 祥、李杨等人又提出了一种带标记的反向搜索的规 划识别算法[20 ] . 该方法修改了规划知识图算法中对 支持程度和可能性的部分计算 ,并采用了从下往上 动态生成解图的方法. 在有多个或节点存在时 ,他们 对节点做了标记 ,使得动态增加新的观察现象时不 用完全重新生成解图. 该方法解决了动态增加新节 点的问题. 214 基于语法分析的规划识别 1990 年 Vilain 以 Kautz 理论为基础提出了一 种基于语法分析的规划识别理论[5 ] . 他并没有真正 采用语法分析的方法来处理规划识别问题 ,而是通 过减少规划识别的限制情况来进行语法分析 ,用以 研究 Kautz 理论的复杂度. 2000 年 Pynadat h 和 Wellman 提出了基于概率 状态独立语法 (probabilistic state2dependent gram2 mar , PSD G) 的规划识别方法[23 ] . 该语法扩展了上 下文无关语法(probabilistic context2free grammar , PCFG) . 由于 PCF G较同期的语法有更多的独立假 设 ,因此能够支持更广泛的问题领域 ,并能支持有效 的语法分析算法. PSD G 正是在继承了 PCF G 的这 些优点之上 ,进一步要求产生式的概率要依赖于规 划智能体内部和外部状态的确切模型. 给定规划生 成过程的 PSD G 描述 ,通过利用 PSD G 语法独立特 性的推理算法 ,可以快速地识别出用户的提问 ,并给 出回答. PSD G模型的假设和推理算法缺乏一定的 通用性 ,但是 PSD G模型的约束限制保证了算法应 用的独立属性 ,同时也可阻止推理复杂化. 2002 年 , Moore 和 Essa 将上下文自由语法 (CF G) 扩充为随机上下文自由语法 (SCF G) [ 24 ] ,并 将该方法用于对视频中多任务活动的识别. Moore 和 Essa 为 CF G 中的每个产生式规则 (如 x →λ) 添 加了一个概率 p (记作 p ( x →λ) ) ,用此概率及语言 模型中的依赖关系 ,可以将语法分析分类 ,或删除不 必要的分析. 该方法特别适合基于规则活动的识别. Moore 和 Essa 采用 Earley2Stolcke 算法来决定最 大可能的语义推理结果. 他们将错误分为 3 种 :替换 错误、插入错误和删除错误 ,并提出新的分析策略来 进行错误检测和恢复 ,以此来提高规划识别的成功 概率. Moore 和 Essa 以二十一点牌为例 ,描述了对 视频中多任务活动的识别过程. 利用 SCF G 方法进行规划识别能够从多个对 象和任务的长期行为序列中有效地提取出高层行 为. 通过监控还可以对某一对象形成经验性评估 ,方 便进一步的识别. 215 基于规划执行的规划识别 1999 年 Goldman , Geib 和 Miller 在文献[ 1 ]中 给出了一种规划识别的新模型 ———基于规划执行的 规划识别. 该模型的主要用途是向用户提供智能辅 助. Kautz 的规划识别是以规划图为核心 ,它要求 确定动作的最小集合 ,其最终是一个图覆盖的问题. 对比 Kautz 的规划识别 , Goldman 等人提出的这一 新模型是以规划执行为核心的 ,并加入了概率推理 , 用概率的方法替代了最小动作集合的方法 ,使识别 结果更合理 ,增强了规划识别的准确性. 这一模型采 用与或 树作为规 划库 , 相 对于 Kautz 规划识别的事件层而言 ,更易于应用到计算 机上. 该模型可以处理规划识别中遇到的多方面的 问题 ,包括 :考虑世界状态的影响 ,利用否定证据 ,识 别中采用干预理论 ,对偏序规划的识别 ,处理重载动 作及由自身原因触发的动作 ,并能识别交错规划. Goldman 等人认为规划的执行是动态的 ,智能 体可以选择执行任何已被激活的动作. 因此 ,每一时 刻智能体都会有一个装载着被激活动作的待定集 合 ,智能体可以从当前待定集中选取任一动作来执 行. 随着事件的进行 ,智能体会反复执行一个操作 , 即从当前待定集中选取动作执行 ,并生成新的待定 集 ,再从新生成的待定集中选取动作执行 ,同时生成 新的待定集 ,如此反复. 不同的选取方式会产生不同 的动作选取序列. 一个解释对应一个待定集合的动 作选择序列 ,即一个解释记录了每一时刻从待定集 合中选择的动作及这些动作执行的先后顺序. 由于 待定集中待选动作的选取方式不唯一 ,在识别过程 中会生成很多种解释 ,每种解释本质上是一种对智 能体所执行规划的猜想. Goldman 等人在他们的模 型中加入了概率推理 ,这使得每种解释都具有一定 ·4 · 智 能 系 统 学 报 第 2 卷
第1期 谷文祥，等：规划识别的研究及其应用 。5 的概率给出适当的阈值，即可得到满足条件的解 态领域，一个被称为初始条件的命题集合，一个说明 释，由此可以判断智能体所执行的规划 可能目标的目标概要集合；一个在连续时间步观察 这种方法从一个新的角度出发构建了基于规划 到的动作集合 执行的规划识别，加入概率推理使其结果更合理，更 目标图是一个直接的层次图，由命题层、动作 准确.不仅如此，Goldman等人还在该模型中加入 层、目标层依次交错排列.目标图开始于时间步1的 了Pearl在1994年提出的干预理论，使得其智能辅 初始条件命题层，结束于当前所观察到的最后一个 助作用更大，效果更好.该模型可以很好地处理交错 动作所在时间步的目标层.识别过程首先从初始状 规划生成的动作序列、偏序规划，还可以利用背景进 态出发，根据所观察到的动作，反复执行目标扩张及 行推理.但在解释生成过程中不能排除空间按指数 动作扩展，并对目标图进行分析，找到与观察动作一 级增长的情况.Goldman等人认为该模型不能与周 致的已完成或部分完成的目标.删除冗余目标，并选 围环境交互，并且没有考虑到世界的状态的改变. 择具有最多相关动作的一致目标，即最一致目标，作 Goldman和Geib等人将该方法进行了更深入 为识别结果 的研究，对敌对智能体251和部分可观察规划进行了 该方法突破了必须有特定规划库才能进行规划 识别26).他们还将该方法应用到计算机智能辅助、 识别的限制，能够对新规划做出识别，所以很适合入 入侵检测21等领域，并以该方法为基准，对规划识 侵检测等智能体处于敌对状态下的识别.但由于它 别的复杂度进行了评估21 还不够完善，只能解释过去的动作而不能预测未来 2.6基于目标图分析的目标识别 动作，因此，该方法目前适合应用在故事理解、软件 通常的规划识别都是建立在规划库基础上的. 咨询系统、数据库查询优化和客户数据挖掘等领域， 2000年，Jun Hong提出了一种不需要规划库的目 2.7基于动态贝叶斯网络的规划识别 标识别方法3.141 贝叶斯网络又称信度网，是目前比较流行的一 给定观察动作集合，通常的规划识别方法会搜 种不确定性推理方法，它用图形的方法来表达节点 索可能的规划识别假设，作为候选规划和目标，以此 间的因果关系.近年来，学者们将贝叶斯网络应用到 来解释观察动作.这一搜索过程无疑会增加规划识 动态领域，即贝叶斯网络随着时间的推移而逐渐扩 别的时间及空间消耗，甚至使有些识别问题无法解 大，以往通过手工编码来建立规划库的方法限制了 决.因此，相对于无库规划识别而言，有库规划识别 规划识别的发展，而动态贝叶斯网络可以在训练过 有如下缺点： 程中学习到领域特征，并能将所学应用到推理过程 1)识别器不能识别规划库中没有的新规划 中.因此将动态贝叶斯网络应用到规划识别领域能 2)对于复杂领域来说，手工编写的规划库需要 有效地解决手工编码所带来的问题 消耗大量的时间，并且可能会导致这一工作会无法 Albrecht等人利用动态贝叶斯网络来表示领 完成，即使采用机器学习的方法，空间搜索有时也会 域特征，用以推导用户的规划及目标30).其网络结 产生指数级的消耗 构是根据分析领域特征而确定的.网络中有3种节 3)在有些领域中，规划知识不容易获得，无法进 点，包括动作(Action)、地点(Location)和目标 行识别 (Quest),其信度更新方法如下： 而Jun Hong提出的无库的规划识别方法与大 初始第1步时 多数规划识别不同.该方法没有规划库，因此可识别 Pr(L1=h|q,m,o)=∑Pr(L1=h|b， 新规划，不立即搜索可能规划，而是先构建一个目标 g)Pr(g'l g, 图，以此图来分析识别的目标和规划，因此不存在指 Pr(A1 =al q.a,lo)=>Pr(A1=al a 数级空间消耗的问题；只保留与当前己观察动作一 致的目标及规划，降低了识别结果的二义性.因此， q)Pr(q'l q, 与有库规划识别相比，该方法有着明显的优势 Pr(0′=q'1q,am,l6)=Pr(0'=q'1. Jun Hong在Blum和Furst提出的图规划方 更新第n+1步时 法21及Lesh和Etzioniy的一致图方法21的基础上 Pr(Ln-1 Int1 I g,a,lo,,an,In)= 提出了目标图，该方法采用ADL域表示.一个目标 >Pr(L=1.9)Pr(g'l q.a.bo..a. 识别问题包括：一个给定初始动作的动作概要集合； In) 一个可由动作添加或删除的类型化对象的有限、动 Pr(A+ an1 g,a,l,,an,In) 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的概率. 给出适当的阈值 ,即可得到满足条件的解 释 ,由此可以判断智能体所执行的规划. 这种方法从一个新的角度出发构建了基于规划 执行的规划识别 ,加入概率推理使其结果更合理 ,更 准确. 不仅如此 , Goldman 等人还在该模型中加入 了 Pearl 在 1994 年提出的干预理论 ,使得其智能辅 助作用更大 ,效果更好. 该模型可以很好地处理交错 规划生成的动作序列、偏序规划 ,还可以利用背景进 行推理. 但在解释生成过程中不能排除空间按指数 级增长的情况. Goldman 等人认为该模型不能与周 围环境交互 ,并且没有考虑到世界的状态的改变. Goldman 和 Geib 等人将该方法进行了更深入 的研究 ,对敌对智能体[ 25 ]和部分可观察规划进行了 识别[ 26 ] . 他们还将该方法应用到计算机智能辅助、 入侵检测[12 ]等领域 ,并以该方法为基准 ,对规划识 别的复杂度进行了评估[27 ] . 216 基于目标图分析的目标识别 通常的规划识别都是建立在规划库基础上的. 2000 年 ,J un Hong 提出了一种不需要规划库的目 标识别方法[13 - 14 ] . 给定观察动作集合 ,通常的规划识别方法会搜 索可能的规划识别假设 ,作为候选规划和目标 ,以此 来解释观察动作. 这一搜索过程无疑会增加规划识 别的时间及空间消耗 ,甚至使有些识别问题无法解 决. 因此 ,相对于无库规划识别而言 ,有库规划识别 有如下缺点 : 1) 识别器不能识别规划库中没有的新规划. 2) 对于复杂领域来说 ,手工编写的规划库需要 消耗大量的时间 ,并且可能会导致这一工作会无法 完成 ,即使采用机器学习的方法 ,空间搜索有时也会 产生指数级的消耗. 3) 在有些领域中 ,规划知识不容易获得 ,无法进 行识别. 而 J un Hong 提出的无库的规划识别方法与大 多数规划识别不同. 该方法没有规划库 ,因此可识别 新规划 ;不立即搜索可能规划 ,而是先构建一个目标 图 ,以此图来分析识别的目标和规划 ,因此不存在指 数级空间消耗的问题 ;只保留与当前已观察动作一 致的目标及规划 ,降低了识别结果的二义性. 因此 , 与有库规划识别相比 ,该方法有着明显的优势. J un Hong 在 Blum 和 Furst 提出的图规划方 法[28 ]及 Lesh 和 Etzioniy 的一致图方法[29 ]的基础上 提出了目标图 ,该方法采用 ADL 域表示. 一个目标 识别问题包括 :一个给定初始动作的动作概要集合 ; 一个可由动作添加或删除的类型化对象的有限、动 态领域 ;一个被称为初始条件的命题集合 ;一个说明 可能目标的目标概要集合 ;一个在连续时间步观察 到的动作集合. 目标图是一个直接的层次图 ,由命题层、动作 层、目标层依次交错排列. 目标图开始于时间步 1 的 初始条件命题层 ,结束于当前所观察到的最后一个 动作所在时间步的目标层. 识别过程首先从初始状 态出发 ,根据所观察到的动作 ,反复执行目标扩张及 动作扩展 ,并对目标图进行分析 ,找到与观察动作一 致的已完成或部分完成的目标. 删除冗余目标 ,并选 择具有最多相关动作的一致目标 ,即最一致目标 ,作 为识别结果. 该方法突破了必须有特定规划库才能进行规划 识别的限制 ,能够对新规划做出识别 ,所以很适合入 侵检测等智能体处于敌对状态下的识别. 但由于它 还不够完善 ,只能解释过去的动作而不能预测未来 动作 ,因此 ,该方法目前适合应用在故事理解、软件 咨询系统、数据库查询优化和客户数据挖掘等领域. 217 基于动态贝叶斯网络的规划识别 贝叶斯网络又称信度网 ,是目前比较流行的一 种不确定性推理方法 ,它用图形的方法来表达节点 间的因果关系. 近年来 ,学者们将贝叶斯网络应用到 动态领域 ,即贝叶斯网络随着时间的推移而逐渐扩 大. 以往通过手工编码来建立规划库的方法限制了 规划识别的发展 ,而动态贝叶斯网络可以在训练过 程中学习到领域特征 ,并能将所学应用到推理过程 中. 因此将动态贝叶斯网络应用到规划识别领域能 有效地解决手工编码所带来的问题. Albrecht 等人利用动态贝叶斯网络来表示领 域特征 ,用以推导用户的规划及目标[30 ] . 其网络结 构是根据分析领域特征而确定的. 网络中有 3 种节 点 ,包括动 作 ( Action) 、地 点 (Location ) 和 目 标 (Quest) ,其信度更新方法如下 : 初始第 1 步时 Pr(L1 = l1 | q , a0 , l0 ) = ∑q′Pr( L1 = l1 | l0 , q′) Pr( q′| q) , Pr( A1 = a1 | q , a0 , l0 ) = ∑q′Pr( A1 = a1 | a0 , q′) Pr( q′| q) , Pr( Q′= q′| q , a0 , l0 ) = Pr( Q′= q′| q) . 更新第 n + 1 步时 Pr(L n+1 = ln+1 | q , a0 , l0 , …, an , ln ) = ∑q′Pr( L n+1 = ln+1 | ln , q′) Pr( q′| q , a0 , l0 , …, an , ln ) , Pr( A n+1 = an+1 | q , a0 , l0 , …, an , ln ) = 第 1 期 谷文祥 ,等 :规划识别的研究及其应用 ·5 ·
6 智能系统学报 第2卷 >Pr(A=anl an.9)Pr(g'l q.ab.an. E可以采用如下方法计算： 1) E(A =p(Resuilt (A)Do(A).BU(Result(A ) Prto'=g'l q.a.1o,.an1,In1)=apr(Inti In, 式中：A为某一非确定行动，它具有可能的结果状态 g)Pr(antl an.q)Pr(o'=g'l q.a,l,.an.In). Result,(A);i为索引，最大不超过不同结果的个数 在执行A之前，智能体为每个结果赋以概率P(Re 式中：a为常化因子 sult,(A)川Do(A),E),其中E综合了智能体关于世 该方法在训练过程中确定条件概率分布，因此 界的可用证据，Do(A)是在当前状态下执行动作A 能够依据所观察到的行为动态构建概率分布.在训 的命题.而最大期望效用(MEU原则指出，一个理 练和测试过程中允许不完整的、零散的或带有噪声 性智能体应该选择能最大化该智能体的期望效用的 的数据存在.Albrecht等人用大量数据进行的试验 那个行动2 表明该方法具有很高的预测准确度，虽然该方法是 概率理论是在证据的基础上，描述一个智能体 在游戏领域进行的实验，但在具有相似特征的领域 应该相信什么；而效用理论描述一个智能体想要什 中，该方法也非常适用，并且能够取得很好的效果. 么；决策理论则将两者结合起来以描述一个智能体 Horvitz等人也将贝叶斯网络应用到了规划识 应该做什么.因此，将决策理论方法应用到规划识别 别当中s).他们的Lumiere工程通过建立贝叶斯用 领域中，从规划智能体的角度来进行决策分析，必将 户模型来推测用户的需求，并考虑用户的背景、动作 会得到更合理化的识别结果 及问题查询.Lumiere工程的主要任务是构建贝叶 Mao Wenji和Jonathan Gratch认为规划识别 斯用户模型，用于从所观察到的动作和查询上推理 可以被看作是在为模型化另一个智能体的决策制定 出计算机用户随时间变化的目标；从软件应用中获 策略]，之前的方法只是向规划识别中添加概率， 取事件流；开发可以将系统事件转化为贝叶斯用户 却缺少了对效用值的应用.因此，他们提出了规划识 模型中所表达的观察变量，开发持续简档(profile) 别的一种新方法，即通过最大期望效用来判断某一 以获取用户技能的变化；为智能用户接口开发一个 智能体所执行的规划.他们的规划采用经典 总体结构.该工程是office助手的基础，其目的主要 STRIPS的一种扩展表示，允许概率条件效果及抽 是观察程序状态、动作序列及用户查询词语，并根据 象动作.其规划识别方法有2种效用值节点，分别为 这些观察结果识别出用户的需求或目标，辅助用户 规划效用值节点和结果效用值节点.向贝叶斯网络 达到其最终目标.他们的决策模型包括用户的目标 中添加这2种节点，把计算出的结果作为证据来调 和需求，其中目标是指用户关注的目的任务或子任 整概率分布以便选择期待的结果.在规划识别过程 务；需求是指能减少用户完成任务的时间或工作量 中，遇到2个规划的先验概率及后验概率均相同的 的信息或动作.该模型在规划识别的过程中能够推 情况时，识别器可根据两个规划不同的效用值，即执 断用户需要帮助的可能性及需要帮助的类型.Hor 行规划的智能体对2规划的偏好来选择出更合理的 vtz等人还将用户的证据分为如下几类：搜索、专 规划作为识别结果.而以往的概率规划识别由于没 注、反省、非期待效果、非高效命令序列、域特征句法 有考虑到状态的期望值，因此不能做出这种合理的 和语义.根据用户证据，可以识别出用户的目标以及 区分 是否需要帮助 2.9基于动态概率关系模型的规划识别 由于不确定性无处不在，而动态贝叶斯网络又 1999年，Friedman等人提出了概率关系模 是建立在概率方法基础之上的，因此，采用动态贝叶 型.他们认为，己有的数据学习方法的数据表达 斯网络可以有效地诊断出用户的需求，并向用户提 方式都太过单调，不能很好地学习数据库中所存储 供有用的帮助.该方法在实际应用中效果很好 的知识，因此要用这些方法来表达数据库中的数据 2.8基于决策理论方法的规划识别 必然会丢失大量的关系结构信息.Friedman等人提 效用理论认为，任何状态对一个智能体而言都 出了概率关系模型(PRM),用这种方法来对数据库 有一定程度的有用性，即效用.智能体会偏好具有更 中的信息进行学习.概率关系模型允许某一对象的 高效用的状态.决策网络是贝叶斯网络的一个扩展， 属性与该对象本身的其他属性有概率依赖关系，还 它将贝叶斯网络与行动以及效用的附加节点类型结 允许某一对象的属性与其相关对象的属性有概率依 合起来 赖关系.因此概率关系模型的表达能力要强于一般 给定证据E,某一行动A的期望效用EU(A| 的标准模型（如贝叶斯网络）.为了从大型数据库中 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
∑q′Pr( A n+1 = an+1 | an , q′) Pr( q′| q , a0 , l0 , …, an , ln ) , Pr( Q′= q′| q , a0 , l0 , …, an+1 , ln+1 ) =αPr( l n+1 | ln , q′) Pr( an+1 | an , q′) Pr( Q′= q′| q , a0 , l0 , …, an , ln ) . 式中 :α为常化因子. 该方法在训练过程中确定条件概率分布 ,因此 能够依据所观察到的行为动态构建概率分布. 在训 练和测试过程中允许不完整的、零散的或带有噪声 的数据存在. Albrecht 等人用大量数据进行的试验 表明该方法具有很高的预测准确度. 虽然该方法是 在游戏领域进行的实验 ,但在具有相似特征的领域 中 ,该方法也非常适用 ,并且能够取得很好的效果. Horvitz 等人也将贝叶斯网络应用到了规划识 别当中[31 ] . 他们的 Lumiere 工程通过建立贝叶斯用 户模型来推测用户的需求 ,并考虑用户的背景、动作 及问题查询. Lumiere 工程的主要任务是构建贝叶 斯用户模型 ,用于从所观察到的动作和查询上推理 出计算机用户随时间变化的目标 ;从软件应用中获 取事件流 ;开发可以将系统事件转化为贝叶斯用户 模型中所表达的观察变量 ;开发持续简档 (profile) 以获取用户技能的变化 ;为智能用户接口开发一个 总体结构. 该工程是 office 助手的基础 ,其目的主要 是观察程序状态、动作序列及用户查询词语 ,并根据 这些观察结果识别出用户的需求或目标 ,辅助用户 达到其最终目标. 他们的决策模型包括用户的目标 和需求 ,其中目标是指用户关注的目的任务或子任 务 ;需求是指能减少用户完成任务的时间或工作量 的信息或动作. 该模型在规划识别的过程中能够推 断用户需要帮助的可能性及需要帮助的类型. Hor2 vitz 等人还将用户的证据分为如下几类 :搜索、专 注、反省、非期待效果、非高效命令序列、域特征句法 和语义. 根据用户证据 ,可以识别出用户的目标以及 是否需要帮助. 由于不确定性无处不在 ,而动态贝叶斯网络又 是建立在概率方法基础之上的 ,因此 ,采用动态贝叶 斯网络可以有效地诊断出用户的需求 ,并向用户提 供有用的帮助. 该方法在实际应用中效果很好. 218 基于决策理论方法的规划识别 效用理论认为 ,任何状态对一个智能体而言都 有一定程度的有用性 ,即效用. 智能体会偏好具有更 高效用的状态. 决策网络是贝叶斯网络的一个扩展 , 它将贝叶斯网络与行动以及效用的附加节点类型结 合起来. 给定证据 E,某一行动 A 的期望效用 EU ( A | E) 可以采用如下方法计算 : EU(A | E) = ∑i p(Result(A) | Do(A) , E)U (Result ( A ) ) . 式中 :A 为某一非确定行动 ,它具有可能的结果状态 Resulti ( A) ; i 为索引 ,最大不超过不同结果的个数. 在执行 A 之前 ,智能体为每个结果赋以概率 P(Re2 sulti ( A) | Do( A) , E) ,其中 E 综合了智能体关于世 界的可用证据 , Do( A) 是在当前状态下执行动作 A 的命题. 而最大期望效用 ( M EU) 原则指出 ,一个理 性智能体应该选择能最大化该智能体的期望效用的 那个行动[32 ] . 概率理论是在证据的基础上 ,描述一个智能体 应该相信什么;而效用理论描述一个智能体想要什 么;决策理论则将两者结合起来以描述一个智能体 应该做什么. 因此 ,将决策理论方法应用到规划识别 领域中 ,从规划智能体的角度来进行决策分析 ,必将 会得到更合理化的识别结果. Mao Wenji 和 Jonat han Gratch 认为规划识别 可以被看作是在为模型化另一个智能体的决策制定 策略[33 ] . 之前的方法只是向规划识别中添加概率 , 却缺少了对效用值的应用. 因此 ,他们提出了规划识 别的一种新方法 ,即通过最大期望效用来判断某一 智能 体 所 执 行 的 规 划. 他 们 的 规 划 采 用 经 典 STRIPS 的一种扩展表示 ,允许概率条件效果及抽 象动作. 其规划识别方法有 2 种效用值节点 ,分别为 规划效用值节点和结果效用值节点. 向贝叶斯网络 中添加这 2 种节点 ,把计算出的结果作为证据来调 整概率分布以便选择期待的结果. 在规划识别过程 中 ,遇到 2 个规划的先验概率及后验概率均相同的 情况时 ,识别器可根据两个规划不同的效用值 ,即执 行规划的智能体对 2 规划的偏好来选择出更合理的 规划作为识别结果. 而以往的概率规划识别由于没 有考虑到状态的期望值 ,因此不能做出这种合理的 区分. 219 基于动态概率关系模型的规划识别 1999 年 , Friedman 等人提出 了概率关 系模 型[34 ] . 他们认为 ,已有的数据学习方法的数据表达 方式都太过单调 ,不能很好地学习数据库中所存储 的知识 ,因此要用这些方法来表达数据库中的数据 必然会丢失大量的关系结构信息. Friedman 等人提 出了概率关系模型(PRM) ,用这种方法来对数据库 中的信息进行学习. 概率关系模型允许某一对象的 属性与该对象本身的其他属性有概率依赖关系 ,还 允许某一对象的属性与其相关对象的属性有概率依 赖关系. 因此概率关系模型的表达能力要强于一般 的标准模型(如贝叶斯网络) . 为了从大型数据库中 ·6 · 智 能 系 统 学 报 第 2 卷
第1期 谷文祥，等：规划识别的研究及其应用 快速的掌握某些信息，该模型还利用了标准的数据 假设的假设空间的某个区域.如果在某一点上极大 检索技术.概率关系模型是建立在贝叶斯网络基础 一般假设与极大特殊假设相同，那么学习者就获得 上的，它的基本目标是模型化领域对象属性的不确 了概念的唯一定义。 定性，即给定一个框架结构，概率关系模型会试图为 Tessa Lau等人利用变形空间代数的方法，进 该框架定义一个完整的概率分布， 行实例规划(programming by demonstration, 通常情况下，智能体必须在一个不确定的环境 PBD)借助于用户的实例操作来识别出用户的 下工作，而该不确定的环境中通常又存在着随时间 操作目标36].他们通过扩展变形空间来学习任意函 变化的多个对象和关系.这就要求解决该问题的模 数，而不是局限于原有的概念学习.引入变形空间代 型必须既有丰富的表达能力，又能进行概率推理，还 数，将简单的变形空间组合成复杂的变形空间，即从 能随着时间的变化而改变.2003年，Shanghai等人 复杂对象映射到复杂对象，由此映射出最终目标他 基于概率关系模型的方法提出了动态概率关系模型 们将该方法应用到文本编辑领域，建立了SMART- (DPRM)B1.动态概率关系模型在每个时间片上都 edit系统，该系统可以通过实例来学习重复的文本 有一个概率关系模型，且每一个时间片上的状态都 编辑过程，即识别出用户的目标，并辅助用户完成目 依赖于前一个时间片的状态 标任务 Shanghai等人认为一个动态概率关系模型是 这种规划识别方法能够识别出新的规划，根据 这样的：一个关系概要S的动态概率关系模型是一 少量观察实例就能够推测出用户目标，并且能够感 个序对(M6,M,其中M是6上的一个概率关系 知噪声，但该方法要求所识别的对象是完全可观察 模型，表示S在初始实例上的分布Po;M-是一个 的，因此其应用领域有一定的局限性 2TPRM,表示转移分布P(lI.)连接S的下一个 2.11基于回归图的规划识别 实例.动态概率关系模型能够包含多个对象及对象 回归图识别s1方法与目标图识别3.14方法一 类，以及其上的多种关系类型；对象和关系可以在时 样，都属于无库识别方法.它的主体思想直接来源于 间上出现或消失.动态概率关系模型能够处理时间 图规划和目标图方法，主要通过回归的思想来完成 变化现象、关系结构及原则方式上的不确定性.实验 对观察到的和未观察到的动作和目标的识别以及对 中，Shanghai等人首先用FF规划器来生成一个规 未来可能发生的动作和目标的预测.回归图的结构 划，然后用PF(particle filtering)来监督规划的执 与目标图的结构相似，均是由命题节点、动作节点以 行，再用RBPF(rao-blackwellised particle filtering) 及目标节点组织成的层结构，其中这3种节点交替 来提取规划树.他们将该方法应用于生产中对装配 出现.这种方法通过将回归图中的节点分为确定的 规划的监控和错误的识别，取得了很好的效果 节点和可能的节点进行确定的目标和可能的目标的 2.10基于变形空间的规划识别 识别，其中确定的节点由观察到的动作生成，可能的 变形空间(version space)方法是由Tom 节点通过领域知识生成.利用回归图的方法进行规 Mitchell在1977年提出的，主要用于机器学习领 划识别，首先识别器会根据观察到的动作以及领域 域.变形空间是知识的一种层次表达，通过这些知识 知识构造回归图，每观察到一个动作就将其添加到 可以不用记住任何样例，就能掌握由学习样例序列 图中，并且立即回退，以删除那些由领域知识生成的 提供的全部有用信息.变形空间方法是一个概念学 但与观察到的动作有冲突的动作节点和命题节点， 习过程，在一个变形空间中，该学习过程是通过控制 通过这样的回退来达到识别确定的目标和可能的目 多个模型来完成的.变形空间的基本思想是：用2种 标.也就是说，它可以识别出确实发生的动作及目 可能假设来完成一个诱导学习任务.这2种假设是 标，也可以预测未来可能发生的动作和目标 2种特殊的假设，分别为极大一般假设（对应结构的 回归图识别方法继承了Hong Jun目标图方法 最顶端)和极大特殊假设（对应结构的最底端）.正例 的优点，并且在弥补其不足的同时又具有自己特有 总是与极大一般假设相一致，与极大特殊假设相背 的优势.它考虑了不可观察动作这一情况，这使回归 离.因此加入正例后这种极大特殊假设就会更具一 图算法更符合客观事实，同时它也可以预测未来可 般性.反例与极大特殊假设相一致，但是与极大一般 能发生的动作及产生的目标.由于引入了互斥关系 假设相背离，因此加入反例后这种极大一般假设就 回归图变得更为紧凑，在准确性、有效性以及可伸缩 会更具特殊性所以在训练序列的任意点，学习者都 性等方面都有良好的表现.由于它属于无库识别方 会具有2种假设，正确的假设会依赖于连接这2个 法，省去了对规划库的建立、管理和完善等繁杂工 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
快速的掌握某些信息 ,该模型还利用了标准的数据 检索技术. 概率关系模型是建立在贝叶斯网络基础 上的 ,它的基本目标是模型化领域对象属性的不确 定性 ,即给定一个框架结构 ,概率关系模型会试图为 该框架定义一个完整的概率分布. 通常情况下 ,智能体必须在一个不确定的环境 下工作 ,而该不确定的环境中通常又存在着随时间 变化的多个对象和关系. 这就要求解决该问题的模 型必须既有丰富的表达能力 ,又能进行概率推理 ,还 能随着时间的变化而改变. 2003 年 ,Shanghai 等人 基于概率关系模型的方法提出了动态概率关系模型 (DPRM) [35 ] . 动态概率关系模型在每个时间片上都 有一个概率关系模型 ,且每一个时间片上的状态都 依赖于前一个时间片的状态. Shanghai 等人认为一个动态概率关系模型是 这样的 :一个关系概要 S 的动态概率关系模型是一 个序对( M0 , M →) ,其中 M0 是 I0 上的一个概率关系 模型 ,表示 S 在初始实例上的分布 P0 ; M →是一个 2 TPRM ,表示转移分布 P( It | It - 1 ) 连接 S 的下一个 实例. 动态概率关系模型能够包含多个对象及对象 类 ,以及其上的多种关系类型 ;对象和关系可以在时 间上出现或消失. 动态概率关系模型能够处理时间 变化现象、关系结构及原则方式上的不确定性. 实验 中 ,Shanghai 等人首先用 FF 规划器来生成一个规 划 ,然后用 PF (particle filtering) 来监督规划的执 行 ,再用 RBPF(rao2blackwellised particle filtering) 来提取规划树. 他们将该方法应用于生产中对装配 规划的监控和错误的识别 ,取得了很好的效果. 2110 基于变形空间的规划识别 变形 空 间 ( version space ) 方 法 是 由 Tom Mitchell 在 1977 年提出的 ,主要用于机器学习领 域. 变形空间是知识的一种层次表达 ,通过这些知识 可以不用记住任何样例 ,就能掌握由学习样例序列 提供的全部有用信息. 变形空间方法是一个概念学 习过程 ,在一个变形空间中 ,该学习过程是通过控制 多个模型来完成的. 变形空间的基本思想是 :用 2 种 可能假设来完成一个诱导学习任务. 这 2 种假设是 2 种特殊的假设 ,分别为极大一般假设(对应结构的 最顶端) 和极大特殊假设(对应结构的最底端) . 正例 总是与极大一般假设相一致 ,与极大特殊假设相背 离. 因此加入正例后这种极大特殊假设就会更具一 般性. 反例与极大特殊假设相一致 ,但是与极大一般 假设相背离 ,因此加入反例后这种极大一般假设就 会更具特殊性. 所以在训练序列的任意点 ,学习者都 会具有 2 种假设 ,正确的假设会依赖于连接这 2 个 假设的假设空间的某个区域. 如果在某一点上极大 一般假设与极大特殊假设相同 ,那么学习者就获得 了概念的唯一定义. Tessa Lau 等人利用变形空间代数的方法 ,进 行实 例 规 划 ( programming by demonstration , PBD) ———借助于用户的实例操作来识别出用户的 操作目标[36 ] . 他们通过扩展变形空间来学习任意函 数 ,而不是局限于原有的概念学习. 引入变形空间代 数 ,将简单的变形空间组合成复杂的变形空间 ,即从 复杂对象映射到复杂对象 ,由此映射出最终目标. 他 们将该方法应用到文本编辑领域 ,建立了 SMART2 edit 系统 ,该系统可以通过实例来学习重复的文本 编辑过程 ,即识别出用户的目标 ,并辅助用户完成目 标任务. 这种规划识别方法能够识别出新的规划 ,根据 少量观察实例就能够推测出用户目标 ,并且能够感 知噪声 ,但该方法要求所识别的对象是完全可观察 的 ,因此其应用领域有一定的局限性. 2111 基于回归图的规划识别 回归图识别[15 ]方法与目标图识别[13 - 14 ] 方法一 样 ,都属于无库识别方法. 它的主体思想直接来源于 图规划和目标图方法 ,主要通过回归的思想来完成 对观察到的和未观察到的动作和目标的识别以及对 未来可能发生的动作和目标的预测. 回归图的结构 与目标图的结构相似 ,均是由命题节点、动作节点以 及目标节点组织成的层结构 ,其中这 3 种节点交替 出现. 这种方法通过将回归图中的节点分为确定的 节点和可能的节点进行确定的目标和可能的目标的 识别 ,其中确定的节点由观察到的动作生成 ,可能的 节点通过领域知识生成. 利用回归图的方法进行规 划识别 ,首先识别器会根据观察到的动作以及领域 知识构造回归图 ,每观察到一个动作就将其添加到 图中 ,并且立即回退 ,以删除那些由领域知识生成的 但与观察到的动作有冲突的动作节点和命题节点 , 通过这样的回退来达到识别确定的目标和可能的目 标. 也就是说 ,它可以识别出确实发生的动作及目 标 ,也可以预测未来可能发生的动作和目标. 回归图识别方法继承了 Hong J un 目标图方法 的优点 ,并且在弥补其不足的同时又具有自己特有 的优势. 它考虑了不可观察动作这一情况 ,这使回归 图算法更符合客观事实 ,同时它也可以预测未来可 能发生的动作及产生的目标. 由于引入了互斥关系 , 回归图变得更为紧凑 ,在准确性、有效性以及可伸缩 性等方面都有良好的表现. 由于它属于无库识别方 法 ,省去了对规划库的建立、管理和完善等繁杂工 第 1 期 谷文祥 ,等 :规划识别的研究及其应用 ·7 ·
智能系统学报 第2卷 作.但是回归图识别方法在处理一些动作之间的关 应用.H.H.Bui,S.Venkatesh等人提出了一种在 系上还存在着一定的问题，识别也只限制在 有噪音和不确定性领域中识别智能体行为的方 STRIPS域，同时只有具有了较完整的领域知识才 法)，它可跨越多层抽象，即在抽象概率推理中应 可以完成相关的识别工作 用抽象马尔可夫策略(abstract Markov policies, 2.12基于隐马尔可夫模型的规划识别 AMP)作为智能体行为的模型，且在动态贝叶斯网 俄国统计学家安德列·马尔可夫最早深入研究 络中应用概率推理，从一系列观察中推断出正确的 了满足马尔可夫假设的过程—当前状态只依赖于 策略.AMP是马尔可夫决策过程(MDP)一个策略 过去有限的已出现的状态历史.马尔可夫假设最初 的扩展.原始的MDP被模型化为2层：原始动作层 是用来解决随机过程问题的.随着马尔可夫模型的 和规划层（也就是策略）.而AMP是多层的，顶层是 不断完善与成熟，近些年来一些人工智能学者把马 最抽象的策略（记为x,t时刻的高层策略记为 尔可夫模型引入到识别中，并将其发展成为解决识 Tx),抽象程度依次下降，底层为策略层，即原始动 别问题的重要方法，其中以隐马尔可夫模型(hidden 作层.当执行上层的抽象策略时会引发下层抽象策 Markov model,HMM)为主要模型B 略的执行，依次向下直到执行到底层策略！给定 隐马尔可夫模型在识别问题上受到了很大的关 当前的观察序列状态系列，相应的策略识别问题 注，在随后的研究中又根据不同的应用领域和情况 可以形式化为计算当前策略的条件概率.在t时刻， 发展了多种基于隐马尔可夫模型的方法.其中，N. 给定观察序列，AMP关心的是在当前状态下所有 Oliver,E.Horvitz和A.Garg提出了一种层隐马 第k层策略的概率，这样就知道了从当前动作层 尔可夫模型3I(layered hidden Markov model,LH- (k=0)到高层策略(k=)在所有抽象层上智能体 HM),提出这种表示主要是想通过减少训练和调整 行为的相关信息.策略识别问题的解决还建立在信 需求来分解参数空间，LHHM可以看成是对HMM 度状态(belief state)和基于状态空间区域分解 的层叠.在这个层模型中，体系结构每一层都通过它 (state-space regiom based decomposition)的基础 推理出的结果与下一层相连接.这种表示把问题分 割为不同的层，这些层可以运行在不同的时序粒度 执行高层策略x的过程可以用一个动态贝叶 上，即允许从在多个特定时刻的逐点观察到不同时 斯网络DBN表示，如图1，这一过程可以命名为抽 序间隔的解释的时序抽象.Kevin Murphy提到了一 象马尔可夫模型(abstract markov model,AMM). 种隐半马尔可夫模型1(HSMM),它是一种类马尔 当状态是部分可观察时，一个观察层可以附属于一 可夫模型，其主要特点是对于每个状态都可以忽略 个状态层，如图1.因为状态像HMM一样被隐藏 观察的序列 所以得到的结果称为抽象隐马尔可夫模型(abstract 隐马尔可夫模型主要应用在语音识别、机器视 hidden Markov model).AHMM是HMM的扩展， 觉（人脸检测，机器人足球）、图像处理（图像去噪、图 HMM中的单链由多层隐链代替，也可以说 像识别)、人机交互系统中的人类行为的自动与半自 AHMM是动态概率网络(DPN,也称动态贝叶斯网 动识别、生物医学分析(DNA/蛋白质序列分析)等 络)的一种特殊形式，其中DPN是一种特殊的贝叶 方面.隐马尔可夫模型因其研究的透彻性以及算法 斯网络，可以处理具有时序动态变化的环境2] 的成熟性，使它在识别领域中具有很高的效率，识别 AHMM的基础是多层贝叶斯动态结构，连续2层 效果好，同时也易于训练.但它也存在着一定的问 之间的连接是较高层较抽象路径向较低层改进路径 题，比如缺乏结构性，参数过量，在用训练数据进行 的分解.智能体想要实现高层目标时，它可以通过层 长而复杂的时序序列推理时，易产生数据过拟合（过 层关系在不同的抽象层创建一系列子目标，直到底 拟合是指模型不能拟合未来的数据).正因为HMM 层状态层，以这样的过程来实现这个高层目标.实际 具有以上的缺陷才导致复杂贝叶斯网络在识别上的 上AHMM的识别与AMP的识别过程在本质上是 发展和应用 没有区别的 2.13基于抽象策略的规划识别 策略识别和AHMM都适用在大规模的空间环 抽象(abstraction)在智能体规划其行为的方式 境，这样的环境具有复杂的空间布局、大的状态空间 上起着非常重要的作用，特别是在大的规划领域中 等特点，它可以处理不满足马尔可夫假设的问题.但 降低计算复杂度上，抽象显得尤为重要.有了抽象的 是策略识别与AHMM识别在信度状态上的计算量 规划方法，自然容易让人想到抽象在规划识别上的 仍然很大，虽然也采取了一些方法降低计算复杂 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
作. 但是回归图识别方法在处理一些动作之间的关 系上 还 存 在 着 一 定 的 问 题 , 识 别 也 只 限 制 在 STRIPS 域 ,同时只有具有了较完整的领域知识才 可以完成相关的识别工作. 2112 基于隐马尔可夫模型的规划识别 俄国统计学家安德列 ·马尔可夫最早深入研究 了满足马尔可夫假设的过程 ———当前状态只依赖于 过去有限的已出现的状态历史. 马尔可夫假设最初 是用来解决随机过程问题的. 随着马尔可夫模型的 不断完善与成熟 ,近些年来一些人工智能学者把马 尔可夫模型引入到识别中 ,并将其发展成为解决识 别问题的重要方法 ,其中以隐马尔可夫模型(hidden Markov model , HMM) 为主要模型[37 ] . 隐马尔可夫模型在识别问题上受到了很大的关 注 ,在随后的研究中又根据不同的应用领域和情况 发展了多种基于隐马尔可夫模型的方法. 其中 ,N. Oliver ,E. Horvitz 和 A. Garg 提出了一种层隐马 尔可夫模型[38 ] (layered hidden Markov model ,L H2 HM) ,提出这种表示主要是想通过减少训练和调整 需求来分解参数空间 ,L H HM 可以看成是对 HMM 的层叠. 在这个层模型中 ,体系结构每一层都通过它 推理出的结果与下一层相连接. 这种表示把问题分 割为不同的层 ,这些层可以运行在不同的时序粒度 上 ,即允许从在多个特定时刻的逐点观察到不同时 序间隔的解释的时序抽象. Kevin Murp hy 提到了一 种隐半马尔可夫模型[39 ] ( HSMM) ,它是一种类马尔 可夫模型 ,其主要特点是对于每个状态都可以忽略 观察的序列. 隐马尔可夫模型主要应用在语音识别、机器视 觉(人脸检测 ,机器人足球) 、图像处理(图像去噪、图 像识别) 、人机交互系统中的人类行为的自动与半自 动识别、生物医学分析 (DNA/ 蛋白质序列分析) 等 方面. 隐马尔可夫模型因其研究的透彻性以及算法 的成熟性 ,使它在识别领域中具有很高的效率 ,识别 效果好 ,同时也易于训练. 但它也存在着一定的问 题 ,比如缺乏结构性 ,参数过量 ,在用训练数据进行 长而复杂的时序序列推理时 ,易产生数据过拟合(过 拟合是指模型不能拟合未来的数据) . 正因为 HMM 具有以上的缺陷才导致复杂贝叶斯网络在识别上的 发展和应用. 2113 基于抽象策略的规划识别 抽象(abstraction) 在智能体规划其行为的方式 上起着非常重要的作用 ,特别是在大的规划领域中 降低计算复杂度上 ,抽象显得尤为重要. 有了抽象的 规划方法 ,自然容易让人想到抽象在规划识别上的 应用. H. H. Bui ,S. Venkatesh 等人提出了一种在 有噪音和不确定性领域中识别智能体行为的方 法[40 ] ,它可跨越多层抽象 ,即在抽象概率推理中应 用抽象马尔可夫策略 ( abstract Markov policies , AMP) 作为智能体行为的模型 ,且在动态贝叶斯网 络中应用概率推理 ,从一系列观察中推断出正确的 策略. AMP 是马尔可夫决策过程 (MDP) 一个策略 的扩展. 原始的 MDP 被模型化为 2 层 :原始动作层 和规划层(也就是策略) . 而 AMP 是多层的 ,顶层是 最抽象的策略 (记为πK , t 时刻的高层策略记为 πK ( t) ) ,抽象程度依次下降 ,底层为策略层 ,即原始动 作层. 当执行上层的抽象策略时会引发下层抽象策 略的执行 ,依次向下直到执行到底层策略[41 ] . 给定 当前的观察序列 (状态系列) ,相应的策略识别问题 可以形式化为计算当前策略的条件概率. 在 t 时刻 , 给定观察序列 , AMP 关心的是在当前状态下所有 第 k 层策略的概率 , 这样就知道了从当前动作层 ( k = 0) 到高层策略( k = K) 在所有抽象层上智能体 行为的相关信息. 策略识别问题的解决还建立在信 度状态 ( belief state ) 和基于状态空间区域分解 (state2space region2based decompo sition ) 的 基 础 上. 执行高层策略πK 的过程可以用一个动态贝叶 斯网络 DBN 表示 ,如图 1 ,这一过程可以命名为抽 象马尔可夫模型(abstract markov model , AMM) . 当状态是部分可观察时 ,一个观察层可以附属于一 个状态层 ,如图 1. 因为状态像 HMM 一样被隐藏 , 所以得到的结果称为抽象隐马尔可夫模型(abstract hidden Markov model) . A HMM 是 HMM 的扩展 , HMM 中 的 单 链 由 多 层 隐 链 代 替 , 也 可 以 说 A HMM 是动态概率网络(DPN ,也称动态贝叶斯网 络) 的一种特殊形式 ,其中 DPN 是一种特殊的贝叶 斯网络 ,可以处理具有时序动态变化的环境[42 ] . A HMM 的基础是多层贝叶斯动态结构 ,连续 2 层 之间的连接是较高层较抽象路径向较低层改进路径 的分解. 智能体想要实现高层目标时 ,它可以通过层 层关系在不同的抽象层创建一系列子目标 ,直到底 层状态层 ,以这样的过程来实现这个高层目标. 实际 上 A HMM 的识别与 AMP 的识别过程在本质上是 没有区别的. 策略识别和 A HMM 都适用在大规模的空间环 境 ,这样的环境具有复杂的空间布局、大的状态空间 等特点 ,它可以处理不满足马尔可夫假设的问题. 但 是策略识别与 A HMM 识别在信度状态上的计算量 仍然很大 ,虽然也采取了一些方法降低计算复杂 ·8 · 智 能 系 统 学 报 第 2 卷
第1期 谷文祥，等：规划识别的研究及其应用 ·9 察到的攻击行为预测潜在的攻击.与其他的网络规 Level K 划识别方法相比，基于因果网络的攻击规划识别方 法不但可以实现对孤立的警报集的相关性分析，重 Level I Policy 要的是它可以识别出攻击者的高层策略和目标.但 Stop natns s Level0 Actionπ 是这种方法在应用上还存在着一定问题.首先因果 Stop natus s. 网络是由攻击树转化而来的，而攻击树的定义和构 State Layer 造具有一定的难度，其困难程度相当于传统规划识 Observation Layer Time index 别的规划库的建立，虽然O.Sheyner等人提出一种 自动构造攻击树的方法)，但仍存在着很多问题」 图1DBN表示 其次，因果网络的构造目前还停留在比较简单的层 Fig 1 DBN representation 次上，即单连接因果网络，以简化因果网络连接程度 度)，但仍不能从根本上解决计算复杂度的问题 的方式来减少概率推理的时间代价 2.14基于因果网络的攻击规划识别 规划识别的方法很多，除以上方法外，还包括基 在安全管理中，安全警报的联系与分析是一项 于Dempster-Shafer证据理论的规划识别]，基于 非常重要而又有挑战性的任务，之所以要进行这样 溯因理论的规划识别46]，基于案例的规划识别) 的工作是要有效地识别攻击者的攻击目标、策略以 基于语料库及统计方法的规划识别8·4等」 及预测未来的攻击，以便及时有效地阻止攻击者对 3 规划识别的应用 需要保护的网络和系统的攻击.nzhou Qin和 Wenke Lee提出一种名为因果网络(causal net- 规划识别经过近30年的发展，在很多领域中都 work)的方法来解决以上问题).这种方法首先用 有所应用.早期广泛应用在自然语言理解、智能用户 攻击树4定义攻击规划库来联系孤立的警报集，然 接口及用户模型等方面.目前其应用己扩展到网络 后把攻击树转化为因果网络.在因果网络上，可以通 安全、入侵检测，战术规划识别及工业控制等领域 过合并领域知识来估计攻击目标的可能性和预测未 3.1网络安全 来攻击」 入侵检测是当前网络安全中一个非常活跃的研 一个因果网络通常由一个有向无环图表示，它 究领域.而入侵检测系统想要更进一步发展，就必须 实际上也是一个与或图.图中每个节点表示一个变 加入人工智能方法.入侵检测系统(DSs)要求从己 量，变量有一个确定的状态集合，有向边表示变量之 发生的动作中预测出未来动作，而这一过程在人工 间的因果或依赖关系.因果网络的根节点表示攻击 智能领域中称为规划识别.规划识别可以预测入侵 规划的最终目标，内部节点表示子目标，叶节点表示 者的未来动作，并做出适当的回应.因此，规划识别 收到的证据.每个节点有两值状态，即0和1,1表示 方法必将是未来入侵检测系统的重要组成部分 节点所代表的目标或子目标得以实现，0则表示失 2001年，Geib和Goldman将规划识别应用到 败.一个叶节点的状态值为1时，表示叶节点收到证 入侵检测领域2！.该方法采用了Geib等人之前的 据，否则值为0.“AND”节点表示到达一个目标的不 基于规划执行的规划识别方法，该方法没有设置太 同攻击步骤，而“OR”节点表示实现目标的不同方 多的限制性假设，因此，能够处理较广泛的规划识别 式.为实现对攻击规划的识别，还需要2个参数，一 问题.该方法着重处理了与以往识别环境不同的敌 个是父节点状态的优先概率，另一个是伴随每个子 对环境下的规划识别问题，包括从已观察到的动作 节点的一个条件概率表的集合CPT1.识别时，攻 或状态改变中推理出未观察到的动作.这些能力的 击分析系统会根据当前的警报集以及对其的分析， 增加，也极大地扩展了规划识别的应用领域.该方法 依据已经建立好的攻击因果网络来实现对攻击者目 可以从同一观察数据流中区分出多个智能体的攻击 标和策略的识别以及对未来目标的预测 目标及规划 网络攻击规划识别与传统的规划识别有着非常 Qin等人认为Geib和Goldman提出的旨在识 大的区别，所以传统的规划识别方法并不适用于识 别网络攻击的规划识别方法，对规划库的定义过于 别网络攻击.基于因果网络的攻击规划识别可以针 细致，会增加推理的计算复杂度.2004年，Xinzhou 对网络识别的特殊要求，来实现源于底层警报的相 Qin和Wenke Lee采用因果网络对网络攻击进行 关性分析，识别攻击者的高层策略和目标，并基于观 识别1.他们认为，将传统的规划识别应用到安全 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 DBN 表示 Fig11 DBN representation 度[42 ] ,但仍不能从根本上解决计算复杂度的问题. 2114 基于因果网络的攻击规划识别 在安全管理中 ,安全警报的联系与分析是一项 非常重要而又有挑战性的任务 ,之所以要进行这样 的工作是要有效地识别攻击者的攻击目标、策略以 及预测未来的攻击 ,以便及时有效地阻止攻击者对 需要保护的网络和系统的攻击. Xinzhou Qin 和 Wenke Lee 提出一种名为因果网络 ( causal net2 work) 的方法来解决以上问题[ 43 ] . 这种方法首先用 攻击树[44 ]定义攻击规划库来联系孤立的警报集 ,然 后把攻击树转化为因果网络. 在因果网络上 ,可以通 过合并领域知识来估计攻击目标的可能性和预测未 来攻击. 一个因果网络通常由一个有向无环图表示 ,它 实际上也是一个与或图. 图中每个节点表示一个变 量 ,变量有一个确定的状态集合 ,有向边表示变量之 间的因果或依赖关系. 因果网络的根节点表示攻击 规划的最终目标 ,内部节点表示子目标 ,叶节点表示 收到的证据. 每个节点有两值状态 ,即 0 和 1 ,1 表示 节点所代表的目标或子目标得以实现 ,0 则表示失 败. 一个叶节点的状态值为 1 时 ,表示叶节点收到证 据 ,否则值为 0.“AND”节点表示到达一个目标的不 同攻击步骤 ,而“OR”节点表示实现目标的不同方 式. 为实现对攻击规划的识别 ,还需要 2 个参数 ,一 个是父节点状态的优先概率 ,另一个是伴随每个子 节点的一个条件概率表的集合 CPT [43 ] . 识别时 ,攻 击分析系统会根据当前的警报集以及对其的分析 , 依据已经建立好的攻击因果网络来实现对攻击者目 标和策略的识别以及对未来目标的预测. 网络攻击规划识别与传统的规划识别有着非常 大的区别 ,所以传统的规划识别方法并不适用于识 别网络攻击. 基于因果网络的攻击规划识别可以针 对网络识别的特殊要求 ,来实现源于底层警报的相 关性分析 ,识别攻击者的高层策略和目标 ,并基于观 察到的攻击行为预测潜在的攻击. 与其他的网络规 划识别方法相比 ,基于因果网络的攻击规划识别方 法不但可以实现对孤立的警报集的相关性分析 ,重 要的是它可以识别出攻击者的高层策略和目标. 但 是这种方法在应用上还存在着一定问题. 首先因果 网络是由攻击树转化而来的 ,而攻击树的定义和构 造具有一定的难度 ,其困难程度相当于传统规划识 别的规划库的建立 ,虽然 O. Sheyner 等人提出一种 自动构造攻击树的方法[45 ] ,但仍存在着很多问题. 其次 ,因果网络的构造目前还停留在比较简单的层 次上 ,即单连接因果网络 ,以简化因果网络连接程度 的方式来减少概率推理的时间代价. 规划识别的方法很多 ,除以上方法外 ,还包括基 于 Demp ster2Shafer 证据理论的规划识别[6 ] ,基于 溯因理论的规划识别[ 46 ] ,基于案例的规划识别[47 ] , 基于语料库及统计方法的规划识别[48 - 49 ]等. 3 规划识别的应用 规划识别经过近 30 年的发展 ,在很多领域中都 有所应用. 早期广泛应用在自然语言理解、智能用户 接口及用户模型等方面. 目前其应用已扩展到网络 安全、入侵检测 ,战术规划识别及工业控制等领域. 311 网络安全 入侵检测是当前网络安全中一个非常活跃的研 究领域. 而入侵检测系统想要更进一步发展 ,就必须 加入人工智能方法. 入侵检测系统 ( IDSs) 要求从已 发生的动作中预测出未来动作 ,而这一过程在人工 智能领域中称为规划识别. 规划识别可以预测入侵 者的未来动作 ,并做出适当的回应. 因此 ,规划识别 方法必将是未来入侵检测系统的重要组成部分. 2001 年 , Geib 和 Goldman 将规划识别应用到 入侵检测领域[12 ] . 该方法采用了 Geib 等人之前的 基于规划执行的规划识别方法 ,该方法没有设置太 多的限制性假设 ,因此 ,能够处理较广泛的规划识别 问题. 该方法着重处理了与以往识别环境不同的敌 对环境下的规划识别问题 ,包括从已观察到的动作 或状态改变中推理出未观察到的动作. 这些能力的 增加 ,也极大地扩展了规划识别的应用领域. 该方法 可以从同一观察数据流中区分出多个智能体的攻击 目标及规划. Qin 等人认为 Geib 和 Goldman 提出的旨在识 别网络攻击的规划识别方法 ,对规划库的定义过于 细致 ,会增加推理的计算复杂度. 2004 年 , Xinzhou Qin 和 Wenke Lee 采用因果网络对网络攻击进行 识别[43 ] . 他们认为 ,将传统的规划识别应用到安全 第 1 期 谷文祥 ,等 :规划识别的研究及其应用 ·9 ·
·10 智能系统学报 第2卷 领域必须解决以下问题.首先，传统的规划识别技术 打破了早期方法只能识别敌方对象及智能体未经确 通常应用在非敌对的情况下，识别过程可以是辅助 认的观察结果的限制.Frank Mulder和Frans 式的，也可以是不受所识别智能体干扰的.然而，在 Voorbraak在2003年又对战术规划识别进行了形 安全应用方面，攻击者试图消除或者干预对其入侵 式化描述54，.他们认为战术规划识别中最重要的是 行动的识别.其次，在传统规划识别中应用的假设在 对敌军被观察对象一致性的识别.因为在战术规划 对手式规划识别中已经不再适用.因此必须对原有 识别中，不知道所观察到的动作或行为是否出自于 方法加以改进，以适应应用领域的变化.他们研究了 同一个对象.所以战术规划识别器不仅要生成规划 组织概率推理方式，使其能够联系和分析攻击方案 假设，还要对规划假设赋值，根据假设赋值来判断观 所提出的方法可以解决如下问题：怎样从低层的警 察到的动作是否属于同一对象.该方法主要应用于 报中识别出独立的攻击方案，怎样识别攻击者的高 军事领域，对于相似的敌对智能体间的识别也有较 层方案及目标，怎样用观察到的攻击行为来预测潜 好的应用 在的攻击 Robert Suzic在2003年采用统计模型对敌军 诸葛建伟等人针对网络攻防领域中规划识别的 策略的不确定性加以表示和识别5].他们采用网络 特点扩展了Hong Jun的目标图，形成了扩展目标 结构将单一智能体问题扩展成在线多智能体随机策 规划图模型，将其应用到了识别网络攻击上).基 略识别问题.根据智能体之间的相互关系，Suzic创 于该模型的攻击规划识别算法可以从大量底层警报 建了一种与敌军组织相兼容的策略结构.通过这种 信息中识别出攻击者的规划以及隐含的攻击者的意 方法利用已知的军事组织知识，减少了大量的假设 图 空间.因此该方法可以降低问题复杂度，使得战术规 3.2军事指挥 划识别方法更加可行.同样，通过在策略识别中应用 战术规划识别需要能够处理不完全知识，动作 统计模型，可以用一种相容的方式来处理不确定性」 的随机结果及不确定观察.在军事应用中，特别在利 也就是说，提高了策略识别的健壮性.为了达到信息 用感知数据进行决策时，采用规划识别方法有其重 融合的目的，Sc的模型可以整合预处理的不确定 要的价值.战术规划识别的主要特点是快速、准确、 动态感知数据，例如可以将敌人的位置与地形数据 高效.因为军事指挥者通常需要快速、准确、高效地 和不确定先验知识结合在一起，以健壮、合理的方式 判断战场状况及战争走势，并根据判断结果来做出 推断出多智能体策略 战争部署 Suzc在其自身的研究基础上又进行了深入研 早在1986年就已经有了战术规划识别方法，当 究.2005年，他又提出了规划识别的一种通用模 时是Jerome Azarewicz等人将规划识别的方法应 型6]，并将其用于威胁评估.他认为规划识别应该 用在了空运的战术决策制定中511.1989年，他们又 以一种统计的健壮方式，考虑尽可能多的战术情况 提出了基于模板的、应用于多智能体的战术规划识 和单位类型.Suzic在其通用模型中加入了明确的效 别方法，并将其应用在海军作战指挥中5].他们所 用值，并将多实体贝叶斯网络(multi-entity bayesian 设计的多智能体模板用来获取战略指挥者的知识， networks,MEBN)作为设计灵活规划识别模型的 特别是战船协同作战方面的知识.Azarewicz等人 主要方法.这种网络可以将网络片段组合成贝叶斯 提出的这一模板提供了一种灵活的知识表示方法， 网络.通过使用多实体网络片段，这种模型能够扩展 依据该模板构造的规划识别模型能够推理出多智能 假设空间，并能表达多种多实体结构 体规划方式所显露的不同情况的特征变量.模板实 3.3对手规划/敌意规划/应对规划 例能够根据智能体的行为对智能体的未来动作做出 多年来，规划识别的研究一直都聚焦在传统的 假设.这种规划识别方法通过处理特征机制来限制 规划识别领域和方法上，而规划识别的应用也仅限 多智能体域中可能假设的增长.该方法能够解释敌 在传统领域，比如自然语言理解，智能帮助系统等 方船只的活动，并预测敌军的规划及目标，可用于辅 近些年来，一些学者把目光放在了具有对抗性质的 助海军指挥者进行战略决策 研究领域上，如博弈策略、军事领域、网络入侵检测 1998年，Mulder提出了战术规划识别的一种 系统等，这些具有对抗性质的领域可以称为对手规 通用任务模型5).他认为，在许多领域中对所观察 划(adversarial plan)领域或敌意规划(hostile plan) 到的人类行为进行识别都是非常重要的.Mulder提 领域，把应对对手规划或敌意规划的规划称为应对 出的通用任务模型主要用来识别敌方规划.该方法 规划.具有对抗性质的规划领域与传统规划领域相 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
领域必须解决以下问题. 首先 ,传统的规划识别技术 通常应用在非敌对的情况下 ,识别过程可以是辅助 式的 ,也可以是不受所识别智能体干扰的. 然而 ,在 安全应用方面 ,攻击者试图消除或者干预对其入侵 行动的识别. 其次 ,在传统规划识别中应用的假设在 对手式规划识别中已经不再适用. 因此必须对原有 方法加以改进 ,以适应应用领域的变化. 他们研究了 组织概率推理方式 ,使其能够联系和分析攻击方案. 所提出的方法可以解决如下问题 :怎样从低层的警 报中识别出独立的攻击方案 ;怎样识别攻击者的高 层方案及目标 ;怎样用观察到的攻击行为来预测潜 在的攻击. 诸葛建伟等人针对网络攻防领域中规划识别的 特点扩展了 Hong J un 的目标图 ,形成了扩展目标 规划图模型 ,将其应用到了识别网络攻击上[ 50 ] . 基 于该模型的攻击规划识别算法可以从大量底层警报 信息中识别出攻击者的规划以及隐含的攻击者的意 图. 312 军事指挥 战术规划识别需要能够处理不完全知识 ,动作 的随机结果及不确定观察. 在军事应用中 ,特别在利 用感知数据进行决策时 ,采用规划识别方法有其重 要的价值. 战术规划识别的主要特点是快速、准确、 高效. 因为军事指挥者通常需要快速、准确、高效地 判断战场状况及战争走势 ,并根据判断结果来做出 战争部署. 早在 1986 年就已经有了战术规划识别方法 ,当 时是 J erome Azarewicz 等人将规划识别的方法应 用在了空运的战术决策制定中[51 ] . 1989 年 ,他们又 提出了基于模板的、应用于多智能体的战术规划识 别方法 ,并将其应用在海军作战指挥中[52 ] . 他们所 设计的多智能体模板用来获取战略指挥者的知识 , 特别是战船协同作战方面的知识. Azarewicz 等人 提出的这一模板提供了一种灵活的知识表示方法. 依据该模板构造的规划识别模型能够推理出多智能 体规划方式所显露的不同情况的特征变量. 模板实 例能够根据智能体的行为对智能体的未来动作做出 假设. 这种规划识别方法通过处理特征机制来限制 多智能体域中可能假设的增长. 该方法能够解释敌 方船只的活动 ,并预测敌军的规划及目标 ,可用于辅 助海军指挥者进行战略决策. 1998 年 ,Mulder 提出了战术规划识别的一种 通用任务模型[ 53 ] . 他认为 ,在许多领域中对所观察 到的人类行为进行识别都是非常重要的. Mulder 提 出的通用任务模型主要用来识别敌方规划. 该方法 打破了早期方法只能识别敌方对象及智能体未经确 认的 观 察 结 果 的 限 制. Frank Mulder 和 Frans Voorbraak 在 2003 年又对战术规划识别进行了形 式化描述[54 ] . 他们认为战术规划识别中最重要的是 对敌军被观察对象一致性的识别. 因为在战术规划 识别中 ,不知道所观察到的动作或行为是否出自于 同一个对象. 所以战术规划识别器不仅要生成规划 假设 ,还要对规划假设赋值 ,根据假设赋值来判断观 察到的动作是否属于同一对象. 该方法主要应用于 军事领域 ,对于相似的敌对智能体间的识别也有较 好的应用. Robert Suzic 在 2003 年采用统计模型对敌军 策略的不确定性加以表示和识别[55 ] . 他们采用网络 结构将单一智能体问题扩展成在线多智能体随机策 略识别问题. 根据智能体之间的相互关系 ,Suzic 创 建了一种与敌军组织相兼容的策略结构. 通过这种 方法利用已知的军事组织知识 ,减少了大量的假设 空间. 因此该方法可以降低问题复杂度 ,使得战术规 划识别方法更加可行. 同样 ,通过在策略识别中应用 统计模型 ,可以用一种相容的方式来处理不确定性 , 也就是说 ,提高了策略识别的健壮性. 为了达到信息 融合的目的 ,Suzic 的模型可以整合预处理的不确定 动态感知数据 ,例如可以将敌人的位置与地形数据 和不确定先验知识结合在一起 ,以健壮、合理的方式 推断出多智能体策略. Suzic 在其自身的研究基础上又进行了深入研 究. 2005 年 ,他又提出了规划识别的一种通用模 型[56 ] ,并将其用于威胁评估. 他认为规划识别应该 以一种统计的健壮方式 ,考虑尽可能多的战术情况 和单位类型. Suzic 在其通用模型中加入了明确的效 用值 ,并将多实体贝叶斯网络(multi2entity bayesian networks , MEBN) 作为设计灵活规划识别模型的 主要方法. 这种网络可以将网络片段组合成贝叶斯 网络. 通过使用多实体网络片段 ,这种模型能够扩展 假设空间 ,并能表达多种多实体结构. 313 对手规划/ 敌意规划/ 应对规划 多年来 ,规划识别的研究一直都聚焦在传统的 规划识别领域和方法上 ,而规划识别的应用也仅限 在传统领域 ,比如自然语言理解 ,智能帮助系统等. 近些年来 ,一些学者把目光放在了具有对抗性质的 研究领域上 ,如博弈策略、军事领域、网络入侵检测 系统等 ,这些具有对抗性质的领域可以称为对手规 划(adversarial plan) 领域或敌意规划 ( hostile plan) 领域 ,把应对对手规划或敌意规划的规划称为应对 规划. 具有对抗性质的规划领域与传统规划领域相 ·10 · 智 能 系 统 学 报 第 2 卷