Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [admissible-heuristic]

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

19 questions
14
votes
1 answer

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its successor, $n'$, plus the successor's heuristic…
Wizard
  • 313
  • 1
  • 2
  • 6
7
votes
1 answer

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 distances. Which other heuristic functions are…
m2rik
  • 333
  • 1
  • 9
6
votes
1 answer

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 wondering this because I had to prove if each…
JRowan
  • 163
  • 5
4
votes
2 answers

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 mind the values, but the solution says it's not…
Awa
  • 41
  • 1
  • 2
4
votes
1 answer

Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}. If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) is also admissible? If all heuristics in $H$ are…
ihavenoidea
  • 265
  • 2
  • 11
4
votes
1 answer

How do I find whether this heuristic is or not admissible and consistent?

I was given the following problem to solve. Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge between segments $n-1$ and $0$) and the agent's speed…
hpr16
  • 41
  • 2
3
votes
1 answer

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$ and $q$ to the goal. Assume $P
Harry Stuart
  • 161
  • 1
  • 3
3
votes
1 answer

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 or counterexample to show the contradiction?
Mostafa Ghadimi
  • 177
  • 12
2
votes
1 answer

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 have $h(s)\le h^*(s)$, where $h^*(s)$ is the…
Jose Manuel
  • 21
  • 1
2
votes
1 answer

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?
hello
  • 21
  • 1
2
votes
1 answer

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 long as the optimal path. $h_2(n) + 1$ is…
Jia Rong
  • 21
  • 2
2
votes
1 answer

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; so the vehicle $i$ that starts in $(i, 1)$ must…
Mostafa Ghadimi
  • 177
  • 12
2
votes
1 answer

Understanding the proof that A* search is optimal

I don't understand the proof that $A^*$ is optimal. The proof is by contradiction: Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $p''$ (Which is part of the path $p'$) is chosen from…
Gooby
  • 351
  • 3
  • 12
2
votes
1 answer

Why isn't Nilsson's Sequence Score an admissible heuristic function?

I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson's sequence score heuristic function isn't admissible.
Jay Critch
  • 343
  • 1
  • 7
1
vote
0 answers

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* is optimal if h(n) is admissible, while the graph-search version…
gotgolp
  • 11
  • 1
1
2