4
$\begingroup$

I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in mind the values, but the solution says it's not consistent either. Can someone tell why?

New contributor
Awa is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 1
    $\begingroup$ A consistent heuristic is always admissible, but an admissible heuristic does not have to be consistent. Someone may be able to give some examples for you in an answer. However, if you want to know why your heuristic is neither, you need to share details of the problem and your attempted solution $\endgroup$ – Neil Slater Nov 9 at 13:00
1
$\begingroup$

For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state.

For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state.

What this means is that, as you move along the sequence of nodes from start to goal that the heuristic recommends, a consistent heuristic should monotonically decrease in value. A consistent heuristic is thus also always admissible.

Notice that this means that if a heuristic is not admissible (like yours), it is also not consistent (by the contrapositive).

Therefore, if you already know your heuristic is not admissible, you should not be surprised that it is not consistent.

It seems most likely that you may have confused the definition of consistent for monotone. A consistent heuristic is both monotone and admissible.

As Neil Says, if you want to know why your specific heuristic is inadmissible, you should post another question about it, or modify this one.

$\endgroup$
0
$\begingroup$

If a heuristic is not admissible, can it be consistent?

No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent.

Definitions

Given a graph $G=(V, E)$ representing the search space, where $V$ and $E$ are respectively the set of vertices and edges, and the function $w: E \times E \rightarrow \mathbb{R}$ that defines the weight (or cost) of each edge of $G$, an admissible heuristic $h_{\text{a}}$ is defined as

$$h_{\text{a}}(n) \leq h^*(n), \forall n \in V$$

where $h^*(n)$ is the optimal cost to reach a goal from $n$ (so $h^*(n)$ is the optimal heuristic).

On the other hand, a consistent heuristic $h_{\text{c}}$ is defined as

\begin{align} h_{\text{c}}(n) &\leq w(n, s) + h_{\text{c}}(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\ h_{\text{c}}(g) &= 0, \forall g \in \mathcal{G}, \end{align} where $s$ is a successor of $n$, $g$ is any goal node and $\mathcal{G}$ is the set of goal nodes of the graph $G$.

Theorem

A consistent heuristic is an admissible heuristic.

Proof

Let $h$ be a consistent heuristic. Given that $h$ is consistent, then $h(g) = 0$, for any goal node $g$, so it does not overestimate the cost of reaching the goal at any of the goal nodes (given that, if you already are at a goal node, the cost is $0$, and $h(g) = 0$ is not greater than $0$). Let $g_{n}$ be an arbitrary neighbour of an arbitrary goal node $g$. Given that $h$ is consistent, then $h(g_{n}) \leq w(g_{n}, g) + h(g)$. Given that $h(g)$ does not overestimate the cost to reach the goal from $g$, then $w(g_{n}, g) + h(g)$ also does not overestimate the cost of reaching the goal from $g_n$, given that $w(g_{n}, g)$ is the true cost of the edge $(g_{n}, g) \in E$ and the cost to reach the goal from $g_n$ must be at least $w(g_{n}, g)$. This reasoning can be applied inductively (or recursively) on $g_n$ (then on the neighbouring nodes of $g_n$, and so on), so $h$ must be admissible.

$\endgroup$
  • $\begingroup$ A proof by induction usually requires you to prove 2 cases: 1) a base case (prove that a property holds for a base case of the statement) and 2) induction step (assume that a property holds for $n$ and prove it also holds for $n+1$ or $n-1$). This proof by induction does not have a proper induction step, but I hope it is intuitive enough. This is more like a recursive proof. $\endgroup$ – nbro Nov 10 at 16:10

Your Answer

Awa is a new contributor. Be nice, and check out our Code of Conduct.

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.