For questions related to admissible heuristics, which are heuristics that never overestimate the cost of reaching a goal.

18 questions
Filter by
Sorted by
Tagged with
1 vote
22 views

### Doesn't an admissible heuristic ensure optimality in the graph-search version of A*?

I'm reading a text book "Artificial Intelligence - A Modern Approach (3rd Edition)". In page 95, the book mentions that "A* has the following properties: the tree-search version of A* ...
• 11
96 views

### How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?

I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof. The proof is by induction on $k$, the number of actions from a node $n$ ...
259 views

### How to determine that an heuristic is admissible

An heuristic is admissible if never overestimates the real cost to reach the goal. In order to prove that an heuristic $h$ is admissible we need to prove that for every state $s$ in the state space we ...
559 views

### Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?

The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says "With an admissible heuristic, A* is cost-optimal...". An admissible heuristic is one ...
• 1
203 views

### Is $\min(h_1(s),\ h_2(s))$ consistent?

If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
• 21
379 views

### If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible. Why are the following statements true? $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
• 21
3k views

### Is A* with an admissible but inconsistent heuristic optimal?

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows: Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
• 161
1 vote
1k views

### Which heuristics guarantee the optimality of A*?

The following is a statement and I am trying to figure out if it's true or false and why. Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
• 25
1k views

### If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?

Consider the following question: $n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of an $n \times n$ grid. The vehicles must be moved to the top row but in reverse order; ...
2k views

### Is the summation of consistent heuristic functions also consistent?

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 ...
9k views

### If an heuristic is not admissible, can it be consistent?

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 ...
• 41
1k views

### Can two admissable heuristics not dominate each other?

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 ...
• 163
2k views

### How do we determine whether a heuristic function is better than another?

I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions. Currently, I explored the Manhattan and Euclidean ...
• 333