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

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

Forward Heuristic Search Planning Based on Ordered Hill Climbing Algorithm

According to the relationship between relaxed planning graph and helpful actions in forward heuristic search planner FF, the notion of state adaptive function is defined, which is used to fast compare heuristic evaluations for expanded successor states approximately. Integrating with greedy selection mechanism in enforced hill climbing search, we propose an improved local search algorithm named ordered hill climbing search algorithm based on state adaptive function. The core idea of our algorithm is to order all expanded successor states according to their state adaptive functions, and then insert them into an expanded priority queen. In heuristic evaluation stage, a state with higher adaptive value will be computed earlier, as a result, better state can be found earlier and the frequency of calling heuristic evaluation procedure will be cut down. Experiments in Depots and FreeCell domains of IPC show that the proposed algorithm reduces search nodes and search time significantly and therefore improves the search efficiency effectively.