16
votes
Accepted
What are the differences between Q-Learning and A*?
Q-learning and A* can both be viewed as search algorithms, but, apart from that, they are not very similar.
Q-learning is a reinforcement learning algorithm, i.e. an algorithm that attempts to find a ...
- 37.1k
13
votes
Accepted
Why is A* optimal if the heuristic function is admissible?
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 ...
- 9,037
11
votes
Accepted
How is iterative deepening A* better than A*?
A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic ...
- 37.1k
11
votes
Accepted
What are the differences between A* and greedy best-first search?
Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that can use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and ...
- 37.1k
7
votes
Accepted
How do I show that uniform-cost search is a special case of A*?
Yes, UCS is a special case of A*.
UCS uses the evaluation function $f(n) = g(n)$, where $g(n)$ is the length of the path from the starting node to $n$, whereas A* uses the evaluation function $f(n) =...
- 37.1k
5
votes
How does A* search work given there are multiple goal states?
Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
- 7,176
3
votes
Accepted
A* and uniform-cost search are apparently incomplete
You forgot to calculate and take into account the costs of the actual paths. You forgot to accumulate the cost of the edges for going forward and backward multiple times!
The evaluation function of ...
- 37.1k
3
votes
How do we determine whether a heuristic function is better than another?
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)$ ...
- 37.1k
3
votes
How is the cost of the path to each node computed in A*?
The evaluation function in A* is $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the starting node to $n$ and $h(n)$ is an estimate of the distance from $n$ to the goal node. To ...
- 37.1k
3
votes
What is a good heuristic function for A* to solve the "blocks world" game?
You may start assigning penalties for undesirable conditions in a state like:
1) Number of blocks outside stack 0.
Supose you penalize with 10 units each block outside stack 0, then the starting ...
- 176
2
votes
What heuristic to use when doing A* search with multiple targets?
If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is ...
- 9,037
2
votes
Accepted
How do you calculate the heuristic value in this specific case?
The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y...
- 9,804
2
votes
What are the differences between A* and greedy best-first search?
According to the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart Russel and Peter Norvig, specifically, section 3.5.1 Greedy best-first search (p. 92)
Greedy best-first ...
2
votes
Accepted
How can I calculate the shortest path between two 2d vector points in an environment with obstacles?
The usual way to solve this kind of problem is to construct a configuration space: extruding all the polygonal obstacles by sliding the polygon corresponding to the robot around them (some slides).
...
- 7,176
2
votes
Understanding the proof that A* search is optimal
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 ...
2
votes
Is there any situation in which breadth-first search is preferable over A*?
The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, ...
- 37.1k
2
votes
Accepted
What is the difference between the heuristic function and the evaluation function in A*?
What is the difference between the heuristic function and the evaluation function in A*?
The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand ...
- 37.1k
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,037
2
votes
Is there an error in A* optimality proof Russel-Norvig 4th edition?
You did not compute $g(n)$ correctly.
A* expands according to the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the start node to $n$. Initially, you add $A$ to ...
- 37.1k
1
vote
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?
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 ...
- 1,723
1
vote
Is there any situation in which breadth-first search is preferable over A*?
There is an inherent assumption in heuristic search that the heuristic function points you in the right direction.
A* largely depends on how good the heuristic function is. Two nice properties for the ...
- 3,143
1
vote
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 ...
- 361
1
vote
A* is similar to Dijkstra with reduced cost
What you are doing when calculating $d'(x,y)$:
$d(x,y)$: calculating the original edge distance from $x$ to $y$
$h(y)$: plus the heuristic from $y$ to the goal
$h(x)$: minus the heuristic from $x$ to ...
- 901
1
vote
Accepted
How can the A* algorithm be optimized?
Check below reference url for A* algorithms ...
https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/
https://en.wikipedia.org/wiki/Heap_%28data_structure%29
1
vote
How can the A* algorithm be optimized?
The first step of optimisation is to measure where inside the implementation most time is spent -- you don't actually optimise the algorithm itself, but a specific implementation of it. This step ...
- 5,252
1
vote
What kind of search method is A*?
A* is an informed search algorithm. A* informed because it is based on the use of a heuristic function, which estimates the distance of each node to the goal, that is, the heuristic function provides ...
- 37.1k
1
vote
What are the differences between A* and greedy best-first search?
What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching ...
- 11
1
vote
Accepted
How does A* search work given there are multiple goal states?
Question 1: First of all, you state that that the goal G2 will be found first by relying on the expansion order R, B, D, G2.
This is wrong. It is extremely easy to ...
- 200
Only top scored, non community-wiki answers of a minimum length are eligible