SINBlock1Chapter5.

pdf

Anónimo

Sistemas Inteligentes

3º Grado en Ingeniería Informática

Escuela Técnica Superior de Ingeniería Informática

Universidad Politécnica de Valencia

Reservados todos los derechos.

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
 No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
SIN – (B1-C5) Heuristic Search
Heuristic search
Informed (heuristic) search: one that uses problem-specific knowledge to guide search.
Heuristic search can find solutions more efficiently than an uninformed search. It is recommended for
complex problems of combinatorial explosion (e.g.: traveling salesman problem).
Why use heuristics? In order to efficiently solve a problem, we must sometimes give up using a systematic
search strategy which guarantees optimality and use instead a search strategy that returns a good solution
though not the optimal one.

Reservados todos los derechos.

Heuristic search performs an intelligent search guidance and allows for pruning large parts of the search
tree.
Why are heuristics appropriate?
1. Usually, we do not need to get the optimal solution in complex problem, but a good solution is just
enough.
2. Heuristics may not return a good solution for the worst-case problem, but this case seldom happens.
3. Understanding how heuristics work (or do not work) helps people understand and go deeply into
the problem
We will consider a general approach called best-first search:

• An instance of the TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected

for expansion based on an evaluation function f(n)
• f(n) is a cost estimate so the node with the lowest cost is expanded first from the priority queue
(in uninformed search, f(n) is a different function for each strategy so that nodes are inserted in
the OPEN LIST according to the expansion order of the strategy)
• In fact, all search strategies can be implemented by using f(n); the choice of f determines the
search strategy
• Two special cases of best-first search: greedy best-first search and A*
Greedy search
Most best-first algorithms include as a component of f a heuristic function h(n).

Heuristic function: A rule of thumb, simplification, or educated guess that reduces or limits the search for
solutions in domains that are difficult and poorly understood
h(n) = estimated cost of the cheapest path from the state at node n to the goal state. If n is the goal state
then ℎ(𝑛) = 0
Greedy best-first search expands the node that appears to be closest to goal; it expands the closest node to
the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using
just the heuristic function: 𝑓(𝑛) = ℎ(𝑛)

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 Features
• Complete
o NO, it can get stuck in loops, e.g. (consider the problem to go from Iasi to Fagaras):
Iasi → Neamt → Iasi → Neamt (dead end, infinite loop)

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
o Resembles depth-first search (it prefers to follow a single path to the goal)
o The GRAPH-SEARCH version is complete (check on repeated states in the CLOSED LIST)

• Optimal:
o No, at each step it tries to get as close to the goal state as it can; this is why it is called greedy!

• Time complexity (execution time):

o The worst-case time complexity is 𝑂(𝑏 𝑚 ) where m is the maximum depth of the search space
o Like worst case in depth-first search
o Good heuristic can give dramatic improvement
o The amount of the reduction depends on the particular problem and on the quality of the
heuristic

Reservados todos los derechos.

• Space complexity (memory requirements):
o 𝑂(𝑏 𝑚 ) where m is the maximum depth of the search space
Example – The Romania example
ℎ𝑆𝐿𝐷 = straight-line distance heuristic from a city to
Bucharest. It CANNOT be computed from the
problem description itself.
Examples:
• ℎ(𝐴𝑟𝑎𝑑) = 366
• ℎ(𝐹𝑎𝑔𝑎𝑟𝑎𝑠) = 176
• ℎ(𝐵𝑢𝑐ℎ𝑎𝑟𝑒𝑠𝑡) = 0
In this example 𝑓(𝑛) = ℎ(𝑛)

• Expand node that is closest to goal Arad 366 Mehadia 241

• Greedy best-first search Bucharest 0 Neamt 234
Craiova 160 Oradea 380
Dobreta 242 Pitesti 100
Reached goal: non-optimal solution (alternative solution: Arad – Sibiu - Eforie 161 Rimnicu Vikea 193
Rimnicu Vilcea – Pitesti - Bucharest) Fagaras 176 Sibiu 253
Giurgiu 77 Timisoara 329
* By using the GRAPH-SEARCH version, we could check repeated states Hirsova 151 Urzicemi 80
in the CLOSED list and the new appearance of the Arad node would not be Iasi 226 Vaslui 199
Lugoj 244 Zerind 374
inserted in the OPEN list.

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 A* search
A* search is the most widely-known form of best-first search. It evaluates nodes by combining g(n), the
cost to reach the node n, and h(n), the cost to get from the node to the goal state. 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
The idea is to avoid paths that are already expensive. f(n) is the estimated total cost of the cheapest
solution through n. Algorithms that use an evaluation function of the form 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛) are called
A algorithms.
A* search uses an admissible heuristic function. A heuristic is admissible if it never overestimates the cost
to reach the goal, i.e., it is optimistic.
Formally:

