Intelligent Agents and Search Problem

[slides partially adapted from Dan Klein, Pieter Abeel, Stuart Russel, Dawn Song from University of California [Link]]
 Search Agents
• Search Problem
• Uninformed Search Methods
• Depth-First Search
• Breadth-First Search
• Uniform-Cost Search

• Informed Search Methods

• greedy Search
• A* search

• Search Programming Assignment

Simple Example: Vacuum-
Cleaner agent
Vacuum-Cleaner percept-action
sequences
Simple Reflex Agent
Model-Goal based Agent
Model-Utility based Agent
General Learning Agent
Task Environment Characteristics

• Actions?
• Action Utility
• Accumulated
Expected Utility
State-Space graph for 2-cell
Vacuum Agent
Exploring a solution for Routing in Romania:
 Search Problem Concepts
• Initial State: the state where agent starts
• Goal State/Goal test: a set of target destination for the agent
• Action: given a state s, ACTION(s) returns a finite set of actions to execute on s :
for Romania map: like ACTIONs(Arad) = {to sibiu, to Timisoara, to Zerind}
• Transition Model: describes what each action does: RESULT(s, a) returns the
state that results from doing action a on state s
• Action Cost Function: denoted by ACTION_COST(s, a, s’) gives numeric cost of
applying action a on state s to reach state s’. For Romania example cost could be
distance, flight time, ticket price, …., anything that worth minimizing
 Search Properties
• Complete Planning vs replanning: Plan the whole solution first,
then execute actions based on it; vs; plan just enough
to get you to next step, then search again…
• Completeness: is the algorithm guaranteed to find all
solution or report failure if there is none?
• Cost Optimality: does it first find a solution with the lowest
path cost among all the solutions?
• Time Complexity: how long does it take to find a solution?
• Space Complexity: how much memory needed to perform
the search
• Computation Complexity: how much computation power
needed (let’s say in FLOPS)
Search Problem Example: Knuth
Integer Engine
• Donald Knuth (1964) conjectured: all positive numbers can be reached by
applying a sequence of , !, and ] operations on 4. For instance:

• Define the problem:

• States: Positive Integers
• Initial State: 4
• Action: Apply any of the 3 operations
• Goal State: the desired positive integer
• Action Cost: 1
Exercise: 8-puzzle
• Goal is to start from an unordered
configuration of blocks, and using 2d sliding
end up with an ordering where the first slot is
empty.
• What are the states?
• How to model the Search States?
• What are the actions?
• What is the goal test?
• What about the cost?
• Draw the search tree for first row.
Types of Search Nodes
 Search types to Consider
1. Un-Informed Search Types:
• Breadth First Search: first explore the immediate neighbors
• Depth First Search: explore a node all the way down the tree
• Uniform Cost Search: explore nodes according to lowest “cost” so far (g function)
2. Informed Search Types:
• Greedy Search: looks for the shortest path to the goal, using heuristic (h function)
• A* Search: Considers both “cost” so far and heuristic to goal (f = g + h function)
 General Search Algorithm
Function Best-First-Search(problem, f = exploreMethod) returns solution node or failure
node  Node(STATE=[Link])
Frontier  a priority queue ordered by f with node as first element
Explored  a lookup table, with one entry : {key=[Link], value=node}
while not Is-Empty(Frontier) do:
node  Pop (Frontier)
if [Link]-GOAL([Link]) then return node
add node to Explored
for each child in EXPAND(node) do:
s  [Link]
if s not in Explored and child not in Frontier:
add child to Frontier
elif child in frontier and f(child) < frontier[child]
del frontier[child]
add child to Frontier
return failure
Continued…

Function EXPAND(problem, node) yield nodes

s  [Link]
for each action in [Link](s) do
s1  [Link](s, action)
cost [Link]-COST + [Link]-COST(s, action, s1)
yield Node(STATE=s’, PARENT=node, ACTION=action, PATH-COST=cost)

node:
STATE : the state to which this node corresponds
PARENT: the node in the search tree that generated this node
ACTION: the action that was applied to the parent’s state to generate this
node
PATH-COST: the total pathcost denoted by g(s) (potentially plus heuristic
h(s))
 BFS Analysis
• Let’s assume Branching factor is b
• Processes all nodes above the shallowest solution
• For shallowest solution takes O(bs) (time complexity)
• Space-wise the size of the Frontier, s o O(bs)
• Runtime memory O(bs)
• Is it Complete?
 Uniform Cost Search (UCS) (Dijkstra algorithm )
• Prioritize expansion of those nodes in Frontier which are least
expensive based on a cumulative cost measure.
• In case of Arad-Bucharest, the total cost is total distance from Arad to
the current node.
• Usually uses priority queue to implement.
function UNIFORM-COST-SEARCH(problem):
return BEST-FIRST-SEARCH(problem, f= PATH-COST)
• Let’s apply UCS to Arad-Bucharest Path finding: (Romania Map example)
Example of UCS
 DFS Search
