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

发布时间：2021-04-05 20:46

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

【文章来源】：中南大学湖南省 211工程院校 985工程院校 教育部直属院校

【文章页数】：57 页

【学位级别】：硕士

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


【参考文献】：
期刊论文
[1]从规划解中学习一阶派生谓词规则[J]. 饶东宁,蒋志华,姜云飞,刘强.  计算机学报. 2010(02)
[2]基于规划图的蚁群规划算法[J]. 柴啸龙,姜云飞,陈蔼祥.  计算机研究与发展. 2009(09)
[3]智能规划器StepByStep的研究和开发[J]. 吴向军,姜云飞,凌应标.  软件学报. 2008(09)



本文编号：3120076