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 卷