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.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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)$$
-
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. $\endgroup$– nbroCommented Nov 11, 2019 at 15:46