Debela Desalegn
March 16, 2025
An intelligent agent that finds solutions by searching
for the best sequence of actions.
Informed vs Uninformed
: Known world
▪ Goal Formulation
▪ Problem Formulation (Abstraction)
▪ Search (simulated)
▪ Execution (Closed Loop vs Open Loop)
▪ Choose action based on current percept (and maybe memory)
▪ May have memory or a model of the world’s current state
▪ Do not consider the future consequences of their actions
▪ Ask “what if”
▪ Decisions based on (hypothesized) consequences of actions
▪ Must have a model of how the world evolves in response to actions
▪ Must formulate a goal (test)
a sequence of actions (a plan/path) which transforms the start state to a goal
state
ü A state space ▪ Cities
ü A successor function (with actions, costs) ▪ Roads: Go to adjacent
▪ city with cost =
ü A start state and a goal test
distance
▪ Arad
▪ Is state == Bucharest?
The world state includes every last detail of the environment.
A search state/search tree keeps only the details needed for planning (abstraction).
§ States: (x,y) location ▪ States: {(x,y), dot booleans}
§ Actions: NSEW ▪ Actions: NSEW
§ Successor: update location only ▪ Successor: update location and
§ Goal test: is (x,y)=END possibly a dot boolean
▪ Goal test: dots all false
: A mathematical representation of
a search problem
are (abstracted) world configurations
represent successors (action results)
§ The is a set of goal nodes (maybe only
one)
▪ We can rarely build this full graph in memory (it’s
too big), but it’s a useful idea
: A mathematical representation of
a search problem
are (abstracted) world configurations a G
represent successors (action results) b c
§ The is a set of goal nodes (maybe only
e
one) d f
S h
p r
q
▪ We can rarely build this full graph in memory (it’s Tiny state space graph for a tiny
too big), but it’s a useful idea search problem
▪ A “what if” tree of plans and their outcomes
▪ The start state is the root node
▪ Children correspond to successors
▪ Nodes show states, but correspond to PLANS that achieve those states
▪ For most problems, we can never actually build the whole tree
How big is its search tree (from S)?
▪Expand out potential plans (tree nodes)
▪Maintain a fringe/frontier of partial plans under consideration
▪Try to expand as few tree nodes as possible
▪Fringe/Frontier
▪Expansion
▪Exploration strategy
Which fringe nodes to explore?
The essence of search
a G
b c
e
d f
S h
p q r
the state to which the node corresponds;
the node in the tree that generated this node;
the action that was applied to the parent’s state to generate this node;
the total cost of the path from the initial state to this node. In
mathematical formulas, we use as a synonym for PATH-COST.
▪ A data structure for a frontier could be a Queue (Priority Queue, FIFO Queue, LIFO
queue (stack)).
No clue about how close a state is to the goal(s).
Have information on how to traverse or visit the nodes in the tree.
: expand a deepest node first
: Fringe is a LIFO stack
a G
b c
e
d f
S h
p q r
▪ Some left prefix of the tree.
▪ Could process the whole tree!
▪ If m is finite, takes time O(bm)
▪ Only has siblings on path to root, so O(bm)
▪ m could be infinite, so only if we prevent
cycles (more later)
▪ Incomplete: in infinite state spaces
▪ No, it finds the “leftmost” solution, regardless
of depth or cost
- Optimal when all action cost is the same.
- Node Expansion sequence
- Root, successors of the root, next successors
- Complete in infinite state spaces.
- Is Best first search where f(n) is the depth.
- Good efficiency � FIFO queue
a G
: expand a shallowest node first b c
: Fringe is a FIFO queue e
d f
S h
p q r
▪ Processes all nodes above shallowest solution
▪ Let depth of shallowest solution be s
▪ Search takes time O(bs)
▪ Has roughly the last tier, so O(bs)
▪ The memory requirements are higher than time
requirements.
▪ s must be finite if a solution exists, so yes!
▪ Only if costs are all 1 (more on costs later)
▪Limit depth to some specific level “l” and get a
time and space complexity of O(bl) and O(bl)
respectively.
: get DFS’s space advantage with BFS’s time /
shallow-solution advantages
▪Run a DFS with depth limit 1. If no solution…
▪Run a DFS with depth limit 2. If no solution…
▪Run a DFS with depth limit 3. …..
▪Generally most work happens in the lowest level
searched, so not so bad!
▪Good if the diameter of the problem is known
: O(bd) when there is a solution and O(bM) when there is none.
: O(bd) when there is a solution and O(bm) when there is none.
: expand a cheapest node first:
Fringe is a priority queue (priority: cumulative cost)
▪ Processes all nodes with cost less than cheapest
solution!
▪ If that solution costs C* and arcs cost at least ε , then the
“effective depth” is roughly C*/ε
▪ Takes time O(bC*/ε) (exponential in effective depth)
▪ Has roughly the last tier, so O(bC*/ε)
▪ Assuming best solution has a finite cost and minimum
arc cost is positive, yes!
▪ Yes! (Proof next lecture via A*)
Find the shortest path from state A to state F.