• A heuristic h(n) is admissible if for every node n, ℎ(𝑛) ≤ ℎ∗ (𝑛), where h*(n) is the real cost
to reach the goal state from n.
• Because A* search uses an admissible heuristic, it returns the optimal solution.
• ℎ(𝑛) >= 0 so ℎ(𝐺) = 0 for any goal G

Reservados todos los derechos.

e.g. ℎ𝑆𝐿𝐷 (𝑛) never overestimates the actual road distance.
Example – The Romania example
In this example 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

• ℎ(𝑛) = ℎ𝑆𝐿𝐷 (𝑛)

• Expand node with the lowest estimated total cost to the goal state
• A* search
Iteration 1 Iteration 3

Iteration 2

In GRAPH-SEARCH version: Arad is a repeated node; the Arad

node in the CLOSED list has a better f-value.

Last iteration:

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 OPEN list = {𝐵𝑢𝑐ℎ𝑎𝑟𝑒𝑠𝑡(418), 𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎(447), 𝑍𝑒𝑟𝑖𝑛𝑑(449), 𝐶𝑟𝑎𝑖𝑜𝑣𝑎(526), 𝑂𝑟𝑎𝑑𝑒𝑎 (671)}
CLOSED list = {𝐴𝑟𝑎𝑑, 𝑆𝑖𝑏𝑖𝑢, 𝑅𝑖𝑚𝑛𝑖𝑐𝑢 𝑉𝑖𝑙𝑐𝑒𝑎, 𝐹𝑎𝑔𝑎𝑟𝑎𝑠, 𝑃𝑖𝑡𝑒𝑠𝑡𝑖}
Bucharest is already in the OPEN LIST (𝑐𝑜𝑠𝑡 = 450). The newly generated node has a lower estimated

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
total cost (𝑓 − 𝑣𝑎𝑙𝑢𝑒 = 418) than the one in the OPEN LIST. We replace the Bucharest node in OPEN
with the new found instance.
Example (2)
TREE-SEARCH version without control of repeated states

Reservados todos los derechos.

TREE-SEARCH version with control of repeated states GRAPH-SEARCH version

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
Comparison and analysis

• Comparison to other search strategies:

o Breadth-first search (optimal if all operators have the same cost). Equivalent to 𝑓(𝑛) =
𝑙𝑒𝑣𝑒𝑙(𝑛) + 0, where ℎ(𝑛) = 0 < ℎ∗ (𝑛).
o Uniform-cost (optimal). Equivalent to 𝑓(𝑛) = 𝑔(𝑛) + 0 where ℎ(𝑛) = 0 < ℎ∗ (𝑛)
o Depth-first (non-optimal). Not comparable to A*

• Heuristic knowledge:
o ℎ(𝑛) = 0, lack of knowledge
o ℎ(𝑛) = ℎ∗ (𝑛), maximal knowledge

Reservados todos los derechos.

o if ℎ2(𝑛) ≥ ℎ1(𝑛) for all n (both admissible) then h2 dominates h1 (h2 is more
informed than h1); h2 will never expand more nodes than h1

• ℎ(𝑛) = 0: no computational cost of h(n). (Slow search. Admissible.)

• ℎ(𝑛) = ℎ∗ (𝑛): large computational cost of h(n). (Fast search. Admissible).
• ℎ(𝑛) > ℎ∗ (𝑛): very high computational cost of h(n). (Very fast search. No admissible)
In general, h* is not known but it is possible to state whether h is a lower bound of h* or not.

