CS计算机代考程序代写 AI algorithm PowerPoint Presentation

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