Informed Search I

AIMA Chapter 3.5.1, 3.5.2

CIS 521
Outline
PART I
 Informed = use problem-specific knowledge
 Best-first search and its variants
 A* - Optimal Search using Knowledge
Today!!
 Proof of Optimality of A*
 A* for maneuvering AI agents in games
 Heuristic functions?
 How to invent them

PART II
 Local search and optimization
• Hill climbing, local beam search, genetic algorithms,…
 Local search in continuous spaces
 Online search agents

CIS 521 - Intro to AI

2
 Is Uniform Cost Search the best we can do?
Consider finding a route from Bucharest to Arad..

Arad

118

CIS 521 - Intro to AI

3
A Better Idea…
 Node expansion based on some estimate of
distance to the goal, extending current path

 General approach of informed search:

• Best-first search: node selected for expansion based
on an evaluation function f(n)
—f(n) includes estimate of distance to goal

 Implementation:
• Sort frontier queue monotonically by f(n).
• Special cases: greedy search, A* search
CIS 521 - Intro to AI
4
Arad

11
8

Romania with city-to-city

distances & straight-
line distances in km

CIS 521 - Intro to AI

5
A heuristic function

 Let evaluation function f(n) = h(n) (heuristic)

• h(n) = estimated cost of the cheapest path from
node n to goal node.
• If n is goal then h(n)=0

 Here: hSLD(n) = straight-line distance from n to

Bucharest

[dictionary]“A rule of thumb, simplification, or educated guess that reduces

or limits the search for solutions in domains that are difficult and poorly
understood.”

Heuristic knowledge is useful, but not necessarily correct.

Heuristic algorithms use heuristic knowledge to solve a problem.
A heuristic function here takes a state and returns an estimate of the distance to the goal.
Heureka! ---Archimedes
CIS 521 - Intro to AI
6
 Breadth First (Dijkstra) for Games, Robots, …

 Pink: Starting Point

 Blue: Goal
 Teal: Scanned squares
• Darker: Closer to starting point…

Graphics from
http://theory.stanford.edu/~amitp/GameProgramming/
(A great site for practical AI & game Programming

CIS 521 - Intro to AI

7
An optimal informed search algorithm (A*)

 We add a heuristic estimate of distance to the goal

 Yellow: examined nodes with high estimated distance

 Blue: examined nodes with low estimated distance

CIS 521 - Intro to AI

8
Breadth first in a world with obstacles

CIS 521 - Intro to AI

9
 Informed search (A*) in a world with obstacles

CIS 521 - Intro to AI

10
Greedy best-first search
 Informally: Expands the node that is estimated to
be closest to goal
 Expands nodes based on f(n) = h(n)
• (Again, h(n)): Some heuristic estimate of cost from n to goal)
 Ignores cost so far to get to that node (g(n))
 Here, h(n) = hSLD(n) = straight-line distance from n
to Bucharest

CIS 521 - Intro to AI

11
 Greedy best-first search example
Frontier
queue:
Arad

 Initial State = Arad

 Goal State = Bucharest

CIS 521 - Intro to AI

12
 Greedy best-first search example
Frontier
queue:
Sibiu
Timisoara
Zerind

CIS 521 - Intro to AI

13
 Greedy best-first search example
Frontier queue:
Fagaras
Rimnicu Vilcea
Timisoara
Arad
Zerind
Oradea

CIS 521 - Intro to AI

14
 Greedy best-first search example
Frontier queue:
Bucharest
Rimnicu Vilcea
Timisoara
Sibiu
Arad
Zerind
Oradea

Goal reached !!

CIS 521 - Intro to AI

15
Properties of greedy best-first search
 Optimal?
• No!
— Found: Arad  Sibiu  Fagaras  Bucharest (450km)
— Shorter: Arad  Sibiu  Rimnicu Vilcea  Pitesti Bucharest (418km)

Arad

118

CIS 521 - Intro to AI

16
Properties of greedy best-first search
 Complete?
• No – can get stuck in loops,
• e.g., Iasi  Neamt  Iasi  Neamt …

Initial
Goal

CIS 521 - Intro to AI

17
Properties of greedy best-first search
 Complete?
• No – can get stuck in loops,
• e.g., Iasi  Neamt  Iasi  Neamt 
 Time?
• O(bm) – worst case (like Depth First Search)
• But a good heuristic can give dramatic improvement
 Space?
• O(bm) – keeps all nodes in memory
 Optimal? No

CIS 521 - Intro to AI

18
A* search
 Best-known form of best-first search.
 Key Idea: avoid expanding paths that are already
expensive.
 Evaluation function f(n)=g(n) + h(n)
• g(n) the cost (so far) to reach the node
• h(n) estimated cost to get from the node to the goal
• f(n) estimated total cost of path through n to goal
 Implementation: Sort frontier queue by
increasing f(n)

CIS 521 - Intro to AI

19
Admissible heuristics
 Let h(n) be an admissible heuristic
• A heuristic is admissible if it never overestimates the
cost to reach the goal; i.e. it is optimistic
• Formally:
n, where n is a node:
1. h(n)  h*(n) where h*(n) is the true cost from n
2. h(n)  0 so h(G)=0 for any goal G.
• Example:
hSLD(n) never overestimates the actual road distance

Theorem: If h(n) is admissible, A* using Tree Search is

optimal
CIS 521 - Intro to AI
20
 A* search example
Frontier queue:
Arad

CIS 521 - Intro to AI

21
 A* search example
Frontier queue:
Sibiu
Timisoara
Zerind

We add the three nodes we found to the Frontier queue.

We sort them according to the g()+h() calculation.

CIS 521 - Intro to AI

22
 A* search example
Frontier queue:
Rimricu Vicea
Fagaras
Timisoara
Zerind
Arad
Oradea

When we expand Sibiu, we run into Arad again. Note that we’ve
already expanded this node once; but we still add it to the Frontier
queue again.
CIS 521 - Intro to AI
23
 A* search example
Frontier queue:
Fagaras
Pitesti
Timisoara
Zerind
Craiova
Sibiu
Arad
Oradea

We expand Rimricu Vicea.

CIS 521 - Intro to AI

24
 A* search example
Frontier queue:
Pitesti
Timisoara
Zerind
Bucharest
Craiova
Sibiu
Sibiu
Arad
Oradea

When we expand Fagaras, we find Bucharest, but we’re not done. The
algorithm doesn’t end until we “expand” the goal node – it has to be at
the top of the Frontier queue.

CIS 521 - Intro to AI

25
 A* search example
Frontier queue:
Bucharest
Timisoara
Zerind
Bucharest
Craiova
Rimricu Vicea
Sibiu
Sibiu
Craiova
Arad
Oradea

Note that we just found a better value for Bucharest!

Now we expand this better value for Bucharest.
We’re done and we know the value found is optimal!
CIS 521 - Intro to AI
26