3
$\begingroup$

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?

Is there any proof or counterexample to show the contradiction?

$\endgroup$
5
$\begingroup$

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.

s --1-- g

Assume that $h_0$ and $h_1$ are perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an undirected graph the heuristic will be inconsistent because $|h(s)-h(g)| > d(s, g)$.

If you'd like to understand the conditions for the sum of heuristics to be consistent and admissible, I would look at the work on additive PDB heuristics.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Would you please give an example and update your post? $\endgroup$ – Mostafa Ghadimi Feb 28 at 16:34
  • $\begingroup$ @MostafaGhadimi In my answer I described an example with two states, the goal state and a second state distance one from the goal. Is there something particular you are looking for more than this? $\endgroup$ – Nathan S. Feb 28 at 16:37
  • $\begingroup$ I didn't get what you mean by this example. $\endgroup$ – Mostafa Ghadimi Feb 28 at 16:38
  • $\begingroup$ I will add a simple drawing of this example. $\endgroup$ – Nathan S. Feb 28 at 16:39
  • 2
    $\begingroup$ For a more extreme version of this answer, consider taking a single admissible, consistent heuristic, and then adding up an infinite number of copies of them. For any base heuristic value $> 0$, this sum is going to end up being $\infty$, which is generally not admissible. $\endgroup$ – Dennis Soemers Feb 28 at 16: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.