CPSC 322: Introduction to
Artificial Intelligence
Lecture 04: Introduction to Search
Mehrdad Oveisi
Adapted from slides by Cristina Conati, Giuseppe Carenini,
Varada Kolhatkar, and Jordon Johnson
1
Big Picture – CPSC 322
Environment
Problem Deterministic Stochastic
Variables + Constraints
Constraint Search
Satisfaction Arc Consistency
Static Local Search
Logics Bayesian (Belief) Networks
Query
Search Variable Elimination
STRIPS Decision Networks
Sequential Planning
Search Variable Elimination
Representation
Reasoning Technique
2
What is Search?
3
Search: Sample A* Applications
• An Efficient A* Search Algorithm For Statistical Machine Translation. (2001)
• The Generalized A* Architecture. Journal of Artificial Intelligence Research (2007)
• applied to Machine Vision
• Factored A*search for models over sequences and trees. International Conference on AI
(2003)
• applied to NLP and BioInformatics
• Finding shortest paths on real road networks: the case for A*. International Journal of
Geographical Information Science (2009)
• Humanoid robot path planning and rerouting using A-Star search algorithm. IEEE
International Conference on Signals and Systems (2019)
• Active balancing of lithium-ion batteries using graph theory and A-star search
algorithm. IEEE Transactions on Industrial Informatics (2020)
• A Pipe Routing Hybrid Approach Based on A-Star Search and Linear Programming.
International Conference on Integration of Constraint Programming, Artificial
Intelligence, and Operations Research (2021) 4
Today’s Class: Learning Goals
• Identify real-world examples that make use of deterministic,
goal-driven planning agents
• Assess the size of the search space of a given search problem.
• Trace through/implement a generic search algorithm.
5
Lecture Overview
• Simple agent and examples
• Search space graph
• Search procedure
6
Simple Planning Agent
• Deterministic, goal-driven (planning) agent
• initially in a start state
• given a goal (subset of the possible states)
• Environment changes only when the agent acts
• Agent perfectly knows
• what actions can be applied in any given state
• the state it will end up in when it takes an action
• The sequence of actions (in the proper order) is the solution
7
Three Examples
• A delivery robot planning the route it will take to get from one
room to another within a building
• Solving an 8-puzzle
• Automated vacuum cleaner
8
Delivery Robot
9
8-Puzzle
States: specify which number (or the blank) occupies each of 9 tiles
How many states? A: 89 B: 29 C: 99 D: 9! E: 42
10
8-Puzzle
States: specify which number (or the blank) occupies each of 9 tiles
Actions: blank moves up/down/left/right
Goal: configuration with numbers in desired locations
11
Vacuum Cleaner
Possible start state Possible end state
States:
How many possible states?
• Two rooms (r1 and r2)
• Each room can be either dirty or not 2x2
• Agent (the vacuum) can be in either r1 or r2 2 So, 23
Actions: move left, move right, clean
Goal: agent in either room with both rooms clean 12
Vacuum Cleaner
Suppose we have the same problem with k rooms.
The number of states is…
clean dirty dirty clean clean clean dirty clean dirty dirty
agent
A. kk
B. k+2k
C. k*2k
D. 2*kk
E. Never mind, I’ll just clean the rooms myself
13
Lecture Overview
• Simple agent and examples
• Search space graph
• Search procedure
14
Finding a Solution
How can we find a sequence of actions (in the appropriate ordering)
that lead to the goal?
• Define underlying search space graph where nodes (or vertices)
are states and arcs (or edges) are actions
b4 o113 r113
o107 o109 o111
r107 r109 r111
15
Search Space: 8-puzzle
• Only a tiny fraction of the
search space is shown here
• Actions are reversible, so
there should be twice as
many edges…
16
Search Space: Vacuum Cleaner
Entire search
space
• States: dirty/clean, robot location
• Actions: left (L), right (R), clean (S)
• Possible goal test: every room clean 17
Lecture Overview
• Simple agent and examples
• Search space graph
• Search procedure
18
Search: Abstract Definition
HOW TO SEARCH
• Start at the start state
• Consider the effects of different actions from
states that have been encountered in the
search so far
• Stop when a goal state is encountered
To make this more formal, we’ll need to review
the formal definition of a graph
19
Search: Graph Definition
• A graph consists of a set N of nodes (vertices)
and a set A of ordered pairs of nodes, called arcs (edges).
• Node n2 is a neighbor of n1 if there is an arc from n1 to n2.
That is, if <n1, n2> ϵ A.
• A path is a sequence of nodes n0, n1,.., nk such that <ni-1, ni> ϵ A.
• A cycle is a path with two or more nodes such that
the start node is the same as the end node.
• A directed acyclic graph (DAG) is a graph with no cycles and
where the arcs have associated directions.
• Given a start node and goal nodes,
a solution is a path from a start node to a goal node.
20
Search: Solution Example
• Start state b4, goal state r113
• Solution: <b4, o107, o109, o113, r113>
b4 o113 r113
o107 o109 o111
r107 r109 r111
21
Generic Search Algorithm
Inputs:
• a graph
• a start node s
• Boolean procedure goal(n) to test if n is a goal
frontier <-- [<s>]
while frontier is not empty
select and remove path <no,….,nk> from frontier
if goal(nk)
return <no,….,nk>
for every neighbor n of nk
add <no,….,nk, n> to frontier
return NULL
In-class activity: trace through and figure out the algorithm
• What is frontier? ➢ Collection of paths; like a ToDo list
• How can you get different kinds of search from this? ➢ Use different data structures 22
Generic Search Algorithm
• Given a graph, a start node, and goal node(s),
incrementally explore paths from the start node
• Maintain a frontier of paths
from the start node that have been explored
• As the search proceeds, the frontier expands into the
unexplored nodes until (hopefully!) a goal node is encountered
• The way in which the frontier is expanded
defines the search strategy
23
Generic Search Algorithm
ends of
paths on frontier
start node
explored paths
unexplored paths
24
Generic Search Algorithm
Inputs:
• a graph
• a start node s
• Boolean procedure goal(n) to test if n is a goal
frontier <-- [<s>]
while frontier is not empty
select and remove path <no,….,nk> from frontier
if goal(nk)
return <no,….,nk>
for every neighbor n of nk
add <no,….,nk, n> to frontier
return NULL
Exercise: Consider the given graph, the start node S and the goal node X.
Assume frontier is a stack (last in, first out).
What is the path returned? What nodes are visited? 25
Branching Factors
• The (forward) branching factor of a node is the number of arcs
going out of the node
• The backward branching factor of a node is the number of arcs
going into the node
• If the forward branching factor of any node n is b and the graph
is a tree, how many nodes are m steps away from n?
A. b*m B: bm C: mb D: m/b E: None of these
26
Lecture Summary
• Search is a key computational mechanism in many AI agents
• We will study the basic principles of search
using the simple deterministic planning agent model
• Generic search approach:
• define a search space graph
• start from current state
• incrementally explore paths
from current state until goal state is reached.
• The way in which the frontier is expanded defines the search
strategy
27
Up Next
• Uninformed Search Strategies
• Practice Exercise 3.A
• http://www.aispace.org/exercises.shtml
28
