Informed (Heuristic) Search

Informed (Heuristic) Search

Idea: be smart
about what paths
to try.

Blind Search vs. Informed Search

Informed search
• AI search problems are typically very large. We would like to improve efficiency
by expanding as few nodes as possible. • What’s the difference?
• The agent can use additional information in the form of “hints” about how
promising different states/nodes are to lead to the goal. These hints are derived
from
• information the agent has (e.g., a map) or
• percepts coming from a sensor. • How do we formally specify this?
• The agent uses a heuristic function 𝒉(𝒏) to rank nodes in the frontier and
A node is selected for expansion based on an
select the most promising state in the frontier for expansion using a best-first
search strategy.
evaluation function that estimates cost to goal.

• Algorithms:
• Greedy best-first search
• A* search
 Heuristic function Heuristic for the Romania problem
• Heuristic function ℎ(𝑛) estimates the cost of reaching a node representing the goal
state from the current node 𝑛. Drive from Arad to Bucharest using a table with straight-line distances.
• Examples: h(n)
Euclidean distance Manhattan distance
Start state Start state

Goal state Goal state

General Tree Search Paradigm General Graph Search Paradigm

function tree-search(root-node) function tree-search(root-node)
fringe  successors(root-node) fringe  successors(root-node)
while ( notempty(fringe) ) explored  empty
while ( notempty(fringe) )
{node  remove-first(fringe) //lowest f
{node  remove-first(fringe)
value state  state(node)
state  state(node)
if goal-test(state) return solution(node) if goal-test(state) return solution(node)
fringe  insert-all(successors(node),fringe) explored  insert(node,explored)
} return failure fringe  insert-all(successors(node),fringe, if node not in explored)
end tree-search }
return failure
end tree-search
• Frontier or fringe or open list

• Frontier or fringe or open list

• Explored or closed list

7 8
 Best-First Search
Best-first search
• Use an evaluation function f(n) for node n. • A search strategy is defined by picking the order of node expansion
• Always choose the node from fringe that has the lowest f value.
• Idea: use an evaluation function f(n) for each node
– estimate of "desirability“

 Expand most desirable unexpanded node

• Implementation:
Order the nodes in fringe in decreasing order of desirability
3 5 1

• Special cases:
4 6 – greedy best-first search
– A* search
9

Old (Uninformed) Friends

Romania with step costs in km • Breadth First =
– Best First
– with f(n) = depth(n)

• Uniform cost search =

– Best First
– with f(n) = the sum of edge costs from start to n
g(n)

12
 Greedy best-first search
• Evaluation function f(n) = h(n) (heuristic function)
= estimate of cost from n to goal greedy best-first search
• e.g., hSLD(n) = straight-line distance from n to Bucharest search algorithm that expands the node
that is closest to the goal, as estimated by a
• Greedy best-first search expands the node that appears to be heuristic function h(n)
closest to goal

Heuristic function? Heuristic function?

B B

A A
Heuristic function? Manhattan distance. Greedy Best-First Search

B 11 9 7 3 2 B
12 10 8 7 6 4 1

D 13 12 11 9 7 6 5 2

13 10 8 6 3

C 14 13 12 11 9 7 6 5 4

13 10

A A 16 15 14 11 10 9 8 7 6

Greedy Best-First Search Greedy Best-First Search

11 9 7 3 2 B 10 9 8 7 6 5 4 3 2 1 B
12 10 8 7 6 4 1 11 1

13 12 11 9 7 6 5 2 12 10 9 8 7 6 5 4 2

13 10 8 6 3 13 11 5 3

14 13 12 11 9 7 6 5 4 14 13 12 10 9 8 7 6 4

13 10 13 11 5

A 16 15 14 11 10 9 8 7 6 A 16 15 14 12 11 10 9 8 7 6
Greedy Best-First Search Greedy Best-First Search

10 9 8 7 6 5 4 3 2 1 B 10 9 8 7 6 5 4 3 2 1 B
11 1 11 1

12 10 9 8 7 6 5 4 2 12 10 9 8 7 6 5 4 2

13 11 5 3 13 11 5 3

14 13 12 10 9 8 7 6 4 14 13 12 10 9 8 7 6 4

13 11 5 13 11 5

A 16 15 14 12 11 10 9 8 7 6 A 16 15 14 12 11 10 9 8 7 6

Greedy best-first search example Greedy best-first search example

Expansion rule: Expand the node
that has the lowest value of the h(n)=
heuristic function h(n)
 Greedy best-first search example Greedy best-first search example

Total:
140 + 99 + 211 = 450 miles

Properties of greedy best-first search Implementation of greedy best-first search

• Complete?
Yes – Best-first search if complete in finite spaces.

• Optimal?
No Best-First Expand the frontier
using
Search 𝑓 𝑛 = ℎ(𝑛)
Total:
140 + 99 + 211 = 450 miles

Alternative through Rimnicu Vilcea:

140 + 80 + 97 + 101 = 418 miles
 Implementation of greedy best-first search Properties of greedy best-first search
Heuristic 𝒉(𝒏) so we expand the node with the lowest estimated cost
• Complete?
Yes – Best-first search if complete in finite spaces.

• Optimal?
No d: depth of the optimal
The order for expanding the solution
m: max. depth of tree
frontier is determined by
f(n)
• Time? b: maximum branching factor
Worst case: O(bm)  like DFS
Best case: O(bm) – If ℎ(𝑛) is 100% accurate

