Artificial Intelligence

DITI 3113
Uniformed Search I
Dr. Zahriah binti Sahri
szahriah@utem.edu.my
 Lesson Outcomes
• Understand the theory of uninformed search

• Recognize the different uninformed search algorithms

• Apply these search algorithms to solve real-world problems

 Outlines
1. Problem to Solve
2. Problem Formulation
3. Search Algorithms
4. Uninformed Search Algorithms
5. Breadth First Search
6. Depth First Search
7. Repeated States
 Problem To Solve
• Traveler problem - find a route from one city (Lubok China) to the other
city (Bandar Melaka)
Lubok China
Simpang Empat
Tebong
15 10
Kuala Linggi 12
14
Alor Gajah
11 Machap

Kuala Sungai 11 15
14
Baru 6 Masjid Tanah
25
12 9 Durian Tunggal
Pengkalan
Balak 10 8
21
Sungai Udang
Batu Berendam Ayer Keroh
9 8
7 Bemban
12
13
Tanjung Keling 14
Bandar Melaka 10
20
Kandang 14

Merlimau
 Problem to Solve
• Planning problem– how can a farmer get the fox, the chicken
and the grain across safely?

A Farmer has to get a Fox, a Chicken and a

sack of Grain across a river. He has a rowboat
and it can carry him and one other thing.

If fox and chicken leave together, the fox will

eat the chicken. If chicken and corn are left
together, chicken will eat the corn.
 Problem to Solve
• 8-Puzzle problem – find a sequence of tile movements that
leads from a starting configuration to a goal configuration.
•
.
 Problem to Solve
• 4-Queens Problem – how to place four queens on a chessboard
such that no queen attacks any other

Start Goal
 More Problems to Solve
• Route finding
– (computer networks, airline travel planning system, …)
• Touring (traveling salesman)
– (package delivery, automatic drills, ….)
• VLSI layout problems
– (VLSI layout, furniture layout, packaging, …)
• Assembly sequencing
– (assembly of electric motors, …)
• Task scheduling
– (manufacturing, timetables)
 Problem Formulation
• These problems can be formulated as follows:
1. Initial state – starting state
2. Goal state – ending state
3. State space – all states reachable from the initial state by any sequence of
actions
4. Action – valid move to go/transform from one state to another
5. Path - sequence through state space
6. Path cost - function that assigns a numerical cost to a path. Cost of a path is
the sum of costs of individual actions along the path. Denoted as g
7. Goal test – determines whether a given state is a goal state
8. Solution – path from the initial state to the goal state
9. Optimal solution has the lowest path cost among all solutions
 Problem Formulation
• More on state space:-
– Before a search problem can be solved it must be represented as a
state space. The state space is then searched to find a solution to the
problem. A state space essentially consists of a set of nodes
representing each state of the problem, arcs between nodes
representing the legal moves from one state to another, an initial
state and a goal state. Each state space takes the form of a tree or a
graph.
 Problem Formulation
• More on state
– A state is
• Refer uninformed_search.pdf
 Problem Formulation
• Example of a state space (Graph) representation for Traveler
problem:- Lubok China
Simpang Empat
Tebong
15 10
Kuala Linggi 12
14
Alor Gajah
11 Machap

Kuala Sungai 11 15
14
Baru 6 Masjid Tanah
25
12 9 Durian Tunggal
Pengkalan
Balak 10 8
21
Sungai Udang
Batu Berendam Ayer Keroh
9 8
7 Bemban
12
13
Tanjung Keling 14
Bandar Melaka 10
20
Kandang 14

Merlimau
 Problem Formulation
• Example of a state space (Tree) representation for Traveler
problem:- Lubok China

Kuala Sungai Baru Masjid Tanah

Kuala Linggi Lubok China Pengkalan Lubok China Sungai Udang Alor Gajah
Balak
Batu
Kuala Sungai Baru Pengkalan Berendam Durian
Kuala Sungai Udang Balak
Masjid Tanjung Keling Tunggal
Sungai Baru
Tanah
Simpang Alor Batu Ayer
Empat Gajah Berendam Keroh Machap
Masjid
Tanah Alor Gajah

