COMP 424 - Artificial Intelligence

Uninformed Search

Instructors: Jackie CK Cheung

Bogdan Mazoure
Readings: R&N Ch. 3, up to 3.4 (3rd or 4th ed)
Search in AI
• Search is at the heart of all AI systems!
Typical setup of an AI task:
Knowledge
• Formal representation of the problem to be solved
• Includes definitions of state, goal, available actions
• Other factual or probabilistic knowledge about the problem
Search
• Process of finding a solution (or possibly, the best solution)

2
Eight-Puzzle

How would you build an AI agent to solve this problem?

3
Dialogue systems
• Decide what do say next:
Hi, [Cortana / Google /
Bixby / Siri]. Tell me a joke!

• Suppose we have a measure of goodness for every

possible sequence of words, and a list of words the
system knows about.

4
Outline of Rest of Lecture
• Search
• Definition of problem
• Uninformed search algorithms
• Breadth-first search
• Depth-first search
• Analyzing search algorithms
• More uninformed search algorithms
• Uniform-cost search
• Depth-limited and iterative deepening search

5
Defining a search problem
• State space S: all possible configurations of the domain.

• Initial state s0  S: the start state

• Goal states G  S: the set of end states

• Operators A: the actions available

• Often defined in terms of mapping from state to successor state.

6
Defining a search problem (cont’d)
• Path: a sequence of states and operators.

• Path cost, c: a number associated with any path.

• Solution of search problem: a path from s0 to sgG

• Optimal solution: a path with minimum cost.

7
Example: Eight-Puzzle

• States?
• Goals?
• Operators?
• Path cost?
8
Example: Eight-Puzzle

• States? Configurations of the puzzle.

• Goals? Target configuration.
• Operators? Swap the blank with an adjacent tile.
• Path cost? Number of moves.
9
Example: Robot path planning
Get from red square
to yellow dot.

• States?
• Goals?
• Operators?
• Path cost?

10
Example: Robot path planning
Get from red square
to yellow dot.

• States? Position, velocity, map, obstacles.

• Goals? Get to target position without crashing.
• Operators? Small steps in several directions.
• Path cost? Length of path, energy consumption, time to goal, ...

11
Basic assumptions (for next few
lectures)
• Static (c.f. dynamic) environment
• Observable (c.f. unobservable) environment
• Discrete (c.f. continuous) states
• Deterministic (c.f. stochastic) environment

Simplifying assumptions for now. Later, we will consider

search in other settings.

12
State Space Graph
• Can visualize the state space search in terms of a graph.

• Graph defined by a set of vertices and a set of edges

connecting the vertices.
• Nodes correspond to states in S.
• Edges correspond to operators.

s0
• e.g., pathfinding in a grid

13
Search Tree
• Represents the exploration paths in a search procedure
• Nodes represent partial solutions, including a state in S.
• Edges correspond to operators.
e.g., first two levels of search tree for previous problem
s0

s0 s0

g g

14
Example with edge costs

Search tree nodes are NOT the same as the state space
graph nodes!
15
Data structures for search tree
• Defining a search tree node:
• Each node contains a state id (from the states in the graph)
• Node also contain additional information:
• The parent state and the operator used to generate it
• Cost of the path so far
• Depth of the node

• Expanding a search tree node:

• Applying all legal operators to the state
• Generating nodes for all the corresponding successor states

16
Generic search algorithm
• Initialize the search tree using the initial state of the
problem

• Repeat
1. If no candidate nodes can be expanded, return failure.
2. Choose a node for expansion, according to some search strategy.
3. If the node contains a goal state, then
• return the corresponding path.
4. Otherwise expand the node, by:
• applying each applicable operator
• generating the successor state, and
• adding the resulting nodes to the tree.

17
Example

Now expand a little further…

18
Example

Problem: Search trees can get very big!

19
Implementation details
• Need to keep track of the nodes to be expanded: the
frontier.

• Implement this using a queue:

1. Initialize queue by inserting a node for the initial state.
2. Repeat
a) If the queue is empty, return failure
b) Dequeue a node.
c) If the node contains a goal state, return path.
d) Otherwise expand the node by applying all legal operators to the state.
e) Insert the resulting nodes in the queue.

