Artificial Intelligence Heuristic (Informed) Search

Artificial Intelligence
Heuristic (Informed) Search
Prof. Dr. habil. Jana Koehler

Dr. Sophia Saller, M. Sc. Annika Engel
Deep thanks goes to
Summer 2020 Prof. Jörg Hoffmann for
sharing his course material
© JK
Agenda
 Using Knowledge during Search
– evaluation of search states
– admissible and consistent (monotone) heuristics
 Algorithms
1) Greedy (Best-First) Search
2) A* and IDA*
3) Bidirectional Search
 Finding good heuristics
2 Artificial Intelligence: Heuristic Search © JK

Recommended Reading
 AIMA Chapter 3: Solving Problems by Searching
– 3.4 Uninformed Search Strategies, the following subchapters:
• 3.4.6 Bidirectional search
– 3.5 Informed (Heuristic) Search Strategies
• 3.5.1 Greedy best-first search
• 3.5.2 A* search: Minimizing the total estimated solution cost
– 3.6 Heuristic Functions
• 3.6.1 The effect of heuristic accuracy on performance
• 3.6.2 Generating admissible heuristics from relaxed problems
• 3.6.3 Generating admissible heuristics from subproblems: Pattern
databases
 Optional reading:
– R. C. Holte, A. Felner, G. Sharon, N. R. Sturtevant: Bidirectional
Search That Is Guaranteed to Meet in the Middle, AAAI-2016
How to Determine the next Node for Expansion?
 Uninformed Search
– rigid procedure, no knowledge of the cost from a node to
the goal
– e.g. FIFO, LIFO queues
 Informed Search
– "value" of expanding a node (state) used as guidance
that steers the search algorithm through the search
space
– evaluation function f(s) assigns a number to each state

The Evaluation Function 𝒇𝒇(𝒔𝒔) = 𝒈𝒈(𝒔𝒔) + 𝒉𝒉(𝒔𝒔)
C(3) s4
s1 𝑠𝑠𝑔𝑔𝑔
A(2) g=5
g=2
s2 h*=7
G(0) G(0)
C(3)
I C(3)
s5 𝑠𝑠𝑔𝑔𝑔
G(0)
g=7
B(4) s3 h*=0 G(0)
E(0)
g=4 F(1) H(2) 𝑠𝑠𝑔𝑔𝑔
E(0) s6
s7
𝑔𝑔(𝑠𝑠) corresponds to the costs ℎ(𝑠𝑠) corresponds to the

from the initial state to the + estimated costs from the current
current state 𝑠𝑠 state 𝑠𝑠 to the goal state 𝑠𝑠𝑔𝑔
 a precise value  an estimated value
Heuristic Functions 𝒉𝒉 and 𝒉𝒉∗
Let Π be a problem with state space Θ. A heuristic function, short heuristic,
for Θ is a function ℎ ∶ 𝑆𝑆 ↦ ℝ+
0 ∪ ∞ so that, for every goal state 𝑠𝑠, we have
ℎ(𝑠𝑠) = 0.
The perfect heuristic ℎ∗ is the function assigning every 𝑠𝑠 ∈ 𝑆𝑆 the cost of a

cheapest path from 𝑠𝑠 to a goal state, or ∞ if no such path exists.
0, if 𝑠𝑠 is a goal state
 ℎ 𝑠𝑠 = �
> 0, otherwise
 ℎ∗ 𝑠𝑠 = ∞ for dead-end states, from which the goal is unreachable
 ℎ∗ 𝑠𝑠 is also called the goal distance of 𝑠𝑠
 The value of ℎ depends only on the state 𝑠𝑠, not on the path that we
followed so far to construct the partial solution (and the costs 𝑔𝑔 of this
path)
6 © JK
Artificial Intelligence: Heuristic Search
Desirable Properties of Heuristic Function 𝒉𝒉(𝒔𝒔)
1) Efficient to compute (ℎ 𝑠𝑠 = 0 as extreme case)
2) Informative (ℎ(𝑠𝑠) = ℎ∗ (𝑠𝑠) as extreme case)
0, if 𝑠𝑠 is a goal state
3) ℎ 𝑠𝑠 = �
> 0, otherwise
4) ℎ is admissible
5) ℎ 𝑠𝑠𝑑𝑑 = ∞ for dead-end states 𝑠𝑠𝑑𝑑
6) ℎ is consistent
 GOOD heuristics should satisfy a balanced compromise of properties (1)
to (4) at least, better of all 6
 Properties (5) ensures effective dead-end recognition and (6) is a
prerequisite for algorithms to guarantee minimal-cost (optimal) solutions
Admissiblity of 𝒉𝒉(𝒔𝒔)
Let Π be a problem with state space Θ and let ℎ be a heuristic

