Introduction to AI  Week 8
Search
Represent a search problem as:
 a state space that contains all possible
configurations, (with start state and goal state)
 a set of operators for manipulating states
 start state and goal
state (or a goal test)
 path costs for measuring the cost going along a path
The Blocks World
Blocks World: classical planning scenario:
blocks that stand on a table or stand on top of each other or are hold
by a robot hand (mutual relationship disregarded otherwise) and can be
manipulated by a robot hand
Description by predicates of the form
Ontable(x) 
x stands on the table 
On(x,y) 
x stands on y 
Clear(x) 
nothing stands on x 
Handempty 
robot hand is empty 
Holds(x) 
robot hand holds x 
Ontable(A)
Ontable(B)
On(D,A)
On(C,D)
Clear(C)
Clear(B)
Handempty
What is a "Search Problem"?
Planning problem is
given by initial state & goal state, e.g., goal:
Ontable(B)
Ontable(C)
On(D,B)
On(A,D)
Clear(A)
Clear(C)
Handempty
For this transition are certain operators available. In blocks
world
PICKUP(x) 
picking up x from the table 
PUTDOWN(x) 
putting down x on the table 
STACK(x,y) 
putting x on y 
UNSTACK(x,y) 
picking up x from y 
Formalise operators!
Find plan
Operators of the Blocks World
 
 
 
PICKUP(x)
preconditions 
Clear(x) 

Ontable(x) 

Handempty 
delete list 
Clear(x) 

Ontable(x) 

Handempty 
add list 
Holds(x) 

PUTDOWN(x)
preconditions 
Holds(x) 
delete list 
Holds(x) 
add list 
Clear(x) 

Ontable(x) 

Handempty 

 
 
 
STACK(x,y)
preconditions 
Holds(x) 

Clear(y) 
delete list 
Holds(x) 

Clear(y) 
add list 
Clear(x) 

On(x,y) 

Handempty 

UNSTACK(x,y)
preconditions 
Clear(x) 

On(x,y) 

Handempty 
delete list 
Clear(x) 

On(x,y) 

Handempty 
add list 
Holds(x) 

Clear(y) 

 
 
 
General search algorithm
function generalsearch(problem,insert) > solution
;;; insert is a function to determine, where to
;;; insert the nodes which are newly expanded
insertionfunction(init(problem)) > nodes
while not null(nodes) or not goaltest(problem)(node)
do
first(nodes) > node
insert(nodes,expand(node,operators(problem))) > nodes
remove(node,nodes) > nodes
od
if null(nodes) then failure
else node > solution
Breadthfirst search
Breadthfirst is given by:
insert appends the new nodes to the end of nodes
Example:
Breadthfirst search finds optimal solutions
implemented as Queue ("First in First Out")
An Example for Breadthfirst search
Depthfirst search
Depthfirst is given by:
insert inserts the new nodes at the front of nodes
Example: (assume no expansion possible when no successor)
Depthfirst search can fail to find solutions
implemented as Stack ("Last in First Out")
An Example for Depthfirst search
Depth Limited Depth First
As depth first, but do not generate nodes deeper in the tree than an a
priori fixed limit.
If there is no solution within limit l, then no solution will be found.
Iterative Deepening
 DepthLimited Search has the main advantage that the search process
can't descend forever (in a branch without solution).
 However, it will not find a solution if all
solutions require a depth greater than the limit.
 To overcome this problem (and to maintain the advantages of
depth limited depth first search), one has introduced a form in
which the limit is increased if there is no solution of a limit l.
That is, choose initially l=1, iteratively increase
l by 1, and perform on each level Depth Limited Depth
First search until a solution is found.
BiDirectional Search
In bidirectional search, start the process simultaneously from the
initial start and backwards from the goal state, in order to reduce
the complexity.
The shaded area corresponds to the search effort
Avoiding Repeated States
The safest way to avoid any repeated states is to store all states
visited and compare each node whether it has been visited
before. If yes, don't add it. The problem with this strategy
is that firstly you have to store all states visited (space) and make
many comparisons (time). Cheaper (albeit incomplete) forms are:
 Do not return to the state you came from.
That is, do not generate a node that is equal to your parent.
 Do not create cycles.
