Intelligent Systems
Search Methods
Outline
 Motivation
 Technical Solution
 Uninformed Search
 DepthFirst Search
 BreadthFirst Search
 Informed Search
 BestFirst Search
 Hill Climbing
 A*
 Illustration by a Larger Example
 Extensions
 Summary
MOTIVATION
Problem Solving as Search
Motivation
 One of the major goals of AI is to help humans in solving complex tasks
 How can I fill my container with pallets?
 Which is the shortest way from Milan to Innsbruck?
 Which is the fastest way from Milan to Innsbruck?
 How can I optimize the load of my freight to maximize my revenue?
 How can I solve my Sudoku game?
 What is the sequence of actions I should apply to win a game?
 Sometimes finding a solution is not enough, you want the optimal solution according to some “cost” criteria
 All the example presented above involve looking for a plan
 A plan that can be defined as the set of operations to be performed of an initial state, to reach a final state that is considered the goal state
 Thus we need efficient techniques to search for paths, or sequences of actions, that can enable us to reach the goal state, i.e. to find a plan
 Such techniques are commonly called Search Methods
Examples of Problems: Towers of Hanoi

Move disk to peg
to the initial state ((123)()()) a new state is reached ((23)()(1))

Examples of Problems: Blocksworld


TECHNICAL SOLUTION
Search Methods
Search Space Representation




Search Space Representation