function for Θ. We say that ℎ is admissible if, for all 𝑠𝑠 ∈ 𝑆𝑆, we
have ℎ 𝑠𝑠 ≤ ℎ∗ (𝑠𝑠).
The function ℎ∗ 𝑠𝑠 corresponds to the real cost of the optimal

path from node 𝑛𝑛 to a goal state.
The function ℎ is an optimistic estimation of the costs that

actually occur. It underestimates the real costs and provides
the search algorithm with a lower bound on the goal distance.

Consistency (Monotonicity) of h(s)
Let Π be a problem with state space Θ, and let ℎ be a heuristic function for
𝑎𝑎
Θ. We say that ℎ is consistent if, for all transitions s → 𝑠𝑠 ′ in Θ, we have
ℎ 𝑠𝑠 − ℎ 𝑠𝑠 ′ ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 .
The value 𝑐𝑐 𝑠𝑠, 𝑎𝑎 is the action cost of getting from 𝑠𝑠 to 𝑠𝑠𝑠 with action 𝑎𝑎.
We reformulate the inequality from above to: ℎ 𝑠𝑠 ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 + ℎ(𝑠𝑠𝑠).
𝑠𝑠
𝑐𝑐(𝑠𝑠, 𝑎𝑎) Triangle inequality: The sum of the lengths of
any two sides of a triangle must be greater or
equal than the length of the remaining side.
𝑠𝑠𝑠
ℎ(𝑠𝑠)
ℎ(𝑠𝑠𝑠) Applying an action 𝑎𝑎 to the state 𝑠𝑠, the
heuristic value cannot decrease by more
than the cost 𝑐𝑐 𝑠𝑠, 𝑎𝑎 of 𝑎𝑎.
goal state
Consistency ⟹ Admissibility
Let Π be a problem with state space Θ and let ℎ be a heuristic function forΘ.
If ℎ is consistent, then ℎ is admissible.
𝑎𝑎
To show: ℎ 𝑠𝑠 − ℎ 𝑠𝑠 ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 , ∀𝑠𝑠 → 𝑠𝑠 ′ ⟹ ℎ(𝑠𝑠) ≤ ℎ∗ (𝑠𝑠), ∀𝑠𝑠 ∈ 𝑆𝑆.
′
This means that we need to show that a consistent heuristic never

overestimates the costs to the goal.
Observation: The value of ℎ can at most decrease by the action costs.

ℎ(𝑠𝑠)
ℎ(𝑠𝑠0)
𝑐𝑐(𝑠𝑠0 , 𝑎𝑎1)
ℎ 𝑠𝑠 − ℎ(𝑠𝑠𝑠) ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎
ℎ(𝑠𝑠1)
⇔ ℎ 𝑠𝑠 ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 + ℎ(𝑠𝑠𝑠)
𝑐𝑐(𝑠𝑠1 , 𝑎𝑎2) ℎ(𝑠𝑠2)
.
.
.
𝑎𝑎1 𝑎𝑎2 𝑎𝑎3

𝑠𝑠0 𝑠𝑠1 𝑠𝑠2 𝑠𝑠3 → ⋯ → 𝑠𝑠𝑔𝑔
10 © JK
Artificial Intelligence: Heuristic Search
Proof: We need to show that 𝒉𝒉 𝒔𝒔 ≤ 𝒉𝒉∗ 𝒔𝒔 for all 𝒔𝒔.
For states 𝑠𝑠 (dead ends) where ℎ∗ (𝑠𝑠) = ∞, this is trivial as any number is ≤ ∞.
Now let 𝒮𝒮𝑘𝑘 be the set of non dead-end states with a shortest cheapest path to a goal
state of length 𝑘𝑘.
We will prove for all 𝑘𝑘 that ℎ 𝑠𝑠 ≤ ℎ∗ 𝑠𝑠 for all 𝑠𝑠 ∈ 𝒮𝒮𝑘𝑘 by induction over 𝑘𝑘.
Base case: 𝑠𝑠 is a goal state, so 𝑠𝑠 ∈ 𝒮𝒮0 (𝑘𝑘 = 0). By the definition of heuristic functions
then ℎ(𝑠𝑠) = 0 and so ℎ(𝑠𝑠) ≤ ℎ∗ (𝑠𝑠) = 0 as required.
Inductive Hypothesis: For all 𝑠𝑠 ∈ 𝒮𝒮𝑘𝑘 we have that ℎ 𝑠𝑠 ≤ ℎ∗ 𝑠𝑠 .
Inductive step: Let 𝑠𝑠 ∈ 𝒮𝒮𝑘𝑘+1 . Then the cheapest path from 𝑠𝑠 to a goal state has length
𝑎𝑎
𝑘𝑘 + 1. Let 𝑠𝑠𝑠 be the successor state of 𝑠𝑠 in this cheapest path, so 𝑠𝑠 → 𝑠𝑠𝑠. We thus know
that 𝑠𝑠𝑠 ∈ 𝒮𝒮𝑘𝑘 and therefore
1) By the consistency of ℎ we have: ℎ 𝑠𝑠 − ℎ 𝑠𝑠 ′ ≤ 𝑐𝑐(𝑠𝑠, 𝑎𝑎)
2) By the Inductive Hypothesis: ℎ 𝑠𝑠 ′ ≤ ℎ∗ 𝑠𝑠′
3) Since the cheapest path has the cheapest costs: ℎ∗ 𝑠𝑠 = ℎ∗ 𝑠𝑠 ′ + 𝑐𝑐(𝑠𝑠, 𝑎𝑎)
Combining these three statements, we get
𝒉𝒉 𝒔𝒔 ≤ ℎ 𝑠𝑠 ′ + 𝑐𝑐 𝑠𝑠, 𝑎𝑎 ≤ ℎ∗ 𝑠𝑠′ + 𝑐𝑐 𝑠𝑠, 𝑎𝑎 = 𝒉𝒉∗ (𝒔𝒔)
QED
11
1) 2) 3) © JK
(1) Greedy Best-First Search
 Uses only the heuristic part of the evaluation function
