Columbia University

COMS W4701

SEARCH AGENTS
Problem formulation:
Initial state: starting state
States: all states reachable by any sequence of actions
Actions: possible actions available to agent; Action(s)
returns set of actions that can be executed in state s
Transition model: description of what each action does;
Results(s,a)
Goal test
Path cost
State space is a physical configuration
Search space is an abstract configuration represented by a
search tree
Evaluate searches by:
1. Completeness (does it always find a solution)
2. Time complexity (number of nodes
generated/expanded)
3. Space complexity (max number of nodes in memory)
4. Optimality (does it always find a least-cost solution)
B (max branching factor), d (depth of solution), m (max depth
of state space)
UNINFORMED SEARCH
1. BFS (expand shallowest node) à queue
Complete? Yes in finite spaces but no in infinite
depth spaces & spaces w/ loops
Time? 1 + b + b2 + b3 + ... + bd = O(bd )
Space? O(bd )
Optimal? Yes (if cost = 1 per step)
2. DFS (expand deepest node) à stack (REVERSE)
Complete? Yes (if b is finite)
Time? 1 + b + b2 + b3 + ... + bm = O(bm ) ; bad if m >>
d but if solutions are dense, may be much faster than BFS
Space? O(bm) ; needs to store only a single path
from root to leaf node along with remaining unexpanded
sibling nodes for each node on path)
Optimal? No
3. DLS (depth first with depth limit)
4. IDS (DLS with increasing limit)
Complete? Yes
Time? # nodes generated: bd + 2bd-1 + 3bd-2 + ... + bd
= bd(1 – 1/b)-2 (b > 1) à waste in time (represented by C) is
negligible for large space
Space? O(bd) (same as DFS)
Optimal? Yes ; explores all nodes at level L before
going deeper which guarantees the shallowest and least cost
solution
5. UCS (expand least cost node) à priority queue; jagged
fringe
Complete? Yes if solution has finite cost
Time? O(bC* / e ) where C* is cost of optimal solution
and each action costs at least e ; (exponent is how deep the
cheapest solution could be)
Space? O(bC* / e )
Optimal? Yes
queue/stack/priority queue
order of visit
* find path by marking origin above (from where did it get
added to the queue/stack/priority queue?
INFORMED SEARCH (using heuristics)
Greedy search expands node that appears to be closest to
goal using heuristic function h(n)
A* search minimizes total estimated solution cost by
combining g(n) (cost to reach node n) and h(n) (cost to get
from n to goal); combines UCS and greedy search
Complete? Yes
Time? exponential
Space? keeps every node in memory
Optimal? Yes
An admissible heuristic never overestimates the cost to
reach the goal
à if h(n) is admissible, A* is optimal
LOCAL SEARCH
Use if path does not matter or systematic search is not
possible à keep a single “current” state and try to improve it
No need to maintain search tree, use very little memory, can
find good enough solutions in continuous or large state
spaces
Hill Climbing (greedy local search)
- looks only to immediate good neighbors and moves uphill
until it reaches a pick
- can terminate with local maximum, global maximum or can
get stuck in a plateau (shoulder)
Local beam search maintains k states instead of one like
random restart, but information is passed among states about
better areas for search
Stochastic beam search choosees k successors at random
(helps prevent states from being in the same part of the state
space)
Genetic algorithms is a variant of stochastic beam search but
successor states are generated by combining two parents
rather by modifying a single state; better states have higher
values of fitness function