For difficult problems, it is recommended to highly reduce the search space. In these cases, it is worth using
ℎ(𝑛) > ℎ∗ (𝑛) to eventually find a solution at a reasonable cost even though this is not the optimal solution.
For each problem, find a balance between the search cost and the cost of the solution path found.

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 Optimality
The optimality of a TREE-SEARCH A* algorithm is guaranteed if h(n) is an admissible heuristic.
Admissibility:

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
o h(n) is admissible if it never overestimates the cost to reach the goal (∀𝑛, ℎ(𝑛) ≤ ℎ∗ (𝑛))
o Let G be a goal/objective node, and n a node on an optimal path to G. f(n) never overestimates
the true cost of a solution through n
o 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛) ≤ 𝑔(𝑛) + ℎ∗ (𝑛) = 𝑔(𝐺) = 𝑓(𝐺) ⇒ 𝑓(𝑛) ≤ 𝑔(𝐺) (1)
Proof that if h(n) is admissible, then A* is optimal

• Let Start be the initial state of a problem such that the optimal
solution from Start leads to a solution node 𝐺: 𝑓(𝐺) = 𝑔(𝐺)
• Let G2 be another solution node (𝑓(𝐺2) = 𝑔(𝐺2)) such that the
cost of G2 is higher than the cost of G: 𝑔(𝐺2) > 𝑔(𝐺) (2)
• Let n be a node on the optimal path to G

Reservados todos los derechos.

• Let’s suppose that both n and G2 are in OPEN.

If n is not chosen for expansion then 𝑓(𝑛) >= 𝑓(𝐺2) (3)

If we combine (1) and (3) we get 𝑓(𝐺2) ≤ 𝑓(𝑛) ≤ 𝑔(𝐺) ⇒ 𝑔(𝐺2) ≤ 𝑔(𝐺) that contradicts
(2) so n is chosen first for expansion. Therefore, the algorithm will return the optimal solution.

The optimality of a GRAPH-SEARCH A* algorithm where repeated states in CLOSED are re-expanded is
guaranteed if h(n) is an admissible heuristic.
In a GRAPH-SEARCH A* algorithm with no re-expansion of repeated states in CLOSED, the optimal
solution is guaranteed if we can ensure the first found path to any node is the best path to the node. This
occurs if h(n) is a consistent heuristic.
Consistency, also called monotonicity is a slightly stronger condition than admissibility:
h(n) is consistent if, for every node n and every successor n’ of n generated by any action a:
ℎ(𝑛) ≤ ℎ(𝑛’) + 𝑐(𝑛, 𝑎, 𝑛’)
Therefore, a GRAPH-SEARCH A* algorithm with no re-expansion of repeated states that uses a consistent
heuristic h(n) also returns the optimal solution:

• Because it is guaranteed that when a node n is expanded, we have found the optimal solution from
the initial state to n so it is not necessary to re-expand n in case of a repeated instance; i.e. the cost
of the first instance of n will never be improved by any repeated node (they will be at least as
expensive).
• A derivation of the consistency condition is that the sequence of expanded nodes by the GRAPH-
SEARCH version of A* is in non-decreasing order of f(n).

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 Evaluation
• Complete
o YES; if there exists at least one solution, A* finishes (unless there are infinitely many
nodes with 𝑓 < 𝑓(𝐺))

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
• Optimal
o YES, under consistency condition (for GRAPH-SEARCH version)
o There always exists at least a node n on the OPEN LIST that belongs to the optimal
solution path from the start node to a goal node
o If C* is the cost of the optimal solution:
▪ A* expands all nodes with 𝑓(𝑛) < 𝐶 ∗
▪ A* might expand some nodes with 𝑓(𝑛) = 𝐶 ∗
▪ A* expands no nodes with 𝑓(𝑛) > 𝐶 ∗

• Time complexity (execution time):

∗
o 𝑂(𝑏 𝐶 /𝑚𝑖𝑛_𝑎𝑐𝑡𝑖𝑜𝑛_𝑐𝑜𝑠𝑡 ); exponential with path length

Reservados todos los derechos.

o Number of nodes expanded is still exponential in the length of the solution

• Space complexity (memory requirements):

