AERO 489/689

Foundations of
Aerospace
Autonomy
Dr. Daniel Selva dselva@[Link]
Problem-solving agents: Search
September 3-10, 2024

1
Logistics
• Programming assignment 1 is due this Thursday Sep 5
• No class this Thursday
• Reading quiz for week 3 is due Sep 8
• Programming assignment 2 will go out this Thursday and will be due on Sep 17

2
Problem-solving agents
• Reflex agents choose an action based only on current state/precepts.
• This is challenging because that mapping can be too large to store or learn
• Goal-based agents consider future actions and their effect

• Problem-solving agents are a class of goal-based agents that use atomic representations of the
world, as opposed to planning agents which use structured representations of the world
• Problem-solving agents search through the space of sequences of actions and try to find a
sequence that will lead to a goal

• For now, we limit ourselves to simple environments

• Single agent, observable, static, deterministic, known
• This guarantees that the solution is a fixed sequence of actions

3
Example: UAV
• A UAV realizes that its battery charge is low and so creates a goal to
return to the charging station.
• If the agent doesn’t know anything about the world or how its
actions change the state of the world, it can’t possibly know what to
do.
• But if it knows its current state, a map, and a basic model of what its
actions do to the state of the world, it can find a sequence of
actions that will take it to the charging station
• Once it has found a sequence, it can execute it and if the model is
good and the environment is static and deterministic, it is
guaranteed to succeed

4
Problem formulation – intuition
• One must define a set of states, a set of actions, a transition model of how actions
change the state of the world, and an action cost function
• States are atomic (e.g., state 1, state 2) without any structure.
• Actions deterministically take the agent from one state to the other
• Action costs are additive
• A goal is defined as a subset of world states (goal states)
• Note that the current goal may change over time but for now we assume one
• The agent must find a sequence of actions that leads to a goal state, and ideally
one that minimizes total cost.
• This process is called search.

5
Level of abstraction in problem formulation
• A problem formulation is an abstraction of the real problem (i.e., it hides detail)
• Example: A UAV realizes that its battery charge is low and so creates a goal to
return to the charging station. How do you define states and actions?
• Option 1:
• States: XYZ coordinates discretized at a given precision.
• Actions: up/down/north/east/south/west by one cell.
• Option 2:
• States: a set of pre-defined waypoints in a graph.
• Actions: “go from A to neighboring point B”
• What is the right level of abstraction? Hard to say, but consider:
• Usefulness: Finding a solution in the abstract problem is easier than in the real problem
• Validity: A solution in the abstract model can be expanded to a solution in the real-world
problem

6
Navigation problems

7
Search Problems
• A search problem is defined by:
• An initial state 𝑠0 (e.g., Arad)
• A function that returns the list of actions available to the agent in a given state 𝑠
ACTIONS 𝑠
• A transition model RESULT(𝑠, 𝑎) describing the effect of performing action a in state s
(i.e., the new state 𝑠’)
• A goal test function, that given a state s, returns True if it is a goal state and False
otherwise.
• It can be implemented as an explicit list of states, a set of conditions that must be satisfied, etc.
• An action cost function, ACTION-COST(𝑠, 𝑎, 𝑠’) or 𝑐(𝑠, 𝑎, 𝑠′) that returns a scalar cost
𝑐 ≥ 0 of doing action a in state s to reach state s’
• This is the performance measure of the agent
• We assume here that path cost is additive – i.e., path cost is the sum of action costs.

8
State space graph
• Together, the initial state and the ACTIONS
and RESULTS functions define the state space.
• The state space can be represented as a graph
where nodes are states and edges are actions
• A solution to the problem is a path in the
graph (a sequence of actions) that leads from
the initial state to a goal state
• The quality of the solution is measured by the
cost function ➔ the optimal solution is the
solution with the lowest path cost
• Example: in simple navigation problems, the
state space graph is essentially the map

9
 Example: state space graph for vacuum agent
• States: there are n locations, each of which
may or may not have dirt. In addition, the
agent can be in either of those n locations.
• Actions: {Left, Right, Suck} for all states
• Transition model: as expected. Left in
leftmost cell, Right in rightmost cell, and
Suck in a clean cell have no effect.
• Goal test: Check if all squares are clean
• Path cost: 1 per action, including moving
and sucking actions.
• State space for the n=2 vacuum world is
shown to the right.

10
Think-pair-share: 8-puzzle
• Provide a formal problem
formulation for the 8-puzzle
game
• Remember, a formulation
includes the states, actions,
transition model, goal test, and
cost function

11
Search algorithms – intuition
• Takes a search problem as input and returns a solution or failure
• Focus on algorithms that perform a tree search of the state space
• Note that the search tree is different from the state space graph!
• Start with just the root node – the initial state
• Expand the node by considering all available actions for that state
• Use the RESULT function to see where each action leads
• Generate a new child or successor node for each resulting state
• A state for which a node has been generated has been reached
• The subset of reached nodes available for expansion (i.e. unexpanded) is called the frontier of the search tree
• Select the next node to expand
• Check if it is a goal state, return it
• Otherwise continue…

