基于有序爬山法的前向启发式搜索规划

摘要：

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

关键词：智能规划、启发式搜索、有序爬山法、状态适应度函数

所属期刊栏目：42

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60773201,60970042;广东省自然科学基金S2012040011123

在线出版日期：2013-10-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：464-468