Sungai Udang Durian Tebong Bemban

Bandar Melaka
Tunggal

Machap
Sungai Bandar Ayer Durian
Udang Melaka Keroh Tunggal
Kandang Machap Merlimau

Bandar Batu Durian

Melaka Berendam Tunggal
Kandang Bemban

Bandar Bemban Merlimau

Melaka
 Problem Formulation
• Traveler problem can be formulated as follows:
i. Initial state – at Lubok China
ii. Goal state – at Bandar Melaka
iii. State space –all cities reachable from Lubok China by any sequence of actions
iv. Action – “drive a car from Lubok China to Masjid Tanah”, “take a taxi from Tanjung Keling”
are some valid actions
v. Path – {Lubok China , Masjid Tanah, Sungai Udang} and {Lubok China, Kuala Sungai Baru,
Pengkalan Bakak, Sungai Udang} are some path examples
vi. Path Cost – g{Lubok China , Masjid Tanah, Sungai Udang} = 33km is a path cost example
vii. Solution – {Lubok China , Masjid Tanah, Sungai Udang, Tanjung Keling, Bandar Melaka} is a
possible solution
viii. Optimal solution – {Lubok China , Masjid Tanah, Sungai Udang, Tanjung Keling, Bandar
Melaka}
 Problem Formulation
• 4-Queens problem can be formulated as follows:
i. Initial state –
ii. Goal state –
iii. State space –all possible configurations of the queens
iv. Action – move a queen left, right, up, down
v. Path – not important
vi. Path Cost – 1 per move
vii. Solution –
viii. Optimal solution – NP-hard

Start Goal
 Problem Formulation: an Exercise
• 8-Puzzle problem can be formulated as follows:
i. Initial state – ??
ii. Goal state – ??
iii. State space – ??
iv. Action – ??
v. Path – not important
vi. Path Cost – depends on the distance metric used
vii. Solution –??
viii. Optimal solution – NP-hard
 Problem Formulation : an Exercise
• Planning problem can be formulated as follows:
i. Initial state – ??
ii. Goal state – ??
iii. State space – ??
iv. Action – ??
v. Path – not important
vi. Path Cost – number of river crossings
vii. Solution – ??
viii. Optimal solution – ??
How Artificial Intelligence Solves These Problems?
 Search Algorithms
• What is a search algorithm?
– in Artificial Intelligence, a search algorithm, is an algorithm that
evaluates all or several sequence of actions (possible solutions) and
choosing one that achieves the desired goal.
– for some problems, each sequence of actions may be associated with
a certain cost. A search algorithm that aims not only reaching the
goal but doing so at a minimal cost is also an optimization algorithm
 Search Algorithms
• The fundamental idea of a search algorithm:-
– at any given moment it is in some state s
– s will usually offer several possible actions
– choose one action to explore first
– keep s and the other actions to explore later, in case the first one
does not deliver
– action-selection is determined by a search strategy
– it pictures a search tree of states, expanding outwards from the initial
state of the problem
http://teaching.csse.uwa.edu.au/units/CITS3001/lectures/lectures/05UninformedSearch.pdf
 Search Algorithms
• The general algorithm

http://teaching.csse.uwa.edu.au/units/CITS3001/lectures/lectures/05UninformedSearch.pdf
 Search Algorithms
• What is a search strategy?
– A search strategy is defined by picking the order of node expansion

– Search strategies are evaluated along the following dimensions:

• Completeness: does the strategy always find a solution (if one exists)?.
• Time complexity: number of nodes generated. How long does the strategy take to find a solution?.
• Space complexity: maximum number of nodes in memory. How much memory is needed to conduct the search?.
• Optimality: does the strategy always find a least-cost solution?

– Time and space complexity are measured in terms of

• b: maximum branching factor of the search tree
• d: depth of the least-cost solution
• m: maximum depth of the state space (may be ∞)
 Search Algorithms
• Search strategies are evaluated along the following
dimensions:
– Completeness: does the strategy always find a solution (if one exists)?.
– Time complexity: number of nodes generated. How long does the strategy take to find a
solution?.
– Space complexity: maximum number of nodes in memory. How much memory is needed to
conduct the search?.
– Optimality: does the strategy always find a least-cost solution?

