基于有序爬山法的前向启发式搜索规划 |
| |
引用本文: | 梁瑞仕,姜云飞,杨会志.基于有序爬山法的前向启发式搜索规划[J].电子科技大学学报(社会科学版),2013(3):145-149. |
| |
作者姓名: | 梁瑞仕 姜云飞 杨会志 |
| |
作者单位: | 电子科技大学中山学院计算机学院;中山大学信息科学与技术学院 |
| |
基金项目: | 国家自然科学基金(60773201,60970042);广东省自然科学基金(S2012040011123);中山市科技计划项目(20123A314,20123A327,411S16)的资助 |
| |
摘 要: | 根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列。在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升。
|
关 键 词: | 智能规划 启发式搜索 有序爬山法 状态适应度函数 |
本文献已被 CNKI 等数据库收录! |
|