𝑓𝑓(𝑠𝑠) = ℎ(𝑠𝑠)
 Expands the node first that is estimated as being closest to

the goal
 Does not consider the current path costs

– "counterpart" to uniform-cost search, which uses
𝑓𝑓(𝑠𝑠) = 𝑔𝑔(𝑠𝑠)

GBFS Algorithm
 Frontier ordered by ascending ℎ

 Duplicates checked at successor generation, against both
the frontier and the explored set
GBFS on the Romania Travel Example
h: Aerial Distances
to Bucharest

Properties of GBFS
 Complete
– for finite state spaces and with duplicate elimination
 Not optimal
 Time complexity is 𝑂𝑂(𝑏𝑏𝑚𝑚)

 Space complexity is 𝑂𝑂 𝑏𝑏𝑚𝑚
where 𝑚𝑚 is the maximum depth of the search space

(2) A* (Hart, Nilsson, Raphael 1968)
 Greedy search only uses ℎ(𝑠𝑠)
 Uniform-Cost search uses 𝑔𝑔(𝑠𝑠)

– finds an optimal solution if path costs grow monotonically:
𝑔𝑔(𝑠𝑠) ≤ 𝑔𝑔(𝑠𝑠𝑠)
 A* uses 𝑓𝑓(𝑠𝑠) = 𝑔𝑔(𝑠𝑠) + ℎ(𝑠𝑠)
 A* combines both using preferably admissible and consistent

heuristics
 http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
gives a good introduction

A* Algorithm
Frontier ordered by ascending 𝑔𝑔 + ℎ, duplicates handled as in UCS (nodes

replaced by duplicates with cheaper costs)
Properties of A*
 A* is complete
– if a solution exists, A* will find it provided that
1) every node has a finite number of successor nodes, and
2) each action has positive and finite costs
 A* is optimal
– first solution found has minimum path cost if ℎ is
admissible (on trees) or if ℎ is consistent (on graphs)
• under an admissible heuristics on graphs, A* needs to expand all
nodes with 𝑓𝑓(𝑛𝑛) ≤ 𝐶𝐶 ∗ (the cost of an optimal solution), called
“re-opening”
• For any path, re-opening checks if it is the cheapest to a state 𝑠𝑠
and puts explored states back into the frontier if a cheaper path
was found
Properties of A*
 Time Complexity is 𝑂𝑂(𝑏𝑏 𝑑𝑑 )
 Space Complexity is 𝑂𝑂(𝑏𝑏𝑚𝑚), where 𝑚𝑚 is the maximum

depth of the search space
– subexponential growth requires that the error in the

heuristic function grows no faster than the logarithm of
the actual path cost
ℎ 𝑠𝑠 − ℎ∗ (𝑠𝑠) ≤ 𝑂𝑂 log ℎ∗ (𝑠𝑠)

A* on the Romania Travel Example
h: Aerial Distances
to Bucharest

Computed f-Values in the Example
Frontier:
S,T,Z
R,F,T,Z,O
F,P,T,Z,C,O
P,T,Z,B,C´,O
Bucharest is inserted
after Pitesti in the
frontier!
B´,T,Z,C´,O

f-based Contours in the Search Space
 A* fans out from the start node, adding nodes in concentric
bands of increasing f-costs
– with good heuristics the bands stretch towards the goal state and are
more narrowly focused around the optimal path

