Searching

Artificial Intelligence
Problem types
 Deterministic, fully observable  single-state problem
 Agent knows exactly which state it will be in; solution is a
sequence
 Non-observable  sensorless problem (conformant
problem)
 Agent may have no idea where it is; solution is a sequence
 Nondeterministic and/or partially observable 
contingency problem
 percepts provide new information about current state
 often interleave} search, execution
 Unknown state space  exploration problem
 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
Search-based problem solver
 Representationof actions: programs that generate
successor state descriptions

 Representation of states: complete state

descriptions; typically, data structure holding
permutations of all possible states

 Representation of goals: goal test and heuristic

function to decide desirability

 Representation of plans: solution is sequence of

actions; considers only unbroken sequences of
actions
 Famous Problem Solver Task: “Missionaries and Cannibals”

 “Missionaries and cannibals” problem:

 Famous in AI

 Was subject of first paper (Amarel, 1968) that

approached problem formulation from analytical
viewpoint

 Problem statement:
 3 missionaries and 3 cannibals on one side of river, with boat that
can hold 1-2 people
 Find: way to get everyone to other side of river, without ever leaving
group of missionaries in one place outnumbered by cannibals in that
place
 Formalizing Missionaries and Cannibals Problem
 Ignore all irrelevant parts of the problem (e.g., weather conditions,
crocodiles, etc.)
 Define states, operators, goal test, path cost:
 States: ordered sequence of 3 numbers:
 (# missionaries, # cannibals, #boats on initial riverbank)
 E.g.: Start state = (3, 3, 1)
 Operators:
 Take 1 missionary, 1 cannibal, 2 missionaries, 2 cannibals, or one of
each across in boat.
 Take care to avoid illegal states
 Goal test:
 We’ve reached state (0, 0, 0)
 Path cost:
 # of crossings
 Solving Missionaries and Cannibals Problem
(3, 3, 1)

X (2, 3, 0) (3, 2, 0) X(1, 3, 0) (3, 1, 0) (2, 2, 0)

(3, 2, 1) X (2, 3, 1)
(2, 2, 0) X(1, 2, 0) (3, 0, 0) (2, 1, 0) X

(3, 1, 1)
(1, 1, 0)

(2, 2, 1)
(2, 2, 1)
etc. (0, 0, 0)
Examples of Problems: Towers of Hanoi
 3 pegs A, B, C
1
 3 discs represented as natural 2
numbers (1, 2, 3) which 3
A B C
correspond to the size of the
Operators:
discs
Move disk to peg
 The three discs can be
arbitrarily distributed over the Applying: Move 1 to C (1 → C)
three pegs, such that the to the initial state ((123)()())
following constraint holds: a new state is reached
di is on top of dj → di < dj ((23)()(1))
 Initial status: ((123)()())
Cycles may appear in the
 Goal status: (()()(123)) solution!
Examples of Problems: Blocksworld
E
D C B
E A B C A D
Initial State Goal State

 Objects: blocks • Initial state:

– ontable(E), cleartop(E)
 Attributes (1-ary – ontable(A), cleartop(A)
relations): cleartop(x), – ontable(B), cleartop(B)
– ontable(C)
ontable(x) – on(D,C), cleartop (D)
 Relations: on(x,y) • Applying the move put(E,A):
–
 Operators: puttable(x) on(E,A), cleartop(E)
– ontable(A)
where x must be – ontable(B), cleartop(B)
cleartop; put(x,y), where – ontable(C)
– on(D,C), cleartop (D)
x and y must be cleartop
Example: Towers of Hanoi*
These nodes
are equals
1
2
3
A B C

2 2
3 1 3 1
A B C A B C

… 2
3 1 2 3 2 1 3 1
A B C A B C A B C
…
1 1 1 1
3 2 3 2 3 2 3 2
A B C A B C A B C A B C

… … … … …
1 …
2 3
A B C

… …
* A partial tree search space representation
Example: Towers of Hanoi*

* A complete direct graph representation

[http://en.wikipedia.org/wiki/Tower_of_Hanoi]
Example: The 8-puzzle

 states?
 actions?
 goal test?
 path cost?
Example: The 8-puzzle

 states? locations of tiles

 actions? move blank left, right, up, down
 goal test? = goal state (given)
 path cost? 1 per move

[Note: optimal solution of n-Puzzle family is NP-hard]

Example: robotic assembly

 states?: real-valued coordinates of robot joint

angles parts of the object to be assembled
 actions?: continuous motions of robot joints
 goal test?: complete assembly
 path cost?: time to execute
Search Space Representation
Node
Loop
 Representing the search
space is the first step to enable Arc
the problem resolution
 Search space is mostly
represented through graphs
 A graph is a finite set of nodes
that are connected by arcs
 A loop may exist in a graph,
where an arc lead back to the
original node
 In general, such a graph is not
explicitly given
 Search space is constructed
during search
Search Space Representation
undirect direct
 A graph is undirected if arcs do
not imply a direction, direct
otherwise
connected disconnected

 A graph is connected if every

pair of nodes is connected by
a path tree

 A connected graph with no

loop is called tree
weighted
 A weighted graph, is a graph 1
1
4 5
for which a value is associated 2 1
6

to each arc 2 1
Tree search algorithms
 Basic idea:
 offline,simulated exploration of state space by
generating successors of already-explored states
(a.k.a.~expanding states)
Tree search example
Tree search example
Tree search example
Implementation: general tree search
 Implementation: states vs. nodes

 A state is a (representation of) a physical configuration

 A node is a data structure constituting part of a search
tree includes state, parent node, action, path cost g(x),
depth

 The Expand function creates new nodes, filling in the

various fields and using the SuccessorFn of the
problem to create the corresponding states.
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?
 time complexity: number of nodes generated
 space complexity: maximum number of nodes in memory
 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 ∞)
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
 Alternative Search Strategies for Problem Solvers
 Variety of search approaches:
 Uninformed search (no information about path cost from current
state to goal):
 Breadth-first
 Uniform cost search
 Depth-first
 Depth-limited search
 Iterative deepening
 Bidirectional
 Etc.

 Informed search
 Greedy
 A*
 Hill-climbing/gradient descent
 Simulated annealing (a messy search tree)
 Etc.
UNINFORMED
SEARCH
Brute force approach to explore search space
Uninformed search strategies
 Uninformed search strategies use only the
information available in the problem
definition
 Breadth-first search
 Uniform-cost search
 Depth-first search
 Depth-limited search
 Iterative deepening search
Breadth-first search
 Expand shallowest unexpanded node
 Implementation:
 fringeis a FIFO queue, i.e., new successors
go at end
A
Breadth-first search
 Expand shallowest unexpanded node
 Implementation:
 fringeis a FIFO queue, i.e., new successors
go at end

A
B
C
Breadth-first search
 Expand shallowest unexpanded node

A
B
C
D
E
Breadth-first search
 Expand shallowest unexpanded node

A
B
C
D
E
F
G
Properties of breadth-first search
 Complete? Yes (if b is finite)
 Time? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1)
 Space? O(bd+1) (keeps every node in memory)
 Optimal? Yes (if cost = 1 per step)

 Space is the bigger problem (more than time)

