Hot answers tagged

16

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 policy or, more precisely, value function (from which the policy can be derived) by taking stochastic moves (or actions) with some policy (which is different ...


12

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 function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in ...


11

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 definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A ...


8

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 a heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$ in the search space (often represented as a graph). ...


6

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) = g(n) + h(n)$, where $g(n)$ means the same thing as in UCS and $h(n)$, called the "heuristic" function, is an estimate of the distance from $n$ to the goal ...


5

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.


3

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 uniform-cost search (UCS) is $f(n) = g(n)$, where $g(n)$ represents the cost of the path from the start node to $n$. The evaluation function of A* is $f(n) = g(n)...


3

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 compute $g(n)$, you simply do $g(n) = g(p) + c(p, n)$, where $p$ is the parent node, and $c(p, n)$ is the $c$ost of the edge between $p$ and $n$. So, yes, to compute $...


2

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 roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search. To do this, you can't just change your heuristic, instead you ...


2

The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y coordinates for all the nodes in your graph, that would be extremely easy to compute. The straight-line distance also fits the requirements of an admissible heuristic, in that it will never overestimate the distance. The travel-...


2

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 search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using ...


2

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). The exterior vertices of the configuration space can then be used as input to a path-planning algorithm, such as A*.


2

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)$ is the length (or cost) of the cheapest path from the start node to the current node $n$ and $h(n)$ is the heuristic function that estimates the cost of the ...


2

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 since the frontier is ordered by $\textbf{cost + heuristic}$, when a completed path $p$ is dequeued from the frontier, we know that it must necessarily be $\...


2

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, A* (which is equivalent to UCS) behaves like BFS (except for the goal test: see section 3.4.2 of this book), i.e. it will first expand nodes at level $l$, then ...


2

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 during one iteration of A* (i.e. decide which node to take from the frontier, determine the next possible actions and which next nodes those actions lead to, and ...


2

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 from $A \rightarrow B$, plus our guess of the time to go from $B \rightarrow C$. Supposing we remove a given edge $c(n,m)$ from our graph, but that our ...


1

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 for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of ...


1

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 heuristic function are for it to be admissible and consistent. If the latter stands, I can't think of any case where BFS would outperform A*. However, this ...


1

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 is overloaded and means something slightly different for an algorithm and a heuristic.) If you talk about the set of nodes expanded by A*, then it expands the ...


1

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 the goal So, using this recalculation of the original edge-values ($1.$) in Dijkstra's algorithm you are inherently accounting for the heuristic component of ...


1

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

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 should give you an overview of where you can make improvements. Speculative changes usually don't do much. There are several aspects of A* which would be ...


1

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 information about the distance from any node to the goal node. The heuristic function can e.g. be the Euclidean distance (in the case this can be defined). ...


1

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 the goal. In that case, the A* algorithm is way better than the greedy search algorithm.


1

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 see that this is wrong, because A* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never ...


Only top voted, non community-wiki answers of a minimum length are eligible