基于解释图剪枝算法的概率规划识别系统的研究及实现

论文摘要

规划识别是指规划识别器根据观察到的智能体（一个或多个）的片断的、琐碎的动作,推测出在一定程度上具有合理因果关系的智能体将要执行的动作和欲实现的目标,即推导出智能体正在执行的规划。但是,通常无二义性地确定一个规划假设是很困难的,因为在许多领域,或者一个动作服务于多个目标,或者被识别域中存在多规划甚至是多智能体多规划并行执行,而且,其中的许多领域仅仅是部分可观察的等等。这些问题的存在限制了许多规划识别方法的应用。比如,没有状态转移概率模型的复杂领域的大规模特性使得抽象马尔可夫模型的应用变得困难;基于概率语法的方法无法处理多规划交替并行实现的问题;采用语法分析的方法,虽然搜寻速度快,但无法处理时序约束等等。Goldman和Geib于1999年提出了一种新的基于规划执行的规划识别模型,之后又于2005年加以完善,其方法不仅可以识别偏序规划及多规划交替执行,还可以处理域的部分可观察问题。但是,随着考虑的未观察动作在整个规划假设中所占比例的增加,其效率将明显下降。在本文中,我们提出了一种新的规划识别方法——基于解释图剪枝技术的规划识别算法,该算法在给出新的软时序约束和硬时序约束的概念的基础上,以高效的图搜索为基础,以解释图的剪枝技术为核心,利用本文中定义的两种时序约束来推测未观察动作,扩展解释图,并利用软时序约束对当前解释图进行剪枝,以精确目标假设集合,然后计算各目标假设的概率,并以之对目标假设进行分级与选择,最后对所选目标假设子树进行扩展,即可得到完整的规划假设。同时,本文还引入了支持程度的概念,以使规划识别可以随着收集到越来越多的证据而合理地改变。该算法不仅可以有效处理域的部分可观察问题和偏序规划及多规划交替执行等问题,还可以排除智能体的误导动作,这将在网络安全及入侵检测等许多领域都有广阔的应用前景。在给出算法的基础上,本文采用C++语言对该算法进行了实现,设计了基于解释图剪枝技术的概率规划识别系统EGPPR,并用实例对其性能加以测试,结果表明,该系统完全可以达到理论预期效果,即不仅可以识别出智能体的目标和已经发生却未被观察到的动作,还可以推测出智能体将要执行的动作,以及排除干扰动作等,这一性能将有相当可观的应用价值,尤其是在敌对领域,推测出智能体将要执行的动作将是对敌方正在执行的规划进行应对的至关重要的依据和基础。而且,由于目前国内尚没有一款公开的成形的规划识别器,所以本文的EGPPR系统将以其创新性而具有较大的研究价值与可观的应用前景。

论文目录

• 摘要
• ABSTRACT
• 引言
• 第一章 智能规划概述
• 1.1 智能规划的基本概念
• 1.2 智能规划的发展
• 1.3 规划问题描述语言
• 第二章 规划识别的研究与发展
• 2.1 规划识别概述
• 2.2 规划识别的发展
• 2.3 规划识别分类
• 2.3.1 根据智能体在规划识别中的作用分类
• 2.3.2 根据规划识别是否具有规划库分类
• 2.3.3 根据规划识别是否有完备的领域知识分类
• 2.3.4 根据所识别的动作序列是否完全可观察分类
• 2.3.5 根据观察结果是否可信赖分类
• 2.4 规划识别方法
• 2.4.1 基于事件层的规划识别
• 2.4.2 基于限定理论的规划识别
• 2.4.3 基于规划知识图的规划识别
• 2.4.4 基于语法分析的规划识别
• 2.4.5 基于规划执行的规划识别
• 2.4.6 基于目标图分析的目标识别
• 2.4.7 基于动态贝叶斯网络的规划识别
• 2.4.8 基于决策理论的规划识别
• 2.4.9 基于隐马尔可夫模型的规划识别
• 2.5 规划识别的应用
• 第三章 基于解释图剪枝的规划识别算法
• 3.1 基本的规划表示
• 3.1.1 表示行动分解
• 3.1.2 层次规划的图形化表示
• 3.2 时序约束关系及定义
• 3.3 值传递
• 3.4 扩展的规划表示
• 3.5 识别算法
• 3.5.1 解释图剪枝算法
• 3.5.2 解释图（EG）的扩展算法
• 3.5.3 概率值传递算法
• 3.5.4 目标假设子树（GHT）扩展算法
• 3.5.5 识别算法
• 3.6 应用举例
• 3.7 可处理的问题
• 3.7.1 偏序规划
• 3.7.2 未观察动作（部分可观察性）
• 3.7.3 实现多目标的交替多规划
• 3.7.4 误导动作
• 第四章 EGPPR 规划识别系统的设计与实现
• 4.1 系统介绍
• 4.2 系统功能设计
• 4.3 系统基本类的设计
• 4.3.1 结点类
• 4.3.2 边类
• 4.3.3 解释图类
• 4.3.4 关系类
• 4.4 各类之间的关系
• 4.5 系统工作流程
• 4.6 开发工具及测试环境
• 4.7 实验结果及分析
• 结论
• 参考文献
• 后记
• 在学期间公开发表论文情况