基于模型检测方法的规划

论文摘要

规划(planning)技术是人工智能中的一项核心技术,可以应用于工业智能控制,太空系统,软件工程,机器人,决策支持,教育与娱乐等各个领域,是当前人工智能领域最热门的领域之一。首先,本文对目前常见的规划(Planning)问题的解决方法做了简单的介绍,并对比了出各自的优缺点。然后介绍模型检测方法,模型检测已经成功的被应用在电路控制和通讯协议领域用来寻找细微的错误。通过对比模型检测问题和Planning 问题想相似与不同,说明能够采用模型检测方法来解决Planning 问题,并自己定义了一门Planning 域描述语言ADL,实现了基于该语言的Planning 系统MYPLANNER。目前世界上已开发出几个基于模型检测方法的规划器,但是他们都没能很好的利用模型检测方法中划分以及抽象等最新研究成果。在该系统中,采用了OBDD(有向决策图)这一特殊的数据结构。根据OBDD中关系乘积的计算和量词量化的特性,对转换关系进行了划分,并提出提前量化这一方法,使得关系乘积的复杂度大大降低。对于OBDD 变量的排序,采用动态变量排序法并根据系统的特殊性进行了改进。本文最后对MYPLANNER 系统所采用的方法优缺点进行了评价并指出了几个比较有前景研究方向。

论文目录

• 第一章 引言
• 1.1 规划的简单介绍
• 1.2 Planning 目前发展状况
• 1.2.1 基于满足的规划
• 1.2.2 Graphplan 方法
• 1.2.3 启发式信息搜索
• 1.2.4 混合方法
• 1.2.5 模型检测方法的现况
• 1.3 本文的主要工作
• 第二章 规划基本概念的介绍
• 2.1 规划基本概念的定义
• 2.2 非确定planning 的简单介绍
• 第三章 模型检测介绍
• 3.1 模型检测的简单介绍
• 3.1.1 模型检测的基本概念
• 3.1.2 CTL
• 3.1.3 符号校验
• 3.2 用模型检测方法解决planning 问题
• 3.2.1 planning 问题和模型检测问题的对比
• 3.2.2 用模型检测方法来解决planning 问题
• 第四章 OBDD 介绍及应用
• 4.1 决策树
• 4.2 决策树归约成 OBDD
• 4.3 OBDD 在planning 问题中的应用
• 4.3.1 为什么采用OBDD
• 4.3.2 用特征函数表示状态和状态集合
• 第五章 转换关系
• 5.1 有限状态机的表示
• 5.2 影像计算
• 5.3 可到达状态分析
• 5.4 OBDD 在planning 中的具体应用
• 第六章 划分以及提前量化
• 6.1 划分的优点
• 6.2 提前量化
• 第七章 ADL 语言
• 7.1 ADL 语言介绍
• 7.1.1 ADL 语言定义的关键字及操作符
• 7.1.2 ADL 语言的语法规则
• 7.2 用ADL 表示非确定性planning
• 7.3 ADL 语言的解析
• 7.3.1 Lex
• 7.3.2 Yacc
• 7.3.3 Lex 与Yacc 结合
• 7.3.4 计算机中命题逻辑的表示
• 第八章 MYPLANNER 系统的实现
• 8.1 转换关系的表示及计算
• 8.1.1 转换关系的构造
• 8.1.2 转换关系的划分
• 8.2 变量排序
• 8.2.1 已经存在的方法
• 8.2.2 本系统采用的方法
• 8.3 核心程序
• 8.3.1 程序流程
• 8.3.2 程序伪码
• 8.4 OBDD 包的优化
• 8.5 试验结果
• 第九章 结束语
• 参考文献
• 摘要
• Abstract
• 致谢
• 导师及作者简介