Proof of Optimality of A* under Consistent Heuristics
 The general idea for the proof is to encode the consistent
heuristic function as action costs and establish a
correspondence to uniform cost search
– UCS is optimal for non-negative action costs (Dijkstra´s
algorithm)
 We then show that the original and the transformed problem

have the same optimal solutions and isomorphic search
spaces
 Finally, we can prove that every optimal solution found by A*
on the transformed problem, is also an optimal solution for
the original problem

Step 1: Encoding Heuristic Values as Action Costs
Definition: Let Π be a problem with state space Θ = 𝑆𝑆, 𝐴𝐴, 𝑐𝑐, 𝑇𝑇, 𝐼𝐼, 𝑆𝑆 𝐺𝐺 , and
let ℎ be a consistent heuristic function for Π. We define the ℎ-weighted
state space as Θℎ = 𝑆𝑆, 𝐴𝐴ℎ , 𝑐𝑐 ℎ , 𝑇𝑇 ℎ , 𝐼𝐼, 𝑆𝑆 𝐺𝐺 where:
• 𝐴𝐴ℎ ≔ 𝑎𝑎 𝑠𝑠, 𝑠𝑠 ′ | 𝑎𝑎 ∈ 𝐴𝐴, 𝑠𝑠, 𝑠𝑠 ′ ∈ 𝑆𝑆, 𝑠𝑠, 𝑎𝑎, 𝑠𝑠 ′ ∈ 𝑇𝑇 ,
• 𝑐𝑐 ℎ : 𝐴𝐴ℎ → ℝ+ ℎ
0 is defined by 𝑐𝑐 𝑎𝑎 𝑠𝑠, 𝑠𝑠𝑠 ≔ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 − ℎ 𝑠𝑠 − ℎ 𝑠𝑠
′ ,
• 𝑇𝑇 ℎ = 𝑠𝑠, 𝑎𝑎 𝑠𝑠, 𝑠𝑠𝑠 , 𝑠𝑠 | 𝑠𝑠, 𝑎𝑎, 𝑠𝑠𝑠 ∈ 𝑇𝑇 .

Remember consistency of ℎ:
ℎ 𝑠𝑠 ≤ 𝑐𝑐 𝑠𝑠, 𝑎𝑎 + ℎ 𝑠𝑠 ′
= ℎ 𝑠𝑠 − ℎ(𝑠𝑠𝑠) ≤ 𝑐𝑐(𝑠𝑠, 𝑎𝑎)
Lemma: Θℎ is well-defined, i.e.

𝑐𝑐 𝑠𝑠, 𝑎𝑎 − ℎ 𝑠𝑠 − ℎ(𝑠𝑠𝑠) ≥ 0.
Proof: The assumption follows immediately from consistency.

Illustration of Encoding
700 = 400 - (2200 - 2500) 150 = 650 - (2200 -1700) 250 = 1950 - (1700 - 0)
Optimal Solution: SB - DD - M 650 + 1950 = 2600 = 150 + 250 + 2200

26 h(SB) © JK
Identify the Correspondence (1)
Lemma A: Θ and Θℎ have the same optimal solutions.
𝑎𝑎1 𝑎𝑎𝑛𝑛
Proof: Let 𝑠𝑠0 𝑠𝑠1 , … , 𝑠𝑠𝑛𝑛−1 𝑠𝑠𝑛𝑛 be the corresponding state path of a solution
in Θ, 𝑠𝑠𝑛𝑛 ∈ 𝑆𝑆 𝐺𝐺 . The cost of the same path in Θℎ is 𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁: − ℎ 𝑠𝑠 − ℎ 𝑠𝑠 ′ = −ℎ 𝑠𝑠 + ℎ 𝑠𝑠 ′
−ℎ 𝑠𝑠0 + 𝑐𝑐 𝑠𝑠0 , 𝑎𝑎1 + ℎ(𝑠𝑠1 ) + −ℎ 𝑠𝑠1 + 𝑐𝑐 𝑠𝑠1 , 𝑎𝑎2 + ℎ(𝑠𝑠2 ) +