– Time and space complexity are measured in terms of

• b: maximum branching factor of the search tree
• d: depth of the least-cost solution
• m: maximum depth of the state space (may be ∞)
Search Algorithms

Search
Algorithms

Uninformed Informed
Search Search
 Uninformed Search Algorithms
• Characteristics of uninformed search:-
– While searching you have no clue whether one non-goal state is
better than any other.
– Your search is blind. You don’t know if your current exploration is
likely to be fruitful.
– Uses only the information available in the problem definition.

27
Some of the Uninformed Search Algorithms

Uninformed
Search

Iterative
Best First Depth First Depth Limited Bidirectional
Deepening Uniform Cost
Search Search Search Search
Search
 What to Search?
A Start
• Search a path from A to N
B C

D E F G H

I J K L M N O P
Goal

Q R S T U V W X

Y Z
 Assumptions
• Search algorithms always choose the left branch of a search
tree first when there is a choice.
• Alphabetical ordering is the second choice when left-to-right
branching produces tie-up
• Search algorithms avoid repeated states ( nodes that have
been expanded/generated)
 Notations
• Generated/Unexpanded node

• Expanded node

• Terminated node
 Frontier
• Frontier is the list of nodes that have been generated but have
not been expanded
• Also called fringe

Source of image: https://www.cs.ubc.ca/~mack/CS322/lectures/2-Search2.pdf

 Breadth-First Search
• The strategy:-
– Expand the shallowest unexpanded node in the frontier i.e., root
node is expanded first, then all the successors of the root node are
expanded next, then their successors, and so on.

Source of image: http://ai.berkeley.edu/lecture_slides.html/Lecture2: Uninformed Search

 Breadth-First Search
• The implementation:-
– Frontier is a first-in-first-out (FIFO) queue, i.e., new successors go at
the end of the frontier successor list.
– The goal test is applied to each node when it is generated.
– Repeated states are always avoided.
 Breadth-First Search
• The algorithm:-

Source : https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
 Breadth-First Search
1. Frontier = {A}. A is not goal. Expands A
• The search begins:- 2. Frontier = {B,C}. Both are not goals. Both are equally
shallowest. B is chosen for expansion based on left to right
branching
3. Frontier = {C,D,E,F}. D,E,F are not goals. C is the shallowest.
A Expands C
4. Frontier = {D,E,F,G,H}. G,H are not goals. All equally
B C shallowest. Expands D
5. Frontier = {E,F,G,H,I}. I is not goal. E, F,G,H are equally
shallowest. Expands E
D E F G H 6. Frontier = {F,G,H,I,J,K,L}. J,K,L are not goals. F, G, H are
equally shallowest. Expands F
7. Frontier = {G,H,I,J,K,L}. G, H are equally shallowest. Expands G
I J K L M N 8. Frontier = {H,I,J,K,L,M,N}. Goal N is generated. Stop the search
Goal
9. Traversed path = {ABCDEFGMN}
10. Solution path = {ACGN}
 Breadth-First Search
• The properties
– Complete?
• Yes it always reaches goal (if b is finite)

– Time Complexity?
• 1 + b + b2 + … + bd + b(bd-1) = O(bd+1)
• exponential in d

– Space Complexity
• O(bd+1)
• Keeps every node that aspires to be extended to a goal node in memory

– Optimal?
• Yes (if cost is 1 per step); not optimal in general
 Breadth-First Search
• Suitable to use when:-
– you know a goal node is not far from the root of the tree
– if the tree is very deep and solution paths are rare.
– computing memory is huge
– can quickly discard unlikely paths
 Testing Your Understanding
• Find the traversed path and the solution path from S to G using
Breadth First Search :-
 Depth First Search
• The strategy:-
– expands the deepest unexpanded node in the current frontier of the
search tree

Source of image: http://ai.berkeley.edu/lecture_slides.html/Lecture2: Uninformed Search

 Depth First Search
