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.