AIML Modue2

Artificial Intelligence and Machine Learning
21CS54
Module 2
Solving Problems by Searching
July 25, 2024 1

Informed (Heuristic) Search Strategies
• This section shows how an informed search strategy—one that uses
domain-specific hints about the location of goals—can find solutions
more efficiently than an uninformed strategy.
• The hints come in the form of a heuristic function, denoted h(n):
• Heuristic function
h(n) = estimated cost of the cheapest path from the state at node n
to a goal state.
• For example, in route-finding problems, we can estimate the distance
from the current state to a goal by computing the straight-line
distance on the map between the two points.
July 25, 2024 2
July 25, 2024 3
Greedy best-first search
• Greedy best-first search is a form of best-first search that

expands first the node with the lowest h(n) value—the node
that appears to be closest to the goal—on the grounds that
this is likely to lead to a solution quickly.
• So the evaluation function
f (n) = h(n).
July 25, 2024 4

July 25, 2024 5
July 25, 2024 6
A∗ search
• The most common informed search algorithm is A ∗ search
(pronounced “A-star search”), a best-first search that uses the
evaluation function
f (n) = g(n)+h(n)
• where g(n) is the path cost from the initial state to node n, and
h(n) is the estimated cost of the shortest path from n to a goal
state, so we have
f (n) = estimated cost of the best path that continues from n to
a goal.
July 25, 2024 7
July 25, 2024 8
July 25, 2024 9
July 25, 2024 10
July 25, 2024 11
July 25, 2024 12
July 25, 2024 13
• In Figure 3.18, we show the progress of an A∗ search with the goal
of reaching Bucharest.
• The values of g are computed from the action costs in Figure 3.1,
and the values of hSLD are given in Figure 3.16.
• Notice that Bucharest first appears on the frontier at step (e), but it
is not selected for expansion (and thus not detected as a solution)
because at f =450 it is not the lowest-cost node on the frontier—
that would be Pitesti, at f =417.
• Another way to say this is that there might be a solution through
Pitesti whose cost is as low as 417, so the algorithm will not settle
for a solution that costs 450.
• At step (f), a different path to Bucharest is now the lowest-cost
node, at f =418, so it is selected and detected as the optimal
solution.
July 25, 2024 14
• A∗ search is complete.
• Whether A∗ is cost-optimal depends on certain properties of

the heuristic.
• A key property is admissibility: an admissible heuristic is one
that never overestimates the cost to reach a goal. (An
admissible heuristic is therefore optimistic.)
• With an admissible heuristic, A∗ is cost-optimal, which we can
show with a proof by contradiction.
• Suppose the optimal path has cost C∗, but the algorithm
returns a path with cost C >C∗.
July 25, 2024 15
• Then there must be some node n which is on the optimal path and
is unexpanded (because if all the nodes on the optimal path had
been expanded, then we would have returned that optimal
solution).
• So then, using the notation g∗(n) to mean the cost of the optimal
path from the start to n, and h∗(n) to mean the cost of the optimal
path from n to the nearest goal, we have:
f (n) > C∗ (otherwise n would have been expanded)
f (n) = g(n)+h(n) (by definition)
f (n) = g∗(n)+h(n) (because n is on an optimal path)
f (n) ≤ g∗(n)+h∗(n) (because of admissibility, h(n) ≤ h∗(n))
f (n) ≤ C∗ (by definition, C∗ = g∗(n)+h∗(n))
• The first and last lines form a contradiction, so the supposition that
the algorithm could return a suboptimal path must be wrong—it
must be that A∗ returns only cost-optimal paths.
July 25, 2024 16
• A slightly stronger property is called consistency. A heuristic h(n) is
consistent if, for every node n and every successor n′ of n generated
by an action a, we have: h(n) ≤ c(n, a, n′)+h(n′) .
• This is a form of the triangle inequality, which stipulates that a side
of a triangle cannot be longer than the sum of the other two sides
(see Figure 3.19).
• An example of a consistent heuristic is the straight-line distance hSLD
that we used in getting to Bucharest.
July 25, 2024 17

• Every consistent heuristic is admissible (but not vice versa), so
with a consistent heuristic, A∗ is cost-optimal.
• But with an inconsistent heuristic, we may end up with

multiple paths reaching the same state, and if each new path
has a lower path cost than the previous one, then we will end
up with multiple nodes for that state in the frontier, costing us
both time and space.
July 25, 2024 18

Heuristic Functions
• We discuss how the accuracy of a heuristic affects search

performance, and also consider how heuristics can be invented.
Example: The 8-puzzle.
• The objective of the puzzle is to slide the tiles horizontally or
vertically into the empty space until the configuration matches the
goal configuration (Figure 3.25).
July 25, 2024 19

• There are 9!/2=181,400 reachable states in an 8-puzzle, so a
search could easily keep them all in memory.
• But for the 15-puzzle, there are 16!/2 states—over 10 trillion—so
to search that space we will need the help of a good admissible
heuristic function.
Here are two commonly used candidates:
1. h1 = the number of misplaced tiles (blank not included). For