That is, do not generate a node that is equal to any of your ancestors.
Heuristic Search
Assume a heuristic function h such that h(n) is the
estimated cost of the cheapest path from the state at node n to a
goal state.
In bestfirstsearch the insertion function orders the nodes
with respect to some measure.
function
BestFirstSearch(problem,evalfunction) > solution
;;; input: a problem and an evaluation function
function orders nodes by evalfunction > queuefunction
generalsearch(problem,queuefunction) > solution
Greedy Search and A^{*}Search
greedysearch: insert best nodes at beginning of nodes
according to h, that is,
function GreedySearch(problem) > solution
;;; input: a problem
bestfirstsearch(problem,h) > solution
A^{*}search: insert best nodes at beginning
of nodes
according to f=g+h with g
actual cost to that node, h estimated cost to the goal. In the A^{*}
algorithm the heuristic function h must be optimistic in order to
find the best solution.
function Astar(problem) > solution
;;; input: a problem
bestfirstsearch(problem,g+h) > solution
Example
Assume you wanted to search for the shortest path from Arad to
Bucharest (taken from [RussellNorvig 2003])
Task: Find path from Arad to Bucharest
Heuristic: Air distance
Town 
Air Dist. 
Arad 
366 
Bucharest 
0 
Craiova 
160 
Dobreta 
242 
Eforie 
161 
Fagaras 
176 
Giurgiu 
77 
Hirsova 
151 
Iasi 
226 
Lugoj 
244 
Mehadia 
241 
Neamt 
234 
Oradea 
380 
Pitesti 
100 
Rimnicu Vilcea 
193 
Sibiu 
253 
Timisoara 
329 
Urziceni 
80 
Vaslui 
199 
Zerind 
374 
Greedy Search in the Example
Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu?
Take as heuristic the air distance:
Zerind (374), Timisoara (329), or Sibiu (253)
Closest air distance Sibiu, hence go to Sibiu. Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea?
Take as heuristic the air distance:
Arad (366), Fagaras (176), Oradea (380), or Rimnicu Vilcea (193)
Closest air distance Fagaras, hence go to Fagaras.
Possibilities from Fagaras: Go to Sibiu or Bucharest?
Take as heuristic the air distance:
Sibiu (253) or Bucharest (0)?
Closest air distance Bucharest, hence go to Bucharest.
That is 140km +99km +211km = 450km .
Greedy Search in the Example (Cont'd)
A^{*}Search in the Example
Possibilities from Arad: Go to Zerind, Timisoara, or Sibiu?
Take as heuristic the air distance plus cost to town:
Zerind (374+75=449), Timisoara
(329+118=447), or
Sibiu (253+140=393)
Most promising Sibiu, hence explore going to Sibiu. Possibilities from Sibiu: Arad, Fagaras, Oradea, or Rimnicu Vilcea?
Take as heuristic the air distance plus cost to town:
Arad (140+140+366=646), Fagaras (140+99+176=415), Oradea (140+151+380=671), or Rimnicu Vilcea (140+80+193=413)
Overall most promising not expanded Rimnicu Vilcea, hence
explore going to Rimnicu Vilcea
A^{*}Search in the Example (Cont'd)
Possibilities from Rimnicu Vilcea: Sibiu, Pitesti, or Craiova?
Take as heuristic the air distance plus cost to town:
Sibiu (140+80+80+253=553), Pitesti (140+80+97+100=417), or Craiova (140+80+146+160=526)
Overall most promising not expanded Fagaras, hence
explore going to Fagaras (from Sibiu) Possibilities from Fagaras: Sibiu, or Bucharest?
Take as heuristic the air distance plus cost to town:
Sibiu (140+99+99+253=591), or Bucharest (140+99+211+0=450)
Overall most promising not expanded Pitesti, hence
explore going to Pitesti (from Rimnicu Vilcea)
A^{*}Search in the Example (Cont'd)
Possibilities from Pitesti: Rimnicu Vilcea, Craiova, or Bucharest?
Take as heuristic the air distance plus cost to town:
Rimnicu Vilcea (140+80+97+97+193=607),
Craiova (140+80+97+138+160=615) or
Bucharest (140+80+97+101+0=418)
Overall most promising go to Bucharest from
Pitesti. Since there is no way to get on a shorter route to Bucharest the last
one is taken.
A^{*}Search in the Example (Cont'd)
Properties of the A^{*}Algorithm
 Restriction on h: the heuristic function h may never
overestimate the cost to reach the goal (such a heuristic is called
admissible.
Example: h as air distance is an optimistic
estimate for a travel distance.
 If h is admissible, then f=g+h is as well.
 Along any path from the root, the fcost never decreases, that
is f is monotonic
 If h is admissible, the search tree is finitely branching
(and there is a solution), then the A^{*}algorithm
finds an optimal solution
HillClimbing and Simulated Annealing
 Hill climbing is a search method, in which the next node to
expand, is the node with the highest value of the nodes generated
from the expansion of the current node.
 Problems with hillclimbing:
 local maxima (algorithm misses the total maximum)
 plateaux (the evaluation function is flat and is not
informative)
 ridges (saddle shaped area, oscillation, without finding the
way further up may happen)
 Solutions:
 Random restart hillclimbing
 Simulated annealing: Allow for bad moves as well (that is,
moves that lead downhill), where the probability of such a move
decreases exponentially with its badness. With decreasing
temperature T, bad moves become less and less likely.
Heuristics in the Blocksworld
Problem: Find a heuristic function h for estimating how far the
current state is from goal state:
 differences in Ontable(x) considered
particularly high
 differences in Handempty and Holds(x)
very low
 Optimally, the differences for On(x,y) would be
considered the more the lower in a tower x and y are
In the extreme case, the heuristic function exactly knows what to do.
Then there is no search, but we have an algorithmic procedure.
Properties of Some Search Algorithm
 Completeness: solution will eventually be found if there
is one at all
 Optimality: does it find the highestquality solution when
there are several
 Time complexity: time to find a solution as function of
the complexity of the problem
 Space complexity: how much memory is necessary for the
search as function of the complexity of the problem
Properties of Search Algorithms (Cont'd)

Breadthfirst 
Depthfirst 
Greedy 
A^{*} 
 
 
 
Complete 
Yes 
No 
No 
Yes 
Optimal 
Yes 
No 
No 
Yes 
Time 
exponential 
exponential 
exponential 
exponential 
Space 
exponential 
linear 
linear 
exponential 
Further Reading
 S. Russell, P. Norvig. Artificial Intelligence  A
Modern Approach. 2nd Edition, Pearson Education,
2003. Chapters 3 & 4.
 Judea Pearl: Heuristics  Intelligent Search Strategies
for Computer Problem Solving, AddisonWesley,
1984. Reading, Massachusetts.
© Manfred Kerber, 2004, Introduction to AI
24.4.2005
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l8.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/