学位论文 > 优秀研究生学位论文题录展示

智能规划的一种逻辑化描述

作　者: 孙楠
导　师: 蔡自兴
学　校: 中南大学
专　业: 计算机科学与技术
关键词: 智能规划计算复杂性描述复杂性逻辑 PDDL 知识工程
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

摘要：经典智能规划问题是人工智能研究领域里最为重要的问题之一。但是由于其时间复杂度上的不可跟踪性,使得这项技术在实际应用中的范围十分受限,所以一直以来,与智能规划有关的计算复杂性问题备受关注。本文试图从形式描述的角度探究智能规划的计算复杂性。本文提出一种全新的方法：使用形式逻辑语言来描述经典智能规划问题,并提供相应的算法来将这种描述“解释”为传统的基于动作的规划问题描述。在本文的算法之前,还没有能够完全实现该功能的方法,达到使任何一种泛化描述的PSPACE类问题转化为基于动作的智能规划问题。该方法是基于二阶传递闭包逻辑(SO(TC))的。首先,本文提出一种SO(TC)的范式,并证明其完全性,根据这个证明,可以容易的得到一种可以针对SO(TC)范围内的任何表达式的规范化方法。在此基础上,提出一个算法,可以直接将这种范式“解释”成一个PDDL语言描述的智能规划问题,于是就得到了一个完整的算法。生成结果编码使用PDDL这种功能丰富的语言。本问提出的这个方法,价值可以体现在两个方面：一方面,这个算法使得使用智能规划求解器来求解逻辑化描述的模型检测问题成为可能。这种逻辑描述,既可以来自手工编制的代码,也可以由其它形式描述转化而来；另一方面,本文提出的这种二阶逻辑的传递闭包范式,可以看成是一种紧凑的,统一的智能规划问题描述,本文认为这种描述方法可以促进智能规划理论的进一步研究。该算法由两个主要过程连接组成。本文使用C++编程语言实现了这个算法,该程序能够生成标准的PDDL代码,可以直接作为智能规划求解器的输入数据,进行求解。最后,我们证明本算法的一条重要性质,能够保证在转化的过程中不扩大NP的复杂度。

全文目录

摘要  4-5
Abstract  5-6
目录  6-8
1 绪论  8-13
  1.1 研究意义  8-9
  1.2 相关研究工作  9-11
  1.3 本文提出的基于传递闭包逻辑的描述方法  11-12
  1.4 本文的主要内容和组织  12-13
2 智能规划理论及相关技术  13-24
  2.1 智能规划模型  13-15
  2.2 智能规划的计算复杂性分析  15-20
    2.2.1 与之相关的计算复杂性理论基础  15-18
    2.2.2 智能规划的复杂性结论  18-20
  2.3 智能规划问题的建模语言  20-22
    2.3.1 STRIPS描述方法  20
    2.3.2 PDDL语言及其主要版本  20-22
  2.4 本章小结  22-24
3 描述复杂性理论及其与智能规划的联系  24-32
  3.1 描述复杂性理论  24-30
    3.1.1 一阶和二阶谓词逻辑  24-26
    3.1.2 传递闭包逻辑  26-27
    3.1.3 逻辑推论  27-28
    3.1.4 描述复杂性理论及其重要结论  28-30
  3.2 智能规划的描述复杂性分析  30-31
  3.3 本章小结  31-32
4 智能规划的逻辑化描述及相关算法  32-44
  4.1 传递闭包逻辑表达式的规范形式  32-36
    4.1.1 一阶传递闭包逻辑的范式和规范化方法  32-33
    4.1.2 二阶传递闭包逻辑的范式的提出  33-36
  4.2 从规范化形式到PDDL语言描述  36-41
    4.2.1 域定义(Domain)  37-38
    4.2.2 基动作翻译(Action)  38-40
    4.2.3 问题实例生成(Problem Instance)  40-41
  4.3 实验实现及其结果  41-43
  4.4 本章小结  43-44
5 论性质方面的结论  44-49
  5.1 可靠性和完全性  44-45
  5.2 复杂性  45-46
  5.3 转化过程对NP的复杂度保持  46-47
  5.4 本章小结  47-49
6 总结与展望  49-50
参考文献  50-53
附录：部分实验结果  53-56
攻读学位期间主要的研究成果  56-57
致谢  57

智能规划的一种逻辑化描述

内容摘要

全文目录

相似论文