Search algorithms differ in their queuing function.

20
Uninformed (blind) search
• If a state is not a goal, you cannot tell how close to the
goal it might be.
• Hence, all you can do is move systematically between
states until you stumble on a goal.
• In contrast, informed (heuristic) search uses a guess on
how close to the goal a state might be.
• (More on this next class.)

21
Uniformed Search Algorithms
Basic algorithms
• Breadth-first search
• Depth-first search

Dealing with general-cost graphs

• Uniform-cost search

Search with limited resources

• Depth-limited search
• Iterative deepening search

22
Breadth-First Search (BFS)
• Enqueue nodes at the end of queue.
• All nodes at level i get expanded before all nodes at level
i+1.

=expand next

=terminal node

23
Example
• In what order are nodes expanded using Breadth-first
search?

24
Example
• Label all start states as V0.

25
Example
• Label all successors of states in V0 that have not been labeled as
V1.

26
Example
• Label all successors of states in V1 that have not been labeled as
V2.

27
Example
• Label all successors of states in V2 that have not been labeled as
V3.

28
Example
• Label all successors of states in V3 that have not been labeled as
V4.

29
Example
• To recover the path, follow pointers back to the parent node.

30
Revisiting states
• What if we revisit a state that was already expanded?
• What if we visit a state that was already in the queue?
• Example:
s0

s1
s4
s2

s3

sg

31
Revisiting states
• Maintain a closed list to store every expanded node.
• More efficient on problems with many repeated states.
• Worst-case time and space requirements are O(|S|) (|S| =
#states)

• In some cases, allowing states to be re-expanded could

produce a better solution.
• When repeated state is detected, compare old and new path to
find lowest cost path.
• In large domains, may not be able to store all states.

32
Depth-First Search (DFS)
• Enqueue nodes at the front of queue
• In other words, use a stack in stead of a queue.
• Nodes at deepest level expanded before shallower ones.

=expand next

=terminal node

33
Example
In what order are nodes expanded using Depth-first search?

34
Example
In what order are nodes expanded using Depth-first search?
Order of operators matter!

Solution (if you expand nodes in clockwise order, staring at 9

o’clock): {Start, d, b, a, c, e, r, f, Goal}

35
Example
In what order are nodes expanded using Depth-first search?
Order of operators matter!

Solution (if you expand nodes in clockwise order, staring at 9

o’clock): {Start, d, b, a, c, e, r, f, Goal}
What if we expand nodes counter-clockwise, from 9 o’clock?

36
Example
In what order are nodes expanded using Depth-first search?
Order of operators matter!

Solution (if you expand nodes in clockwise order, staring at 9

o’clock): {Start, d, b, a, c, e, r, f, Goal}
Solution (if we expand nodes counter-clockwise): {Start, p, q, r, f, Goal}

37
Key properties of search algorithms
• Completeness: Are we assured to find a solution, if one
exists?
• Optimality: How good is the solution?
• Space complexity: How much storage is needed?
• Time complexity: How many operations are needed?

38
Key properties of search algorithms
• Completeness: Are we assured to find a solution, if one
exists?
• Optimality: How good is the solution?
• Space complexity: How much storage is needed?
• Time complexity: How many operations are needed?

• Other desirable properties:

• Can the algorithm provide an intermediate solution?
• Can an inadequate solution be refined or improved?
• Can the work done on one search be reused for a different set of
start/goal states?

39
Search complexity
• Evaluated in terms of two characteristics:
• Branching factor of the state space (“b”): how many operators
(upper limit) can be applied at any time?

E.g. for the eight-puzzle problem: branching factor is 4, although

most of the time we can apply only 2 or 3 operators.

• Solution depth (“d”): how long is the path to the closest

(shallowest) goal state?

40
Analyzing BFS
Good news:
• Complete.
• Paths to different goals can be explored at the same time.
• Guaranteed to find shallowest path to the goal if unit cost per step.
Will not necessarily find optimal path if graph is weighted.

Bad news:
• Exponential time complexity: O(bd)

• Exponential space complexity: O(bd) [This is not good!]

41
Analyzing DFS

Good news:
• Linear space complexity: O(bm)
• m is the maximum depth of the tree
• Why? Need to remember where we are at each level of the tree
• Easy to implement recursively (do not even need queue data
structure).
• More efficient than BFS if there are many paths leading to
solution.

42
Analyzing DFS

Good news:
• Linear space complexity: O(bm)
• Easy to implement recursively (do not even need queue data
structure).
• More efficient than BFS if there are many paths leading to
solution.

Bad news:
• Exponential time complexity: O(bm)
• Not optimal.
• DFS may not complete!
• NEVER use DFS if you suspect a big tree depth!
43
Uniformed Search Algorithms
Basic algorithms
• Breadth-first search
• Depth-first search

Dealing with general-cost graphs

• Uniform-cost search

Search with limited resources

• Depth-limited search
• Iterative deepening search

44
General Step Cost
• Actions often have different costs

• e.g., I can buy a burger for $5 or fries for $3

• e.g., I can walk to the classroom outside at a cost of 500

units of warmth, or I can walk through the underground
tunnels at a cost of 5 units of warmth

45
Uniform Cost Search
• Goal: Fix BFS to ensure an optimal path with general step
costs (i.e., in a weighted graph).
Important distinction:
• Unit cost = Problem where each action has the same cost.
• General cost = Actions can have different costs.

46
Uniform Cost Search
• Goal: Fix BFS to ensure an optimal path with general step
costs (i.e., in a weighted graph).
Important distinction:
• Unit cost = Problem where each action has the same cost.
• General cost = Actions can have different costs.
• Approach:
• Use a priority queue instead of a simple queue.
• Insert nodes in the increasing order of the cost of the path so far.
• Properties:
• Guaranteed to find optimal solution for with general step costs
(same as BFS when all operators have the same cost).

47
Example
• In what order are nodes expanded using Uniform cost
search?

48
Example - solved

Priority queue = {(Start, 0)}

= {(Start, 0), (p,1), (d,3), (e,9)}
= {(Start, 0), (p,1), (d,3), (e,9), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (c,11), (q,16)} [Find faster path to e.]
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (c,11), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (c,11), (r,14), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (c,11), (r,14), (q,16)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,14)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18)}
= {(Start, 0), (p,1), (d,3), (b,4), (e,5), (a,6), (h,6), (q,10), (c,11), (r,13), (f,18), (goal,23)}