This check is the different • Space?

to BFS! It visits a node
See BFS for function EXPAND. again if it can be reached
Same as time complexity.
by a better (cheaper) path.
29

A* search
How can we fix the optimality problem with greedy best-first
search?
A* search
• Idea: avoid expanding paths that are already expensive
• Evaluation function f(n) = g(n) + h(n) search algorithm that expands node with
lowest value of g(n) + h(n)
• g(n) = cost so far to reach n
• h(n) = estimated cost from n to goal
g(n) = cost to reach node
h(n) = estimated cost to goal
• f(n) = estimated total cost of path through n to goal
A* Search A* Search

10 9 8 7 6 5 4 3 2 1 B 10 9 8 7 6 5 4 3 2 1 B
11 1 11 1

12 10 9 8 7 6 5 4 2 12 10 9 8 7 6 5 4 2

13 11 5 3 13 11 5 3

14 13 12 10 9 8 7 6 4 14 13 12 10 9 8 7 6 4

13 11 5 13 11 5

A 16 15 14 12 11 10 9 8 7 6 A 1+16 15 14 12 11 10 9 8 7 6

A* Search
A* search example
11+10 12+9 13+8 14+7 15+6 16+5 17+4 18+3 19+2 20+1 B Expansion rule: Expand 𝑓 𝑛 = 𝑔(𝑛) + ℎ(𝑛) =

the node with the

10+11 1
smallest f(n)
9+12 7+10 8+9 9+8 10+7 11+6 12+5 13+4 2

8+13 6+11 14+5 3 ℎ(𝑛)

7+14 6+13 5+12 10 9 8 7 15+6 4

4+13 11 5

A 1+16 2+15 3+14 12 11 10 9 8 7 6

A* search example A* search example
𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

ℎ(𝑛) ℎ(𝑛)

A* search example A* search example

𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛) 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

ℎ(𝑛) ℎ(𝑛)
A* search example Implementation of A* Search
𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

Best-First Expand the frontier

using
ℎ(𝑛) Search 𝑓 𝑛 = 𝑔 𝑛 + ℎ(𝑛)

Implementation of A* Search Example: Greedy Best First Search

Path cost to 𝑛 + heuristic from 𝑛 to goal = estimate of the total cost
𝑔 𝑛 + ℎ(𝑛)

[Link] Queue Visited

1 (S 10) S
2 (A 2) (B 3) S, A, B
The order for expanding the 3 (C 1) ( B 3)(D 4) S,A,B,D,C
frontier is determined by 4 (B 3)(D 4) S,A,B,D,C
𝑓(𝑛)
5 (G 0) (D 4) S,A,B,D,C,G

This check is different to

BFS! It visits a node again if
See BFS for function EXPAND. it can be reached by a
better (cheaper) redundant
path. 43
Example A* graph search Example: use A* to search Goal G

[Link] Queue Visited

1 (S 0) S
2 (A 4) (B 8) S, A, B
3 (C 5) (D 7)( B 8) S,A,B,D,C
4 (D 7)(B 8) S,A,B,D,C
5 (G 8) (B 8)(C 10) S,A,B,D,C,G
A* search Example A*
A and G be respectively the starting and goal nodes
•h(A) =0; h(B)=3; h(C)=4; h(G)=0

If the A∗ algorithm starts initially from node A, it will

select next node B for expansion and, after this, it will
reach node G from there. And the path will
be A→B→G with cost 4, instead of A→C→G with
cost 3.

[Link]

Admissible heuristic
• An admissible heuristic never overestimates the cost to reach the
A* search goal, i.e., it is optimistic
• A heuristic h(n) is admissible if for every node n, h(n) ≤ h*(n), where
h*(n) is the true cost to reach the goal state from n
optimal if
• Consequence: f(n) never over estimates the true cost of a solution
- h(n) is admissible (never overestimates through n since g(n) is the exact cost to reach n
the true cost), and • Example: straight line distance never overestimates the
- h(n) is consistent (for every node n and actual road distance
successor n' with step cost c, h(n) ≤ h(n') + c) • Theorem: If h(n) is admissible,A* is optimal
 Example A* Not all heuristics are admissible
A and G be respectively the starting and goal nodes
•h(A) =0; h(B)=3; h(C)=4; h(G)=0

This heuristics function h is not admissible,

because h(C)=4>c(C,G)=2
If the heuristic function was admissible this
would not have happened.

Consistent heuristics
67

Consistency of heuristics

h=4 • A heuristic is consistent if for every node n, every successor n' of n

generated by any action a,
h(n) ≤ c(n,a,n') + h(n')
n' = successor of n generated by action a
• The estimated cost of reaching the goal from n is no greater than the step
cost of getting to n' plus the estimated cost of reaching the goal from n'
• If h is consistent, we have
f(n') = g(n') + h(n')
= g(n) + c(n,a,n') + h(n')
≥ g(n) + h(n)
≥ f(n)
• if h(n) is consistent then the values of f(n) along any path are non-
decreasing
• Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal
Optimality of A* Example

• Tree search (i.e., search without repeated state detection):

– A* is optimal if heuristic is admissible (and non- negative)
• Graph search (i.e., search with repeated state detection)
– A* optimal if heuristic is consistent
• Consistency implies admissibility
– In general, most natural admissible heuristics tend to be consistent,
especially if they come from relaxed problems