（计算机应用技术专业论文）基于概率目标图分析的规划识别.pdf

摘要 智能规划识别是人工智能研究领域近年来发展起来的一个热门分支， 由 于其广 泛的实用性， 受到研究者的高度重视。 尤其是具有不完全信息和不确定信息的规划 识别问题已经成为智能规划识别中的研究重点。 在各种研究方法中，由 于概率方法 能较准确地对不确定信息定量描述，因 此研究动作具有概率输出的概率规划识别方 法体现了 较强的优越性， 这个方法得到了研究者的肯定， 并在此基础上产生了 大量 的算法。基于目 标图分析的规划识别算法是近几年出现的优秀的规划识别算法之 一。 本文首先从域表示、目 标图的构造等几个方面对基于目 标图分析的 规划识别算 法进行了 扩展，并给出了因 果连接强度、 相关动作支持强度、有效规划的可信度、 一致目 标的强度等一系列新的定义， 通过新给出的定义我们成功的给出了 基于概率 目 标图 分析的 规划识别算法， 使这样既保留了 基于目 标图规划识别的 原 有优点， 又 使基于目 标图的 规划识别具有处理概率规划的能力， 使基于目 标图的 概率规划识别 能够更好地运用到各个应用领域中。 关键词:人工智能;规划识别;概率规划识别;目标图分析;概率目标 图分析 ab s t r a c t i n t e ll i g e n t p l a n r e c o g n i t i o n i s a n h o t b r a n c h o f a l i n r e s e n t y e a r s . a s i f s w i d e l y a p p l ic a t i o n , m a n y f a m o u s s c h o l a r s h o m e a n d a b r o a d d e v o t e t h e m s e l v e s t o t h e r e s e a r c h . e s p e c i a l l y , t h e i n c o m p l e t e a n d u n d e te r m i n e d p l a n r e c o g n i t i o n p ro b l e m i s th e k e y b r a n c h o f .t h i s f i e l d . i n v a r i o u s k i n d s o f r e s e a r c h a p p r o a c h e s , b e c a u s e t h e p r o b a b i l i t y m e t h o d c a n d e s c r i b e t h e u n c e r t a i n i n f o r m a t i o n r a t i o n r e l a t i v e l y a c c u r a t e l y , s o s t u d y t h e p r o b a b i l i s t i c p l a n r e c o g n i t i o n t h a t t h e o p e r a t o r h a s p r o b a b i l i s t i c o u t c o m e r e l a t i v e l y s t r o n g s u p e r i o r i t y i n m e t h o d . ma n y r e s e a r c h e r s a r e i n f a v o r o f t h i s m e t h o d a n d h a v e p r o d u c e d a l a r g e a m o u n t o f a l g o r i t h m s o n t h e b a s i s o f t h i s . g o a l r e c o g n i t i o n t h r o u g h g o a l g r a p h a n a l y s i s i s a e x c e l l e n t a l g o r i t h m o f t h e s e . i n t h i s p a p e r , w e g i v e e x t e n d t h e g o a l g r a p h ,f ro m t h e d o m a i n r e p r e s e n t a t i o n , g o a l g r a p h c o n s t r u c t i o n e t c . a n d t h e n w e g i v e t h e ， d e f i n i t i o n o # c a u s a l l i n k i n t e n s i t y , r e l e v a n t a c t i o n s u p p l y i n t e n s i t y , c o n s i s t e n t g o a l in t e n s i t y a n d s o o n , u s i n g w h i c h w e g i v e t h e n e w a l g o r it h m o f p ro b a b i l i s t i c p la n r e c o g n i t i o n b a s e d o n p r o b a b i l i s t i c g o a l g r a p h . o u r a l g o r i t h m n o t o n l y k e e p s d o w n t h e v ir t u e o f g o a l g r a p h , b u t a ls o e x t e n d s t h e g o a l g r a p h t o h a n d l e t h e p ro b a b i l i s t i c a l g o r i t h m o f p r o b a b i l i s t i c a p p l i c a t i o n i n m a n y f i e l d s . 声 o b l e m s . b a s e d o n a s o u r a l g o r i t h m盯r s e s , p ro b a b i l i s t i c g o a l gr a p h t h e 口 翔 n k e y w o r d s: a i ; i n t e l l i g e n t p l a n r e c o g n i t i o n ; p r o b a b i l i s t i c p l a n r e c o g n i t g r a p h; p r o b a b i l i s t i c g o a l g r a p h i on ;g o a l 一 一- 一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下 进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外， 论文中小包含其他人己经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 学位论文作者签名:日期: 学位论文版权使用授权书 本学位论文作者完全了 解东北师范大学有关保留、使用学位 论文的规定，即:东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论 文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 日期: 指导教师签名: 日期: 学位论文作者毕业后去向: 工作单位: 通讯地址: 东北师范大学传媒学院 东北师范大学净月校区 电话: 邮编:1 3 0 1 1 7 引言 智能规划与规划识别是人工智能中较早的一个研究领域。 智能规划的任务是在 给定初始条件下寻找一动作序列， 通过这一动作序列的执行使得世界状态从初始态 到 达目 标状态; 而 规 划识别 是 根据观察到的a g e n t 的 片断的、 琐碎的 动作 来推断a g e n t 的目 标及它的 规划， 从而 预 测a g e n t 未 来的 动作序列， 帮 助a g e n t 完成或阻 止 其完成 规划。 规划识别的应用领域很广泛， 早期的规划识别主要应用在故事理解、 自 然语言 识别、 谈话分析和智能计算机接口等领域， 现在规划识别的应用己 扩展到计算机应 用的各个领域，如网 络入侵检测、 程序理解、智能用户接口 等。在自 然语言理解中 运用规划识别， 可以 实现人机友好式的交互; 在智能用户接口中， 运用规划识别可 以站在用户的肩膀上观察用户的动作， 在适当的时候给用户提供帮助或识别出用户 的目 标后直接帮用户完成任务， 减轻用户的负担。 规划识别的方法有很多种， 有基于限定的规划识别， 有采用语义分析的规划识 别， 也有基于贝 叶 斯 推 理的 规划识别。 1 9 9 5 年b l u m和f u r s t t8 ,提出 利 用规划图 进 行 快 速 规 划 ，h o n g j u n 15 . 6 t 从 规 划 图 得 到 灵 感 ， 提出 利 用目 标图 进 行 规 划 识 别。 利 用 目标图进行规划识别的主要思想是先构造一个目 标图， 然后对目 标图进行分析以识 别与目 前的观察集相一致的部分或完全实现的目 标。基于目 标图识别方法的 特点: 1 )日标图分析不需要规划库;( 2 )不像其他的规划识别系统直接在规划空间中 直接搜索规划，目 标图 分析是先建立一个称为目 标图的图结构， 然后分析目 标图以 识别目 标和规划; ( 3 )日 标图分析识别的只是与目 前观察到的动作相一致的部分或 完全实 现的目 标; ( 4 ) 基于目 标图的规划识别的目 的是为了 解释观察到的 动作而不 是预测未来的动作。 该算法的优点是， 它利用目 标图来表示世界的状态和观察到的动作等， 不需要 规划库，而且不像别的识别系统是在整个规划空间中搜索规划， 而是先构造一个目 标图， 然后分析目 标图 来识别目 标和有效规划， 从而克服了 长期以 来限 制规 划识别 在复杂问题领域的 应用的一个约束， 就是规划库的 建立及规划库的自 动更新， 而且 该算法是合理的， 是多项式时间和空间的。 另一个特点是这种方法识别的规划是与 目 前观察到的动作一致的部分或完全实现的目 标。 它适用于故事理解、 软件的咨询 系统、 数据查询优化等领域。 这些问 题领域有以下几个特点: 大多数动作都是可 以 完全观察的; 通过这些观察到的 动作， 用户的目 标可能部分或完全实现; 识 别目 标是为了 解释已 发生的 ( 过去的) 动作而不是为了 预测未来的动作。 该方法的 优点是目 标图构造算法和分析算法都是多项式时间和空间的， 而且识别的日 标准确 率比较高。 从 卜 面，我们可以看到基于目 标图的规划识别适用的问题领域具有很强的限 制， 在实际世界的问题， 动作通常是不能完全可观察的， 观察到的只是部分的动作， 而且 识别目 标是为了能够进行预测未发生的动作。 为了使基于月标图的规划识别能 够吏好地运用到实际问题中， 我们必须将基于目标图的规划识别扩展到能够处理不 确定信息的概率规划识别。 规划识别中的不确定性主要有三个来源，一是初始状态 的不确定性;一 乙 是动作不确定性，即动作具有多个可能的结果; 三是观察的不确定 j性，即所观察的动作不是一个完全的动作，动作的对象或属性是未知的。 本文在基于目 标图规划识别的框架下， 深入研究如何在目标图中嵌入不确定性 表示和不确定性推理，以使基于目 标图的规划识别能够识别具有动作不确定性的问 题域， 并且能够识别出各个目 标发生的可能 性， 这样既保留了 基于目 标图 规划识别 的原有优点， 又使基于目 标图的规划识别具有处理概率规划的能力， 使基于目 标图 的概率规划识别能够更好地运用到各个应用领域中。 因此， 开展基于目 标图的概率规划识别的研究， 不仅具有重要的学术价值， 也具 有较高的应用价值。 第一章规划识别概述 1 . 1规划识别简介 1 . 1 . 1规划识别的分类及其应用 规 划识 别是 根 据 观察到 的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 完 成 规划。 规划识别问题的解由一个已识别的目 标集合( 己 识别的目标与所观察到的执行 动作相一致) 和每个目 标的有效规划组成 ( 有效规划由已 观察到的动作集合中支持 目 标的那些动作组成) 。 1 . 规划识别的分类 规划识别根据被推理的 a g e n t在规划识别中豹作用可以分为洞孔式规划识别 ( k e y h o l e r e c o g n i t i o n ) 和有意的规划识别 ( i n t e n d e d r 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 影响规划识别过程。 此外通常也根据有无规划库来划分。 典型的规划识别方法是利用规划库进行规划识别， 规划库中包含所有可能的月 标， 然后将观察到的动作与规划库中的规划进行匹配， 识别出育 含 够解释观察到的动 作 的 规 划 ， 主 要 以k a u tz i9 】的 方 法 为 代 表 。 j v n h o n g i 的 基 于 目 标 图 分 析 的 规 划 识 别 和m in g - h a o y i n i t的 基 于 回 归 图 分 析 的 规 划 识 别 方 法 则 属 于 无 规 划 库的 规 划 识 别。 规 划 识 别 还 可以 根 据 识 别 器 是 否 具 有 完 整 的 知 识 及 被 观 察 的八 g e n t 是 否 会 犯 错误进行分类。 2 规划识别的应用 规 划 识别 问 题 是当 前 人工 智能 研究 的 一 个 热 点问 题， 这 是因 为 规 划 识 别 有 着 广 泛的应用领域。 早期的规划识别主要 应用在自 然语言瑰解 ( 谈话分析、故事理解、 机 器 翻 译) 和 智 能 计 算 机 接口 等 领 域 ; 现 在 娜 划 识 别 的 应 用已 扩 展 到 计 算 机 应 用的 各 个领 域， 如网 络 入 僚检 测、 程 序 理 解、 智 能 用户 接口 、 多a g e n t 的 协 作以 及 程 序 理解等。 ( 1 )操作系统 在操作系统环境中识别用户的规划可以使系统做许多有用的事情。 例如: 提出 建议、自 动 地纠正 用 户的 错误， 并自 动完成任务。 h u f f 和l e s s e r 1 7 1 建立了 一 个智 能系统来帮助计算机程序员。系统观察 u n i x中的用户命令，基于这些命令决定用 户的规 划。 ,l 可以识别程序设计员的规划， 如浏览代码， 编辑代码、 编译等等。 l e s h l l s . 1 8 . 19 . 2 0 . 2 1 1 建立一个规划识别系统， 它可以识别u n i x 和w i n d o w s n t 环境下的 用户目 标 。 ( 2 )自 然语言 理 解( n a t u r a l l a n g u a g e ) 规划识别研究的早期最主要的应用领域是自 然语言处理。 人与人之间的 沟通和 交流就是有意地识别，需要识别讲话者的意图。 故 事 理 解( s t o r y u n d e r s t a n d i n g ) 故事是有结构的， 根据故事中人物的言语和行为识别人物的 性格能更好地理解 故 事中 人物的活动。 早期的故事理解系统s a m 2 3 ( s c r i p t a p p l i e r m e c h a n i s m ) 和 p a m 2 3 ( p l a n a p p l i e r m e c h a n i s m ) 都采用了 规划识别来提取故事的结构。 谈 话 分 析( d i s c o u r s e ) 早期的规划识别在谈话分析上应用很广泛。 根据一 段谈话， 这段谈话所传达的 意思， 识别出谈话的内容后， 自 动地生成回答。 这在早期的人机对话系统很有意义。 机 器 翻译( m a c h i n e t r a n s l a t i o n ) 一 个 好的 机 器 翻译 系 统需 要 理 解 讲 话 者的 规 划 和目 标 及意图 。 v e r b m o b i 1 13 3 1系 统是一个一句一句自 然语言翻译系统， 它能翻译英语、德语和日语， 对规划的识别 可以允许更健壮和精确的翻译。 对 话 系 统( d i a l o g u e s y s t e m s ) c a r b e r r y 2 4 1 在一 个对话 系统中 使 用规划识 别来建议大 学生的 选课、 如 何得到 学 位等。识 别用户的规划可以使系统提出更适宜和有用的回答给学生。 ( 3 )智能用户接口 在智能用户接口中， 运用规划识别可以站在用户的肩膀上观察用户的动作， 在 适当的时 候给用户提供帮助或识别出 用户的目 标后直接帮用户完成任务， 减轻用户 的负担。 智能帮助系统 与 规划识别在操作系统中的 应用相对应的是智能帮助系统， 它可以 观察用户的 动作， 识别 用户当 前的目 标， 给出 帮 助。 如u n i x 咨 询 if +. ( u n i x c o n s u l t a n t p r o j e c t , u c ) 1 2 5 . 2 6 . 3 4 1是在u n i x 操作系 统下 进行 规划识 别， 它的 另一个作 用是帮 助初学 者学 习使用u n i x ， 初学者可以提出 关于如何使用u n i x 操作系统的问题及如何在u n i x 环 境下完成一个任务等问题， u c 将给出回答并根据用户的问 题识别用户的目 标， 给出 最 好的 帮 助。 b a u e r 3 5 1 实 现了 一 个 邮 件 智能 帮 助 系统。 智能教学 g r e e r 和k o e h n 12 3 1 给出了 几 个规 划识别怎 么 与智能 教学相关的 例子。 包括识 别 学生求解问题的规划，并改进学生问题求解模型。 多智能体交互协作( m u l t i - a g e n t i n t e r a c 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 的目 标 和 规 划， 调 整 和修改自 己 的 规 划， 更 好 地协 作完成任务。 ( 4 军事防御系 统: 战术规划识别在军事防御系统中 尤为重要。 它可以识别敌方的目 标及规划， 也 叮以阻止敌方对自己的规划的识别， 在发现自己的目标被对方识别时， 立即生成应 对 规划来阻 碍 规划识别 过程。 文献 2 7 . 3 7 给出了 战 术规 划识别的 形 式 化描 述。 ( 5 ) 入侵检测系统 入侵检测系统的主要功能是发现入侵动作并发出 警报。 没有运用规划识别的入 侵检测系统只能在发生入侵行为后发出警报， 这样用户可能来不及采取措施;而带 有规划识别的入侵检测系统可以根据一些观察到的动作或其他可怀疑的行为进行 预测是否有人准备入侵系统，这样就可以在发生入侵行为之前发出警报， 用户可以 采取相应的安全措施。 ( 6 ) 程序理解 程序理解就是从一段源程序来理解这段程序的设计目 标和规划， 很自 然地可以 运用智能规划识别来进行程序理解。 规划识别在程序理解中的应用与其他应用最大 的区 别是它可以 获得所 有的 动作 ( 程序代码) ， 文献29 1 给出了 规 划识 别 在程 序理解 中的应用。 ( 7 )自 动驾 驶 在自 动驾 驶中， a g e n t 必 须将自 己 的 规 划与 其它驾驶员 的规划相 互协 调。 这种 协调依赖于对其它驾驶员动作的观察，如车的移动及标志。 根据观察到的其它驾驶 员的动作识别出其它驾驶员的规划，然后调整和修改自己的驾驶规划。 1 . 1 . 2规划识别的发展过程及方法 1 . 基于k a u t z 的理论的推理方法 k a u t z 9 1 的主 要思 想是建立一 个事件 ( 规划) 的层次 结构，由 动 作的 不同 抽象 组成。 这个层次结构用来组成规划库。 规划识别时通过将观察到的动作与这个层次 结构相匹配， 试图建立用户高层目 标的规划。每当观察到一个动作， 识别器就试图 剪 去 和 该 动作 不 一 致的 规 划， 把该 动 作 加入 到 与 其 一 致的 规划中。k a u tz ” 作了 两 个封闭世界假设: . 已 知的执行一个动作的方法就是执行该动作的 所有方法; . 所有动作都是有目 的的， 必须知道执行一 个动作的 所有可能的理由。 这些假设用来评价从一个观察到的动作集合得到的结论是否合理，可以 通过 m c c a r t h y s36 1的 限 定 理 论 体 现。 k a u t z 方法的问题是: ( 1 ) k a u t :的 规划识别得到的 是所观察到的动作的最小规划集。如 果规划集里有多 个规划时，它不能够确定哪一个规划更能解释观察到的动作集合。 ( 2 )高层规划的确定是根据具体的问题来确定的，没有明确的标准，例如走路可以 作为一个高层规划也可以作为购物规划的一部分。 ( 3 )k a u t z的规划识别不能识别没有出现在规划库中的新规划，即它要求规划库是 完备的。 2 .基于逻辑的规划识别 ( 1 )基于溯因理论的规划识别 溯因理论是一种逆推理归纳， 它是一种由结论成立而推出前提以 某种置信度成 立的归纳方法。 这种方法的一般模式是: 若h 为真时， 具 j h - - e 必为真; 观察 到e 成 立; 则h 以 某 种 置 信 度成 立。 l i n 和g o e b e 1 1 1 发 现了 溯因 理 论 和 规 划 识 别之间的联系，可以将溯因理论运用到规划识别中，当 观察到一个结论时，会寻找 它发生的原因来作为该结论产生的解释。 ( 2 )基于缺省推理的规划识别 缺省理论是在知识不完全的情况下使推理得以 继续下去的一种非单调推理理 论。 缺 省 推 理的 核 心是 在 默认 或 假设 某 些命 题 成 立 的 前 提下 进 行 推理. c a r b e r r y l24 l 根据对自 然对话的分析以及对人类推理的心理研究提出了一个基于默认推理的规划 识别的模型。它的主要思想是通过支持适当的默认推理来延迟无根据的结论 ( 或决 策)直到进一步的证据出 现，从而逐步 ( 逐渐) 地更新用户规划的系统模型。比如 说， 我们对鸟 默认的推理是鸟会飞，但其实并不是所有的鸟都会飞 ( 如鸵鸟、企鹅 等就不会飞) ， 但对于某个具体的鸟a ， 我们可能开始时就会推断a 会飞。 如果随后 我们又获得进一步的证据a 是一个鸵鸟， 我们就会更新或撤消前面的 结论， 并做出 结论a 不会飞。 ( 3 )基于限定理论的规划识别 规划识别是根据观察到的一些现象来推测a g e n t 可能执行的规划。 这些规划通 常是在假设识别器具有完整的知识， 而且a g e n t 不会犯错误的条件下获得的。 如果 由于执行了某一个动作而改变了 某个性质或出 现某个现象， 那么这个动作是能使这 个 性 质改 变 或这 个 现象出 现的 所知 道的 所 有动 作。 m c c a r t h y p 6 1 的 限 定 逻辑 ( c i r c , c i r c u m s c r i p t i o n ) 的 基本思想是“ 从某些事实a 出 发能 够推出 具有 某一性 质p 的 对象就是满足性质p的全部对象” 。 规划识别和限定理论很相似， 所以用限定理论 来 求解 规划识别问 题是一 种很 好的 方 法。 k a u t z 19 1 的 规 划识别 表示方法 就是 基于限 定 的思想来进行规划识别的， 但井没有采用限定理论进行求解。 姜云飞 和马宁2 1 提出 了 利用限定理论求解规划识别问 题。 由 于各种逻辑理论都比 较完备， 所以 基于逻辑框架的规划识别能 够较好地进行 形式化地推理，使得规划识别的推理过程得到简化。 3 基于概率方法的规划识别 由于纯粹的逻辑框架将产生多个规划假设， 虽然各个假设的可能性不同， 但在 基于逻辑的规划识别框架中是相同对待的。所以，很多学者提出在规划识别中引入 不确定性推理来对规划假设进行排序，选出最优的 规划假设作为规划识别的解。 c h a r n i a k 和g o l d m a n i1 3 提出 将贝 叶 斯 推理 运 用到 规 划识 别中 ， b a u e r 10 川 提出 将 证 据理论运用到智能帮助系统领域的规划识别中。 ( 1 )贝叶斯网络方法:( b a y e s i a n n e t w o r k a p p r o a c h ) c h a r n i a k 和g o l d m a n 13 1提出 一 种 基 于贝 叶 斯网 络的 规划 识 别 模 型。 他 们 将 规 划 识别看作是推理的特例， 并描述了一种根据一些观察到的动作生成可能的解释图的 规划识别方法。 这种规划识别模型由关于这个世界的事实的知识库组成， 它用于生成贝叶斯网 络，称为规划识别贝叶斯网 络。通过对给定的知识库和一些给定的动作形成规划识 别贝叶斯网络集合， 然后采用前向 链式规则进行推理。 这种方法的主要问 题是当知识库和证据集合增加时， 贝叶斯网络的大小会快速 增加， 所以不适用于比较复杂的问题领域。 ( 2 )贝叶斯方法: ( b a y e s i a n a p p r o a c h ) 贝叶斯方法是使用概率中的贝叶斯理论来评估一个解释的可能性。 规划识别的 思想是生成所有可能的解释， 然后利用贝叶斯理论来评价各个解释， 最后选择最可 能的一个。 它和贝叶斯网络方法的区别是:贝叶斯网络方法是将规划库中的因果关 系用贝叶斯网络来表示， 然后根据新出现的证据进行推理， 而贝叶斯方法只是用贝 叶斯推理来估计各个候选规划的可能性， 然后选一个可能性最大的作为所观察到的 动作集合的解释，适用于那些比较容易得到先验概率的问题领域。 ( 3 )基于d e m p s t e r - s h a f e r 证据理论的规划识别 由于贝叶斯推理需要知道各个假设的先验概率及条件概率， 这在很多领域是很 难得到的。证据理论具有比 概率论弱的公理，能够区分 “ 不确定”和 “ 不知道”的 差 异， 并能 处 理由“ 不 知 道” 引 起的 不 确定 性， 具 有 较 大的 灵活 性。 b a u e r f l0 n 提 出将证据理论运用到智能帮助系统领域的规划识别中。 利用证据理论进行规划识别 的主要思想是: 将规划识别过程分为两个阶段， 第一个阶段是根据观察到的动作或 现象及背景知识进行规划推理， 得到多个规划假设; 第二个阶段是利用证据理论对 各个候选的规划假设进行评价， 选择出最优的规划假设。 利用证据理论选择最优的 规划假设过程是: 假设给规划假设集合一个初始的概率分配函数m o ，当出 现一个新 的观察w 后， 根据， 将生成一个新的概率分配函数m l ， 然后运用证据理论的合并规 则将m o 和m l 合并成一个新的概率分配函数。 证据理论的优点是它只需要基本的概 率分配函数，而不象贝叶 斯方法需要条件概率。 4 基于语法分析的 规划识别 v i l l a i n 1 2 ，提出 了 采用 语 法 分析 的 方 法 进 行规 划 描述。 采 用语 法分 析 的 规 划 识 别模型主要用在故事理解和d i s c o u r s e 谈话分析) 中。 5 . 基于规划知识图的规划识别 姜云飞 i3 1在 一种基于规划知识图的规划识别算法中提出 利用规划知识图 进 行规划识别。 它的主要思想是将k a u t z 的 层次结构图转换为一个规划知识图， 规划 知识图是一 个非循环的与或图。 然后利用与或图的宽度优先算法来求能够解释观察 到的动作集合的规划集。该方法的主要优点是与或图的搜索算法己 经非常成熟，所 以可以很好地控制搜索过程。 6 . 利用目 标图分析进行规划识别 b l u m 和f u r s t 1 提出 利 用 规 划图 进 行 快 速 规 划， h o n g j u n 15 ,6 1从 规 划 图 得 到 灵 感， 提出 利用目 标图 进行规划识别。 它的主要思想是先构造一个目 标图， 然后通过对目 标图的分析进行规划识别。 这种识别方法的特色是它不需要规划库，而且不像别的 识别系统是在整个规划空间中搜索规划， 而是先构造一个目 标图， 然后分析目标图 来识别目 标和有效规划。 另一个特点 是这种方法识别的 规划是与目 前观察到的动作 一致的部分或完全实现的目 标。 它适用于故事理解、 软件的咨询系统、 数据查询优 化等领 域。 这些问 题领域有以下几个特点: 大多数动作都是可以 观察到的; 通 过这些观察到的 动作， 用户的目 标可能部分或完全实 现; 识别目 标是为了 解释己 发生的 ( 过去的) 动作而不是为了预测未来的动作.该方法的优点是目 标图构造算 法和分析算法都是多项式时间和空间i a j ，而且识别的目标准确率比较高。 7 .基于回归图的规划识别 m i n g - h a o y m 1t 1在h o n g j u n is . 6 !的 目 标 图 的 基 础 上 提 出 了 利 用 回 归 图 进 行 规 划 识别。回归图是由命题结点、 动作结点和目 标结点组成的。它是基于将回归图中的 结点分成确定的结点和可能的结点的思想进行识别确定的目 标和可能的目 标。 该方 法既保留了目 标图分析的方法的优点， 又有自己 独特的优点:能识别出 确定的一致 目标和可能的一致目 标。 1 . 2当前主要规划识别算法的分析 1 . 2 . 1衡量规划识 别算法的标准 l e s h 5 1 提到 一 个规划识 别算法的 质量可以 从两 个 方面 来衡 量和评价: 精确度 ( 性) ( a c c u r a c y ) :即规划识别器识别的正确率。 可 识 别的 范 围 ( 识 别 率) ( c o v e r a g e ) : 即 规 划识 别 器 所能 识 别 的问 题 范围口 在实际的 应用中， 可以 根据应用本身对识别器这两个方面的不同要求来评价某 个 规 划 识 别 器， 可 以 通 过 一 个 评 价 函 数 ( s c o r e f u n c t io n ) 来 实 现 。 如 果 一 个 应 用 是 利 用 规划识别来帮助用户完成任务 则要求具有很高精确性， 因为这样可以避免给用户提 供不恰当、 不合适的帮助; 而对于一个安全系统使用的规划识别器的算法是为了 检 测 各 种可 能的 危险 行为， 它可以 忍受 错误的 识别， 但 希望有 任何可 能潜 在的 危险 行 为时都能 够发出 誉报， 可以 牺牲一点精确性来换取识别范围 ( 识别率) 。 1 . 2 . 2几种主要算法的分析 1基于k a u t z 的理论的推理方法 k a u 澎 3 0 1 在 1 9 8 6年 第一次 基于限定理论 和最小 化集合的思想 提出了 规划识 别 的 通用框架， 在1 9 8 7 19 1 年提出了 规划识别的形式理论， 它的主要思想是建立一个事 件 ( 规划)的层次结构， 规划识别时 通过将观察到的 动作与这个层次结构相匹配， 试图建立用户高层目 标的规划。 k a u t z 的方法具有丰富的表达能力， 是目 前最著名、 也 最具广泛影响的一 种表示及处理规划识别的方法， 但k a u t z 的识别框架的仍然存 在下面的几个问题: ( 1 ) k a u t z的规划识别得到的是所观察到的动作的最小规划集。如果规划集里有多 个规划时，它不能够确定哪一个规划更能解释观察到的动作集合。 ( 2 )高层规划的确定是根据具体的问题来确定的， 没有明确的标准， 例如走路可以 作为一个高层规划也可以作为购物规划的一部分。 ( 3 ) k a u t z 的规划识别不能识别没有出 现在规划库中的新规划，即它要求规划库是 完备的。 2 .基于逻辑的规划识别 ( 1 )基于溯因理论的规划识别 溯因理论是一种逆推理归纳， 它是一种由结论成立而推出前提以某种置信度成 立的归 纳 方法。 l i n 和g o e b e l p 1 1 发 现了 溯因 理论和规 划识别之间的 联系， 可以 将 溯 因理论运用到规划识别中，当观察到一个结论时， 会寻找它发生的原因来作为该结 论产生的解释。这种方法的缺点是知识表示差，不能处理抽象继承等问题。 ( 2 )基于限定理论的规划识别 规划识别是根据观察到的一些现象来推测a g e n t 可能执行的规划。 这些规划通 常是在假设识别器具有完整的知识， 而且a g e n t 不 会犯错误的条件下获得的。 如果 由 于执行了某一个动作而改变了某个性质或出现某个现象， 那么这个动作是能使这 个性 质改 变或 这 个现 象出 现的 所 知 道的 所 有 动 作。 m c c a r t h y 3 6 j 的 限 定 逻辑 ( c 工 r c , c i r c u m s c r i p t i o n )的基本思想是“ 从某些事实a 出 发能够推出具有某一性质p 的 对象就是满足性质 p的全部对象” 。 规划识别和限定理论很相似，所以用限定理论 来 求解规 划识别问 题是 一种 很好的 方 法。 k a u t z 1 9 1 的 规 划识 别表示 方法就是 基于限 定 的思想来进行规划识别的， 但并没有 采用限定理论进行求解。 姜云飞和马宁提出了 利用限定理论求解规划识别问题。 由 于各种逻辑理论都比 较完备， 所以 基于逻辑框架的 规划识别能够 较好地进行 形式化地推理，使得规划识别的推理过程得到简化。 3 基于概率方法的规划识别 由 于纯粹的逻辑框架将产生多个规划假设， 虽然各个假设的可能性不同， 但在 基于逻辑的规划识别框架中是相同 对待的。 所以，很多学者提出在规划识别中引入 不确定性推理来对规划假设进行排序，选出最优的规划假设作为规划识别的解。 c h a r n i a k 和g o l d m a n 13 1 提出 将贝 叶 斯 推 理 运用 到 规 划 识 别中， b a u e r llo . 1 1 提出 将 证 据理论运用到智能帮助系统领域的规划识别中。 ( 1 )贝叶斯网 络方法:( b a y e s i a n n e t w o r k a p p r o a c h ) 这种方法的主要问题是当知识库和证据集合增加时， 贝叶斯网络的大小会快速 增加， 所以不适用于比较复杂的 伺题领域。 ( 2 )贝 叶 斯 方法: ( b a y e s i a n a p p r o a c h ) 贝 叶斯方法和贝 叶斯网络方法的区别是: 贝叶斯网络方法是将规划库中的因果 关系用贝叶斯网络来表示， 然后根据新出现的证据进行推理，而贝叶斯方法只是用 贝 叶斯推理来估计 .各个候选规划的可能 性， 然后选一个可能性最大的 作为所观察到 的动作集合的解释，适用于那些比较容易得到先验概率的间题领域。 ( 3 )基于d e m p s t e r - s h a f e r 证据理论的规划识趴 13 a u e r p o , i l l提出 将 证据理 论 运 用到 智 能 帮 助 系 统 领 域 的规 划识 别 中。 证 据 理 论 的优点是它只需要基本的 概率分配函 数， 而不象贝叶斯方法需要条件概率。 4 . 基于语法分析的规划识别 v i l f a i n 1 1 2 ) 提出了 采用 语法分析的 方 法 分析规划描 述，该方 法虽然 有其搜寻 速 度快的优点，但是它不可能像k a u t z 的方法具有很强的表达能力。 5 . 基于规划知识图的规划识别 姜云 飞 13 1在 一 种 基于 规 划 知识图 韵规 划识 别 算 法 中 提出 利 用 规 划 知 识图 进 行规划识别。 它的主要思想最将一k a u t z 的 层次结构图转换为一个规划知识图， 规划 知识图是一个非循环的与或翻a 然后利用与 或图的宽度 优先算法来求能 够 解释观察 到的动作集合的规划集。 该方法的主要优点 是与或图 的搜索算法已 经非常成熟， 所 以可以 很好地控制搜索过程。 6 .利用目 标图分析进行规划识别 b lu m 和f u r s t ta l提出 利 用 规 划 图 进 行 快 速 规 划， h o n g j u n (s 4 i 从 规 划 图 得 到 灵 感 ， 提出 利用目 标图进行规划识别. 它的主要思 想是先构造一个目 标图， 然后通过对目 标图的 分析进行规划 m别. 这种识别方法的特色是它不需要规划库， 而且不像别的 识别系统是在整个规划空间 中搜索规划， 而是先构造一个目 标图， 然后分 析目 标图 来识别目 标和有效规划。 另一个特点 是这种方法识 别的规划是与耳 前观察到的动作 一致的部分或完全实现的目 标。 该方法的优点是目 标图构造算祛和分析算法都是多 项式时间和空间的， 而月 . 识别的目 标准确率比 较高。 7 .基于回归图的 规划识 别 th i n g - h a o y i n l7l 在h o n g j u n fs . b ) 的 目 标 图 的 基 础 上 提 出 了 利 用 回 归 图 进 行 规 划 识 别 。 回 归 图 是由 命 题 结 点 、 动 柞 44点 和目 标 结 点 组 成的 。 它 是 基 于 将 回 归 图 中 的 结点分 成 确定的 结点和可能的 结点 的思 想进行识 别确 定的目 标 和可能的目 标。 该方 法既保留了目 标图分析的方法的 优点， 又 有自 己 独特的优点: 能 识别出 确定的一 致 目 标和可能的一致目 标。 以 上介绍了目 前九种主 要算法 的 特点. 前 几种方 法的 共 伺点是 都建立 在规 划 库 基 础上， 这 类方 法 在 特定 领 域中 的 应 用 效 果 大 都是 很 好的， 但 其局限 性也 是 很 明 显 的。 长期以来限制规划识别在复杂问 题领域应用的一个约束，就是规划库的建立及 规划库的自动更新。 又由于规划库本身的限制，很难找到一种通用于多数领域的规 划识别方法。例如传统方法中著名的k a u t z 的方法具有丰富的表达能力，但也有其 致命弱点，它不能识别没有出现在层次结构中的新规划， 并且其规划表示方法是手 工方法， 这对一个大的 规划识别系统而言是不可想像的。即 使抛开这些问 题不谈， 传统方法在规划库上的搜索也往往是指数级时间。 针 对 这 些问 题h o n g j u n 15 .6 )提出 利 用目 标 图 进 行 规 划 识 别 。 相 对 于 传 统 的 方 法 ， 基于目 标图识别方法具有很多优点，但也有一些不足与局限之处。如下所述。 1 . 3基于目 标图的规划识别 b lu m 和f u r s t l8 1提 出 利 用 规 划 图 进 行 快 速 规 划， h o n g j u n 1s .6 1 从 规 划 图 得 到 灵 感 ， 提出 利用目 标图进行规划识别。 它的主要思想是先构造一个目 标图， 然后通过对目 标图的分析进行规划识别。 它适用于故事理解、 软件的咨询系统、 数据查询优化等 领域。 这些问题领域有以下几个特点: 大多数动作都是可以观察到的; 通过这 些观察到的动作， 用户的目 标可能部分或完全实现; 识别目 标是为了 解释己 发生 的 ( 过去的) 动作而不是为了 预测未来的动作。 该方法的优点是目 标图构造算法和 分析算法都是多项式时间和空间的，而且识别的目 标准确率比较高。 .基于目 标图的规划识别方法的特点: ( 1 )目 标图分析不需要规划库: ( 2 )不像其他的规划识别系统直接在规划空间中直接搜索规划，目 标图分析是先 建立一个称为目 标图的图结构，然后分析目 标图以识别目 标和规划; ( 3 ) 目 标图分析识别的 只是与目 前观察到的动作相一 致的部分或完全实现的目 标; ( 4 ) 基于目 标图的规划识别的目的是为了 解释观察到的动作而不是预测未来的动 作。 .目标图识别算法存在的几个不足之处: ( 1 ) 初始条件必须确定; ( 2 ) 动作的效果必须是确定的，不能处理带有不确定效果的动作; ( 3 ) 必须大多 数动作都是能够观察到的，并且要求观察到的动作必须是清晰、确 定的; ( 4 ) 识别目 标是为了 解释过去发生的动作而不是预测未来的 动作; ( 5 )目 标图识别算法虽然有时能识别一个唯一的目 标但是不能使它很具体; ( 6 )目 标图识别算法不能确定哪个一致目 标的可能性最大。 从上面，我们可以 看到基于目 标图的规划识别适用的问题领域