12
Example search tree for cities problem

Note: There can be cycles in the state space graph! We

will need to handle that.

13
Best-first search meta-algorithm (not to be confused with
greedy best-first search)
• Start with data structures • Problem data structure contains
• Node • [Link]
• Problem • [Link]-GOAL
• Frontier • [Link]
• Reached • [Link]-COST
• Node data structure contains • Frontier: A priority queue of nodes
• [Link]: corresponding state id with priority function f
• [Link]: node that generated • Reached: A dictionary state id ->
this node node (note that nodes and states
• [Link]: action that generated are not the same since we can
this node
• [Link]-COST: total path cost so
reach the same state through
far (up to this node) different paths)

14
 Best-first search meta-algorithm (not to be confused with
greedy best-first search)
• Key points:
• How does this meta-algorithm
implement different search
strategies?
• Yield returns objects sequentially as
they are generated
• More memory efficient than return
• How does this algorithm check for
cycles?
• How does it check if there is a more
optimal path to a given state?
• Is it guaranteed to terminate?
• Is it guaranteed to return the
optimal path?

15
 A note on queues
• Frontier data structure is a queue with the following operations
• IS-EMPTY(frontier)
• POP(frontier) returns and removes top node from frontier
• TOP(frontier) returns but does not remove top node from frontier
• ADD(node, frontier) inserts node into proper place in the queue
• 3 types of queues can be used
• FIFO queue: pops the node that was added first (breadth-first search)
• LIFO queue (or stack): pops the node that was added last (depth-first search)
• Priority queue: pops the node with min cost according to some evaluation function f (uniform cost
search, greedy best-first search, A*…)

Node Node Node Node Node

16
Increasing efficiency: Redundant paths
• Consider the path below Arad-Sibiu-Arad
• repeated state ➔ cycles cannot be optimal and should be pruned
• More generally, if there are two paths to a given state, whichever is highest cost is
redundant and should be pruned out
• It is thus useful to remember nodes visited and the best path to each state
• But that has a cost in memory (size of reached)
• We can check for all redundant paths, cycles only, or none

17
Performance of search algorithms
• There are 4 main performance criteria for search algorithms
• Completeness: Is the algorithm guaranteed to find a solution when
there is one, and to correctly report failure when there is not?
• Cost optimality: Does it find a solution with the lowest path cost?
• Time complexity: How long does it take to find a solution?
• Space complexity: How much memory is needed to perform the
search?
• Time and space complexity are often considered w.r.t. some
measure of the problem size such as:
• d: depth of the shallowest goal state
• b: branching factor, (max) number of successors of any node
• m: maximum depth of the search tree

18
Uninformed vs informed search strategies

• Breadth-first
In uniformed search, the
• Uniform cost
agent does not know how far
• Depth-first
it is from the goal state(s).
• Others: depth-limited, iterative deepening, bi-directional search

In informed search, the agent

• Greedy best-first
has access to a domain-
• A*
specific heuristic function
• Others: iterative-deepening A*, recursive best-first, bidirectional
that tells it how far the given heuristic search
state is from the goal state.

19
 Breadth-first search
• Expand nodes of the same depth (i.e., the number
of actions it takes to reach the node) before
deeper nodes
• Can be implemented as best-first search with f =
depth of the node, but a FIFO queue is faster
• Typical implementations assume that cost
increases with depth (not always true!)
• Reached can be a set of states instead of a map since
we assume cost ~ depth so it’s impossible to reach a
state again in the future with lower cost
• For the same reason, we can do early goal test (as
soon as solution is generated) instead of late goal test
(when popped from the frontier)

20
Example: 8-puzzle

21
Performance of Breadth-first search
• Complete? Yes, although for infinite spaces it would take infinite time
• Optimal? As implemented, only if path cost monotonically increases
with #actions!
• Otherwise, it may find a solution with a suboptimal path cost
• Time complexity: 1 + 𝑏 + 𝑏 2 + ⋯ + 𝑏 𝑑 ~𝑂 𝑏 𝑑 where 𝑏 is branching
factor (number of children or successor nodes) and 𝑑 is the depth of
the solution
• Space complexity: 𝑂 𝑏 𝑑 since all nodes remain in memory
• Exponential complexity makes breadth-first search (and all uninformed
search) impractical for most real-world problems

22
In-class question
• Consider a uniform search tree with a branching factor of 10.
• It takes 1KB of memory to store one node
• The computer can process 1 million nodes/s
1. How long would it take to do a breadth-first search at depth 10?
2. How much memory would it take?
• 𝑂 𝑏 𝑑 = 1010 nodes/106 nodes/s= 104 s
• 𝑂 𝑏 𝑑 = 1010 nodes*1KB/node = 10TB
• Memory is an issue for breadth-first!

