On the importance of breaking ties in the relaxed plan heuristic
The relaxed plan heuristic is a domain-independent heuristic for automated planning that computes an estimate of the cost for achieving the goals from a given state. This heuristic is based on the idea of solving a relaxed version of the planning task. Due to the great size of the state space, most heuristic search algorithms in planning suffer from scalability problems. These algorithms have to evaluate a great amount of states, and the time devoted to heuristic evaluations is one of the causes of the scalability problems. We argue that one way to lighten this problem is breaking ties in the heuristic value using additional information computed during the relaxed plan construction. We add a complementary value to the heuristic, allowing algorithms to discriminate between states with relaxed plans of the same length but with a different difficulty. The experimental evaluation in some planning benchmarks shows that the modification to the original heuristic can reduce the number of evaluated nodes for the most common algorithms used in heuristic planning.
automated planning heuristic search