Introduction to AI
AAPP002-4-2 Ver 1.0
Uninformed Search
Topic & Structure of The Lesson
• Uninformed Search
• Breadth First Search
• Depth First Search
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 2 of 24
Learning Outcomes
• At the end of this topic, You should be
able to
• Introduction to Uninformed Search
• State Space
• Breadth first Search
• Depth first search
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 3 of 24
Key Terms You Must Be Able To
Use
• If you have mastered this topic, you should be able to use the
following terms correctly in your assignments and exams:
• Root
• Branch
• Breadth first search
• Depth first search
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 4 of 24
Intro: Search and AI
• In solving problems,
– possible actions our robot can do,
– possible moves in a chess game,
• Many problems can be formalised in a general way as search
problems.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 5 of 24
Search Techniques
• Construction of a simple search tree
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 6 of 24
Single-state problem formulation
A problem is defined by four items:
1. initial state
2. actions or successor function
3. goal test,
4. path cost (additive)
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 7 of 24
Search and Problem Solving
• Search problems described in terms of:
– An initial state.
– A target state.(
– Some possible actions, that get you from one state to
another.
• Search techniques systematically consider all possible
action sequences to find a path from the initial to target
state.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 8 of 24
Simple Example
• Easiest to first look at simple examples based on searching for route
on a map.
School Factory
Hospital Newsagent
Library church
Park University
• How do we systematically and exhaustively search possible routes, in order
to find, say, route from library to university?
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 9 of 24
Search Space
• The set of all possible states reachable from the initial state defines the
search space.
• We can represent the search space as a tree.
library
school hospital
park newsagent
factory
university church
• We refer to nodes connected to and “under” a node in the tree as
“successor nodes”.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 10 of 24
Simple Search Techniques
• How do we search this tree to find a possible route from
library to University?
• May use simple systematic search techniques, which try
every possibility in systematic way.
• Breadth first search - Try shortest paths first.
• Depth first search - Follow a path as far as it goes, and
when reach dead end, backup and try last encountered
alternative.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 11 of 24
Breadth first search
• Explore nodes in tree order: library, school, hospital, factory, park,
newsagent, uni, church. (conventionally explore left to right at each level)
library
school hospital
park newsagent
factory
university church
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 12 of 24
Depth first search
• Nodes explored in order: library, school, factory, hospital, park, newsagent,
university
library
school hospital
park newsagent
factory
university church
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 13 of 24
Algorithms for breadth first and depth
first search.
• Very easy to implement algorithms to do these kinds of search.
• Both algorithms keep track of the list of nodes found, but for which
routes from them have yet to be considered.
– E.g., [school, hospital] -have found school and hospital in tree,
but not yet considered the nodes connected to these.
• List is sometimes referred to as an agenda. But implemented using
stack for depth first, queue for breadth first.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 14 of 24
Algorithm for breadth first
• Start with queue = [initial-state] and found=FALSE.
• While queue not empty and not found do:
– Remove the first node N from queue.
– If N is a goal state, then found = TRUE.
– Find all the successor nodes of N, and put them on
the end of the queue.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 15 of 24
Algorithm for depth first
• Start with stack = [initial-state] and found=FALSE.
• While stack not empty and not found do:
– Remove the first node N from stack.
– If N is a goal state, then found = TRUE.
– Find all the successor nodes of N, and put them on the top of the
stack.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 16 of 24
Extensions to basic algorithm
• Loops: What if there are loops (ie, we are search a graph)? How do
you avoid (virtually) driving round and round in circles?
– Algorithm should keep track of which nodes have already been
explored, and avoid redoing these nodes.
• Returning the path: How do you get it to actually tell you what the
path it has found is!
– One way: Make an item on the agenda be a path, rather than a
node.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 17 of 24
Robot planning problem
• Consider pet robot (or not very intelligent flat-mate) in small flat with
two rooms. You and your robot are in room1, your beer is in room 2,
the door is closed between the rooms.
• Actions:
– move(robot, Room, AnotherRoom)
– open(robot, door)
– pickup(robot, Object).
• Initial state:
– in(robot, room1) etc.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 18 of 24
Robot planning search tree
Me
Rob Beer
Robit opens door Robot picks up Me
Me Me
Rob Beer Rob Beer
Robot moves to next room
Me Rob Etc etc
Beer
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 19 of 24
Heuristic search algorithms
• Depth first and breadth first search turn out to be too inefficient for
really complex problems.
• Instead we turn to “heuristic search” methods, which don’t search
the whole search space, but focus on promising areas.
• Simplest is best first search. We define some “heuristic evaluation
function” to say roughly how close a node is to our target.
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 20 of 24
Quick Review Question
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 21 of 24
Summary of Main Teaching Points
• Best-first search is general search where
the minimum-cost nodes (according to
some measure) are expanded first.
• Greedy search uses minimal estimated
cost h(n) to the goal state as measure.
This reduces the search time, but the
algorithm is neither complete nor optimal
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 22 of 24
Question and Answer Session
Q&A
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 23 of 24
What we will cover next
• Informed Search
AAPP002-4-2 Introduction to Artificial Intelligence Uninformed Search Slide 24 of 24
