6
$\begingroup$

I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am wondering this because I had to prove if each heuristic is admissible and I did that, and then for each admissible heuristic, we have to prove if each one dominates the other or not. I think I have a case that neither dominates the other and I was wondering if maybe I got the admissibility wrong because of that.

$\endgroup$
4
$\begingroup$

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another and vice-versa. Think of it as a game of rock paper scissors.

Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $h_1$ and $h_2$ are admissible heuristics. Thus, by definition, neither strictly dominates the other.

In fact, there is a way to "combine" the two admissible heuristics to get the best of both using:

$$h_3 = \max(h_1, h_2)$$

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ I would like to note that $\max(h_1, h_2)$ gives you the best of both $h_1$ and $h_2$, if $h_1$ and $h_2$ are admissible: the idea is that, by taking the maximum of both, they are closer to the optimal heuristic. You hadn't explicitly stated that $h_1$ and $h_2$ are admissible. I edited your answer to add this detail. $\endgroup$ – nbro Nov 11 '19 at 15:46

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.