• DFS is a Graph Search where always considers the “Deepest-in-steps”
path for expansion first.
• For minimizing cost, better Goal path be returned when removing
from Frontier not when adding to it.
• BFS, contrary to DFS, is guaranteed to find a path if the depth of the
tree is finite.
• Exercise: apply DFS to finding path from Arad to Bucharest:
 DFS Analysis
• Let’s assume Branching factor is b
• Search tree expands in from left to right
• If m is finite, takes O(bm) (time and space complexity)
• Memory need for execution O(bm)
 Exercise: DFS vs BFS
• For what kind of problems you choose DFS?

• For what kind of problems you choose BFS?

 Informed Search
• Use a heuristic function h(s) to estimate how ‘far’ the agent is from
goal
• h(s) must be optimistic (never overestimate), in order to work. These
are called admissible heuristics.
• UCS tries to minimize the cost function g(s).
• Greedy search tries to minimize its heuristic h(s).
• A* search tries to minimize the combination function f(s) = g(s) + h(s)
• Choosing good heuristic is very important for efficiency of A*
 Search Heuristics
 A heuristic is:
 A function that estimates how close a state is to a goal
 Designed for a particular search problem
 Examples: Manhattan distance, Euclidean distance for
pathing

10

5
11.2
Greedy Search
Example: Heuristic Function

h(x)
 Greedy Search
 Expand the node that seems closest…

 What can go wrong?

 A*: Combining UCS and Greedy
 Uniform-cost orders by path cost, or backward cost
g(n)
 Greedy orders by goal proximity, or forward cost
8 S
h(n) g=0
g=1 h=6
e h=1 a
1 h=5

1 3 2 g=2 g=9
S a d G
h=6 b d g=4 e h=1
h=6 h=5 h=2
1 h=2 h=0
1 g=3 g=6
c b g = 10
h=7 c G h=0 d
h=2
h=7 h=6
g = 12
G h=0
 A* Search orders by the sum: f(n) = g(n) + h(n)
Example: Teg Grenager
When should A* terminate?
 Should we stop when we enqueue a goal?
h=2

2 A 2

S h=3 h=0 G

2 B 3
h=1

 No: only stop when we dequeue a goal

 Is A* Optimal?
h=6

1 A 3

S h=7
G h=0

 What went wrong?

 Actual goal cost < estimated goal cost
 We need estimates to be less than shortest-path costs!
 Admissible Heuristics
 A heuristic h is admissible (optimistic) if:

is the true cost to a nearest goal

 Examples:
4
15

 Coming up with admissible heuristics is crucial step in using A*

in practice.
Why A* Graph Search visiting
same node (C) multiple times?
State space graph Search tree
A S (0+2)
1
1
S h=4
C
h=1 A (1+4) B (1+1)
h=2 1
2
3 C (2+1) C (3+1)
B

h=1
G G (5+0) G (6+0)

h=0
 Answer: Consistency of
Heuristics Main idea: heuristic must be monotone or
consistent to make sure any node on path would
A be visited only once:
1 h(A) ≤ h(C) + cost(A to C)
h=4 C h=1  Consistency implies Admissibility if we start with h(G)=0
h=2

3
 Optimality of A* comes from
Admissibility. Consistency is for
increasing efficiency
G
 Optimality of A* Tree Search
Assume:
…
 A is an optimal goal node
 B is a suboptimal goal node
n
 h is admissible
Optimality Claim: A will be found by A* before B be
found. This means:
 A will exit the Frontier before B (full proof is omitted)
 Proof hint: we need to prove that f(A) < f(B) and
remember f(n) = g(n) + h(n), for a common ancestor of
both A and B. Suppose B is on Frontier as well as n.
Show that A will be expanded first before B using the
facts: f(n) <= g(A) coming from Admissibility.
 UCS vs A* Contours
 Uniform-cost expands equally in all
“directions”
Start Goal

 A* expands mainly toward the goal,

but does hedge its bets to ensure
optimality
Start Goal
 Creating Admissible Heuristics
 Most of the work in solving hard search problems optimally is in coming up
with admissible heuristics

 Often, admissible heuristics are solutions to relaxed problems, where new

actions are available

366
15

 Inadmissible
heuristics are often
 Heuristic Example: 8 Puzzle

Start State Goal State

Admissible Heuristics:

 Number of misplaced: 8
 Sum of Manhattan Distance for each cell: 3 + 1 + 2 + 2 + 3 + 2 + 2 + 3 = 18
 Using actual cost as heuristic?
 A good heuristic is usually cost of a solution to a relaxed version of the problem
 A* Applications
 Video games
 Pathing / routing problems
 Resource planning problems
 Robot motion planning
 Language analysis
 Machine translation
 Speech recognition
 …
 A*: Summary
 A* uses both backward costs and (estimates of) forward costs

 A* is optimal/efficient with admissible/consistent heuristics

 Heuristic design is key: often use relaxed problems

Appendix: Iterative Deepening Search
 Weighted A*
• Uses f(n) = g(n) + w*h(n), w is a factor >= 1.
• The bigger w gives more weight to the heuristic component of search.
• Good for suboptimal cases where finding a solution is more important that a good ideal solution .