49
Uniformed Search Algorithms
Basic algorithms
• Breadth-first search
• Depth-first search

Dealing with general-cost graphs

• Uniform-cost search

Search with limited resources

• Depth-limited search
• Iterative deepening search

50
Depth-limited search
• Algorithm: search depth-first, but terminate a path either
if a goal state is found, or if the maximum depth allowed
is reached.

• Always terminates:
• Avoids the problem of search never terminating by imposing a
hard limit on the depth of any search path.

• However, it is still not complete (the goal depth may be

greater than the limit allowed.)

51
Iterative Deepening Search (IDS)
• Algorithm: do depth-limited search, but with increasing
depth.
• Expands nodes multiple times, but computation time has
same complexity.

52
Analysis of IDS
• Complete (like BFS).
• Has linear memory requirements (like DFS).
• Classical time-space tradeoff.
• Recall from last lecture: achieving rationality subject to resource
constraints
• Will see similar trade-off often in this course.

53
Analysis of IDS
• Complete (like BFS).
• Has linear memory requirements (like DFS).
• Classical time-space tradeoff.
• Recall from last lecture: achieving rationality subject to resource
constraints
• Will see similar trade-off often in this course.
• Optimal for problems with unit step costs.
• This is the preferred method for large state spaces, where
the solution path length is unknown.

54
Summary of uninformed search
• Main difference between methods is order in which they
consider states
• BFS
• Uniform cost search
• DFS
• Fixed-depth DFS
• Iterative deepening
• Assumes no knowledge about the problem:
• Very general, can be applied to any problem
• Very expensive, since no knowledge about the problem
• Some algorithms are complete
• All uninformed search methods have exponential worst-case
complexity.
55