智能规划方法中启发式搜索策略的研究

论文摘要

基于启发式搜索的规划方法是当前智能规划研究的热点，本文针对搜索算法和剪枝策略这两个影响规划求解效率的关键因素进行了深入研究，为经典规划问题和不确定规划问题设计了更灵活的启发式搜索算法和剪枝策略，具体内容如下：（1）提出一种利用路标信息隐式分解前向搜索过程的规划方法，根据路标计数启发式的估值将规划任务分解成多个规模更小的子任务，搜索过程在路标计数启发式的引导下快速向目标方向推进，实现搜索空间的大规模压缩。（2）提出基于缩减信念状态的Conformant规划方法，搜索规划解之前先将初始信念状态转换为不确定性更低的状态，再搜索给定问题的目标。降低信念状态不确定性的方法能够减小问题的求解难度，改善规划系统的求解效率。（3）提出一种Conformant规划下利用有利动作构造新型剪枝策略的方法，根据放松规划解的计算过程给出有利蕴含路径的概念，扩展信念状态时优先应用有利蕴含路径，对搜索空间的探索速度更快。（4）提出Contingent规划下带有强制观察的剪枝策略，通过修改放松规划图的构造过程使得有利动作集合能够提取出观察当前不确定信息的动作，根据观察结果执行不同的求解动作，符合分支规划解的执行语义。

论文目录

• 提要
• 摘要
• Abstract
• 第1章 绪论
• 1.1 智能规划简介
• 1.1.1 智能规划的分类
• 1.1.2 规划问题的描述
• 1.2 规划求解方法
• 1.2.1 图规划方法
• 1.2.2 基于命题可满足性的规划方法
• 1.2.3 基于启发式搜索的规划方法
• 1.3 常用的启发式搜索算法
• 1.4 启发函数的设计
• 1.4.1 和/最大代价启发函数
• 1.4.2 放松规划解启发函数
• 1.4.3 因果图启发函数
• 1.4.4 路标计数启发函数
• 1.5 智能规划研究现状
• 1.6 本文研究工作
• 1.6.1 研究意义
• 1.6.2 具体工作内容
• 第2章 路标计数启发式引导的分解规划方法
• 2.1 相关概念
• 2.1.1 经典规划问题
• 2.1.2 多启发式搜索
• 2.1.3 Anytime搜索
• 2.2 基于路标隐式分解的前向搜索算法
• 2.2.1 路标分解规划任务的基本思想
• 2.2.2 路标计数启发式引导的增强爬山算法
• 2.3 实验测试与分析
• 2.3.1 动作带有执行代价的测试域
• 2.3.2 动作不带有执行代价的测试域
• 2.4 小结
• 第3章 基于缩减信念状态的CONFORMANT规划方法
• 3.1 CONFORMANT规划的相关概念
• 3.1.1 Conformant规划问题
• 3.1.2 隐式信念状态表示
• 3.1.3 Conformant-FF规划系统的基本结构
• 3.2 缩减信念状态的增强爬山算法
• 3.3 CFF-LITE规划系统
• 3.3.1 系统基本结构
• 3.3.2 规划算法的求解过程
• 3.4 实验测试与结果分析
• 3.5 小结
• 第4章 一种新的CONFORMANT规划剪枝策略
• 4.1 CONFORMANT-FF的启发式评估过程
• 4.1.1 Conformant放松规划问题
• 4.1.2 计算放松规划解
• 4.2 蕴含路径剪枝策略
• 4.2.1 蕴含路径的含义
• 4.2.2 构造有利蕴含路径
• 4.3 实验测试与分析
• 4.4 小结
• 第5章 CONTINGENT规划下强制观察剪枝策略
• 5.1 部分可观察规划问题
• 5.2 CONTINGENT-FF的启发式评估过程
• 5.3 强制观察剪枝策略
• 5.3.1 修改放松规划图的构造过程
• 5.3.2 强制提取观察动作
• 5.4 实验测试与分析
• 5.5 小结
• 第6章 总结与展望
• 参考文献
• 作者简介及在学期间所取得的科研成果
• 致谢