5
votes
Is the summation of consistent heuristic functions also consistent?
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 ...
- 371
2
votes
If an heuristic is not admissible, can it be consistent?
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 ...
- 39.1k
2
votes
If an heuristic is not admissible, can it be consistent?
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 ...
- 9,147
2
votes
Accepted
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
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_{\...
- 39.1k
2
votes
How do I find whether this heuristic is or not admissible and consistent?
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 ...
- 9,147
2
votes
Is A* with an admissible but inconsistent heuristic optimal?
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 ...
- 371
2
votes
Accepted
What does a consistent heuristic become if an edge is removed in A*?
Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go ...
- 9,147
1
vote
Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?
TL;DR: All A* requires to find the optimal path is an admissible heuristic
I'll read that section of the book for more clarity and extend this answer; though, I believe the way to interpret that ...
- 1,096
1
vote
Is $\min(h_1(s),\ h_2(s))$ consistent?
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 $...
- 1,731
1
vote
If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
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 ...
- 371
Only top scored, non community-wiki answers of a minimum length are eligible