基于节点多样性和动态参考阈值的智能规划方法研究

摘要

在人工智能领域，智能规划作为一个多领域交叉的学科，逐渐成为了人们研究的热点。智能规划在人际互动、知识及逻辑推理、游戏设定、航天航空、智能机器人等领域得到应用，备受人们关注。近年来具有代表性的启发式规划系统有:FF、Fast-Downward、LAMA等。LAMA规划系统是一个很重要的规划系统，在智能规划发展史上具有重大意义，它采用路标作为伪启发式函数，充分地挖掘了启发式信息，提高了规划系统的性能。
　　 启发式搜索在智能规划中表现出良好的性能。最优优先算法GBFS(greedybest-first search)是LAMA规划系统中非常重要的算法，它提高了搜索的效率和质量。但是GBFS算法本身还存在一定的不足，由于算法本身具有的贪婪性，启发式搜索容易陷入局部最优状态。针对这一问题，本文提出了一种基于增加节点多样性和动态参考阈值的方法IBFS(improved best-first search)，在一定程度上克服了GBFS算法不足。
　　 首先，在GBFS算法中，搜索总是在当前状态下选取启发值最小的状态节点来扩展，这样选择的状态节点并不一定是全局最优，易使搜索陷入了局部最优，搜索大量无用的节点，而且搜索不会从当前的状态中跳出，以至搜索得到的规划解并不是全局最优规划解。本文利用路标启发函数增加节点选择的多样性，在当前评估的状态中选择多个状态节点，增加了节点的评估个数，减少了搜索算法陷入局部最优状态的概率，有效地提高规划的性能，使搜索有更大的机会得到全局最优规划解。其次，本文算法为了更好地克服局部最优状态，采用了一种动态参考阈值的方法来进一步提高算法的性能。动态参考阈值的算法是经过调整优先队列，通过随机方式得到一个参考阈值，利用这个参考阈值来重新构建新的优先队列，然后在这个新的优先队列中去寻找一个要扩展的目标节点。通过这种方式，可以使搜索在全局状态中去选取，增加节点跳出局部最优状态的概率，使规划解的质量更好。
　　 在Linux平台下，我们采用C++语言对本文的改进算法IBFS进行了实现，并将其应用在LAMA规划系统中进行搜索实验，通过对国际规划大赛IPC-6标准领域下问题的实验，结果表明新改进的算法IBFS提高了规划解的质量，减小了状态空间的开销。

目录

声明

摘要

第一章 绪论

1．1 智能规划简介

1．2 智能规划的主要思想

1．3 智能规划研究现状及应用

1．3．1 各届智能规划大赛

1．3．2 智能规划应用

1．4 论文的组织结构

第二章 相关理论和基础

2．1 STRIPS类型规划

2．2 规划图和图规划方法

2．2．1 规划图

2．2．2 图规划方法

2．3 启发式搜索

2．3．1 一般搜索方法

2．3．2 启发式搜索方法

2．3．3 启发式搜索流程

2．4 LAMA规划系统

2．4．1 有限域状态变量

2．4．2 域转化图

2．4．3 路标

2．4．4 可纳性

2．5 本章小结

第三章 基于节点多样性和动态参考阈值的最优优先算法

3．1 引言

3．2 GBFS算法

3．3 基于增加优先队列和节点多样性

3．3．1 利用路标启发函数增加节点多样性

3．3．2 增加节点的优先队列

3．3．3 增加优先队列和节点多样性算法

3．3．4 动态调整队列优先级和使用延迟评估

3．4 动态选取参考阈值

3．4．1 动态选取参考阈值

3．4．2 IBFS算法及流程图

3．5 搜索引擎

3．5．1 翻译部分

3．5．2 知识提取

3．5．3 搜索部分

3．6 本章小结

第四章 实验结果及分析

4．1 实验环境

4．2 规划步骤

4．3 实验分析

4．4 本章小结

第五章 总结及未来工作

5．1 结论

5．2 未来的工作

致谢

攻读硕士学位期间从事的科研工作及发表的论文

参考文献