⋯ + −ℎ 𝑠𝑠𝑛𝑛−1 + 𝑐𝑐 𝑠𝑠𝑛𝑛−1 , 𝑎𝑎𝑛𝑛 + ℎ(𝑠𝑠𝑛𝑛 )
= −ℎ 𝑠𝑠0 + 𝑐𝑐 𝑠𝑠0 , 𝑎𝑎1 + ℎ 𝑠𝑠1 − ℎ 𝑠𝑠1 + 𝑐𝑐 𝑠𝑠1 , 𝑎𝑎2 + ℎ 𝑠𝑠2 − ℎ 𝑠𝑠2 +
ℎ 𝑠𝑠𝑖𝑖 − ℎ 𝑠𝑠𝑖𝑖 = 0 ⋯ − ℎ 𝑠𝑠𝑛𝑛−1 + 𝑐𝑐 𝑠𝑠𝑛𝑛−1 , 𝑎𝑎𝑛𝑛 + ℎ(𝑠𝑠𝑛𝑛 )
∀𝑠𝑠𝑖𝑖 ∈ 𝑆𝑆
𝑛𝑛 𝑛𝑛
= � 𝑐𝑐 𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 − ℎ 𝑠𝑠0 + ℎ(𝑠𝑠𝑛𝑛 ) = � 𝑐𝑐 𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 − ℎ 𝑠𝑠0 ,

𝑖𝑖=1 𝑖𝑖=1
since 𝑠𝑠𝑛𝑛 is a goal state, it holds ℎ 𝑠𝑠𝑛𝑛 = 0.
Thus, the costs of solution paths in Θℎ are those of Θ, minus a constant.

The claim follows.
Identify the Correspondence (2)
Lemma B: The search space of A* on Θ is isomorphic to that of uniform-

cost on Θℎ .
𝑎𝑎1 𝑎𝑎𝑛𝑛
Proof: Let 𝑠𝑠0 𝑠𝑠1 , … , 𝑠𝑠𝑛𝑛−1 𝑠𝑠𝑛𝑛 be any state path in Θ. The 𝑔𝑔 + ℎ value,
used by A*, is ∑𝑛𝑛𝑖𝑖=1 𝑐𝑐(𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 ) + ℎ(𝑠𝑠𝑛𝑛 ). The 𝑔𝑔 value in Θℎ , used by
uniform-cost search on Θℎ , is ∑𝑛𝑛𝑖𝑖=1 𝑐𝑐(𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 ) − ℎ 𝑠𝑠0 + ℎ(𝑠𝑠𝑛𝑛 ) (see Proof
of Lemma A). The difference −ℎ(𝑠𝑠0 ) is constant, so the ordering of the
frontier (open list) is the same. As the duplicate elimination is identical,
the assumption is shown.

Illustration of A* and UCS Searches
400+2500 650+1700
650+1950+0

Proving the Final Theorem
Theorem (Optimality of A*)

Let Π be a problem with state space Θ, and let ℎ be a heuristic
function for Θ. If ℎ is consistent, then the solution returned by
A* (if any) is optimal.
∗
Proof Let 𝜌𝜌 𝐴𝐴 be the solution returned by A* run on Θ. Denote by 𝕊𝕊𝑈𝑈𝑈𝑈𝑈𝑈 the
set of all solutions that can possibly be returned by uniform cost
search run on Θℎ .
∗
By Lemma B we know that 𝜌𝜌 𝐴𝐴 ∈ 𝕊𝕊𝑈𝑈𝑈𝑈𝑈𝑈 .
By optimality of Uniform-Cost-Search, every element of 𝕊𝕊𝑈𝑈𝑈𝑈𝑈𝑈 is an
optimal solution for Θℎ .
∗
Thus 𝜌𝜌 𝐴𝐴 is an optimal solution for Θℎ .
∗
Together with Lemma A, this implies that 𝜌𝜌 𝐴𝐴 is an optimal solution
for Θ.

IDA* (Korf 1985)
 A* requires exponential memory in the worst case
– combine with Depth-Limited Search
 Idea: use successive iterations with increasing 𝑓𝑓-costs
– use 𝑓𝑓-bounds instead of bounding the length of the path
 At each iteration, perform a depth-first search, cutting off a

branch when its total cost (𝑔𝑔 + ℎ) exceeds a given threshold
– threshold starts at the estimate of the cost of the initial
state, and increases for each iteration of the algorithm
– at each iteration, the threshold used for the next iteration
is the minimum cost of all values that exceeded the
current threshold
Example of IDA*
 initial 𝑓𝑓-cost limit = 366 (𝑓𝑓-costs of the initial state)
– first expansion: T=118 +329=447, S=140+253=393, Z=75+374=449
 next 𝑓𝑓-cost limit = 393 (S)

Properties of IDA*
 IDA* is complete if every node has a finite number of successor nodes

and if each action has positive and finite costs
 IDA* is optimal. The first solution found has minimal path costs if ℎ is
admissible (tree) or consistent (graph)
 Time Complexity is 𝑂𝑂(𝑏𝑏 𝑑𝑑 )
 Space Complexity is 𝑂𝑂(𝑑𝑑)

(3) Bidirectional Search (Concept of Searching)
 2 simultaneous searches: 1 forward (starting at initial state) and 1

