[go: up one dir, main page]
Scribd
Upload
18 views3 pages

A Search 3 Recap of A

A* search evaluates states using a function f(s) which estimates the cost from the start to the goal state passing through s. It uses g(s) as the actual cost from start to s and h(s) as a heuristic estimate of the remaining cost from s to the goal. There are three types of states: unseen, done/closed where all neighbors are explored, and open/frontier which are seen but neighbors need exploring. The algorithm can find non-optimal solutions if it does not properly update cost estimates for states in the done/closed set when shorter paths are found later. To fix this, states must be returned to the open set when their costs are updated. The algorithm works correctly when the heuristic

Uploaded by

JosephKuo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views3 pages

A Search 3 Recap of A

A* search evaluates states using a function f(s) which estimates the cost from the start to the goal state passing through s. It uses g(s) as the actual cost from start to s and h(s) as a heuristic estimate of the remaining cost from s to the goal. There are three types of states: unseen, done/closed where all neighbors are explored, and open/frontier which are seen but neighbors need exploring. The algorithm can find non-optimal solutions if it does not properly update cost estimates for states in the done/closed set when shorter paths are found later. To fix this, states must be returned to the open set when their costs are updated. The algorithm works correctly when the heuristic

Uploaded by

JosephKuo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

9/17/2020 CS440 Lectures

CS 440/ECE 448
Fall 2020
Margaret Fleck
A* Search 3

Recap of A*
States are evaluated by a function f which estimates from start to goal via this state.

f(s) = g(s) + h(s)

g(s) is (actual) distance from the start state to s. h(s) is a heuristic estimate of the distance from s to the goal. f(s)
is an estimate of the length of a path from start to goal via s.

Three types of states:

unseen
done/closed = neighbors all explored, allegedly finished with this state
open/frontier = seen but neighbors need to be explored

The frontier is stored in a priority queue, organized by the f values.

Correct bookkeeping isn't obvious


A finds the optimal path only when you do the bookkeeping correctly. The details are somewhat like UCS, but
∗

there are some new issues. Consider the following example (artificially cooked up for the purpoose of
illustration).

(from Berkeley CS 188x materials)

The state graph is shown on the left, with the h value under each state. The right shows a quick picture of the
search process. Walking through the search in more detail:

First we put S in the queue with estimated cost 2, i.e. g(S) = 0 plus h(S) = 2.

We remove S from the queue and add its neighbors. A has estimated cost 5 and B has estimated cost
2. S is now done/closed.

https://courses.grainger.illinois.edu/cs440/fa2020/lectures/astar3.html 1/3
9/17/2020 CS440 Lectures
We remove B from the queue and add its neighbor C. C has estimated cost 4. B is now done/closed.

We remove C from the queue. One of its neighbors (A) is already in the queue. So we only need to
add G. G has cost 6. C is now done/closed.

We remove A from the queue. Its neighbors are all done, so we have nothing to do. A is now done.

We remove G from the queue. It's the goal, so we halt, reporting that the best path is SBCG with
cost 6.

Oops. The best path is through A and has actual cost 5. But heuristic was admissible. What went wrong?
Obviously we didn't do our bookkeeping correctly.

Fixing our bookkeeping


The algorithm we inherited from from UCS only updates costs for nodes that are in the frontier. In this example,
paths through B look better at the start. So SBCG reaches C and G first. C and G are marked done/closed. And
then we see the shorter path SAC. Updating the cost of C won't help because it's in the done/closed set.

Fix: when we update the cost of a node in the closed/done set, put that node back into the frontier
(priority queue).

There is also a second issue, that applies also to UCS. Efficient priority queue implementations (e.g. the ones
supplied with your favorite programming language) don't necessarily support updates to the priority numbers.

Workaround: it may be more efficient to put a second copy of the state (with the new cost) into the
priority queue.

In many applications, decreases in state cost aren't very frequent. So this creates less inefficiency than using a
priority queue implementation with more features.

Consistency
The problem with shorter paths to old states is simplified if our heuristic is "consistent." That is, if we can get
from n to n' with cost c(n,n'), we must have
′ ′
h(s) ≤ c(s, s ) + h(s )

So as we follow a path away from start state, our estimated cost f never decreases. Useful heuristics are often
consistent. For example, the straight-line distance is consistent because of the triangle inequality.

When the heuristic is consistent, we never have to update the path length for a node that is in the done/closed set.
(Though we may still have to update path lengths for nodes in the frontier.)

We can view UCS as A* with a heuristic function f that always returns zero. This heuristic is consistent, so
updates to costs in UCS involve only states in the frontier.

Other hacks and variants


There are many variants of A*, mostly hacks that may help for some problems and not others. See this set of
pages for extensive implementation detail Amit Patel's notes on A*.

https://courses.grainger.illinois.edu/cs440/fa2020/lectures/astar3.html 2/3
9/17/2020 CS440 Lectures
One well-known variant is iterative deepening A*. Remember that iterative deepening is based on a version of
DFS ("length-bounded") in which search is stopped when the path reaches a target length k. Iterative deepening
A* is similar, but search stops if the A* estimated cost f(s) is larger than k.

Another optimization involves building a "pattern database." This is a database of partial problems, together
with the cost to solve the partial problem. The true solution cost for a search state must be at least as high as the
cost for any pattern it contains.

https://courses.grainger.illinois.edu/cs440/fa2020/lectures/astar3.html 3/3

You might also like