PowerPoint Presentation
CSE 3521: Search
[Many slides are adapted from the UC Berkeley. CS188 Intro to AI at UC Berkeley and previous CSE 3521 course at OSU.]
Recap: State space graphs vs. search trees
S
a
b
d
p
a
c
e
p
h
f
r
q
q
c
G
a
q
e
p
h
f
r
q
q
c
G
a
S
G
d
b
p
q
c
e
h
a
f
r
We construct both on demand – and we construct as little as possible.
Each NODE in in the search tree is an entire PATH in the state space graph.
Search Tree
State Space Graph
A unique STATE can show up at multiple NODES in a search tree; each NODE in the search tree is a unique plan.
Recap: Search algorithms
Search tree:
Nodes: represent plans for reaching states
Plans have costs (sum of action costs)
Search algorithm:
Systematically builds/explores a search tree
Chooses an ordering of the fringe (unexplored nodes)
Optimal: finds least-cost plans
Today
Informed Search Methods
Greedy Search
A* Search
Graph search vs. tree search
Uninformed vs. informed search
Uninformed search
Given no information about the problem (other than its definition)
Find solutions by systematically visiting new states and testing for goal
Informed search
Given some ideas of where to look for solutions
Use problem-specific knowledge
Searching with a search tree
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible
When to stop?
General tree search
Search stops when you dequeue/expand a goal state, not when you enqueue a goal state
You know exactly where you came from and how you got there, but you have no idea where you’re going. But, you’ll know it when you see it.
7
General Search
Search stops when you dequeue/expand a goal state, not when you enqueue a goal state
Generalized Search Algorithm
Let f(n) be an evaluation function
Where node n is a node in the search tree
Represents priority value for each search tree node in the min priority queue
Min-priority queue dequeue’s the node with smallest f(n) value
Generalized Search Algorithm
Let function g(n) be the cost from the start state to the state s (found in the search tree node n) in the state space
Actual accumulated cost from start state state s
“Sum of the costs from the start state to state s”
Uniform Cost Search (UCS)
Let f(n) = g(n)
Remember the evaluation function f(n) is used to define the priority for search tree nodes in the min priority queue
Generalized Search Algorithm
What is f(n) for the depth first search?
What is f(n) for breadth first search?
11
Search heuristics
A heuristic is a function
Estimates (Guess!!!) the cost from a state s to a goal in the state space
“How close a state is to a goal”, e.g. If I’m at City C, how close is it to the goal City B?
Designed for a particular search problem
12
Example: Heuristic function
h(s)
A Heuristic for robot navigation
Distance heuristics
Euclidean distance
Manhattan distance
xn
yn
n
xg
yg
Example: 8 Puzzle
What are the states?
How many states?
What are the actions?
How many successors from the start state?
What should the costs be?
Start State
Goal State
Actions
A Heuristic for the 8-puzzle problem
Number of misplaced tiles
h(s) = “# of tiles in the wrong location”
Example, h(s) = 6
Manhattan distance
h(s) = “Sum of the manhattan distance of each tile”
Example, h(s) = 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1 = 13
Is h(sG) = 0 for heuristics, where sG is a goal state?
1
4
7
5
2
6
3
8
State s
6
4
7
1
5
2
8
3
Goal state
Greedy Best First Search
Example: Heuristic function
h(s)
Greedy Best First Search
Expand the node that seems closest to the goal …
Make sure the heuristic h(sG) = 0, where sG is a goal state
What can go wrong in searching for the solution/path/plan?
Search stops when you dequeue/expand a goal state, not when you enqueue a goal state
Greedy Best First Search
Strategy: expand a node that you think is closest to a goal state
Heuristic: cost estimate to the nearest goal for each state
A common case:
Greedy best-first takes you straight to the (wrong) goal
Worst-case: like a badly-guided DFS
…
b
…
b
For any search problem, you know the goal. Now, you have an idea of how far away you are from the goal.
20
Greedy Best First Search Efficiency Issues
f(s) = h(s) = Euclidean (straight distance) to the goal
Local-minimum problem
Greedy Best First Search
Example of a poor case
start
goal
Greedy Best First Search
Complete
No
Get stuck in loops
Time
O(bm)
Average case is much better
Space
O(bm)
Optimal
No
Does not keep track of path cost
23
A* Search
A* Search
UCS
Greedy
A*
Notes: these images licensed from iStockphoto for UC Berkeley use.
25
Combining UCS and Greedy
Uniform-cost orders by current path cost, or backward cost g(n)
Greedy Best First orders by goal proximity, or forward cost h(n)
A* Search orders by the sum: f(n) = g(n) + h(n)
S
a
d
b
G
h=5
h=6
h=2
1
8
1
1
2
h=6
h=0
c
h=7
3
e
h=1
1
S
a
b
c
e
d
d
G
G
g = 0 h=6
g = 1 h=5
g = 2 h=6
g = 3 h=7
g = 4 h=2
g = 6 h=0
g = 9 h=1
g = 10 h=2
g = 12 h=0
State space graph
Search tree
Is A* optimal?
Exercise: What is the optimal solution? What is the one A* finds?
Start state S
Goal state G
A
G
S
1
3
h = 6
h = 0
5
h = 7
Is A* optimal?
Exercise: What is the optimal solution? What is the one A* finds?
What went wrong?
Actual bad goal cost < estimated good goal cost
h(S) is too large (also h(A))
We need estimates to be less than actual costs!
A
G
S
1
3
h = 6
h = 0
5
h = 7
Admissible heuristics
Idea: Admissibility
Inadmissible (pessimistic) heuristics break optimality by trapping good plans on the fringe
Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs
Admissible heuristics
A heuristic h is admissible (optimistic) if:
where is the true cost to a nearest goal G
= g(G) – g(n)
Admissible heuristics
A heuristic h is admissible (optimistic) if:
where is the true cost to a nearest goal G
Examples:
Using admissible heuristics is the key for A* search in practice.
15
= g(G) – g(n)
Optimality of A* Tree Search
Optimality of A* Tree Search
Assume:
A is an optimal goal node
B is a suboptimal goal node
h is admissible
Claim:
A will exit the fringe before B
…
Optimality of A* Tree Search: Blocking
Proof:
Imagine B is on the fringe
Some ancestor n of A is on the fringe, too (maybe A!)
Claim: n will be expanded before B
f(n) is less or equal to f(A)
Definition of f-cost
Admissibility of h
…
h = 0 at a goal
Optimality of A* Tree Search: Blocking
Proof:
Imagine B is on the fringe
Some ancestor n of A is on the fringe, too (maybe A!)
Claim: n will be expanded before B
f(n) is less or equal to f(A)
f(A) is less than f(B)
B is suboptimal
h = 0 at a goal
…
Optimality of A* Tree Search: Blocking
Proof:
Imagine B is on the fringe
Some ancestor n of A is on the fringe, too (maybe A!)
Claim: n will be expanded before B
f(n) is less or equal to f(A)
f(A) is less than f(B)
n expands before B
All ancestors of A expand before B
A expands before B
A* search is optimal
…
UCS vs. A* contours
Uniform-cost expands equally in all “directions”
A* expands mainly toward the goal, but does hedge its bets to ensure optimality
Start
Goal
Start
Goal
38
Comparison
Greedy Best First
Uniform Cost
A*
A* applications
Video games
Pathing/routing problems
Resource planning problems
Robot motion planning
Language analysis
Machine translation
Speech recognition
…
Creating Heuristics
Creating admissible heuristics
Most of the work in solving hard search problems optimally is in coming up with admissible heuristics
Often, admissible heuristics are solutions to relaxed problems, where new actions are available
Inadmissible heuristics are often useful too
15
366
8 Puzzle I
Heuristic: Number of tiles misplaced
Why is it admissible?
h(S) =
This is a relaxed-problem heuristic
8
Average nodes expanded when the optimal path has…
…4 steps …8 steps …12 steps
UCS 112 6,300 3.6 x 106
TILES 13 39 227
Start State S
Goal State
Statistics from Andrew Moore
8 Puzzle II
What if we had an easier 8-puzzle where any tile could slide any direction at any time, ignoring other tiles?
Total Manhattan distance
Why is it admissible?
h(S) =
3 + 1 + 2 + … = 18
Average nodes expanded when the optimal path has…
…4 steps …8 steps …12 steps
TILES 13 39 227
MANHATTAN 12 25 73
Start State S
Goal State
8 Puzzle III
How about using the actual cost to the goal state as a heuristic?
Would it be admissible?
Would we save on nodes expanded?
What’s wrong with it?
With A*: a trade-off between quality of estimate and work per node
As heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself
A* Search
A* Search
A* Search
A* Search
A* Search
A* Search
Robot Navigation
Robot Navigation
0
2
1
1
5
8
7
7
3
4
7
6
7
6
3
2
8
6
4
5
2
3
3
3
6
5
2
4
4
3
5
5
4
6
5
6
4
5
Greedy Best First: f(N) = h(N), where N is a state in the state space
with h(N) = Manhattan distance to the goal
Robot Navigation
0
2
1
1
5
8
7
7
3
4
7
6
7
6
3
2
8
6
4
5
2
3
3
3
6
5
2
4
4
3
5
5
4
6
5
6
4
5
7
0
Greedy Best First: f(N) = h(N),
h(N) = Manhattan distance to the goal
Robot Navigation
A*: f(N) = g(N)+h(N),
h(N) = Manhattan distance to goal
0
2
1
1
5
8
7
7
3
4
7
6
7
6
3
2
8
6
4
5
2
3
3
3
6
5
2
4
4
3
5
5
4
6
5
6
4
5
7+0
6+1
6+1
8+1
7+0
7+2
6+1
7+2
6+1
8+1
7+2
8+3
7+2
6+3
6+3
5+4
5+4
4+5
4+5
3+6
3+6
2+7
8+3
7+4
7+4
6+5
5+6
6+3
5+6
2+7
3+8
4+7
5+6
4+7
3+8
4+7
3+8
3+8
2+9
2+9
3+10
2+9
3+8
2+9
1+10
1+10
0+11
0+11
0+4
1+5
1+5
1+3
3+3
3+4
3+4
3+2
4+1
5+2
5+0
2+3
2+4
2+3
f(N) = g(N) + h(N)
with h(N) = number of misplaced tiles
8-Puzzle Heuristics
Heuristic Practice: Towers of Hanoi
Blocks of decreasing size are placed on a spindle
The blocks should be moved from spindle 1 to 3
Constraint: no block can be placed on top of a smaller block.
Start State
1 2 3
Tree search pseudo-code
Important note for search
Please note the difference between the “search process (nodes that are expanded)” and the “solution (a path from the start state to the goal state)”
Time (e.g., number of expanded nodes) to find a solution IS NOT the cost of the solution (action sequence)
Example: The time to find a traveling plan between City A and City B IS NOT the time to travel from City A to City B
/docProps/thumbnail.jpeg