backward (starting at goal state)
 Hoping that the two searches meet in an intersection state in the
middle
 Motivation: 𝑂𝑂 𝑏𝑏𝑑𝑑⁄2 is exponentially less than 𝑂𝑂 𝑏𝑏 𝑑𝑑
 Any search technique can be used
 Goal test ⟶ test if two searches have intersection state
Example
Forward search Backward search
with BFS: E with DFS:
A→B→C →D K → I → G→ D
B
F
Initial state
A C
G I
Goal state
D K
H J
⟹ Problem: We do not necessary meet in the middle

and there is no guarantee that the solution is optimal
(3) Bidirectional Search – MM Algorithm (Holte et al 2016)
R. C. Holte, A.
Felner, G. Sharon,
N. R. Sturtevant:
Bidirectional
Search That Is
Guaranteed to
Meet in the Middle,
AAAI-2016
 First letter indicates the distance from start (N=near, F=far, R=remote)
and the second letter indicates the distance from goal (N=near, F=far)
 NN includes only those states at the exact midpoint of optimal
solutions

Measuring Heuristic Distances in Bidirectional Search
 A* search in both directions

 Each search direction uses an admissible front-to-end
heuristic that directly estimates the distance from node 𝑛𝑛 to
the target of the search (target for forward search is the
goal, target for backward search is the start state)
 𝑑𝑑(𝑢𝑢, 𝑣𝑣) is the distance (cost of a least-cost path) from state 𝑢𝑢
to state 𝑣𝑣
 𝐶𝐶 ∗ = 𝑑𝑑("start", "goal") is the cost of an optimal solution
 State 𝑠𝑠 is “near to goal” if 𝑑𝑑(𝑠𝑠, goal) ≤ 𝐶𝐶 ∗ ⁄2, and “far from
goal” otherwise. For start, we make a 3-way distinction: 𝑠𝑠 is
“near to start” if 𝑑𝑑(start, 𝑠𝑠) ≤ 𝐶𝐶 ∗ ⁄2, “far from start” if 𝐶𝐶 ∗ ⁄2 <
𝑑𝑑(start, 𝑠𝑠) ≤ 𝐶𝐶 ∗ , and “remote” if 𝑑𝑑(start, 𝑠𝑠) > 𝐶𝐶 ∗
Properties of MM
 MM is complete
 MM is optimal for non-negative action costs, the first

solution found has minimal path costs if ℎ is admissible
(tree) or consistent (graph)
 If there exists a path from start to goal and MM’s heuristics

are consistent, MM never expands a state twice
Overview on Properties of Heuristic Algorithms
Criterion Greedy Best- A* search IDA* search MM Algorithm
First Search (Bidirectional
search)
Evaluation
function 𝒇𝒇(𝒔𝒔) ℎ(𝑠𝑠) 𝑔𝑔 𝑠𝑠 + ℎ(𝑠𝑠) 𝑔𝑔 𝑠𝑠 + ℎ(𝑠𝑠) 𝑔𝑔 𝑠𝑠 + ℎ(𝑠𝑠)
Complete? Yesa,b Yesc,d Yesc,d Yese

Time 𝑂𝑂 𝑏𝑏 𝑚𝑚 𝑂𝑂 𝑏𝑏 𝑑𝑑 𝑂𝑂 𝑏𝑏 𝑑𝑑 ?
Space 𝑂𝑂 𝑏𝑏 𝑚𝑚 𝑂𝑂 𝑏𝑏 𝑚𝑚 𝑂𝑂 𝑑𝑑 g ?
Optimal? No Yese Yese Yesf
Superscripts:
Where: a for finite state spaces
𝑑𝑑 depth of solution b with duplicate elimination
𝑚𝑚 maximum depth of the search space c if every node has a finite number of
successor nodes
d if each action has positive and finite costs
e 1st solution found has minimal path costs if ℎ
is admissible (tree) or consistent (graph)
f for non-negative action costs
39
g with backtracking search, else 𝑂𝑂(𝑏𝑏𝑏𝑏) © JK
Designing Heuristic Functions
 The informedness of the heuristic is critical for the success
of the search algorithm
– steer the algorithm towards the most promising parts of
the search space
– recognize dead ends early
– find a near-optimal solution under practical conditions
 Requires an understanding of the application domain

– keep heuristic and search approach separate
– try out different variants in empirical tests
– an art form and a hot topic in AI research

Heuristic Functions Example
ℎ1 corresponds to the number of tiles in the wrong position (Misplaced Tiles)

ℎ2 corresponds to the sum of the distances of the tiles from their goal
positions (Manhattan distance)
Misplaced Tiles vs. Manhattan Distance
h1 = 8 (all tiles are misplaced)
h2 = 3 + 1 + 2 + … = 18
initial state goal state
 Distance between two points measured along axes at right

