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.]
Today
State Space Graphs and Search Trees
Uninformed Search Methods
Depth-First Search
Breadth-First Search
Uniform-Cost Search
General theme in the class:
A goal we have in mind.
A mathematical abstraction to formalize this
Algorithms that operate on these abstractions
2
State space graphs and search trees
To “systematically” find the solution rather than brute-force
State space graphs
State space graph: a mathematical representation of a search problem
Nodes are states (i.e., abstracted world configurations)
Arcs represent successors (action and results)
The goal test is a set of goal nodes (maybe only one)
In a state space graph, each unique state occurs only once!
We can rarely build this full graph in memory (it’s too big), but it’s a useful idea
State space graphs
State space graph: a mathematical representation of a search problem
Nodes are states (i.e., abstracted world configurations)
Arcs represent successors (action and results)
The goal test is a set of goal nodes (maybe only one)
In a state space graph, each unique state occurs only once!
We can rarely build this full graph in memory (it’s too big), but it’s a useful idea
S
G
d
b
p
q
c
e
h
a
f
r
Tiny state space graph graph for a tiny search problem
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
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
Search trees (moves in state space graphs)
A search tree:
A “what if” tree of plans and their outcomes
The start state is the root node
Children correspond to successors
Nodes show states, but correspond to/record PLANS that achieve those states
For most problems, we can never actually build the whole tree
“E”, 1.0
“N”, 1.0
This is now / start
Possible futures
Different plans that achieve the same state, will be different nodes in the tree.
8
Search trees: nodes are not states but partial plans
G
b
a
c
a
b
c
a
G
(a-b)
(a-b-c)
(a-b-c-a)
(a-b-c-G)
Can we have “a” again? Or should it go back the root (then not a tree anymore)?
Yes! The node is actually (a-b-c-a), different from (a).
(a)
Different plans that achieve the same state, will be different nodes in the tree!
State space graph
Search tree
Different plans that achieve the same state, will be different nodes in the tree.
9
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
Each NODE in in the search tree is an entire PATH in the state space graph.
Search Tree
State Space Graph
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
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.
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.
Exercise: State space graphs vs. search trees
S
G
b
a
Consider this 4-state graph:
How big/deep is its search tree (from S)?
Exercise: State space graphs vs. search trees
S
G
b
a
Consider this 4-state graph:
Important: Lots of repeated structure in the search tree!
How big/deep is its search tree (from S)?
Tree search
How to systematically build/explore a search tree to find the solution!
Search example: Romania
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
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
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 problem
General tree search
Important components:
(1) Fringe (2) Expansion (3) Exploration strategy
Main question: which fringe nodes to explore?
Search problem (state space, successor function, start state, and goal test)
Tree Search
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible
Tree Search
Search:
Expand out potential plans (tree nodes)
Maintain a fringe of partial plans under consideration
Try to expand as few tree nodes as possible
Tree Search
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 Search
enqueue(queue, start_node)
loop do {
if empty(queue) return failure
leaf = getNext(queue)
if isGoal(leaf)
return solution(leaf)
else
enqueue(queue, expand(leaf))
}
Start State
Fail!
Goal Check
Successor Function
General Search: Textbook Pseudocode
Priority queue (assume a MIN priority queue)
DFS: LIFO
Priority = -1 * search tree depth
BFS: FIFO
Priority = search tree depth
UCS
Priority = Accumulated cost path
Depth-First Search (DFS)
Depth-First Search (DFS)
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
q
p
h
f
d
b
a
c
e
r
Strategy: expand a deepest node first
Implementation: Fringe is a LIFO stack
Search algorithm properties
Search algorithm properties
Complete: Guaranteed to find a solution if one exists?
Optimal: Guaranteed to find the least cost path?
Time complexity?
Space complexity (fringe)?
Cartoon of search tree:
b is the branching factor
m is the maximum depth
solutions at various depths
Number of nodes in entire tree?
1 + b + b2 + …. bm = O(bm)
…
b
1 node
b nodes
b2 nodes
bm nodes
m tiers
Depth-First Search (DFS) properties
…
b
1 node
b nodes
b2 nodes
bm nodes
m tiers
What nodes DFS expand?
Assume: Expand left first
Relax assumption: Could process the whole tree!
If m is finite, takes time O(bm)
How much space does the fringe take?
Only has siblings on the current path to root, so O(bm)
Is it complete?
m could be infinite, so only if we prevent cycles
Is it optimal?
Assume: Expand left first
No, it finds the “leftmost” solution, regardless of depth or cost
Breadth-First Search (BFS)
Breadth-First Search (BFS)
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
Search
Tiers
Strategy: expand a shallowest node first
Implementation: Fringe is a FIFO queue
Breadth-First Search (BFS) properties
What nodes does BFS expand?
Processes all nodes above the shallowest solution
Let the depth of the shallowest solution be s
Search takes time O(bs)
How much space does the fringe take?
Has roughly the last tier, so O(bs)
Is it complete?
s must be finite if a solution exists, so yes!
Is it optimal?
Only if costs are all unit cost (every action has the same cost)
…
b
1 node
b nodes
b2 nodes
bm nodes
s tiers
bs nodes
DFS vs. BFS
DFS BFS
Time to find a solution O(bm) O(bs)
Fringe space O(bm) O(bs)
Complete No Yes
Optimal No Yes, if unit costs
Time 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
Iterative deepening
…
b
Idea: get DFS’s space advantage with BFS’s time/shallow-solution advantages
Run a DFS with depth limit 1. If no solution…
Run a DFS with depth limit 2. If no solution…
Run a DFS with depth limit 3. …..
Isn’t that wastefully redundant?
Generally, most of the work is in the deepest level searched, so not so bad!
A preferred method with a large search space and the depth of solution not known
Cost-sensitive search
BFS finds the shortest path (plan; solution) in terms of the number of actions.
It does not find the least-cost path.
We will now study a similar algorithm which does find the least-cost path.
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9
2
8
1
8
2
3
2
4
4
15
1
3
2
2
Uniform Cost Search (UCS)
Uniform Cost Search (UCS)
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
Strategy: expand the cheapest node first
Implementation: Fringe is a priority queue (priority: cumulative cost)
S
G
d
b
p
q
c
e
h
a
f
r
3
9
1
16
4
11
5
7
13
8
10
11
17
11
0
6
3
9
1
1
2
8
8
2
15
1
2
Cost contours
2
…
Uniform Cost Search (UCS) properties
What nodes does UCS expand?
Processes all nodes with cost less than the cheapest solution!
If the cheapest solution costs C* and the arcs cost at least , then the “effective depth” is roughly C*/
Takes time O(bC*/) (exponential in effective depth)
Additional cost of the priority queue
How much space does the fringe take?
Has roughly the last tier, so O(bC*/)
Is it complete?
Assuming the least-cost solution has a finite cost and the minimum arc cost is positive, yes!
Is it optimal?
Yes!
b
C*/ “tiers”
c 3
c 2
c 1
The one queue
All the search algorithms are the same except for fringe/exploration strategies
Conceptually, all fringes are priority queues (i.e. collections of nodes with attached priorities)
Practically, for DFS and BFS, you can avoid the log(n) overhead from an actual priority queue, by using stacks and queues
Can even code one implementation that takes a variable queuing object
Search and models
Search operates over the models of the world
The agent doesn’t actually try all the plans out in the real world!
Planning is all “in simulation”
Your search is only as good as your models …
Search gone wrong?
Summary: 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
Missionaries and Cannibals Problem
3 missionaries and 3 cannibals on one side of the river, with a single boat to cross
http://www.novelgames.com/en/spgames/missionaries/
Boat can hold 1 or 2 people
Can never have more cannibals than missionaries on a side
How do you get them over to the other side?
States? Initial State?
Transition Model?
Goal Test? Path Cost?
Search?
46
/docProps/thumbnail.jpeg