1 of 66

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.]

2 of 66

Announcement

Piazza Link: https://piazza.com/osu/spring2024/cse3521chao
Access code: CSE3521

HW-1: to be released early next week (2 weeks to complete).

Linear algebra quizzes: due next Friday

Changes: 2 midterms and 1 final

Midterm-1 after HW-1 due (early-mid February): Search + Prerequisites + (Logic)

3 of 66

Recap: Search problems

A search problem consists of:

A state space

A successor function

(with actions, costs)

A start state and a goal test

A solution is a sequence of actions (a plan) which transforms the start state to a goal state

“N”, 1.0

“E”, 1.0

Start:

Goal(s): or or ……

4 of 66

Recap: State space graphs vs. search trees

S

a

b

d

p

a

c

e

p

h

f

r

q

c

G

a

q

e

p

h

f

r

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 the search tree is a 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.

5 of 66

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

6 of 66

Recap: 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
Algorithms: DFS, BFS, UCS

Informed search

Given some ideas of where to look for solutions
Use problem-specific knowledge

7 of 66

Recap: Depth-First Search (DFS)

S

a

b

d

p

a

c

e

p

h

f

r

q

c

G

a

q

e

p

h

f

r

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

Costs on edges are assumed to be 1!

8 of 66

Recap: 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 + b² + …. b^m = O(b^m)

…

b

1 node

b nodes

b² nodes

b^m nodes

m tiers

9 of 66

Recap: Depth-First Search (DFS) properties

What nodes DFS expand?

Some left prefix of the tree
Could process the whole tree!
If m is finite, takes time O(b^m)

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?

No, it finds the “leftmost” solution, regardless of depth or cost

…

b

1 node

b nodes

b² nodes

b^m nodes

m tiers

10 of 66

Today

Uninformed Search Methods

Breadth-First Search (BFS)
Uniform-Cost Search (UCS)

Informed Search Methods

Greedy Search
A* Search

11 of 66

Breadth-First Search (BFS)

12 of 66

Breadth-First Search (BFS)

S

a

b

d

p

a

c

e

p

h

f

r

q

c

G

a

q

e

p

h

f

r

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

13 of 66

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(b^s)

How much space does the fringe take?

Has roughly the last tier, so O(b^s)

Is it complete?

s must be finite if a solution exists, so yes!

Is it optimal?

Only if costs are all 1 (more on costs later)

…

b

1 node

b nodes

b² nodes

b^m nodes

s tiers

b^s nodes

14 of 66

DFS vs. BFS

	DFS	BFS
Time to find a solution	O(b^m)	O(b^s)
Fringe space	O(bm)	O(b^s)
Complete	No	Yes
Optimal	No	Yes, if costs are all 1

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

15 of 66

Iterative deepening

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

…

b

16 of 66

Questions?

17 of 66

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

15

1

3

2

18 of 66

Uniform Cost Search (UCS)

19 of 66

Uniform Cost Search (UCS)

S

a

b

d

p

a

c

e

p

h

f

r

q

c

G

a

q

e

p

h

f

r

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

2

8

2

15

1

2

Cost contours

2

20 of 66

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(b^C*/ε) (exponential in effective depth)
Additional cost of the priority queue

How much space does the fringe take?

Has roughly the last tier, so O(b^C*/ε)

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

21 of 66

The one queue

All the search algorithms are the same except for fringe/exploration strategies

A fringe is a collection of nodes waiting to be expanded (with priority).
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

22 of 66

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 world models …

23 of 66

Search gone wrong?

24 of 66

Recent progress

https://wayve.ai/thinking/scaling-gaia-1/

https://wayve.ai/thinking/learning-a-world-model-and-a-driving-policy/

25 of 66

Questions?

26 of 66

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

27 of 66

Example: Pancake problem

Cost: Number of pancakes flipped

28 of 66

Example: Pancake problem

3

2

4

3

2

4

State space graph with costs as weights

3

4

3

4

2

S

G

29 of 66

General tree search

Action: flip top two�Cost: 2

Action: flip all four�Cost: 4

Path to reach goal:

Flip four, flip three

Total cost: 7

Search stops when you dequeue/expand a goal state, not when you enqueue a goal state

30 of 66

Uninformed search

31 of 66

Informed search

32 of 66

Search heuristics

A heuristic is

A function that estimates how close a state is to a goal

Example: If I’m at City C, how close is it to the goal City B?

Designed for a particular search problem
Examples: Manhattan distance, Euclidean distance for pathing (not the exact “path” distance)

10

5

11.2

33 of 66

Example: Heuristic function

h(x)

34 of 66

Example: Heuristic function

Heuristic: the largest pancake that is still out of place

4

3

0

2

3

4

3

4

h(x)

GOAL

35 of 66

Questions?

36 of 66

Greedy Search

37 of 66

Example: Heuristic function

h(x)

38 of 66

Greedy Search

Expand the node that seems closest to the goal …

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

39 of 66

Greedy Search

Strategy: expand a node that you think is closest to a goal state

Heuristic: the estimate of distance to the nearest goal for each state

A common case:

Best-first takes you straight to the (wrong) goal

Worst-case: like a badly-guided DFS

…

b

…

b

40 of 66

Greedy Search

Example of a poor case

G

S

41 of 66

Questions?

42 of 66

A* Search

43 of 66

A* Search

UCS

Greedy

A*

44 of 66

Combining UCS and Greedy

Uniform-cost orders by current path cost, or backward cost g(n)
Greedy 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

2

h=6

h=0

c

h=7

3

e

h=1

1

S

a

b

c

e

d

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

45 of 66

Is A* optimal?

Exercise: What is the optimal solution? What is the one A* finds?

A

G

S

1

3

h = 6

h = 0

5

h = 7

46 of 66

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
We need estimates to be less than actual costs!

A

G

S

1

3

h = 6

h = 0

5

h = 7

47 of 66

Admissible heuristics

48 of 66

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

49 of 66

Admissible heuristics

A heuristic h is admissible (optimistic) if:

where is the true cost to a nearest goal G

= g(G) – g(n)

50 of 66

Admissible heuristics

A heuristic h is admissible (optimistic) if:

where is the true cost to a nearest goal G

Examples:

Producing admissible heuristics is the key for A* search in practice.

15

= g(G) – g(n)

51 of 66

Optimality of A* Tree Search

52 of 66

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

…

53 of 66

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

54 of 66

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

…

55 of 66

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

…

56 of 66

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

57 of 66

Comparison

Greedy

Uniform Cost

A*

58 of 66

A* applications

Video games
Pathing/routing problems
Resource planning problems
Robot motion planning
Language analysis
Machine translation
Speech recognition
…

59 of 66

Creating Heuristics

60 of 66

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

61 of 66

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

62 of 66

8 Puzzle I

Heuristic: Number of tiles misplaced
Why is it admissible?
h(start) =
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 10⁶
TILES	13	39	227

Start State

Goal State

Statistics from Andrew Moore

63 of 66

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(start) =

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

Goal State

64 of 66

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

65 of 66

Tree search pseudo-code

66 of 66

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