第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种假设：穷尽假设 个三元组<T,G,P>,其中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 规划识别 ,姜 云飞、马宁给出了分解和枚举的概念 ,并给出了限定 求解规划识别问题的算法. 以溯因理论为基础 ,他们 给出了规划识别的模型 ,即一个规划识别问题是一 个三元组 < T , G, P > ,其中 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 ·