angles goal position
current position
 Disadvantage: considers all tiles independently

Empirical Comparison of Both Example Heuristics

Linear Conflict Heuristic vs. Manhattan Distance
LC: 2 + 2 = 4
MH: 2 + 0 = 2
 Two tiles 𝑡𝑡𝑗𝑗 and 𝑡𝑡𝑘𝑘 are in a linear conflict if 𝑡𝑡𝑗𝑗 and 𝑡𝑡𝑘𝑘 are in
the same line, the goal positions of 𝑡𝑡𝑗𝑗 and 𝑡𝑡𝑘𝑘 are both in that
line, 𝑡𝑡𝑗𝑗 is to the right of 𝑡𝑡𝑘𝑘 and the goal position of 𝑡𝑡𝑗𝑗 is to the
left of the goal position of 𝑡𝑡𝑘𝑘
– LC will add a cost of 2 moves for each pair of conflicting
tiles to the Manhattan Distance
– Motivation: Tiles need to surround one another
 LC is consistent and more informative than MH
Gaschnig's Heuristic
9 stands for the blank
transform 724596831
into 912345678
Relaxed Move: Any tile can be moved to the blank position

(count the number of swaps)
loop until solution is found:
If 9 is not at the 1st position
then swap 9 with the element whose target position 9 is taking
else swap 9 with the rightmost element that is not in its proper place
724596831 – 729546831 – 792546831 – 712546839 – 712546938 – 712549638 –
712945638 – 712345698 – 912345678
= 8 swaps

Applying Gaschnigs Heuristic During Search
724596831
794526831 724956831 724569831 724536891

 4 successor nodes
 Compute the number of swaps for each node
 Expand the node with the fewest number of swaps first
 Problem relaxation is a powerful idea and very successfully
used to derive good heuristics
Problem Relaxation on Whitebox Description
 Primitive Predicates in the N-Puzzle
– ON(t, y) : tile t is on cell y
– CLEAR(y) : cell y is clear of tiles
– ADJ(y, z) : cell y is adjacent to cell z
 Move(t, y, z)
preconditions : ON(t, y) & CLEAR(z) & ADJ(y, z)
effects : ON(t, z) & CLEAR(y) &
NOT ON(t, y) & NOT CLEAR(z)
 Remove CLEAR(z) & ADJ(y, z) – Misplaced Tile heuristic

 Remove CLEAR(z) – Manhattan Distance heuristic
 Remove ADJ(y, z) – Gaschnig's heuristic
Pattern Database
 Apply the Divide and Conquer principle
– decompose the problem into subproblems (subgoals)
– store solutions to the subproblems with associated costs
(patterns)
– reuse these solutions
Divide the 15 puzzle into Fringe + 8 puzzle
• map the current location of the fringe tiles
into an index of the database
• the data base tells us the minimal number
of moves to achieve the fringe
• achieve the fringe + solve the remaining 8
puzzle
 Famous example: end game libraries in chess

Learning Heuristic Functions
 Relaxed problem heuristic

– problem with fewer restrictions on the actions is called a
relaxed problem
– cost of an optimal solution path to a relaxed problem is
an admissible heuristic for the original problem
 Modern search algorithms analyze the domain and the

given problem instance
– learn a problem-instance specific heuristic before they
start searching

Summary
 Heuristic search is the preferred search method for medium
size search spaces
 The effectiveness of heuristic search depends on the
properties of the heuristic function: efficient to compute,
informative, admissible, consistent
 Only recently, a bidirectional search algorithm was
developed, which is guaranteed to meet in the middle, but
does not gurantee to reduce search and memory costs in
the worst case
 Greedy best-first search often quickly finds good solutions in
practice
 A* is optimal on graphs when using consistent heuristics
 Finding good heuristics can be done by analyzing the
50
search problem, e.g. using relaxation methods © JK
Working Questions
1. Explain the underlying ideas of greedy (best-first) search,
A* and IDA*.
2. What are the properties of A*?
3. Why can IDA* be more efficient than A* in practice?
4. What are heuristics, which role do they play in informed
search?
5. Which properties have good heuristics?
6. What is an admissible/consistent heuristic function?
7. What can happen with A* if the heuristic function is non-
admissible / non-consistent?
8. What is important for bidirectional search to work?

Artificial Intelligence Heuristic (Informed) Search

Uploaded by

Copyright:

Available Formats

Artificial Intelligence Heuristic (Informed) Search

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Artificial Intelligence Heuristic (Informed) Search

Uploaded by

Copyright:

Available Formats

Artificial Intelligence

Heuristic (Informed) Search

Prof. Dr. habil. Jana Koehler

 Finding good heuristics