o Exponential: it keeps all generated nodes in memory (as do all GRAPH-SEARCH
algorithms)
o A* usually runs out of space long before it runs out of time
o Hence, space is the major problem, not time
Design of heuristic functions
Heuristics are problem-dependent functions. Given a particular problem, how might one come up with a
heuristic function for the problem? In case of using an algorithm A*, how can one invent an admissible
heuristic?
A common technique is using a relaxed problem: a problem with less restrictions on the operators.
Admissible heuristics can be derived from the cost of an exact solution to a relaxed version of the problem.
This is usually a good heuristic for the original problem.
Example – Heuristics for the 8-puzzle problem
A tile in square A can move to square B if:
• Restriction 1: B is adjacent to A
• Restriction 2: B is the empty space (blank)
h1: misplaced tiles
• It removes both restrictions
• Relaxed 8-puzzle for h1: a tile can move anywhere
• As a result, h1(n) gives a very optimistic estimate (shortest solution)
h2: Manhattan distance
• It removes Restriction 2
• Relaxed 8-puzzle for h2: a tile can move to any adjacent square
• As a result, h2(n) gives an optimistic estimate (shortest solution)

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 The optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real
problem.

• The 8-puzzle problem

o Average solution cost is about 22 steps (branching factor ≈ 3)

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
o Exhaustive search to depth 22: 322 ≈ 3.1 𝑥 1010 states.
o A good heuristic function can reduce the search process.

• Heuristic 1:
o ℎ1(𝑛): number of misplaced tiles
o ℎ1(𝑛) = 5 for the example
• Heuristic 2:
o ℎ2(𝑛): Manhattan distance (the sum of the
distances of the tiles from their goal positions)
o ℎ2(𝑛) = 1 + 2 + 4 + 1 + 1 = 9 for the example
Manhattan distance dominates misplaced tiles (ℎ2(𝑛) ≥ ℎ1(𝑛), ∀𝑛), so h2 is better for search.

Reservados todos los derechos.

Evaluation of heuristic functions: computational cost
Difficult to apply mathematical analysis
Often used statistical/experimental methods.
Objective: minimize the total cost of the problem, trading off
computational expense and path cost.
Computational cost (temporal cost):

• Search cost: number of nodes generated or applied operators +

• Cost of calculating h(n): cost for selecting the applicable
operator.

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

using h(n) = misplaced tiles

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
Effective branching factor (b*)
If the total number of nodes generated by A* for a particular problem is N, and the solution depth is d, then
b* is the branching factor that a uniform tree of depth d would have to have in order to contain N+1 nodes.
Thus,

𝑁 + 1 = 1 + 𝑏 ∗ + (𝑏 ∗ )2 + … + (𝑏 ∗ )𝑑
For example, if A* finds a solution at depth 5 using 52 nodes, 𝑏 ∗ = 1.92.

Reservados todos los derechos.

• b* defines how sharply a search process is focused toward the goal.
• b* is reasonably independent of path length (d)
• b* can vary across problem instances, but usually is fairly constant for sufficiently hard problems

• A well-designed heuristic would have a value of b* close to 1, allowing fairly large problems to be solved.
• A value of b* near unity corresponds to a search that is highly focused towards the goal, with very little
branching in other directions.
• Experimental measurements of b* on a small set of problems can provide a good guidance to the
heuristic’s overall usefulness.
Example – Heuristics for the traveling salesman problem

• 6 cities: A,B,C,D,E,F
• States: sequences of cities starting in city A which
represent partial routes
• Start: A
• Final: sequences starting and ending in A which are made up of all cities
• Rules or operators: add at the end of each state one city which is not in the sequence already
• Operators cost: distance between the last city in the sequence and the recently added city (see table)

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950
 𝒉(𝑨𝑩𝑬) → C, D, F, back to A
h2(n) = number of missing arcs multiplied by the arc of
minimal cost [ℎ2(𝐴𝐵𝐸) = 4 ∗ 5 = 20]

No se permite la explotación económica ni la transformación de esta obra. Queda permitida la impresión en su totalidad.
h3(n) = sum of the shortest p arcs if there are p missing arcs
(undirected graph) [ℎ3(𝐴𝐵𝐸) = 5 + 5 + 7 + 7 = 24]

h4(n) = sum of the shortest outgoing arcs of the cities

which have not been left yet

h7(n) = number of missing arcs multiplied by their average cost (non-admissible)

Reservados todos los derechos.

[ℎ7(𝐴𝐵𝐸) = 4 ∗ 40.33 = 161.33]

si lees esto me debes un besito

a64b0469ff35958ef4ab887a898bd50bdfbbe91a-3906950