Chapter 3
Solving problems by searching
Search
We will consider the problem of designing goal-based
agents in observable, deterministic, discrete,
known environments
The solution is a fixed sequence of actions
Search is the process of looking for the sequence of actions that
reaches the goal
Once the agent begins executing the search solution, it can ignore
its percepts (open-loop system)
2 compiled by Tomas U (Msc In IT)
Search problem components
Initial state Initial
state
Actions
Transition model
What is the result of
performing a given action
in a given state?
Goal state
Path cost
Assume that it is a sum of Goal
nonnegative step costs state
The optimal solution is the sequence of actions that gives the lowest
path cost for reaching the goal
3 compiled by Tomas U (Msc In IT)
Example: Romania
• On vacation in Romania; currently in Arad
• Flight leaves tomorrow from Bucharest
Initial state
Arad
Actions
Go from one city to another
Transition model
If you go from city A to
city B, you end up in city B
Goal state
Bucharest
Path cost
4 SumbyofTomas
compiled edgeU (Msc
costsIn IT)
State space
The initial state, actions, and transition model define the state space
of the problem
The set of all states reachable from initial state by any sequence of actions
Can be represented as a directed graph where the nodes are states and
links between nodes are actions
What is the state space for the Romania problem?
5 compiled by Tomas U (Msc In IT)
Example: Vacuum world
States
Agent location and dirt location
How many possible states?
What if there are n possible locations?
Actions
Left, right, suck
Transition model
6 compiled by Tomas U (Msc In IT)
Vacuum world state space graph
7 compiled by Tomas U (Msc In IT)
Example: The 8-puzzle
States
Locations of tiles
8-puzzle: 181,440 states
15-puzzle: 1.3 trillion states
24-puzzle: 1025 states
Actions
Move blank left, right, up, down
Path cost
1 per move
Optimal solution of n-Puzzle is NP-hard
8 compiled by Tomas U (Msc In IT)
Example: Robot motion planning
States
Real-valued coordinates of robot joint angles
Actions
Continuous motions of robot joints
Goal state
Desired final configuration (e.g., object is grasped)
Path cost
Time to execute, smoothness of path, etc.
9 compiled by Tomas U (Msc In IT)
Other Real-World Examples
Routing
Touring
VLSI layout
Assembly sequencing
Protein design
10 compiled by Tomas U (Msc In IT)
Tree Search
Let’s begin at the start node and expand it by making a list of all
possible successor states
Maintain a fringe or a list of unexpanded states
At each step, pick a state from the fringe to expand
Keep going until you reach the goal state
Try to expand as few states as possible
11 compiled by Tomas U (Msc In IT)
Search tree
Starting
“What if ” tree of possible actions and state
outcomes Action
The root node corresponds to the starting Successor
state state
The children of a node correspond to the
successor states of that node’s state
…
A path through the tree corresponds to a
sequence of actions ………
A solution is a path ending in the goal state
Goal state
12 compiled by Tomas U (Msc In IT)
Tree Search Algorithm Outline
Initialize the fringe using the starting state
While the fringe is not empty
Choose a fringe node to expand according to search strategy
If the node contains the goal state, return solution
Else expand the node and add its children to the fringe
13 compiled by Tomas U (Msc In IT)
Tree search example
14 compiled by Tomas U (Msc In IT)
Tree search example
15 compiled by Tomas U (Msc In IT)
Tree search example
Fringe
16 compiled by Tomas U (Msc In IT)
Search strategies
A search strategy is defined by picking the order of node
expansion
Strategies are evaluated along the following dimensions:
Completeness: does it always find a solution if one exists?
Optimality: does it always find a least-cost solution?
Time complexity: number of nodes generated
Space complexity: maximum number of nodes in memory
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 length of any path in the state space (may be infinite)
17 compiled by Tomas U (Msc In IT)
Uninformed search strategies
Uninformed search strategies use only the information available in
the problem definition
Breadth-first search
Uniform-cost search
Depth-first search
Iterative deepening search
18 compiled by Tomas U (Msc In IT)
Breadth-first search
Expand shallowest unexpanded node
Implementation:
fringe is a FIFO queue, i.e., new successors go at end
B C
D E F G
19 compiled by Tomas U (Msc In IT)
Breadth-first search
Expand shallowest unexpanded node
Implementation:
fringe is a FIFO queue, i.e., new successors go at end
B C
D E F G
20 compiled by Tomas U (Msc In IT)
Breadth-first search
Expand shallowest unexpanded node
Implementation:
fringe is a FIFO queue, i.e., new successors go at end
B C
D E F G
21 compiled by Tomas U (Msc In IT)
Breadth-first search
Expand shallowest unexpanded node
Implementation:
fringe is a FIFO queue, i.e., new successors go at end
B C
D E F G
22 compiled by Tomas U (Msc In IT)
Breadth-first search
Expand shallowest unexpanded node
Implementation:
fringe is a FIFO queue, i.e., new successors go at end
B C
D E F G
23 compiled by Tomas U (Msc In IT)
Properties of breadth-first search
Complete?
Yes (if branching factor b is finite)
Optimal?
Yes – if cost = 1 per step
Time?
Number of nodes in a b-ary tree of depth d: O(bd)
(d is the depth of the optimal solution)
Space?
O(bd)
Space is the bigger problem (more than time)
24 compiled by Tomas U (Msc In IT)
Uniform-cost search
Expand least-cost unexpanded node
Implementation: fringe is a queue ordered by path cost (priority queue)
Equivalent to breadth-first if step costs all equal
Complete?
Yes, if step cost is greater than some positive constant ε
Optimal?
Yes – nodes expanded in increasing order of path cost
Time?
Number of nodes with path cost ≤ cost of optimal solution (C*), O(bC*/ ε)
This can be greater than O(bd): the search can explore long paths consisting of small
steps before exploring shorter paths consisting of larger steps
Space?
O(bC*/ ε)
25 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
26 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
27 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
28 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
29 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
30 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
31 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
32 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
33 compiled by Tomas U (Msc In IT)
Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
B C
D E F G
34 compiled by Tomas U (Msc In IT)
Properties of depth-first search
Complete?
Fails in infinite-depth spaces, spaces with loops
Modify to avoid repeated states along path
complete in finite spaces
Optimal?
No – returns the first solution it finds
Time?
Could be the time to reach a solution at maximum depth m: O(bm)
Terrible if m is much larger than d
But if there are lots of solutions, may be much faster than BFS
Space?
O(bm), i.e., linear space!
35 compiled by Tomas U (Msc In IT)
Iterative deepening search
Use DFS as a subroutine
1. Check the root
2. Do a DFS searching for a path of length 1
3. If there is no path of length 1, do a DFS searching for a path
of length 2
4. If there is no path of length 2, do a DFS searching for a path
of length 3…
36 compiled by Tomas U (Msc In IT)
Iterative deepening search
37 compiled by Tomas U (Msc In IT)
Iterative deepening search
38 compiled by Tomas U (Msc In IT)
Iterative deepening search
39 compiled by Tomas U (Msc In IT)
Iterative deepening search
40 compiled by Tomas U (Msc In IT)
Properties of iterative deepening
search
Complete?
Yes
Optimal?
Yes, if step cost = 1
Time?
(d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
Space?
O(bd)
41 compiled by Tomas U (Msc In IT)
Informed search
Idea: give the algorithm “hints” about the desirability of
different states
Use an evaluation function to rank nodes and select the most
promising one for expansion
Greedy best-first search
A* search
42 compiled by Tomas U (Msc In IT)
Heuristic function
Heuristic function h(n) estimates the cost of reaching goal from
node n
Example:
Start state
Goal state
43 compiled by Tomas U (Msc In IT)
Heuristic for the Romania problem
44 compiled by Tomas U (Msc In IT)
Greedy best-first search
Expand the node that has the lowest value of the heuristic
function h(n)
45 compiled by Tomas U (Msc In IT)
Greedy best-first search example
46 compiled by Tomas U (Msc In IT)
Greedy best-first search example
47 compiled by Tomas U (Msc In IT)
Greedy best-first search example
48 compiled by Tomas U (Msc In IT)
Greedy best-first search example
49 compiled by Tomas U (Msc In IT)
Properties of greedy best-first search
Complete?
No – can get stuck in loops
start
goal
50 compiled by Tomas U (Msc In IT)
Properties of greedy best-first search
Complete?
No – can get stuck in loops
Optimal?
No
51 compiled by Tomas U (Msc In IT)
Properties of greedy best-first search
Complete?
No – can get stuck in loops
Optimal?
No
Time?
Worst case: O(bm)
Best case: O(bd) – If h(n) is 100% accurate
Space?
Worst case: O(bm)
52 compiled by Tomas U (Msc In IT)
A* search
Idea: avoid expanding paths that are already expensive
The evaluation function f(n) is the estimated total cost of the
path through node n to the goal:
f(n) = g(n) + h(n)
g(n): cost so far to reach n (path cost)
h(n): estimated cost from n to goal (heuristic)
53 compiled by Tomas U (Msc In IT)
A* search example
54 compiled by Tomas U (Msc In IT)
A* search example
55 compiled by Tomas U (Msc In IT)
A* search example
56 compiled by Tomas U (Msc In IT)
A* search example
57 compiled by Tomas U (Msc In IT)
A* search example
58 compiled by Tomas U (Msc In IT)
A* search example
59 compiled by Tomas U (Msc In IT)
Properties of A*
Complete?
Yes – unless there are infinitely many nodes with f(n) ≤ C*
Optimal?
Yes
Time?
Number of nodes for which f(n) ≤ C* (exponential)
Space?
Exponential
60 compiled by Tomas U (Msc In IT)
Admissible heuristics
A heuristic h(n) is admissible if for every node n, h(n) ≤
h*(n), where h*(n) is the true cost to reach the goal state
from n
An admissible heuristic never overestimates the cost to
reach the goal, i.e., it is optimistic
Example: straight line distance never overestimates the
actual road distance
Theorem: If h(n) is admissible, A* is optimal
61 compiled by Tomas U (Msc In IT)
Designing heuristic functions
Heuristics for the 8-puzzle
h1(n) = number of misplaced tiles
h2(n) = total Manhattan distance (number of squares from desired
location of each tile)
h1(start) = 8
h2(start) = 3+1+2+2+2+3+3+2 = 18
62 Are h1 and
compiled h2 Uadmissible?
by Tomas (Msc In IT)
Comparison of search strategies
Time Space
Algorithm Complete? Optimal?
complexity complexity
Yes If all step O(bd) O(bd)
BFS
costs are equal
UCS Yes Yes Number of nodes with g(n) ≤ C*
DFS No No O(bm) O(bm)
If all step O(bd)
IDS Yes O(bd)
costs are equal
Worst case: O(bm)
Greedy No No
Best case: O(bd)
63
A*
compiled by Tomas U (MscYes
In IT) Yes Number of nodes with g(n)+h(n) ≤ C*