CS2109S: Introduction to AI and Machine Learning

Lecture 2:
Solving Problems by Searching
23 January 2023

1
Admin

2
Teaching Assistants

Anxing Xiao Ce Hao Chan We Hao Chen Hanlin Chen Hung-Yu

Chew Kin Whye Rafeed Elliot Eric Florentiana 3

Teaching Assistants

Gan Pang Yen Guo Mengqi Ivan Lee James Shen Jason

Lee Chun Jie Li Po Hsien Liu Diwen Maximilliano Ayaz 4

Utomo Quok
Teaching Assistants

Ng Qi Ting Ramanathan Ruiheng Ryan Reno Lim Tai Tze Kin

Kumarappan

Tan Chee Xiang Tan Ping Zhi Tanveer Singh Udit Singh Wang Cheng 5
Teaching Assistants

Wilson Widyadhana Yu-chuan Liao Chen Yu

Yu Pei Shaun Wang Yunsong 6

Late Policy
• Up to 1 hour, 0%
• Up to 24 hours, -20%
• Up to 3 days, -30%
• Beyond 3 days, -50%

If you need extension (for valid reasons), please ask early

7
Plagiarism Policy
Dos
• Discussions without sharing/consulting/taking away any code
• Use ChatGPT with proof (e.g., share links)
Don’ts
• Use codes from those who has done or currently doing the course
• Use codes from the internet without proper citations
• Publish codes to any publicly accessible sites (e.g., GitHub, Google
Drive) or send your codes to anyone

Plagiarism checker will be performed against all previous batches!

8
Plagiarism Policy
All cases no matter how small will be handed to UG Office and OSC

• Minor offense (<10%): final grade lowered by one full letter grade
• Moderate offense (≥10%): failing grade “F”
• Very hard to return to good standing
• Say goodbye to exchange!

9
Materials

10
 Credit: Cooking with AMC
Recap
• What is AI?
• History lesson
• PEAS: Performance Measure, Environment, Actuators, Sensors
• Properties of the task environment
• Fully observable, deterministic, episodic, static, discrete, single-agent
• Agents
• Common: reflex, model-based, goal-based, utility-based, learning

11
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

12
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

13
Problem-Solving Agents
When the correct action to take is not immediately obvious, an agent
may need to plan-ahead: to consider a sequence of actions that form a
path to a goal state. Such an agent is called a problem-solving agent,
and the computational process it undertakes is called search.

Want to go to Bucharest, how?

Credit: Passport & Plates

14
Problem-Solving Process
• Goal formulation
• Problem formulation
• Create an abstract model of the relevant parts of
the world
• Search
• Simulates sequence of actions using the model,
search until goal is reached
• Execution
• Execute actions in the solution, one at a time

We assume that the task environment is fully

observable and deterministic.
Thus, the solution is a fixed sequence of actions.

15
Problem Formulation
Formally, a search problem can be formulated as follows.
• States (state space).
• Initial state: the initial state of the agent
• Goal state(s)/test
• Actions: things that the agent can do
• Transition model: what each action does
• Action cost function: the cost of performing an action

A sequence of action form a path/trajectory. Solution is a path to a goal.

16
Problem Formulation: Romania

• States: {at Sibiu, at Fagaras, …, at Bucharest}

• Initial state: at Sibiu
• Goal state(s)/test: at Bucharest
• Actions: go to neighboring city x
• Transition model: move to target city
• Action cost function: distance

17
Problem Formulation: Vacuum World

• States: see image

• Initial state: any state
• Goal state(s)/test: all clean
• Actions: suck, left, right
• Transition model: see image
• Action cost function: 1/action

18
Problem Formulation: Grid World

• States: positions of agent

• Initial state: (0,1)
• Goal state(s)/test: (1,2)
• Actions: up, down, left, right
• Transition model: move if there is no wall, die on lava
• Action cost function: 1/action

19
Problem Formulation: 8-Puzzle

• States: location of tiles

• Initial state: see image
• Goal state(s)/test: see image
• Actions: move blank left, right, up, down
• Transition model: move blank
• Action cost function: 1/move

20
Problem Formulation: Robot Assembly

• States: robot joints positions and angles