2 Artificial Intelligence: Heuristic Search © JK

4 Artificial Intelligence: Heuristic Search © JK

𝑔𝑔(𝑠𝑠) corresponds to the costs ℎ(𝑠𝑠) corresponds to the

The perfect heuristic ℎ∗ is the function assigning every 𝑠𝑠 ∈ 𝑆𝑆 the cost of a

Let Π be a problem with state space Θ and let ℎ be a heuristic

The function ℎ∗ 𝑠𝑠 corresponds to the real cost of the optimal

The function ℎ is an optimistic estimation of the costs that

8 Artificial Intelligence: Heuristic Search © JK

This means that we need to show that a consistent heuristic never

Observation: The value of ℎ can at most decrease by the action costs.

𝑎𝑎1 𝑎𝑎2 𝑎𝑎3

Inductive Hypothesis: For all 𝑠𝑠 ∈ 𝒮𝒮𝑘𝑘 we have that ℎ 𝑠𝑠 ≤ ℎ∗ 𝑠𝑠 .

 Expands the node first that is estimated as being closest to

 Does not consider the current path costs

12 Artificial Intelligence: Heuristic Search © JK

 Frontier ordered by ascending ℎ

14 Artificial Intelligence: Heuristic Search © JK

 Time complexity is 𝑂𝑂(𝑏𝑏𝑚𝑚)

where 𝑚𝑚 is the maximum depth of the search space

16 Artificial Intelligence: Heuristic Search © JK

 Uniform-Cost search uses 𝑔𝑔(𝑠𝑠)

 A* uses 𝑓𝑓(𝑠𝑠) = 𝑔𝑔(𝑠𝑠) + ℎ(𝑠𝑠)

 A* combines both using preferably admissible and consistent

17 Artificial Intelligence: Heuristic Search © JK

Frontier ordered by ascending 𝑔𝑔 + ℎ, duplicates handled as in UCS (nodes

 Time Complexity is 𝑂𝑂(𝑏𝑏 𝑑𝑑 )

 Space Complexity is 𝑂𝑂(𝑏𝑏𝑚𝑚), where 𝑚𝑚 is the maximum

– subexponential growth requires that the error in the

20 Artificial Intelligence: Heuristic Search © JK

21 Artificial Intelligence: Heuristic Search © JK

22 Artificial Intelligence: Heuristic Search © JK

23 Artificial Intelligence: Heuristic Search © JK

 We then show that the original and the transformed problem

24 Artificial Intelligence: Heuristic Search © JK

• 𝑇𝑇 ℎ = 𝑠𝑠, 𝑎𝑎 𝑠𝑠, 𝑠𝑠𝑠 , 𝑠𝑠 | 𝑠𝑠, 𝑎𝑎, 𝑠𝑠𝑠 ∈ 𝑇𝑇 .

Lemma: Θℎ is well-defined, i.e.

Proof: The assumption follows immediately from consistency.

25 Artificial Intelligence: Heuristic Search © JK

Optimal Solution: SB - DD - M 650 + 1950 = 2600 = 150 + 250 + 2200

−ℎ 𝑠𝑠0 + 𝑐𝑐 𝑠𝑠0 , 𝑎𝑎1 + ℎ(𝑠𝑠1 ) + −ℎ 𝑠𝑠1 + 𝑐𝑐 𝑠𝑠1 , 𝑎𝑎2 + ℎ(𝑠𝑠2 ) +

= � 𝑐𝑐 𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 − ℎ 𝑠𝑠0 + ℎ(𝑠𝑠𝑛𝑛 ) = � 𝑐𝑐 𝑠𝑠𝑖𝑖−1 , 𝑎𝑎𝑖𝑖 − ℎ 𝑠𝑠0 ,

since 𝑠𝑠𝑛𝑛 is a goal state, it holds ℎ 𝑠𝑠𝑛𝑛 = 0.

Thus, the costs of solution paths in Θℎ are those of Θ, minus a constant.

Lemma B: The search space of A* on Θ is isomorphic to that of uniform-

28 Artificial Intelligence: Heuristic Search © JK

29 Artificial Intelligence: Heuristic Search © JK

Theorem (Optimality of A*)

30 Artificial Intelligence: Heuristic Search © JK

 At each iteration, perform a depth-first search, cutting off a

32 Artificial Intelligence: Heuristic Search © JK

 IDA* is complete if every node has a finite number of successor nodes

 Time Complexity is 𝑂𝑂(𝑏𝑏 𝑑𝑑 )

 Space Complexity is 𝑂𝑂(𝑑𝑑)

33 Artificial Intelligence: Heuristic Search © JK

 2 simultaneous searches: 1 forward (starting at initial state) and 1