Example: Towers of Hanoi*
* A partial tree search space representation
Example: Towers of Hanoi*
* A complete direct graph representation
[http://en.wikipedia.org/wiki/Tower_of_Hanoi]
Search Methods
 A search method 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?
 time complexity: number of nodes generated
 space complexity: maximum number of nodes in memory
 optimality: does it always find the shortest path solution?
 Time and space complexity are measured in terms of
 b: maximum branching factor of the search tree
 d: depth of the shortest path solution
 m: maximum depth of the state space (may be ∞)
Search Methods
 Uninformed techniques
 Systematically search complete graph, unguided
 Also known as brute force, naïve, or blind
 Informed methods
 Use problem specific information to guide search in promising directions
UNINFORMED SEARCH
Brute force approach to explore search space
Uninformed Search
 A class of general purpose algorithms that operates in a brute force way
 The search space is explored without leveraging on any information on the problem
 Also called blind search, or naïve search
 Since the methods are generic they are intrinsically inefficient
 E.g. Random Search
 This method selects randomly a new state from the current one
 If the goal state is reached, the search terminates
 Otherwise the methods randomly select an other operator to move to the next state
 Prominent methods:
 DepthFirst Search
 BreadthFirst Search
 UniformCost Search
DepthFirst Search
 DepthFirst Search (DFS) begins at the root node and exhaustively search each branch to it maximum depth till a solution is found
 The successor node is selected going in depth using from right to left (w.r.t. graph representing the search space)
 If greatest depth is reach with not solution, we backtrack till we find an unexplored branch to follow
 DFS is not complete
 If cycles are presented in the graph, DFS will follow these cycles indefinitively
 If there are no cycles, the algorithm is complete
 Cycles effects can be limited by imposing a maximal depth of search (still the algorithm is incomplete)
 DFS is not optimal
 The first solution is found and not the shortest path to a solution
 The algorithm can be implemented with a Last In First Out (LIFO) stack or recursion
DepthFirst Search: Algorithm
List open, closed, successors={};
Node root_node, current_node;
insertfirst(
root_node,open)
while notempty (open );

current_node= removefirst(open);
insertfirst ( current_node,closed);
if ( goal (current_node)) return current_node;
else

successors=
successorsOf
(current_node);
for(x in successors)
 if(
notin
(x,closed))
insertfirst
(x,open);
N.B.= this version is not saving the path for simplicity
DepthFirst Search: Example
DepthFirst Search: Example
Result is: S>A>B>F
DepthFirst Search: Complexity
=1 + b + b^{2}+ ......... + b^{m} = O (b ^{m} )



BreadthFirst Search
 BreadthFirst Search (BFS) begins at the root node and explore levelwise al the branches

BFS is complete
 If there is a solution, BFS will found it

BFS is optimal
 The solution found is guaranteed to be the shortest path possible
 The algorithm can be implemented with a First In First Out (FIFO) stack
BreadthFirst Search: Algorithm
List open, closed, successors={};
Node root_node, current_node;
insertlast(
root_node,open)
while notempty (open );

current_node= removefirst(open);
insertlast ( current_node,closed);
if ( goal (current_node)) return current_node;
else

successors=
successorsOf
(current_node);
for(x in successors)
 if(
notin
(x,closed))
insertlast
(x,open);
N.B.= this version is not saving the path for simplicity
BreadthFirst Search: Example
BreadthFirst Search: Example
Result is: S>A>F
BreadthFirst Search: Complexity
 Time complexity is the same magnitude as DFS
 O (b ^{ m } )
 where m is the depth of the solution
 Space Complexity
 how many nodes can be in the queue (worstcase)?
 assume (worst case) that there is 1 goal leaf at the RHS

so BFS will store all nodes
=1 + b + b ^{ 2 } + ......... + b ^{ m }
= O (b ^{ m } )
Further Uninformed Search Strategies

Depthlimited search (DLS) : Impose a cutoff (e.g. n for searching a path of length n 1), expand nodes with max. depth first until cutoff depth is reached (LIFO strategy, since it is a variation of depthfirst search).

Bidirectional search (BIDI) : forward search from initial state & backward search from goal state, stop when the two searches meet. Average effort O(b ^{d/2} ) if testing whether the search fronts intersect has constant effort

In AI, the problem graph is typically not known. If the graph is known, to find all optimal paths in a graph with labelled arcs, standard graph algorithms can be used
INFORMED SEARCH
Using knowledge on the search space to reduce search costs
Informed Search

Blind search methods take O(b^{m}) in the worst case

May make blind search algorithms prohibitively slow where d is large
 How can we reduce the running time?

Use problemspecific knowledge to pick which states are better candidates
Informed Search

Also called heuristic search

In a heuristic search each state is assigned a “heuristic value” (hvalue) that the search uses in selecting the “best” next step

A heuristic is an operationallyeffective nugget of information on how to direct search in a problem space

Heuristics are only approximately correct
Informed Search: Prominent methods

BestFirst Search

A*

Hill Climbing
Cost and Cost Estimation
f(n)=g(n)+h(n)

g(n) the cost (so far) to reach the node n

h(n) estimated cost to get from the node to the goal

f(n) estimated total cost of path through n to goal
Informed Search: BestFirst Search
 Special case of breadthfirst search
 Uses h(n) = heuristic function as its evaluation function
 Ignores cost so far to get to that node (g(n))
 Expand the node that appears closest to goal
 Best First Search is complete
 Best First Search is not optimal
 A solution can be found in a longer path (higher h(n) with a lower g(n) value)
 Special cases:
 uniform cost search: f(n) = g(n) = path to n
 A* search
BestFirst Search: Algorithm
List open, closed, successors={};
Node root_node, current_node;
insertlast(
root_node,open)
while notempty (open );

current_node= removefirst(open);
insertlast ( current_node,closed);
if ( goal (current_node)) return current_node;
else

successors=
estimationOrderedSuccessorsOf
(current_node);
for(x in successors)
 if(
notin
(x,closed))
insertlast
(x,open);
estimationOrderedSuccessorsOf
returns the list of direct
descendants of the current
node in shortest cost order
N.B.= this version is not saving the path for simplicity
BestFirst Search: Example
In this case we estimate the cost as the distance from the root node (in term of nodes)
BestFirst Search: Example

Result is: S>A>F!

If we consider real costs, optimal solution is: S>B>F
A*

Derived from BestFirst Search

Uses both g(n) and h(n)

A* is optimal

A* is complete
A* : Algorithm
List open, closed, successors={};
Node root_node, current_node, goal;
insertback(
root_node,open)
while notempty (open );

current_node= removefront(open);
insertback ( current_node,closed);
if (current_node==goal) return current_node;
else

successors=
totalEstOrderedSuccessorsOf
(current_node);
for(x in successors)
 if(
notin
(x,closed))
insertback
(x,open);
totalEstOrderedSuccessorsOf
returns the list of direct
descendants of the current
node in shortest total
estimation order
N.B.= this version is not saving the path for simplicity
A* : Example
In this case we estimate the cost as the distance from the root node (in term of nodes)
A* : Example
Result is: S>B>F!
Hill Climbing
 Special case of depthfirst search
 Uses h(n) = heuristic function as its evaluation function
 Ignores cost so far to get to that node (g(n))
 Expand the node that appears closest to goal
 Hill Climbing is not complete
 Unless we introduce backtracking
 Hill Climbing is not optimal
 Solution found is a local optimum
Hill Climbing: Algorithm

List successors={}; Node root_node, current_node, nextNode;

current_node=root_node
while (current_node!=null)
 if (
goal
(current_node)) return current_node;
else
 successors=successorsOf(current_node);
nextEval = ∞; nextNode=null;
for(x in successors)
 if(
eval
(x)
>
nextEval)
 nexEval=eval(x);
nextNode=x;
N.B.= this version is not saving the path for simplicity
Hill Climbing: Example
In this case we estimate the cost as the distance from the root node (in term of nodes)
Hill Climbing: Example
Result is: S>A>B>F!
Not optimal, more if at step 1 h(S)=2 we would have completed without funding a solution
Informed Search Algorithm Comparison
Algorithm

Time

Space

Optimal

Complete

Derivative


Best First Search

O(bm)

O(bm)

No

Yes

BFS


Hill Climbing

O(∞)

O(b)

No

No



A*

O(2^{N})

O(b^{d})

Yes

Yes

Best First Search


b
, branching factor
d , tree depth of the solution
m , maximum tree depth
ILLUSTRATION BY A LARGER EXAMPLE
Route Search

Graph Representation

DepthFirst Search
N.B.: by building the tree, we are exploring the search space!
BreadthFirst search
N.B.: by building the tree, we are exploring the search space!
DepthFirst Search vs BreadthFirst search
 Distance
 DFS: 464 km
 BFS: 358 km
 Q1: Can we use an algorithm to optimize according to distance?
 Time
 DFS: 4 hours 37 mins
 BFS: 5 hours 18 mins
 Q2: Can we use an algorithm to optimize according to time?
 Search space:
 DFS: 5 expansions
 BFS: 26 expansions
 Not very relevant… depends a lot on how you pick the order of node expansion, never the less BFS is usually more expensive
 To solve Q1 and Q2 we can apply for example and BestFirst Search
 Q1: the heuristic maybe the air distance between cities
 Q2: the heuristic maybe the air distance between cities x average speed (e.g. 90km/h)
Graph Representation with approximate distance
BestFirst search
N.B.: by building the tree, we are exploring the search space!
EXTENSIONS
Variants to presented algorithms
 Combine Depth First Search and Breadth First Search, by performing Depth Limited Search with increased depths until a goal is found
 Enrich Hill Climbing with random restart to hinder the local maximum and foothill problems
 Stochastic Beam Search: select w nodes randomly; nodes with higher values have a higher probability of selection
 Genetic Algorithms: generate nodes like in stochastic beam search, but from two parents rather than from one
SUMMARY
Summary
 Uninformed Search
 If the branching factor is small, BFS is the best solution
 If the tree is depth IDS is a good choice
 Informed Search
 Heuristic function selection determines the efficiency of the algorithm
 If actual cost is very expensive to be computed, then Best First Search is a good solution
 Hill climbing tends to stack in local optimal solutions
REFERENCES
References
 Mandatory reading:
 Chap. 4: Görz et. al. (eds.): Handbuch der Künstlichen Intelligenz , 2000
 Further reading and references:
 Chap. 3: Russell, Stuart J.; Norvig, Peter: Artificial Intelligence: A Modern Approach (2nd ed.), 2003
 Chap.23: M. Tim Jones: Artificial Intelligence: A Systems Approach
 Wikipedia links:
 http://en.wikipedia.org/wiki/Depthfirst_search
 http://en.wikipedia.org/wiki/Breadthfirst_search
 http://en.wikipedia.org/wiki/Bestfirst_search
 http://en.wikipedia.org/wiki/A*_search_algorithm
 http://en.wikipedia.org/wiki/Hill_climbing
Questions?