• Initial state: item not assembled
• Goal state(s)/test: item assembled
• Actions: see image
• Transition model: move/rotate joint
• Action cost function: rotation/displacement

21
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

22
Search Algorithms
A search algorithm takes in a search problem as input and returns a solution
/ failure. It is defined by the order of node expansion.

Evaluation criteria:
• Time complexity: number of nodes generated or expanded
• Space complexity: maximum number of nodes in memory
• Completeness: does it return a solution if it exists?
• Optimality: does it always find the least-cost solution?

Measure: branching factor (b), depth (d), maximum depth (m), …

23
Tree Search
Define order of node expansion
create frontier

insert initial state

while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

24
Representation Invariant
(x,y)=(0,0)

Conditions that ensure that the abstract states have

corresponding concrete states.
Valid state
Representation invariant (Grid World):
(x,y)=(-1,0)
0 ≤ 𝑥 ≤ 2, 0 ≤ 𝑦 ≤ 1

Invalid state

25
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

26
Uninformed Search Algorithms
An uninformed search algorithm is given no clue about how close a
state is to the goal(s).
Condition Algorithm Time Complexity

• Breadth-first search (BFS) No Negative Weight

Cycles
Bellman-Ford
Algorithm
𝑂(𝑉𝐸)

• Uniform-cost search On Unweighted Graph (or

equal weights)
BFS 𝑂(𝑉 + 𝐸)

• Depth-first search (DFS) No Negative Weights

On Tree
Dijkstra’s Algorithm
BFS / DFS
𝑂((𝑉 + 𝐸)𝑙𝑜𝑔 𝑉)
𝑂(𝑉)
On DAG Topological Sort 𝑂(𝑉 + 𝐸)

CS2040S focus was on finding the shortest path (SSSP, APSP)

CS2109S: might not care about shortest path, or even the path
27
Breadth-first Search
create frontier : queue

insert initial state

while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

28
Breadth-first Search
create frontier : queue Sib

insert initial state

while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

Queue:

Sib

29
 Breadth-first Search
create frontier : queue Sib

insert initial state

while frontier is not empty: Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

Queue:

Sib Rim Fag

30
 Breadth-first Search
create frontier : queue Sib

insert initial state

while frontier is not empty: Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action) Pit Sib.

if next state is goal: return solution

frontier.add(next state)
return failure

Queue:

Rim Fag Pit Sib

31
 Breadth-first Search
create frontier : queue Sib

insert initial state

while frontier is not empty: Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action) Pit Sib.
Sib Sib, Buc

if next state is goal: return solution

frontier.add(next state)
return failure

Queue:

Fag Pit Sib Sib Buc

32
 Breadth-first Search
create frontier : queue Sib

insert initial state

while frontier is not empty: Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action) Pit Sib Sib Buc

if next state is goal: return solution

frontier.add(next state)
return failure

Queue:

Fag Pit Sib Sib Buc

33
 Breadth-first Search
create frontier : queue Sib
Branching factor b
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action) Pit Sib Sib Buc

if next state is goal: return solution Depth of the optimal solution d

