Forward heuristic search planning based on ordered hill climbing algorithm

Liang Rui Shi; Jiang Yun Fei; Yang Hui Zhi

doi:10.3969/j.issn.1001-0548.2013.03.028

Forward heuristic search planning based on ordered hill climbing algorithm

Journal of the University of Electronic Science and Technology of China, 2013, 42(3): 464-468.

DOI: 10.3969/j.issn.1001-0548.2013.03.028

Basic Info

Comment

Summary

根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较.在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列.在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数.通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升.

Keywords

Adaptive functions; AI planning; Heuristic evaluation; Heuristic search; Heuristic search planning; Hill climbing algorithms; Local search algorithm; Relaxed planning graphs

Institution

University of Electronic Science and Technology of China; Sun Yat-sen University

Full-text Preview

Access