# Tag Info

## Hot answers tagged admissible-heuristic

12

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A ...

5

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 ...

4

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 $... 2 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, ... 2 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 ... 2 In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as $$f(n)=g(n)+h(n)$$ where$g(n)$is the length (or cost) of the cheapest path from the start node to the current node$n$and$h(n)$is the heuristic function that estimates the cost of the ... 2 The key phrase here is because heuristics are admissible In other words, the heuristics never overestimate the path length: $$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$ And since the frontier is ordered by$\textbf{cost + heuristic}$, when a completed path$p$is dequeued from the frontier, we know that it must necessarily be$\...

2

Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $h_{\max}(n)$ and $h_{\min}(n)$ are, by definition (of $h_{\max}$ and $h_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes $n$, ...

2

Welcome to AI.SE @hpr16! Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given state to a goal state. Notice that states in the search are not the same as positions on the circle in your problem. A state needs to capture all the ...

1

You can easily find a counterexample. Suppose that there are three nodes $s$, $p$, and $goal$ such that $s \rightarrow p \rightarrow goal$. The real cost of going from $s$ to $p$ is $c(s,p) = 10$ and $c(p, goal) = 10$. Also, $h_1(s) = 18$, $h_1(p) = 9$, $h_1(goal) = 0$, $h_2(s) = 17$, $h_2(p) = 1$.On the other hand, $h^*(s) = 19$ and $h^*(p) = 10$. Now, $... 1 The sketch of the proof for your first question: for an open node$n$, if$f_1(n) = g(n) + h_1(n)$, in the same situation in using$h_2$, it will be$f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time for any node$n$,$f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function$h_1$will be admissible (from Theorem 2 of ... 1 It depends on what you mean by optimal. A* will always find the optimal solution (that is, the algorithm is admissible) as long as the heuristic is admissible. (Note that the definition of admissible is overloaded and means something slightly different for an algorithm and a heuristic.) If you talk about the set of nodes expanded by A*, then it expands the ... 1 The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the way to the goal. Thus, your heuristic for each car should be Manhattan distance divided by 2. That's guaranteed to be admissible when you take the max. If you ... 1 I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a$3 \times 3\$ board of (numbered) squares as follows. +---+---+---+ | 0 | 1 | 2 | +---+---+---+ | 7 | 8 | 3 | +---+---+---+ | 6 | 5 | 4 | +---+---+---+ The numbers in these squares are just used to refer to the ...

Only top voted, non community-wiki answers of a minimum length are eligible