2
$\begingroup$

Let's say $h_1(n) \geq h_2(n)$ so that dominance is established even if $h_1$ and $h_2$ are both inadmissible/non-optimal heuristics -in whichever given search space.

Is $h_1$ still faster/better than $h_2$ or does the dominance rule only apply to admissible heuristics?

Also, if I could ask for a bit of extra help, can you provide a link/reference to an academic material that establish this relationship between dominanation and inadmissibility? Thank you!

$\endgroup$
  • $\begingroup$ Are you talking about $A^*$ algorithm? What is your purpose to discuss domination outside of admissible heuristics? Is it for approximation of optimal result? $\endgroup$ – Apass.Jack Nov 22 '18 at 5:41
  • $\begingroup$ Yes, and it's for performance. All node expansion and not optimal result. $\endgroup$ – Charlie Baker Nov 22 '18 at 6:09
  • $\begingroup$ The question actually makes sense in spite of the search algorithm being used ... It does not necessarily apply to a specific one such as A$^*$ $\endgroup$ – Carlos Linares López Nov 23 '18 at 9:44
1
$\begingroup$

First things first. In your question you put together two different concepts, namely admissibility and optimality of heuristic functions:

  • Optimality: A heuristic function $h(n)$ is optimal if and only if $h(n)=h^*(n)$ for every state $n$ of your state space, i.e., it returns the cost of an optimal path from $n$ to the goal.
  • Admissibility: A heuristic function $h(n)$ is said to be admissible if and only if $h(n)\leq h^*(n)$, i.e., it never overestimates the effort to reach the goal.

Clearly, optimality is a stronger property than admissibility. Also their impoortance comes from different factors:

  • Optimality: It can be proven (under a rather restricted model) that a specific class of search algorithms (such A$^*$, IDA$^*$, RBFS, DFBnB, etc.) only expand nodes along an optimal path when a perfect heuristic is used.
  • Admissibility: It can be proven (under a very general model) that a specific class of search algorithms (as those aforementioned) will return optimal solutions when using an admissible heuristic functions.

This said, dominance is an orthogonal property to these as it does refer neither to the accuracy of heuristic functions nor their ability to return optimal solutions. Your definition is correct:

  • Dominance: $h_1(n)$ is said to dominate $h_2(n)$ if and only if $h_1(n) \geq h_2(n)$ for all states $n$ in your state space. Note that this is a strong definition as it should be fulfilled for all states. In general it is said that $h_1(n)$ is more informed than $h_2(n)$.

And its importance is relative to the performance of the search algorithm when using one heuristic function or another:

  • Dominance: It can be proven (again under a rather restricted model) that a search algorithm (from the class of search algorithms mentioned above which are known as admissible search algorithms) expands less nodes when using a more informed heuristic function $h_1(n)$.

There is a lot to say here. First, that this property refers only to the must-expand nodes, that tie-breaking is assumed to be applied in the same way when using one heuristic or another, etc. There is no need to go in much deep detail to note however that this property makes a lot of sense when $h_1(n)$ and $h_2(n)$ are both admissible -optimality, as you say is disregarded here. If you put all conditions together you'll note that: $h_2(n) \leq h_1(n) \leq h^*(n)$ so that $h_1(n)$ provides better estimates for all nodes $n$ in the state space, i.e., the values returned by $h_1(n)$ are closer to the cost of the optimal path. This argument lies at the core of the proof of the effectiveness of $h_1(n)$ when being compared to $h_2(n)$.

Now, if neither $h_1(n)$ nor $h_2(n)$ are admisible, then:

  • Weak inadmissibility: $h_1(n)$ and $h_2(n)$ are inadmissible but they might return admissible estimates for some nodes. In this case, nothing can be said about the relative performance of these heuristics. It can be proven, however, that there is no guarantee about the optimality of the solutions returned by any of the search algorithms mentioned above.

  • Strong inadmissibility $h_1(n)$ and $h_2(n)$ always return inadmissible estimates, i.e., $h_1(n), h_2(n) \geq h^*(n)$ for all states $n$. If $h_1(n)\geq h_2(n)$ then $h_1(n) \geq h_2(n)\geq h^*(n)$ so that the opposite observation applies now and $h_2(n)$ returns estimates which are closer to the cost of the optimal solution. This does not imply that $h_2(n)$ will serve to expand less nodes but in general one should expect better solutions to be obtained with $h_2(n)$.

Concluding, domination is an orthogonal property to admissibility. They, when being put together serve to make observations about the optimality of the solutions returned and the expected number of necessary expansions to find them, but they can be used in different contexts as well.

As for extra material, I do highly recommend you a couple of books:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.