第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 ·