Solving problems by searching
The theory and technology of building agents that can
plan ahead to solve problems.
CS 370 1
Example - Navigation Problem
Given a map, pick the best route from start
state to the goal state.
Assumptions
Environment is Fully observable
State space Known
Environment is Discrete
Environment is Deterministic
Environment is static
CS 370 2
Example: Romania
CS 370 3
Problem formulation
A problem is defined by five items:
1. initial state e.g., "at Arad”
2. Actions A description of possible actions. Given a state s, Actions(s)
returns set of actions that can be executed in s
3. Transition Model: A description of what action does. Specified by a function
Result(s,a) that returns the state that results from doing action a in state s.
4. Goal test Determines whether a given state is a goal. goaltest(s)-> T|F
5. path cost
e.g., sum of distances, number of actions executed, etc.
c(s,a,ś) is the step cost, assumed to be ≥ 0
A solution is a sequence of actions leading from the initial state to a
goal state
Set of all states is called state space
CS 370 4
Example: Romania
Frontier
Explored set
Unexplored set
CS 370 5
Tree Search Algorithm
Tree-search (problem p) returns path
frontier = {path(p.initial)}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
if goaltest(s); return path
for a in p.action(s)
add [path+p.result(s,a)]to frontier
CS 370 6
Example: Romania – Tree Search
CS 370 7
Tree search example
CS 370 8
Tree search example
CS 370 9
Tree search example
CS 370 10
Graph Search Algorithm
Tree -search (problem p) returns path
frontier = {path(p.initial)}, explored = {}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
if goaltest(s); return path
for a in p.action(s)
frontier.push([path+p.result(s,a)])
CS 370 11
Graph Search Algorithm
Graph-search (problem p) returns path
frontier = {path(p.initial)}, explored = {}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
add s to explored list
if goaltest(s); return path
for a in p.action(s)
if p.result(s,a)] not in explored list:
frontier.update([path+p.result(s,a)])
CS 370 12
Graph Search Algorithm
Graph-search (problem p) returns path
frontier = {path(p.initial)}, explored = {}
loop:
if frontier is empty; return fail
path = frontier.pop()
s = path.end
add s to explored list Different Search Strategies
if goaltest(s); return path differ in the way elements are
for a in p.action(s) removed from the frontier
if p.result(s,a)] not in explored list:
frontier.update([path+p.result(s,a)])
CS 370 13
Search strategies
A search strategy is defined by order of paths are removed
from the frontier.
Strategies are evaluated along the following dimensions:
completeness: does it always find a solution if one exists?
time complexity: How long does it take to find solution?
space complexity: How much memory is needed to perform search?
optimality: does it 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 ∞)
CS 370 14
Uninformed search strategies
Uninformed search strategies use only the
information available in the problem
definition
Breadth-first search (Uses Queue)
Uniform-cost search (Uses Priority Queue)
Depth-first search (Uses Stack)
CS 370 15
Breadth-first search
The BFS begins at the initial state/node s,
and inspects all the neighboring nodes. Then
for each of those neighbor nodes in turn, it
inspects their neighbor nodes which were
unvisited, and so on.
CS 370 16
Breadth-first search
Implementation:
Use FIFO queue to implement frontier, i.e.,
paths are removed based on first in first out.
CS 370 17
Breadth-first search
CS 370 18
Breadth-first search
CS 370 19
Breadth-first search
CS 370 20
Properties of breadth-first search
Complete? Yes (if b is finite)
Optimal? Yes (if cost = 1 per step)
CS 370 21
Properties of breadth-first search
Time? 1+b+b2+b3+… +bd + bd+1 = O(bd+1)
Imagine searching a uniform tree where every state has “b”
successors. The root of the search tree generates “b” nodes at the first
level, each of which generates “b” more nodes, for a total of “b2” at the
second level. Each of these generates “b” more nodes, yielding “b3”
nodes at the third level, and so on. Now suppose that the solution is at
depth “d”. In the worst case, it is the last node generated at that level.
Then the total number of nodes generated is
If the algorithm were to apply the goal test to nodes when selected for
expansion, rather than when generated, the whole layer of nodes at
depth d would be expanded before the goal was detected and the time
complexity would be O(bd+1).
CS 370 22
Properties of breadth-first search
Complete? Yes (if b is finite)
Optimal? Yes (if cost = 1 per step)
Time? 1+b+b2+b3+… +bd + bd+1 = O(bd+1)
Space? O(bd+1) (keeps every node in memory)
Space is the bigger problem
Time and space complexity is given for tree search
CS 370 23
Breadth-first search
CS 370 24
Uniform-cost search
Expand least-cost unexpanded node
Implementation:
Use priority queue = queue ordered by path cost
Equivalent to breadth-first if step costs all equal
CS 370 25
Example: Romania – Uniform Cost
The goal is to get from Sibiu to Bucharest.
The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99.
The least-cost node, Rimnicu Vilcea, is expanded.
Next, adding Pitesti with cost 80 + 97=177. The least-cost node is now Fagaras, so it
is expanded, adding Bucharest with cost 99+211=310. Now a goal node has been
generated.
BUT uniform-cost search keeps going, choosing Pitesti for expansion and adding a
second path to Bucharest with cost 80+97+101= 278.
Now the algorithm checks to see if this new path is better than the old one; it is, so
the old one is discarded. Bucharest, now with g-cost 278, is selected for expansion
and the solution is returned.
CS 370 26
Properties: Uniform Cost Search
Complete? Yes, if step cost greater than small
positive constant
Optimal? Yes – nodes expanded in the order of
increasing path cost
Time? O(b1+ceiling(C*/ ε)) where C* is the cost of the
optimal solution, and ε is the least cost an action
can have
Space? O(b1+ceiling(C*/ ε))
Time and space complexity is given for tree search
CS 370 27
Depth-first search
Expand longest unexpanded node
Implementation:
Use LIFO queue to implement frontier, i.e., paths are
removed from frontier based on Last in first out.
CS 370 28
Depth-first search
Expand longest/deepest unexpanded node
CS 370 29
Depth-first search
Expand deepest unexpanded node
CS 370 30
Depth-first search
Expand deepest unexpanded node
CS 370 31
Depth-first search
Expand deepest unexpanded node
CS 370 32
Depth-first search
Expand deepest unexpanded node
CS 370 33
Depth-first search
Expand deepest unexpanded node
CS 370 34
Depth-first search
Expand deepest unexpanded node
CS 370 35
Depth-first search
Expand deepest unexpanded node
CS 370 36
Depth-first search
Expand deepest unexpanded node
CS 370 37
Depth-first search
Expand deepest unexpanded node
CS 370 38
Depth-first search
Expand deepest unexpanded node
CS 370 39
Properties of depth-first search
Complete? No: fails in infinite-depth spaces, spaces
with loops
complete in finite spaces
Optimal? No
Time? O(bm): terrible if m is much larger than d
Space? O(bm) for tree-search, i.e., linear space!
For graph-search space complexity is same as BFS
CS 370 40
Summary of algorithms
CS 370 41
Informed search algorithms
Outline
• Best-first search
• Greedy best-first search
• A* search
CS 370 42
Best-first search
Idea: use an evaluation function f(n) for each node as
estimate of "desirability”
Expand most desirable unexpanded node
Implementation:
Order the nodes in priority Queue in decreasing order of
desirability
Special cases:
greedy best-first search
A* search
CS 370 43
Romania with step costs in km
CS 370 44
Greedy best-first search
Evaluation function f(n) = h(n) (heuristic)
f(n)= estimate of cost from node n to goal
e.g., hSLD(n) = straight-line distance from n
to Bucharest
Greedy best-first search expands the node
that appears to be closest to goal
CS 370 45
Romania with step costs in km
CS 370 46
Greedy best-first search example
CS 370 47
Greedy best-first search example
CS 370 48
Greedy best-first search example
CS 370 49
Greedy best-first search example
CS 370 50
Properties of greedy best-first search
Complete?
Tree search: No – can get stuck in loops, e.g.,
Iasi Neamt Iasi Neamt
Graph search: yes in finite spaces
Time? O(bm),
Space? O(bm) -- keeps all nodes in memory
Optimal? No
CS 370 51
A* search
Idea: combine uniform-cost and greedy
best-first search
Evaluation function f(n) = g(n) + h(n)
g(n) = cost so far to reach n
h(n) = estimated cost from n to goal
f(n) = estimated total cost of path through n
to goal
CS 370 52
Romania with step costs in km
CS 370 53
A* search example
CS 370 54
A* search example
CS 370 55
A* search example
CS 370 56
A* search example
CS 370 57
A* search example
CS 370 58
A* search example
CS 370 59
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: hSLD(n) (never overestimates the actual road
distance)
Theorem: If h(n) is admissible, A* using TREE-
SEARCH is optimal
CS 370 60
Consistent heuristics
A heuristic 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')
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
Consistent heuristic is also admissible 61
Properties of A*
Complete? Yes
Time? Exponential
Space? Keeps all nodes in memory
Optimal? Yes
CS 370 63
CS 370 64
Summary
Problem formulation usually requires abstracting away real-
world details to define a state space that can feasibly be
explored
Uninformed search strategies
Informed search strategies
Problem-solving by searching works when environment is:
fully observable
Discrete
Deterministic
static
CS 370 65
Example 1
SEECS - Fall 2017 CS 370 66
Example 2
You have moved to a new city and are trying to learn how to get
from your home at S to the train station at T. Some streets have
more traffic than others. Your friend who has lived in this city for
a long time provides you with information about the
traffic on each street – the streets are labeled with costs, in the
form of how many minutes it will take you to traverse each one.
You also have access to a distance heuristic, which tells you the
estimated distance from each node to T. The distance is
written above or below each node.
>>>In all search problems, use alphabetical order to break ties
when deciding the
priority to use for removing paths from frontier.
>>>Use Graph Search for all questions.
Q1: Use Breadth First Search to find the path from S to T. (1)
Draw the part of the
search tree that is explored by the search. (2) List in order all
nodes/states inserted
into the explored list.
Q2: Use A* to find the path from S to T. (1) Draw the part of the
search tree that is
explored by the search. (2) List in order all nodes/states inserted
into the explored
list.
SEECS - Fall 2017 CS 370 67
SEECS - Fall 2017 CS 370 68