• The implementation:-
– Frontier is a last-in-first-out (LIFO) queue, i.e., new successors go to
the beginning of the frontier successor list.
– The goal test is applied to each node when it is selected for expansion
– Repeated states are avoided when graph search is used
– Repeated states exists when tree search is used
 Depth-First Search
• The algorithm:-

Source : https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/
 Depth First Search
• The search begins:-
1. Frontier = {A}. A is not goal, expands A
A 2. Frontier = {B,C}. Both are equally deepest. B is chosen for
expansion based on left to right branching and B is not goal
B C 3. Frontier = {D,E,F,C}. D,E,F are equally deepest. D is not the goal,
expands D
4. Frontier = {I,E,F,C}. I is the deepest. I is not the goal, expands I
D E F
5. Frontier = {Q,R,E,F,C}. Q,R are equally deepest. Q is not the goal,
expands Q

I J K L 6. Frontier = {R,E,F,C}. R is the deepest. R is not the goal, expands R

7. Frontier = {E,F,C}. E, F are equally deepest. E is not the goal,
expands E
Q R 8. Frontier = {J,K,L,F,C}. J,K,L are equally deepest. J is not the goal,
expands J
 Depth First Search
• The search begins:-
A 9. Frontier = {S,K,L,F,C}. S is the deepest. S is not the goal,
expands S

B C 10. Frontier = {K,L,F,C}. K,L are equally deepest. K is not the goal,
expands K
11. Frontier = {L,F,C}. L is the deepest. L is not the goal, expands L
D E F 12. Frontier = {T,U,F,C}. T, U are equally deepest. T is not the goal,
expands T
13. Frontier = {U,F,C}. U is the deepest. U is not the goal,
I J K L expands U
14. Frontier = {F,C}. F is the deepest. F is not the goal, expands F

Q R S T U 15. Frontier = {C}. C is not the goal, expands C

 Depth First Search
• The search begins:-
A 16. Frontier = {G,H}. G,H are equally deepest. G is not the goal,
expands G
B C 17. Frontier = {M,N,H}. M, N are equally deep. M is not the goal,
expands M
18. Frontier = {V,N,H}. V is the deepest. V is not the goal,
D E F G H expands V
19. Frontier = {Y,Z,N,H}. Y,Z are equally deepest. Y is not the goal,
expands Y
20. Frontier = {Z,N,H}. Z is the deepest. Z is not the goal, expands
I J K L M N Goal Z
21. Frontier = {N,H}. N is the deepest. But N is the goal. Stop the
Q R S T U V search
22. Traversed path = {ABDIQREJSKLTUFCGMVYZN}
23. Solution path = {ACGN}
Y Z
 Depth-First Search
 The properties
– Complete?
• No: fails in infinite-depth spaces
– Time Complexity?
• O(bm) with m = maximum depth
– Space Complexity
• O(bm), i.e., linear space!
• only need to remember a single path + expanded unexplored nodes
– Optimal?
• No (It may find a non-optimal goal first)
 Depth First Search
• Suitable to use when:-
– d, the depth level of the goal node is known
– space (memory) is restricted
– there are many possible solutions with long paths and wrong paths
are usually terminated quickly
– search can be fine-tuned quickly
 Testing Your Understanding
• Find the traversed path and the solution path from S to G using
Depth First Search :-
When to use Breadth First Search vs. Depth First Search?
The search graph has cycles or is infinite?
BFS DFS
We need the shortest path to a solution
BFS DFS
There are only solutions at great depth
BFS DFS
There are some solutions at shallow depth
BFS DFS
No way the search graph will fit into memory
BFS DFS
 Repeated states
• States that have already been expanded before somewhere
else on the search tree.
• Failure to detect repeated states can turn a linear problem into
an exponential one!
• Examples of repeated states:-
S

B
B C
S

C S B S
C
State Space Search Tree

50
 Avoiding Repeated States
1. Do not return to the state you have just come from.
2. Do not put explored states on the frontier again.
3. Every time a node is added to the frontier, check whether it
already exists in the frontier with a higher path cost, and if
yes, replace that node with the new one.
4. Do not add nodes that are on the path from the root
― avoids paths containing cycles (loops)
5. Do not add parent of a node as a leaf