Optimize Planning Heuristics to Rank: Conditions on Strictly Optimally Efficient Heuristic

Table of Links

• Abstract & Introduction
• Preliminaries
• Conditions on strictly optimally efficient heuristic
• Loss functions
• Related Work
• Experiments
• Conclusion and References
• Appendix

3 Conditions on strictly optimally efficient heuristic

Notice that the heuristic values of states on the optimal path are never compared. This is because if the forward search expands only states on the optimal path, then its Open list always contains only one state from the optimal path. The definition anticipates the presence of multiple optimal solutions and even multiple goals, which requires the heuristic to break ties and have a perfect rank with respect to one of them.

Theorem 1. The forward search with a merit function f(s) = αg(s) + βh(s) and a heuristic h is strictly optimally efficient on a problem instance (hS, E, wi, s0, S ∗ ) if and only if h is a perfect ranking on it.

Proof. Sufficiency: If the conditions of a perfect ranking heuristic hold, then there exists an optimal path such that a state on it that is in the Open list always has the strictly lowest heuristic value. Therefore, forward search will never move off the optimal path and is, therefore, strictly optimally efficient.

Necessity: If h is a strictly optimally efficient heuristic, then the forward search always selects the state on the optimal path, which means that the state has the lowest heuristic value of all the states in the Open list, which is precisely the condition of a perfect ranking heuristic.

Theorem 1, despite being trivial, allows certifying that the forward search with a given heuristic in a given problem instance is strictly optimally efficient. This property has been discussed in [59] for Beam search, but the conditions stated there are different because Beam search prunes states in the Open list. Recall that the complexity class of computing a perfect ranking heuristic function is the same as solving the problem because one implies the other. We now remind the reader that the popular cost-to-goal does not always lead to a strictly optimally efficient forward search.

Example 1. While cost-to-goal h ∗ is the best possible heuristic for algorithms like A* (up to tiebreaking) in terms of nodes being expanded, for GBFS, h∗ does not necessarily yield optimal solutions.

See Figure 2 for a counterexample. The complete proof is in the Appendix. Appendix 8.4 also gives an example of a problem instance, where an optimally efficient heuristic for GBFS returning the optimal solution does not exist.