23
Uniform cost search (Dijkstra’s algorithm)
• What if actions don’t have the same cost or path cost
does not monotonically increase with depth?
• Uniform cost search = Best-first search where the f(n) is
the total path cost from the root node to n
• Complete? Yes
• Optimal? Yes (as long as actions have non-negative cost*)
∗
• Time complexity: 𝑂 𝑏1+ 𝐶 /𝜖 where 𝐶 ∗ is the cost of the
optimal solution and 𝜖 > 0 is a lower bound on the cost
of each action
∗
• Space complexity:𝑂 𝑏1+ 𝐶 /𝜖 since all nodes remain in
memory
• Can be slower than BFS if the solution is down a path with
initial high cost.

24
Depth-first search
• Always expands the deepest
node first
• When a node has no successors,
it backs up to the next deepest
unexpanded node
• Can be implemented as best-
first search where f is -depth of
the node, but a stack is more
efficient
• It is often implemented as a
tree-like search, i.e., one that
does not keep a table of reached
states and just returns the first
solution found
• Subject to cycles and suboptimal
paths!

25
Depth-first search
• Complete? Only in finite state spaces with no cycles.
• Optimal? No
• Returns first solution it finds
• Time complexity: 𝑂 𝑏 𝑚
• Space complexity: 𝑂 𝑏𝑚 where m is the maximum depth of the tree
• note that it doesn’t keep a reached table
• it only needs to store the parent node and siblings to be able to back up when no
successors are found
• Despite not being complete or optimal in general, the huge advantages in
terms of space complexity (memory) make it the baseline algorithm for
many AI areas (e.g., constraint satisfaction, logic-based agents)

26
Depth-limited and iterative deepening search
• Depth-limited search: To prevent DFS from wandering down an infinite path,
we can limit search depth to a limit 𝑙 < 𝑚.
• Time complexity: 𝑂 𝑏 𝑙
• Space complexity: 𝑂 𝑏𝑙
• However, if l is too shallow it may not find the solution
• Solution: Iterative deepening ➔ start with l=0, then l=1, l=2… until a solution
(or failure) is found
• IDS is often the preferred uninformed search algorithm
• Memory efficient
• Complete
• Optimal if cost ~ depth

27
Performance of uninformed search algorithms

1. For finite action spaces

2. If step costs are non-negative
3. If cost is monotonically increasing with depth
4. If both directions use BFS
28
Informed (heuristic) search algorithms
• They use domain-specific knowledge
• Specifically, a heuristic function h(n) that
estimates how far (cheapest path) the
current state is from a goal state
• The performance of informed search
depends on the quality of the heuristic
• Example heuristic: straight line distance
on the map

29
Example: 8-puzzle
• What is a good heuristic for the 8-puzzle problem?
• Number of misplaced tiles
• Manhattan distance: (total Manhattan distance to move each tile to
their goal position, regardless of constraints)

30
 Greedy best-first
• Best-first search that uses as
evaluation function f(n)=h(n)
• Complete in finite spaces
• Not optimal
• Complexity: O(𝑏 𝑚 ) in worst
case but a good heuristic can
do much better

31
A* search
• Best-first search that uses as evaluation function f(n)=g(n)+h(n) where
• g(n) is the path cost from the initial state to node n
• h(n) is the estimated cost of the shortest path from n to the goal state

32
Performance of A* - Admissible heuristics
• A* search is complete.
• Whether A* is cost-optimal depends on certain properties of the
heuristic.
• A key property is admissibility: an admissible heuristic is one that never
overestimates the cost to reach a goal.
• An admissible heuristic is therefore optimistic.
• With an admissible heuristic, A* is cost-optimal.

33
Admissibility implies optimality of A*
• Imagine that the algorithm returns a solution with a cost C>C* (i.e.,
suboptimal). Then, there must exist a node n which is on the optimal path
but is not expanded (otherwise it would have returned that solution).
𝑓 𝑛 = 𝑔 𝑛 + ℎ 𝑛 > 𝐶∗
• At the same time, since the solution was optimal until that point:
𝑓 𝑛 = 𝑔 𝑛 + ℎ 𝑛 = 𝑔∗ 𝑛 + ℎ 𝑛
• If the heuristic is admissible ℎ 𝑛 ≤ ℎ∗ 𝑛 . Combining the last two
𝑓 𝑛 ≤ 𝑔∗ 𝑛 + ℎ∗ 𝑛 = 𝐶 ∗
• Since this is a contradiction, it follows that A* must be optimal for
admissible heuristics.

34
Consistent heuristics
• A heuristic h is consistent if, for every node n
and every successor n’ of n generated by an
action a we have

ℎ 𝑛 ≤ 𝑐 𝑛, 𝑎, 𝑛′ + ℎ 𝑛′

• Note that consistency implies admissibility but

not vice versa.
• Consistency also implies that the first time we
reach state is on an optimal path
• So no need to check for redundant paths

35