Transcript CS 294-5: Statistical Natural Language Processing

Advanced Artificial Intelligence
Lecture 2: Search
Outline
 Problem-solving agents (Book: 3.1)
 Problem types and problem formulation
 Search trees and state space graphs (3.3)
 Uninformed search (3.4)
 Depth-first, Breadth-first, Uniform cost
 Search graphs
 Informed search (3.5)
 Greedy search, A* search
 Heuristics, admissibility
2
Agents
act = AgentFn(percept)
sensors
agent fn
actuators
3
Problem types
 Fully observable, deterministic
 single-belief-state problem

 Non-observable
 sensorless (conformant) problem

 Partially observable/non-deterministic
 contingency problem
 interleave search and execution

 Unknown state space
 exploration problem
 execution first
4
Search Problems
 A search problem consists of:
 A state space
N, 1
 A transition model
E, 1
 A start state, goal test, and path cost function
 A solution is a sequence of actions (a plan)
which transforms the start state to a goal state
Transition Models
 Successor function
 Successors(
) = {(N, 1,
), (E, 1,
)}
 Actions and Results
 Actions(
 Result(
 Cost(
) = {N, E}
, N) =
; Result(
, N,
) = 1; Cost(
, E) =
, E,
)=1
Example: Romania
 State space:
 Cities
 Successor
function:
 Go to adj city
with cost = dist
 Start state:
 Arad
 Goal test:
 Is state ==
Bucharest?
 Solution?
State Space Graphs
 State space graph: A
mathematical
representation of a
search problem
 For every search problem,
there’s a corresponding
state space graph
 The successor function is
represented by arcs
 This can be large or
infinite, so we won’t
create it in memory
G
a
c
b
e
d
f
S
h
p
q
r
Ridiculously tiny search graph
for a tiny search problem
Search Trees
N, 1
E, 1
 A search tree:





This is a “what if” tree of plans and outcomes
Start state at the root node
Children correspond to successors
Nodes contain states, correspond to paths to those states
For most problems, we can never actually build the whole tree
Another Search Tree
 Search:
 Expand out possible plans
 Maintain a frontier of unexpanded plans
 Try to expand as few tree nodes as possible
General Tree Search
 Important ideas:
 Frontier (aka fringe)
 Expansion
 Exploration strategy
 Main question: which frontier nodes to explore?
State Space vs. Search Tree
G
a
Each NODE in in the
search tree is an
entire PATH in the
state space.
c
b
e
d
f
S
h
p
r
q
S
e
d
We construct both
on demand – and
we construct as
little as possible.
b
c
a
a
e
h
p
q
q
c
a
h
r
p
f
q
G
p
q
r
q
f
c
a
G
States vs. Nodes
 Nodes in state space graphs are problem states
 Represent an abstracted state of the world
 Have successors, can be goal / non-goal, have multiple predecessors
 Nodes in search trees are paths
 Represent a path (sequence of actions) which results in the node’s state
 Have a problem state and one parent, a path length, (a depth) & a cost
 The same problem state may be achieved by multiple search tree nodes
State Space Graph
Search Tree
Parent
Depth 5
Action
Node
Depth 6
Depth First Search
G
a
Strategy: expand
deepest node first
c
b
e
d
Implementation:
Frontier is a LIFO
stack
f
S
h
p
r
q
S
e
d
b
c
a
a
e
h
p
q
q
c
a
h
r
p
f
q
G
p
q
r
q
f
c
a
G
Breadth First Search
G
a
Strategy: expand
shallowest node first
c
b
e
d
Implementation:
Fringe is a FIFO
queue
S
f
h
p
r
q
S
e
d
Search
Tiers
b
c
a
a
e
h
p
q
q
c
a
h
r
p
f
q
G
p
q
r
q
f
c
G
a
[demo: bfs]
Santayana’s Warning
 “Those who cannot remember the past are
condemned to repeat it.” – George Santayana
 Failure to detect repeated states can cause
exponentially more work (why?)
Graph Search
 In BFS, for example, we shouldn’t bother
expanding the circled nodes (why?)
S
e
d
b
c
a
a
e
h
p
q
q
c
a
h
r
p
f
q
G
p
q
r
q
f
c
a
G
Graph Search
 Very simple fix: never expand a state twice
 Can this wreck completeness? Lowest cost?
Graph Search Hints
 Graph search is almost always better than
tree search (when not?)
 Implement explored as a dict or set
 Implement frontier as priority Q and set
Costs on Actions
GOAL
a
2
2
c
b
1
3
2
8
2
e
d
3
9
8
START
p
15
2
h
4
1
f
4
q
1
r
Notice that BFS finds the shortest path in terms of number of transitions.
It does not find the least-cost path.
We will quickly cover an algorithm which does find the least-cost path.
Uniform Cost Search
2
b
Expand cheapest node first:
d
S
1
p
15
Cost
contours
c
a 6
a
h 17 r 11
e 5
11
p
9
e
3
b 4
h 13 r 7
p
f 8
q
q
q 11 c
a
G 10
2
9
2
e
h
8
q
f
c
a
G
f
1
1
r
q
0
S
d
c
8
1
3
Frontier is a priority queue
G
a
p
1
q
16
Uniform Cost Issues
 Remember: explores
increasing cost contours
…
c1
c2
c3
 The good: UCS is
complete and optimal!
 The bad:
 Explores options in every
“direction”
 No information about goal
location
Start
Goal
Uniform Cost Search
 What will UCS do for this graph?
0
1
START
b
0
a
1
GOAL
 What does this mean for completeness?
AI Lesson
To do more,
Know more
Heuristics
Greedy Best First Search
 Expand the node that seems closest to goal…
 What can go wrong?
Greedy goes wrong
S
G
Combining UCS and Greedy
 Uniform-cost orders by path cost, or backward cost g(n)
 Best-first orders by distance to goal, or forward cost h(n)
5
e
h=1
1
S
h=6
c
h=7
1
a
h=5
1
1
3
2
d
h=2
G
h=0
b
h=6
 A* Search orders by the sum: f(n) = g(n) + h(n)
When should A* terminate?
 Should we stop when we enqueue a goal?
2
A
2
h=2
S
G
h=3
2
B
h=0
3
h=1
 No: only stop when we dequeue a goal
Is A* Optimal?
1
A
h=6
3
h=0
S
h=7
G
5
 What went wrong?
 Actual bad path cost (5) < estimate good path cost (1+6)
 We need estimates (h=6) to be less than
actual (3) costs!
Admissible Heuristics
 A heuristic h is admissible (optimistic) if:
where
is the true cost to a nearest goal
Never overestimate!
Other A* Applications







Path finding / routing problems
Resource planning problems
Robot motion planning
Language analysis
Machine translation
Speech recognition
…
Summary: A*
 A* uses both backward costs, g(n), and
(estimates of) forward costs, h(n)
 A* is optimal with admissible heuristics
 A* is not the final word in search algorithms
(but it does get the final word for today)