Figure 3.25, all eight tiles are out of position, so the start state
has h1 = 8. h1 is an admissible heuristic because any tile that is
out of place will require at least one move to get it to the right
place.
July 25, 2024 20
2. h2 = the sum of the distances of the tiles from their goal positions.
• Because tiles cannot move along diagonals, the distance is the sum
of the horizontal and vertical distances— sometimes called the city-
block distance or Manhattan distance.
• h2 is also admissible because all any move can do is move one tile
one step closer to the goal. Tiles 1 to 8 in the start state of Figure
3.25 give a Manhattan distance of
h2 = 3+1+2+2+2+3+3+2= 18.
• As expected, neither of these overestimates the true solution cost,

which is 26.
July 25, 2024 21

The effect of heuristic accuracy on performance
• One way to characterize the quality of a heuristic is the
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,
N +1 = 1+b∗+(b∗)2+· · ·+(b∗)d .
• For example, if A∗ finds a solution at depth 5 using 52 nodes,
then the effective branching factor is 1.92.
July 25, 2024 22

• Korf and Reid (1998) argue that a better way to characterize
the effect of A∗ pruning with a given heuristic h is that it
reduces the effective depth by a constant kh compared to the
true depth.
• This means that the total search cost is O(b d−k ) compared to
h
O(bd) for an uninformed search.
• Their experiments on Rubik’s Cube and n-puzzle problems
show that this formula gives accurate predictions for total
search cost for sampled problem instances.

July 25, 2024 23
• One might ask whether h2 is always better than h1.
• The answer is “Essentially, yes.”
• It is easy to see from the definitions of the two heuristics that for any node n,
h2(n) ≥ h1(n).
• We thus say that h2 dominates h1. Domination translates directly into
efficiency: A∗ using h2 Domination will never expand more nodes than A ∗
using h1
July 25, 2024 24
Generating heuristics from relaxed problems
• If the rules of the 8-puzzle were changed so that a tile could move
anywhere instead of just to the adjacent empty square, then h1 would
give the exact length of the shortest solution.
• Similarly, if a tile could move one square in any direction, even onto an
occupied square, then h2 would give the exact length of the shortest
solution.
• A problem with fewer restrictions on the actions is called a relaxed
problem.
• The state-space graph of the relaxed problem is a supergraph of the
original state space because the removal of restrictions creates added
edges in the graph.
July 25, 2024 25
• Because the relaxed problem adds edges to the state-space graph, any
optimal solution in the original problem is, by definition, also a solution in
the relaxed problem; but the relaxed problem may have better solutions if
the added edges provide shortcuts.
• If a problem definition is written down in a formal language, it is possible
to construct relaxed problems automatically. For example, if the 8-puzzle
actions are described as
A tile can move from square X to square Y if X is adjacent to Y and Y is
blank,
we can generate three relaxed problems by removing one or both of the
conditions:
a) A tile can move from square X to square Y if X is adjacent to Y.
b) A tile can move from square X to square Y if Y is blank.
c) A tile can move from square X to square Y.
July 25, 2024 26
• A program called ABSOLVER can generate heuristics automatically from
problem definitions, using the “relaxed problem” method and various

other techniques (Prieditis, 1993).
• ABSOLVER generated a new heuristic for the 8-puzzle that was better
than any preexisting heuristic and found the first useful heuristic for the
famous Rubik’s Cube puzzle.
• If a collection of admissible heuristics h1 . . .hm is available for a problem
and none of them is clearly better than the others, which should we
choose?
• As it turns out, we can have the best of all worlds, by defining
h(n) = max{h1(n), . . . ,hk(n)}.

July 25, 2024 27
Generating heuristics from subproblems: Pattern databases
July 25, 2024 28

Thank You
July 25, 2024 29

AIML Modue2

Uploaded by

Copyright:

Available Formats

AIML Modue2

Uploaded by

Document Information

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

AIML Modue2

Uploaded by

Copyright:

Available Formats

Artificial Intelligence and Machine Learning

July 25, 2024 1

• Greedy best-first search is a form of best-first search that

July 25, 2024 4

• Whether A∗ is cost-optimal depends on certain properties of

July 25, 2024 17

• But with an inconsistent heuristic, we may end up with

July 25, 2024 18

• We discuss how the accuracy of a heuristic affects search

July 25, 2024 19

Here are two commonly used candidates:

1. h1 = the number of misplaced tiles (blank not included). For

• As expected, neither of these overestimates the true solution cost,

July 25, 2024 21

July 25, 2024 22

the effect of A∗ pruning with a given heuristic h is that it

reduces the effective depth by a constant kh compared to the

O(bd) for an uninformed search.

• Their experiments on Rubik’s Cube and n-puzzle problems

show that this formula gives accurate predictions for total

search cost for sampled problem instances.

problem definitions, using the “relaxed problem” method and various

• If a collection of admissible heuristics h1 . . .hm is available for a problem

• As it turns out, we can have the best of all worlds, by defining

h(n) = max{h1(n), . . . ,hk(n)}.

July 25, 2024 28

July 25, 2024 29

You might also like