frontier.add(next state)
• Time complexity (# nodes generated)?
return failure
• 1 + 𝑏 + 𝑏2 + ⋯ + 𝑏𝑑 = 𝑂 𝑏𝑑
• Space complexity?
Queue: • 𝑂 𝑏𝑑 , worst case: expand the last child in a branch
• Complete? Yes, if B is finite
Fag Pit Sib Sib Buc
• Optimal? Yes, if step cost is the same everywhere
34
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2

1
insert initial state
while frontier is not empty:
state = frontier.pop()
if state is goal: return solution
for action in actions(state):

next state = transition(state, action)

frontier.add(next state)
return failure

35
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib
1
insert initial state
while frontier is not empty:
state = frontier.pop()
if state is goal: return solution
for action in actions(state):

next state = transition(state, action)

frontier.add(next state)
return failure

Priority Queue:

Sib

36
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
if state is goal: return solution
for action in actions(state):

next state = transition(state, action)

frontier.add(next state)
return failure

Priority Queue:

Sib Rim Fag

1 2 37
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2.
if state is goal: return solution
for action in actions(state): Pit Sib.

next state = transition(state, action)

frontier.add(next state)
return failure

Priority Queue:

Rim Fag Sib Pit

2 2 3 38
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2. 4 5
if state is goal: return solution
for action in actions(state): Pit Sib . Sib Buc

next state = transition(state, action)

frontier.add(next state)
return failure

Priority Queue:

Fag Sib Pit Sib Buc

2 3 4 5 39
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 . 4 5
if state is goal: return solution
for action in actions(state): Pit Sib . Sib Buc

3
, 4 ,

next state = transition(state, action)

Rim Fag
frontier.add(next state)
,

return failure

Priority Queue:

Sib Pit Rim Fag Sib Buc

3 3 4 4 5 40
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 . 4 5
if state is goal: return solution
for action in actions(state): Pit Sib . Sib Buc

5 4 3
, 4 ,

next state = transition(state, action)

Rim Buc Rim Fag
frontier.add(next state)
,
’`
,

return failure

Priority Queue:

Pit Rim Buc Fag Sib Buc Rim

3 4 4 4 5 5 41
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 . 4 5
if state is goal: return solution
for action in actions(state): Pit Sib . Sib Buc

5 4 3
, 4
,

next state = transition(state, action)

Rim Buc Rim Fag
frontier.add(next state)
,
’`
,

return failure 5
4 ,

Sib Pit
Priority Queue: ,
,

Rim Buc Fag Sib Sib Buc Rim Pit

4 4 4 4 5 5 5 42
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 . 4 5
if state is goal: return solution
for action in actions(state): Pit Sib . Sib Buc

5 4 3
, 4
,

next state = transition(state, action)

Rim Buc Rim Fag
frontier.add(next state)
,
’
,

return failure 5
4 ,
,

Sib Pit
Priority Queue: ,
,

Buc Fag Sib Sib Buc Rim Pit

4 4 4 5 5 5 43
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 4 5
if state is goal: return solution
for action in actions(state): Pit Sib Sib Buc

5 4 3 4
next state = transition(state, action)
Rim Buc Rim Fag
frontier.add(next state)
return failure 5
4
Sib Pit
Priority Queue:

Buc Fag Sib Sib Buc Rim Pit

4 4 4 5 5 5 44
 2
1

Uniform-cost Search Cost from root to a state 3

create frontier : priority queue (path cost)
2
Sib

1 2 1
insert initial state
while frontier is not empty: Rim Fag
state = frontier.pop()
3 2 4 5
if state is goal: return solution
for action in actions(state): Pit Sib Sib Buc
𝐶 ∗ /𝜖 “Tiers”
= 4/1 “Tiers”
5 4 3 4
next state = transition(state, action) 𝐶 ∗ cost of optimal solution
Rim Buc Rim Fag
frontier.add(next state) 𝜖 minimum edge cost
return failure
4 5 • Time complexity (# nodes expanded)?
∗
• 𝑂 𝑏 𝐶 /𝜖
Sib Pit
Priority Queue: • Space complexity?
∗
• 𝑂 𝑏 𝐶 /𝜖
Buc Fag Sib Sib Buc Rim Pit
• Complete? Yes, if 𝜖 > 0 and 𝐶 ∗ finite
• Optimal? Yes, if 𝜖 > 0 45
4 4 4 5 5 5 𝜖 = 0 may cause zero cost cycle
 National
Depth-first Search Day

create frontier : stack

insert initial state

while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

46
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

Stack:

Sib

47
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)

if next state is goal: return solution

frontier.add(next state)
return failure

Stack:

Sib Fag Rim

48
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit

if next state is goal: return solution

frontier.add(next state)
return failure

Stack:

Fag Rim Pit

49
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit

if next state is goal: return solution

frontier.add(next state)
return failure

Stack:

Fag Pit

50
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Pit
,
Buc

if next state is goal: return solution

frontier.add(next state)
return failure

Stack:

Fag Pit

51
 National
Depth-first Search Day

create frontier : stack

Sib

insert initial state

while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Pit Buc

if next state is goal: return solution Max depth m

frontier.add(next state)
• Time complexity (# nodes generated)?
return failure
• 𝑂 𝑏𝑚
• Space complexity?
Stack: • 𝑂 𝑏𝑚
• Complete?
Fag Pit

52
Depth-first Search
create frontier : stack
Sib

insert initial state

while frontier is not empty:
Rim
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Sib

if next state is goal: return solution …

frontier.add(next state)
• Time complexity (# nodes generated)?
return failure
• 𝑂 𝑏𝑚
• Space complexity?
• 𝑂 𝑏𝑚
• Complete? No, when depth is infinite or can go back and forth (loops)
• Optimal?
53
 Can be shorter!
Depth-first Search
create frontier : stack
Sib

insert initial state

while frontier is not empty: Rim
state = frontier.pop()
for action in actions(state): Pit
next state = transition(state, action)

Buc
if next state is goal: return solution
frontier.add(next state)
• Time complexity (# nodes generated)?
return failure
• 𝑂 𝑏𝑚
• Space complexity?
• 𝑂 𝑏𝑚
• Complete? No, when depth is infinite or can go back and forth (loops)
• Optimal? No
How do we handle infinite depth? 54
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

55
Depth-limited Search (DLS)
Depth limit l = 2

• Limit the search depth Sib

• Backtrack once the

Rim Fag
depth limit is reached

Pit Sib Sib Buc

• Time complexity (# nodes expanded)?

• 𝑏0 + 𝑏1 + ⋯ + 𝑏𝑙 = 𝑂(𝑏𝑙 )
How do we know the depth of the solution? • Space complexity?
• 𝑂 𝑏𝑙
We don’t know :( • Complete? No
• Optimal? No
56
Iterative Deepening Search (IDS)
Depth limit l = 0

• Do depth-limited search Sib

with max depth 0 … ∞

• Return solution if found
• Increase the depth
otherwise

57
Iterative Deepening Search (IDS)
Depth limit l = 1

• Do depth-limited search Sib

with max depth 0 … ∞

• Return solution if found Rim Fag

• Increase the depth

otherwise

58
Iterative Deepening Search (IDS)
Depth limit l = 2

• Do depth-limited search Sib

with max depth 0 … ∞

• Return solution if found Rim Fag

• Increase the depth

Pit Sib Sib
otherwise Buc

59
Iterative Deepening Search (IDS)
Depth limit l = 2

• Do depth-limited search Sib

with max depth 0 … ∞

• Return solution if found Rim Fag

• Increase the depth

Pit Sib Sib
otherwise Buc

• Time complexity (# nodes generated)?

Overhead! • 𝑏0 + 𝑏0 + 𝑏1 + ⋯ + 𝑏0 + ⋯ + 𝑏𝑑
• = 𝑑 + 1 𝑏0 + 𝑑𝑏1 + 𝑑 − 1 𝑏2 + ⋯ + 2𝑏𝑑−1 + 𝑏𝑑 = 𝑂(𝑏𝑑 )
• Space complexity?
• 𝑂 𝑏𝑑
• Complete? Yes
• Optimal? Yes, if step cost is the same everywhere 60
Iterative Deepening Search (IDS)
For b=10, d=5,
• 𝑁𝐷𝐿𝑆 = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
• 𝑁𝐼𝐷𝑆 = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Overhead = (123,456 - 111,111)/111,111 = 11%

61
Backward Search
Buc
Search from the goal

Pit Fag

Rim Buc
Sib Sib Buc

62
Bidirectional Search Forward:

Sib
Combine search:
• Forward (from the start)
Rim Fag
• Backward (from the goal)
Backward:

Buc
Stop when two searches meet

Pit Fag
Intuition:
2 × 𝑂 𝑏 𝑑/2 < 𝑂(𝑏 𝑑 ) Issues?
• Operators need to be reversible • How to efficiently check
• Many goal states if a node appears in the
other search tree?63
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

64
Dealing with Repeated States
• Remember states that Sib

are already visited

• Don’t visit again Rim Fag

Pit Sib Sib Buc

65
Tree Search Keep track of visited states Graph Search
(use hashtable/dictionary!)
create frontier create frontier
create visited
insert initial state insert initial state to frontier and visited
while frontier is not empty: while frontier is not empty:
state = frontier.pop() state = frontier.pop()
for action in actions(state): for action in actions(state):
next state = transition(state, action) next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution if next state is goal: return solution
frontier.add(next state) frontier.add(next state)
visited.add(next state)
return failure return failure
66
Graph Search #1 Graph Search #2
create frontier • Expand less states create frontier • Expand more states
• May skip states with less cost • Will not skip states with less cost
create visited create visited
insert initial state to frontier and visited insert initial state to frontier
while frontier is not empty: while frontier is not empty:
state = frontier.pop() state = frontier.pop()
for action in actions(state): if state is goal: return solution
next state = transition(state, action) if state in visited: continue
if next state in visited: continue visited.add(state)
if next state is goal: return solution for action in actions(state):
frontier.add(next state) next state = transition(state, action)
visited.add(next state) frontier.add(next state)
return failure return failure
What’s the difference? There are other variations as well…
67
BFS with Graph Search
create frontier : queue
create visited
insert initial state to queue and visited
while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

68
BFS with Graph Search
create frontier : queue
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

Queue: Visited:

Sib Sib

69
 BFS with Graph Search
create frontier : queue
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

Queue: Visited:

Sib Rim Fag Sib Rim Fag

70
 BFS with Graph Search
create frontier : queue
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib
.

if next state in visited: continue

if next state is goal: return solution
Visited!
frontier.add(next state)
(not added to the queue)
visited.add(next state)
return failure

Queue: Visited:

Rim Fag Pit Sib Rim Fag Pit

71
 BFS with Graph Search
create frontier : queue
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib
. Sib
,
Buc
if next state in visited: continue
if next state is goal: return solution Visited!
frontier.add(next state) (not added to the queue)
visited.add(next state)
return failure

Queue: Visited:

Fag Pit Buc Sib Rim Fag Pit Buc

72
 BFS with Graph Search
create frontier : queue
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib Sib Buc
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

Queue: Visited:

Fag Pit Buc Sib Rim Fag Pit Buc

73
DFS with Graph Search
create frontier : stack
create visited
insert initial state to queue and visited
while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

74
DFS with Graph Search
create frontier : stack
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

Stack: Visited:

Sib Sib

75
DFS with Graph Search
create frontier : stack
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
visited.add(next state)
return failure

Stack: Visited:

Sib Fag Rim Sib Rim Fag

76
DFS with Graph Search
create frontier : stack
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib
.

if next state in visited: continue

if next state is goal: return solution
Visited!
frontier.add(next state)
(not added to the stack)
visited.add(next state)
return failure

Stack: Visited:

Fag Rim Pit Sib Rim Fag Pit

77
DFS with Graph Search
create frontier : stack
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib
.

if next state in visited: continue

if next state is goal: return solution
frontier.add(next state)
Buc Rim.

visited.add(next state)
return failure Visited!
(not added to the stack)
Stack: Visited:

Fag Pit Buc Sib Rim Fag Pit Buc

78
DFS with Graph Search
create frontier : stack
Sib
create visited
insert initial state to queue and visited
while frontier is not empty:
Rim Fag
state = frontier.pop()
for action in actions(state):
next state = transition(state, action)
Pit Sib
if next state in visited: continue
if next state is goal: return solution
frontier.add(next state)
Buc Rim
Sib
visited.add(next state)
return failure

Stack: Visited:

Fag Pit Buc Sib Rim Fag Pit Buc

79
Choosing a Search Strategy
Depends on the problem:
• Number of goal states
• Distribution of goal states in search tree
• Finite/infinite branching factor/depth
• Repeated states
• Need for optimality?
• Need to know if there is no solution?

80
Summary: Uninformed Search Algorithms
• Search algorithms
• Breadth-first search – queue, explore layer by layer
• Uniform-cost search – priority queue (path cost)
• Depth-first search – stack, go deep first then backtrack
• Variants:
• Depth limited search – limit max depth of the search
• Iterative deepening search – try DLS with depth limit 0, …, N
• Bidirectional search – search from the start and the goal, meet in the middle
• Dealing with repeated states
• Graph search – don’t visit nodes that are already visited

81
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

82
 2
3 1 2
Informed Search Algorithms 3
2 2

Uninformed search: 1 1
Sib
Search blindly 1 2
3 0
Rim Fag

Informed search: 2 1 2
2
Use domain information Pit Sib

to guide the search 2 1 1 3

Rim Buc

2 0

83
 2
3 1 2
Best-first Search 3
Evaluation function f(n): 2 2
create frontier : priority queue f(n)
estimate the “goodness” of a state

1 1
insert initial state Sib
while frontier is not empty:
state = frontier.pop() 3 0
if state is goal: return solution Rim Fag

for action in actions(state):

2 2
Pit Sib
next state = transition(state, action)
frontier.add(next state)
1 3
return failure
Rim Buc

Special cases: 2 0
• Greedy best-first search
• A* search
84
 2
3 1 2
Greedy Best-first Search 3
Evaluation function f(n): 2 2
create frontier : priority queue f(n)
estimate the “goodness” of a state

1 1
insert initial state Sib
while frontier is not empty:
state = frontier.pop() 3 0
if state is goal: return solution Rim Fag

for action in actions(state):

2 2
Pit Sib
next state = transition(state, action)
frontier.add(next state)
1 3
return failure
Rim Buc • Time complexity (# nodes expanded)?
• 𝑂 𝑏𝑚 , good heuristic gives improvement
f(n) = h(n) • Space complexity?
2 0
Heuristic: estimated cost from n to goal • 𝑂 𝑏𝑚 , keep all nodes in memory
• Complete?
85
 2
0 1 2
Greedy Best-first Search Anomaly!
3
Evaluation function f(n): 2 2
create frontier : priority queue f(n)
estimate the “goodness” of a state

1 1
insert initial state Sib
while frontier is not empty:
state = frontier.pop() 0 0
if state is goal: return solution Rim Fag

for action in actions(state):

2 2
Pit Sib
next state = transition(state, action)
frontier.add(next state)
return failure
1 0 …
• Time complexity (# nodes expanded)?
• 𝑂 𝑏𝑚 , good heuristic gives improvement
f(n) = h(n) • Space complexity?
Heuristic: estimated cost from n to goal • 𝑂 𝑏𝑚 , keep all nodes in memory
• Complete? No
Doesn’t consider the cost so far! • Optimal? No
86
 2
3 1 2
A* Search 3
Evaluation function f(n): 2 2
create frontier : priority queue f(n)
estimate the “goodness” of a state

1 1
insert initial state Sib
while frontier is not empty: 1 2
state = frontier.pop() 3 0
if state is goal: return solution Rim Fag

for action in actions(state): 2 3

1+2
1 2+2 2
1+2+1 Pit Sib Buc Sib
next state = transition(state, action)
frontier.add(next state) 2 1 1+1+3 2+3+0 2+2+3
return failure
Rim Buc • Time complexity (# nodes expanded)?
• 𝑂 𝑏𝑚 , good heuristic gives improvement
f(n) = g(n) + h(n)
1+2+2+2 1+2+1+0 • Space complexity?
• 𝑂 𝑏𝑚 , keep all nodes in memory
Cost so far to reach n Heuristic: estimated cost from n to goal • Complete? Yes
• Optimal? Yes*
87
Admissible Heuristics
ℎ𝑆𝐿𝐷 (𝑆𝑖𝑏𝑖𝑢)
2
A heuristic h(n) is admissible if for every
1
node n, h(n) ≤ h*(n), where h*(n) is the
true cost to reach the goal state from n.
3
An admissible heuristic never over- 2
estimates the cost to reach the goal, i.e., 1
it is a conservative estimate.
Example: ℎ𝑆𝐿𝐷 (𝑛) never overestimates
the actual road distance
Theorem: if h(n) is admissible, A* using
tree search is optimal

88
Admissible Heuristics: Optimality
Suppose some suboptimal goal 𝐺2 has been generated and is in the fringe. Let n be an
unexpanded node in the fringe such that n is on a shortest path to an optimal goal 𝐺.

𝑓 𝐺 =𝑔 𝐺 +ℎ 𝐺 =𝑔 𝐺 +0
𝑓 𝐺2 = 𝑔 𝐺2 + ℎ 𝐺2 = 𝑔 𝐺2 + 0
𝑔 𝐺2 > 𝑔(𝐺) since 𝐺2 is suboptimal
𝑓 𝐺2 > 𝑓(𝐺)

ℎ 𝑛 ≤ ℎ∗ (𝑛) since ℎ is admissible

𝑓 𝑛 = 𝑔 𝑛 + ℎ 𝑛 ≤ 𝑔 𝑛 + ℎ∗ 𝑛 = 𝑓(𝐺)

𝑓 𝑛 ≤ 𝑓 𝐺 < 𝑓 𝐺2 , 𝐺2 will never be expanded

89
Consistent Heuristics
A heuristic h(n) is consistent if for every node n, every successor n' of n
generated by any action a, h(n) ≤ c(n,a,n') + h(n’), and h(G) = 0.

If h is consistent, we have
f(n’) = g(n') + h(n’)
= g(n) + c(n,a,n') + h(n’)
≥ g(n) + h(n) = f(n)
i.e., f(n) is non-decreasing along any path

Theorem: If h(n) is consistent, A* using graph search is optimal

90
Consistent Heuristics: Optimality

A * expands nodes in order of increasing f-cost

Gradually adds "f-contours" of nodes
Contour 𝑖 has all nodes with 𝑓 = 𝑓 (𝑖) , where 𝑓 (𝑖) < 𝑓 (𝑖+1)
91
Dominance
If ℎ2 𝑛 ≥ ℎ1 (𝑛) for all n, then ℎ2 dominates ℎ1 .
ℎ2 is better for search.

Heuristics
• ℎ1 number of misplaces tiles
• ℎ2 total Manhattan distance

ℎ2 dominates ℎ1
If each tile is at most one distance away from
the goal, then ℎ2 = ℎ1 , otherwise ℎ2 > ℎ1

92
“Inventing” Admissible Heuristics
A problem with fewer restrictions on the actions is called a relaxed
problem. The cost of an optimal solution to a relaxed problem is an
admissible heuristic for the original problem.
Original:
A tile can only move to adjacent blank

Relaxations:
• Each tile can move anywhere
• ℎ1 number of misplaces tiles
• Each tile can move to any adjacent square
• ℎ2 total Manhattan distance

93
Outline
• Problem-solving agents
• Search algorithms
• Uninformed search algorithms
• Breadth-first Search (BFS)
• Uniform-cost search
• Depth-first Search (DFS)
• Variants of uninformed search algorithms
• Depth-limited search
• Iterative deepening search
• Bidirectional search
• Dealing with repeated states
• Informed search algorithms
• Greedy best-first search
• A* search
• Heuristics
• Variants of A*

94
Variants of A*
• Iterative Deepening A* (IDA*)
• Use iterative deepening search
• Cutoff using f-cost [ f(n) = g(n) + h(n) ] instead of depth
• Simplified Memory-bounded A* (SMA*)
• Drop the nodes with worst f-cost if memory is full

95
Summary: Informed Search Algorithms
• Informed search: guide search with domain information
• Best-first search
• Greedy best-first search
• f(n) = h(n), heuristic estimate of cost from n to goal
• A* search
• f(n) = g(n) + h(n), cost so far + heuristic
• Heuristics
• Admissible: h(n) ≤ h*(n)
• Consistent: h(n) ≤ c(n,a,n') + h(n’)
• Dominant: if h1(n) ≤ h2(n), h2 dominant
• Creating admissible heuristic: true cost of the relaxed problem
• A* variants: IDA*, SMA*
• Idea: prune to save memory

96
Summary
• Problem-solving agents
• Uninformed search algorithms
• Breadth-first Search (BFS) – layer by layer
• Uniform-cost search – Djikstra
• Depth-first Search (DFS) – go deep first
• Variants of uninformed search algorithms
• Depth-limited search – set max depth
• Iterative deepening search – try DLS with depth limit 0, …, N
• Bidirectional search – combine forward and backward search
• Dealing with repeated states – visit state only once
• Informed search algorithms
• Greedy best-first search – f(n) = h(n)
• A* search – f(n) = g(n) + h(n)
• Heuristics: admissibility, consistency, dominance
• Variants of A*: IDA*, SMA*

97
Coming Up Next Week
• Local search
• Hill climbing
• Simulated annealing
• Beam search
• Genetic algorithms
• Adversarial search
• Games vs search problems
• Minimax
• Alpha-beta pruning

98
To Do
• Lecture Training 2
• +100 Free EXP
• +50 Early bird bonus
• Problem Set 0
• Due Saturday, 27th January

99