All Questions
Tagged with heuristics a-star
14 questions
0
votes
1
answer
110
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$ ...
0
votes
0
answers
141
views
What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?
In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for ...
- 1
1
vote
0
answers
137
views
Is N the total number of nodes in the frontier plus the number of nodes in the explored list?
I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103):
One ...
- 111
0
votes
0
answers
327
views
Is possible to perform an early goal test with A* using a consistent heuristic?
I have a doubt about A* goal test.
As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
- 21
-1
votes
0
answers
59
views
Incorrect node expansion in game board with A* search
I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...
- 19
3
votes
1
answer
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
1
answer
2k
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
2
votes
0
answers
158
views
How does heuristic work with multiple agents?
I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
- 121
2
votes
1
answer
4k
views
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 $...
- 351
7
votes
1
answer
396
views
A* is similar to Dijkstra with reduced cost
According to this Wikipedia article
If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge),...
4
votes
3
answers
9k
views
What heuristic to use when doing A* search with multiple targets? [closed]
Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which ...
- 41
0
votes
1
answer
11k
views
How do you calculate the heuristic value in this specific case?
The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where
$g(n)$ = cost of the path from the start node to node $n$
$h(n)$ = estimated cost of the cheapest path from $n$ to the ...
- 371
13
votes
1
answer
31k
views
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 ...
- 303
6
votes
2
answers
3k
views
How does A* search work given there are multiple goal states?
When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.
These are the heuristic estimates:
...
- 163