Uniform-cost search
 Expand least-cost unexpanded node
 Implementation:
 fringe = priority queue
 Equivalent to breadth-first if step costs all equal
 Complete? Yes, if step cost ≥ ε
 Time? # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε)) where C* is the cost of the optimal solution
 Space? # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε))
 Optimal? Yes – nodes expanded in increasing order of
g(n)
Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = Stack, i.e., put successors at front

push A;
Depth-first search
 Expand deepest unexpanded node
 Implementation:
 fringe = Stack
A B
C
pop A;
push C;
push B;
Depth-first search
 Expand deepest unexpanded node
 Implementation: B D
 fringe = STACK C E
C
pop B;
push E;
push D;
Depth-first search
 Expand deepest unexpanded node
D H
E I
C E
pop D; C
push I;
push H;
Depth-first search
 Expand deepest unexpanded node
H I
I
E
E
C pop H; C
Depth-first search
 Expand deepest unexpanded node
I E
E
C
C
pop I;
Depth-first search
 Expand deepest unexpanded node
E J
C
K
pop E; C
push K;
push J
Depth-first search
 Expand deepest unexpanded node
J K
K C
C pop J;
Depth-first search
 Expand deepest unexpanded node
K C
C
pop K;
Depth-first search
 Expand deepest unexpanded node
C F
G
pop C;
push G;
push F;
Depth-first search
 Expand deepest unexpanded node
F L
G M
pop F; G
push M;
push L;
Depth-first search
 Expand deepest unexpanded node
L M
M G
G pop L;
Properties of depth-first search
 Complete? No: fails in infinite-depth spaces,
spaces with loops
 Modify to avoid repeated states along path complete in
finite spaces

 Time? O(bm): terrible if m is much larger than d
 but if solutions are dense, may be much faster than
breadth-first
 Space? O(bm), i.e., linear space!
 Optimal? No
Depth-limited search
= depth-first search with depth limit l,
i.e., nodes at depth l have no successors

 Recursive implementation:
Iterative deepening search
Iterative deepening search l =0
Iterative deepening search l =1
Iterative deepening search l =2
Iterative deepening search l =3
Iterative deepening search
 Number of nodes generated in a depth-limited search to
depth d with branching factor b:
NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

 Number of nodes generated in an iterative deepening

search to depth d with branching factor b:
NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd

 For b = 10, d = 5:
 NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
 NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

 Overhead = (123,456 - 111,111)/111,111 = 11%

Properties of iterative
deepening search
 Complete? Yes
 Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd =
O(bd)
 Space? O(bd)
 Optimal? Yes, if step cost = 1
Summary of algorithms
Summary
 Problem formulation usually requires abstracting away
real-world details to define a state space that can
feasibly be explored

 Variety of uninformed search strategies

 Iterative deepening search uses only linear space and

not much more time than other uninformed algorithms