Heuristic Search

Text Book: Russel Norvig- Chapter 4 (A*)

George F Luger and
Rich and Knight (for AO* Search)

Outline
• Heuristics and Optimal search strategies
– heuristics
– hill-climbing algorithms
– Best-First search
– A*: optimal search using heuristics
– An Algorithm for Heuristic Search
– Implementing “Best-first” Search
– Implementing Heuristic Evaluation Function
– Heuristic Search and Expert Systems
• Admissibility, Monotonicity, and Informedness
– Admissibility Measure
– Monotonicity
– When One Heuristic Is Better: More Informed Heuristics
• Using Heuristics in Games
– The Minimax Procedure on Exhaustively Searchable Graphs
– Minimaxing to Fixed Ply Depth
– The Alpha-Beta Procedure

1
Problem: finding a Minimum Cost Path
• Previously we wanted an arbitrary path to a goal.
• Now, we want the minimum cost path to a goal G
– Cost of a path = sum of individual transitions along path
• Examples of path-cost:
– Navigation
• path-cost = distance to node in miles
– minimum => minimum time, least fuel

– VLSI Design
• path-cost = length of wires between chips
– minimum => least clock/signal delay

– 8-Puzzle
• path-cost = number of pieces moved
– minimum => least time to solve the puzzle

BFS and DFS

• Sometimes it is not feasible to search the whole
search space as it is just too big. e.g. chess

• In the cases when search spaces are really big

we need to use heuristic search.
• E.g
– 8 puzzle (3X3) has 9!/2 = 181440 reachable states,
easily gets solved
– 15 puzzle (4X4) has 1.3 trillion states, takes several
miliseconds to search goal
– 24 puzzle (5X5) has 1025 states, takes several hours
to search goal

2
 Informed Search
• A search strategy that uses problem-
specific knowledge beyond the
definition of the problem itself.
• The purpose of a heuristic is to guide the
search process in the most profitable
direction by suggesting which path to
follow first when more than one are
available.

How to take information into account ?

Idea : use an evaluation function for each node
– Estimate of desirability of node
– Expand most desirable unexpanded node
– Heuristic Functions :
• f : States  Numbers
• f(n) : expresses the quality of the state n
– Allows us to express problem-specific knowledge,
– Can be imported in a generic way in the algorithms.
– Priority Queue:
Order the nodes in fringe in decreasing order of
desirability
Special cases:
– greedy best-first search
– A* search

3
 Informed Search
• A search strategy which searches the most
promising branches of the state-space first
can:
– find a solution more quickly,
– find solutions even when there is limited time
available,
– often find a better solution, since more
profitable parts of the state-space can be
examined, while ignoring the unprofitable parts.

Informed / Heuristic Search

• The term Heuristic means Commonsense rule
intended to increase the probability of
solving a problem.
• The basic idea of heuristic search is that, rather
than trying all possible search paths, we try and
focus on paths that seem to be getting you
nearer your goal state.

• A heuristic is a method that:

– Might not always find the best solution
– But is guaranteed to find a good solution
in reasonable time.

4
 Heuristic Search
• To use heuristic search we need an evaluation/
heuristic function that provides an estimate of
how close a given state is to a goal state.
• There are 2 major ways in which domain specific,
heuristic knowledge can be incorporated into a
search procedure:
– In the rules themselves
– As a heuristic function that evaluates individual
problem states and determines how desirable
they are.

Best First Search

• The goal of Best First Search is to find the goal state by
looking at as few states as possible.

• The more informed, the heuristic, the fewer states are

processed in finding the goal.

• In Best F.S.,the most promising node is selected and

all the others are kept around so that they can be
revisited later if the selected path becomes less
promising.
• Unlike H.C., in which one move is selected and all others
are rejected, never to be reconsidered; this produces the
straight line behavior that is characteristic of hill climbing.

5
 State Space Graph Search

OL is a queue OL is stack
(BFS) (DFS) OL is a Priority Queue
accessed by using
functions f= g+h
(Best First Search)

BFS, DFS – Uninformed / Brute Force Search

methods

Heuristic Search
• In order to implement any graph search
procedure we will need to use two lists of nodes:
– OPEN: nodes that have been generated and had
heuristic function applied to them but which have not
yet been examined.
• OPEN is a actually a priority queue in which the elements
with the highest priority are those with the most promising
value of heuristic function.

– CLOSED: nodes that have been examined.

• i.e. their successors have been generated as well as
evaluated.
• We need to keep these nodes in memory if we want to
search a graph rather than a tree.

6
 Greedy best-first search
Evaluation function f(n) = h(n) (heuristic)
= estimate of cost from n to goal

Greedy best-first search expands the node that appears to be

closest to goal

Similar to depth-first search: It prefers to follow a single

path to goal (guided by the heuristic), backing up when it
hits a dead-end.

Greedy Best First Search

• An obvious problem with greedy search is that it doesn't
take account of the cost so far, so it isn't optimal, and can
wander into dead-ends, like depth-first search.

• In most domains, we also don't know the cost of getting to

the goal from a state. So we have to guess, using a
heuristic evaluation function.
– If we knew exactly how far we were from the goal state we
wouldn’t need to search for it!

7
 Route finding problem

Here heuristic is Straight Line Distance (SLD)

Example: Route Finding Problem

8
 Progress
of Greedy
Best First
Search
using SLD

Heuristic Functions for 8-puzzle

• h1 = the number of misplaced tiles
• h2 = the sum of the distances of the tiles from
their goal positions

9
 Source: Luger book

Evaluation function f*
f* (n)= g* (n) + h* (n)
• g* (n) is the cost of the shortest path from the start
node to the current node n.
• h* (n) is the actual cost of the shortest path from node
‘n’ to a goal state.
• f* (n) is the actual cost of optimal path from the initial
state to a goal state that passes through current node n.
• Note: Although oracles such as f* do not exist for
most real problems, we would like the evaluation
function ‘f’ to be a close estimate of ‘f*’.

10
 Evaluation function f
f (n)= g (n)+ h (n)
• g(n) is measure of the cost of current path to state n, is
a reasonable estimate of g*, but they may not be
equal: g(n) ≥ g* (n).
– These are equal only if the graph search has discovered the
optimal path to state n.

• h(n) is an estimate of minimal cost from n to a goal.

• now f(n) estimates total cost of the path from the start
state through ‘n’ to the goal state.
• Note: If the best first search algorithm uses an
evaluation function ‘f’ in which h(n) ≤ h* (n), it is
called A* algorithm.

Behavior of A* Search

11
 Underestimation
i.e. h≤h*

Overestimation h≥h*

Assume from node D there is a direct path to G with cost = 1

i.e. here h>h*

12
Combining cost-so-far and heuristic function
• We can combine the strengths of uniform-cost search and
greedy search.
• Since what we're really looking for is the optimal path
between the initial state, and some goal state, a better
measure of how promising a state is, is the sum of the
cost-so-far, and our best estimate of the cost from there to
the nearest goal state.

• For a state n, with a cost-so-far g(n), and a heuristic

estimate of the cost to goal of h(n), what we want is:
f(n) = g(n) + h(n)

Role of g and h’
• If we want to find the cheapest path and some operators cost
more than others, then we set the cost of going from one
node to another to reflect those costs.
• If we only care about getting to a solution somehow, we can
define g always to be zero.
• If the value of h’ is always 0, the search will be controlled by
g same as uniform cost search, BFS if g=1.
• If the value of both g and h is 0, the search strategy will be
random.
• If we want to find path involving the fewest no. of steps, then
– we set the cost of going from a node to its successor as a constant
usually 1 (h=0);
– in this case search will be breadth first search as all nodes on one
level will have lower g values, and thus lower f’ values than all nodes
on the next level.

13
 A* search
Idea: avoid expanding paths that are already
expensive

Evaluation function f(n) = g(n) + h(n)

– g(n) = cost so far to reach n
– h(n) = estimated cost from n to goal
– f(n) = estimated total cost of path through n to
goal

Uniform-cost search
• One simple way to sort the states is by the cost-so-far. This
might be the number of moves we've made so far in a game, or
the distance we've travelled so far looking for a route between
towns.
• If we sort the OPEN list nodes so that the states with the lowest
costs come first, then we'll always expand these first, and that
means that we're sure we'll always find an optimal solution first.
• This is uniform-cost search. It looks a lot like breadth-first
search, except that it will find an optimal solution even if the
steps between states have different costs (e.g. the distance
between towns is irregular).
• However, uniform-cost search doesn't really direct us towards
the goal we're looking for, so it isn't very informed.

14
 Defining A* Algorithm
1. If Best First Search algorithm is used with evaluation
function h(n), s.t. h(n) ≤ h*(n), where h*(n) is the true cost
to reach the goal state from n then the resulting algorithm
is called A* algorithm.

2. An admissible heuristic never overestimates the cost to

reach the goal, i.e., it is optimistic
Theorem:
If h(n) is admissible, i.e. h(n) ≤ h*(n),
h(goal)=0
A* using Best First Search is
optimal.

A* Search Definitions
• Optimality Definition
A solution is optimal if it conforms to the
minimal-cost path between S0 and SG. If
operators cost is uniform, then the optimal
solution = shortest path

• Admissibility Definition
A heuristic is admissible with respect to a
search method if it guarantees finding the
optimal solution first, even when its value
is only an estimate.

15
 Admissibility of A*
• Admissibility theorem:
– A* using Tree-search is optimal if h(n) is
admissible.

Admissibility of A*
• A search algorithm is admissible, if for any graph, it
always terminates in an optimal path from initial state
to goal state, if path exists.

• If heuristic function h is under estimate of actual value

from current state to goal state, then it is called
admissible function.

• So, we can say that A* always terminates with the optimal

path in case h(x) is an admissible heuristic function.

16
 Monotonicity
• Theorem I: Any consistent/monotonic heuristic is always
admissible.

• Theorem II: If a heuristic h(n) is consistent/monotonic

then the values of f(n) along any path are non-
decreasing or in increasing order.

• Whether the admissibility property of a heuristic also

implies monotonicity ??

17
 Admissibility, Informedness and
Monotonicity
• Heuristics that find the shortest path to a goal whenever
it exists are said to be admissible (role of g).

• We may want to ask whether any better heuristics are

available? Or in what sense is one heuristic better than
another? This is the informedness of a heuristic (role of
h).
• When a state is discovered by using heuristic search, is
there any guarantee that the same state won’t be found
later in the search at a cheaper cost with a shorter path
from the start state. This is the property of Monotonicity.

Admissible, Consistent/Monotonic
Heuristics
• Admissible:
if we define h*(n) as the exact lowest cost from node n to a goal, a
heuristic function h(n) is admissible if and only if n

h(n)  h*(n)
• Consistent:
this quality is similar to the triangle inequality of all metrics. If c(n,m) is
the cost of a shortest path from node n to successor node m , then a
heuristic function h(x) is consistent if n,m

h(n)  c(n,m) + h(m)

• Admissibility does not imply consistency; Consistency is a
stronger property.

18
 Informedness
• We say that a search strategy which searches less of the state-
space in order to find a goal state is more informed.
• Ideally, we'd like a search strategy which is both admissible (so
it will find us an optimal path to the goal state), and informed
(so it will find the optimal path quickly.)
• Admissibility requires that the heuristic evaluation function,
h(n) doesn't overestimate, but we do want a function which is
as close as possible to the actual cost of getting to the goal.
• Formally, for two admissible heuristics h1 and h2,
if h1(n) <= h2(n) for all states n in the state-space, then
heuristic h2 is said to be more informed than h1.

Heuristic Functions for 8-puzzle

• h1 = the number of misplaced tiles
• h2 = the sum of the distances of the tiles from their goal
positions
– If a heuristic h2 is more informed than h1, then the set of states examined
by h2 is a subset of those expanded by h1.

• If h*(true cost) ≥ h2(n) ≥h1(n) ≥0 (base case-breadth first search) for

all n(both admissible),
– here h(n) is estimated cost but not the value of heuristic evaluation
function as we can’t compare two different evaluation functions for their
values

– then h2 dominates h1
i.e. h2 is better for search as it will search state
space graph by exploring lesser number of
nodes, and without much deviation, quickly
reaching goal.

19
 8-puzzle: heuristics
• In fact, it can easily be shown that h2 is both
admissible and more informed than h1.
– It cannot overestimate, since the number of moves we need
to make to get to the goal state must be at least the sum of
the distances of the tiles from their goal positions.

– It always gives a value at least as high as h1, since if a tile is

out of position, by definition it is at least one square away
from its goal position, and often more.

A heuristic of water-jug problem (4,3):

• Take the sum of the differences in jug contents in the

current state versus the goals state, then divide it by 2.

• For example, suppose the contents of the large and

small jugs in a given state are 4 and 1 i.e. (4,1),
respectively.
– Assuming the goal state specifies (2, 0), the differences in
volumes in the large and small jugs are |4-2| = 2 and |1-0| = 1,
respectively. Adding these two values and dividing by two yields
the heuristic value 1.5.

• Is this heuristic admissible? Justify your answer.

20
 The Jug Puzzle: There are two jugs, the first with 3l content,
the second with 4 l content. There is an unlimited amount of
water. How can you get exactly 2 l of water in the second one?

(0,0)

(3,0) (0,4)

(3,4) (0,3) (0,0) (0,0) (3,1) (3,4)

(3,0) (0,4) (3,3) (3,0) (0,0) (0,4) (3,4) (3,0) (0,1) (0,4)

(3,4) (2,4) (3,0) (0,3) (3,1) (1,0) (0,4)

(0,4) (2,0) (3,3) (0,0) (1,4) (0,1) (3,0)

(3,0) (2,4) (0,0) (0,2) (0,4) (3,2) (1,0) (3,4)

(3,0) (0,2) (3,4)

Problem 2: solve using A*

B B B W W W

G: States where no B is to the left of any W; Operators:

1) A tile may hop over one or two other tiles into the empty
position with cost equal to no. of tiles jumped over.
2) A tile may move into an adjacent empty location with cost 1.

1. Analyze the state space with respect to complexity and

looping.
2. Propose a heuristic for solving this problem and analyze
it with respect to admissibility, monotonicity and
informedness.

21
 Specifications
–Try different heuristics and
compare with baseline case,
i.e., the breadth first search.

–Violate the condition h ≤ h*. See

if the optimal path is still found.
Observe the speedup.

Problem 3: Missionaries and Cannibals

using A* R

boat River
boat
L

Missionaries Cannibals
Missionaries Cannibals
Constraints
 The boat can carry at most 2 people

 On no bank should the cannibals outnumber the missionaries

22
 Missionaries and Cannibals Problem:
heuristics
Start state: <3, 3, L>
Goal state: <0, 0, R>
– h1(n) = (no. of m + no. of c) / 2, on the left side

Best
First
Search
-
pseudo
algorithm

23
 A* search complexity
• how many nodes A* generates in the
process of finding a solution.

• The answer depends on the quality of the

heuristic function.

Time Complexity of A*
• The running time of A* is proportional to the number of
nodes generated or expanded.
– Therefore the branching factor is at most a constant,
and heuristic evaluation of a node can be done in
constant time.

• In many cases, the heuristic functions and edge costs are

integer valued or have a small number of distinct values.
• In such case, the Open can be maintained as an array
of lists,
– separate list for each different cost.
– This allows constant-time insertion and retrieval from the
Open list.

24
 Open and closed list
• The Open and Closed lists can be maintained in
constant time per node expansion.
– Closed list - can be organized as hash table,
since we only need to check for the occurrence of a
node.
– Open list - we have to be able to insert a node and
retrieve a lowest-cost node in constant time. This
would take time that is logarithmic in the size of the
Open list.

Special Cases
• Worst case: Cost function f(n) = g(n)
– the heuristic function returns zero for every node and provides
no information to the algorithm, but is still a lower-bound on actual
cost.This is identical to the UCS or Dijkstra’s algorithm, which has a
worst-case time complexity of
O (b C */ )
• Best case: Cost function f(n) = g(n) + h*(n)
– the heuristic function is perfect and always returns the exact
optimal cost to a goal state from any given state, The optimal path
will be chosen, and the number of node-expansion cycles will be d
the depth of the optimal path. Thus, the asymptotic time complexity
is
O(bd) = O(d)

25
 Cost of the search
• the closer h is to the actual cost, the fewer states
considered
– however, the cost of computing h tends to go up as it
improves
the best algorithm is
one that minimizes
cost of solving problem
the total cost of the
computation
solution
cost cost of computing h

cost of search using h

closeness of h to
actual cost

Drawback of A* Search
• That A* search is complete, optimal, and optimally
efficient among all such algorithms is rather satisfying.

• Unfortunately, it does not mean that A* is the answer to

all our searching needs.

• The reason being, for most problems, the number of

nodes within the goal contour search space is still
exponential in the length of the solution.

• It has been shown that exponential growth will occur

unless the error in the heuristic function grows no faster
than the logarithm of the actual path cost.

26
 Complexity of A* Search
• In mathematical notation, the condition for sub exponential
growth is that

– where h* (n) is the true cost of getting from n to the

goal.

• For almost all heuristics in practical use, the error is at

least proportional to the path cost, and the resulting
exponential growth eventually overtakes any computer.

Complexity of A*
• The use of a good heuristic still provides enormous savings
compared to an uninformed search.

• A*'s main drawback is not computation time, but the

memory requirements.

• Because it keeps all generated nodes in memory, A*

usually runs out of space long before it runs out of time.

• Some probabilistic algorithms have overcome the

space problem without sacrificing optimality or
completeness.
– e.g.) IDA*, SMA* (Simplified Memory-Bounded A*), Simulated
Annealing, Genetic Algorithm etc.

27
 IDA*
• The idea is to use increasing limits on path cost.
• The main difference between IDA* and standard iterative
deepening is that the cut off used is the f-cost rather than
depth, at each iteration.
• At each iteration, the cut off value is the smallest f-cost of
any node that exceeded the cut off on the previous
iteration.
• IDA* is practical for many problems with unit step costs
and avoids the substantial overhead associated with
keeping a sorted queue of nodes.
• Unfortunately, it suffers from same difficulties with real
valued costs as does the iterative version of uniform
cost search.

Local Search Algorithms

• The search algorithms we have seen so far are designed
to explore search spaces systematically, when a goal is
found, the path to goal constitutes a solution to the
problem.

• In many problems, the path to the goal is irrelevant; e.g.)

– 4-queens problem, integrated circuit design, factor-floor layout, job-
shop scheduling, automatic programming, telecom network
optimizations, vehicle routing, portfolio management etc.

• If the path to the goal does not matter, we might

consider a different class of algorithms, known as local
search algorithms.

28
 Local Search Algorithms
• Local search algorithms operate using a single current
state rather than multiple paths and generally move only
to neighbors of that state.
– E.g. Simulated Annealing, Genetic Algorithm, etc.

• The paths followed by local search are not retained.

• Local Search Algorithms have these key advantages:

1. They use very little memory – usually a constant amount
2. They can often find reasonable solutions in large or infinite
(continuous) state spaces for which systematic algorithms are
unsuitable.
3. They are useful for solving pure optimization problems in which
the aim is to find the best state according to an objective
function.
4. Suitable for online as well as offline search.

Hill Climbing (Pearl 1948)

• The basic idea in HC is to head towards a state which is
better than the current one.
• It expands the current state by evaluating its successor.
The best successor is selected for further expansion,
neither its siblings nor its parents are retained. Search
halts when it reaches a state better than any of its
successor.
• HC is often used when a good heuristic function is available
for evaluating states but when no other useful knowledge is
available.
• HC is named for the strategy that might be used by an eager,
but blind mountain climber, go uphill along the steepest
possible path until you can go no further, because it keeps no
history.

29
 Hill-Climbing Search
1. Evaluate the initial state. If it is also a goal state, then
return it and quit. Otherwise continue with the initial
state as current state.
2. Loop: (until a solution is found or until there are no
operators left to be applied in the current state)
• Select an operator that has yet not been applied to
the current state and apply it to produce a new state.
• Evaluate the new state
• If it is goal, then return it and quit
• If it is not goal but it is better than the current state, then
make it the current state.
• If it is not better than the current state, then continue in the
loop.

Hill Climbing Search

30
 8-queens using HC
• Local search algorithms use complete state formulation.
E.g.; for 8-queen puzzle,
– each state has 8 queens on the board one per column
• Successors of a state are:
– all possible states generated by moving a single
queen to another square in the same column;
– so each state has 8X7=56 successors

• Heuristic cost function h is:

– no. of pairs of queens that are attacking each other,
either directly or indirectly
• The global minimum (or solution state evaluation) of this
function is zero, which occurs at perfect solution only.

8-queens using HC

• This figure shows value of all its successors, with best

successors having h=12.
• Hill climbing algorithm typically chooses randomly
among set of best successors if there is more than one.

31
 Drawback of Hill Climbing
• A major drawback of HC strategies is their
tendency to become stuck at local maxima.

• If it reaches a state that has a better evaluation

than any of its children / successor, the
algorithm halts.

• And If this state is not a goal state but just a

local maximum, this algorithm fails to find a
solution.

State Space landscape

32
 hill-climbing
• if you think of the state space as a topographical map (heuristic value =
elevation), then hill-climbing selects the steepest gradient to move up
towards the goal

potential dangers
plateau: successor states have
same values, no way to
choose
foothill: local maximum, can
get stuck on minor peak
ridge: results in a sequence of
local maxima, foothill
where N-step lookahead
might help

33
 Hill-climbing variants
• Stochastic HC chooses at random from among uphill
moves, probability of selection can vary with steepness
of uphill move.
 This usually converges more slowly than steepest ascent, but in
some state landscapes it finds better solutions.
• First choice HC implements stochastic HC by generating
successors randomly until one is generated that is better
than current state.
 This is a good strategy when a state has thousands of
successors.
• Random-restart hill climbing adopts the strategy of try
and try again from randomly generated initial states,
stopping when a goal is found i.e., it runs many HC.
 If each HC search has a probability p of success, then expected
no.of restarts required is 1/p.

Hill-climbing variants
simulated annealing
 allow moves in the wrong direction on a probabilistic
basis
 decrease the probability of a backward move as the
search continues
 idea: early in the search, when far from the goal,
heuristic may not be good
heuristic should improve as you get closer to the goal
approach is based on a metallurgical technique

34
 Simulated Annealing (S. A.)
• hill climbing suffers from problems in getting stuck at local
minima (or maxima).
• C is local max, G is global max
• E is local min, A is global min
– Search must go wrong way to proceed!

• We could try to overcome these problems by trying various

techniques.
– We could try a hill climbing algorithm using different starting points.
– We could increase the size of the neighbourhood so that we consider
more of the search space at each move.

• Simulated annealing solves this problem by allowing worse

moves (lesser quality) to be taken some of the time. That is,
it allows some uphill steps so that it can escape from local
minima.

Simulated Annealing
• A alternative to a random-restart hill-climbing when stuck on a
local maximum is to do a ‘reverse walk’ to escape the local
maximum.

• Simulated annealing is a probabilistic method for finding the

global minimum of a cost function that may possess several local
minima. This is the idea of simulated annealing.

• The term simulated annealing derives from the roughly

analogous physical process of heating and then slowly cooling
a substance to obtain a strong crystalline structure.

• The simulated annealing process lowers the temperature by slow

stages until the system “freezes" and no further changes occur.

35
 Idea behind S.A.
• If you heat a solid past melting point and then cool it, the
structural properties of the solid depend on the rate of
cooling.
• If the liquid is cooled slowly enough, large crystals will be
formed.
• However, if the liquid is cooled quickly (quenched) the
crystals will contain imperfections.
• Simulated annealing
– Pick a random action
– If action improves evaluation function then go with it
– If not, choose with probability based on how bad it is
• Can go the ‘wrong’ way
• Effectively rules out really bad moves

Simulated Annealing
• Probability of transition to higher energy state is
given by function:
P = e –∆E/kt
Where ∆E is the positive change in the energy level
T is the temperature
K is Boltzmann constant.

– As T approaches zero, the probability o accepting a move to a

worse state goes to zero and simulated annealing becomes
identical to simple hill climbing.
– As T -> infinity, Probability -> 1

36
 Local Beam Search
• Keeping just one node in memory might seem to be an
extreme reaction to problem of memory limitations.
• Local beam search algorithm keeps track of k states rather
than just one.
• It begins with k randomly generated states.
• At each step, all successors of all k states are
generated.
• If any one is a goal, algorithm halts.
• Otherwise, it selects the k best successors from complete
list and repeats.
 A variant called stochastic beam search, instead of
choosing best k from pool of candidate successors, it
chooses k successors at random, with probability of
choosing a given successor being increasing function of its
value.

37
 Genetic Algorithm
• GA is a variant of stochastic beam search in which
successor states are generated by combining 2
parent states, rather than by modifying a single
state.
• GA begins with a set of k randomly generated states,
called population.
• Successor states are generated by combining 2 parent
states, using genetic operators called crossover and
mutation.
• Each state is rated by evaluation function or fitness
function which signifies how well it solves the problem.

8 Queens using GA

38
 Local search in Continuous space
• Most real-world environments are continuous as
opposed to discrete.

• Yet none of algorithms we have discussed (except first

choice hill climbing & simulated annealing) can handle
continuous state and action spaces, because they have
infinite branching factors.

• Solution: Gradient descent

• E.g. Error Backpropagation in FFNN

Online Search
• offline search algorithms (all algos discussed so far)
compute a complete solution before setting foot in the
real world and then execute the solution.
• In contrast, an online search algorithm interleaves
computation and action i.e. first it takes an action, then it
observes the environment and computes the next action.

• Online search is useful in dynamic and semi-dynamic

domains i.e. domains where there is a penalty for sitting
around and computing too long.

39
 Searching with non-deterministic
actions
• When environment is either partially observable or non-
deterministic (or both) percepts become useful.

OR graphs
• A directed graph in which each node represents a point
in the problem space.

• Each node will contain:

– A description of problem state it represents
– An indication of how promising it is
– A parent link that points back to the best node from
which it came
– A list of nodes that were generated from it

• In OR graph several arcs may emerge from a single

node, indicating a variety of ways in which the original
problem might be solved.
• Either first or any other arc can be headed to find a
solution.

40
 AND-OR graphs
• AND-OR graph (or tree) is useful for representing the
solution of problems that can be solved by decomposing
them into a set of smaller problems, all of which must then
be solved.
• One AND arc may point to any number of successor
nodes, all of which must be solved in order for the arc to
point to a solution.
Goal: Acquire TV Set

Goal: Steal a TV Set Goal: Earn some money Goal: Buy TV Set

AND – OR Graphs
• AND – OR graph is useful for
representing the solution of
problems that can be solved by
A
decomposing them into a set of
9 smaller problems, all of which
must then be solved.
B C D
• This decomposition or reduction
5 3 4 generates arcs that we call AND
arcs.

41
 Business Applications of Heuristic
Search
• Route-finding (computer networks, military operations
planning, airline travel planning)
• Touring
• Manufacturing design (e.g., VLSI layout)
• Manufacturing control
• Robot navigation
• Internet searching

Business Applications

• Network management
• Profit optimization
• Resource optimization
• Stock portfolio optimization

42
 Summary
• Blind search: Depth-First, Breadth-First, IDS
– Do not use knowledge of problem space to find solution.
• Informed search
• Best-first search: Order agenda based on some measure of how
‘good’ each state is.
• Uniform-cost: Cost of getting to current state from initial state = g(n)
• Greedy search: Estimated cost of reaching goal from current state
– Heuristic evaluation functions, h(n)
• A* search: f(n) = g(n) + h(n)
• Admissibility & Monotonicity: h(n)never overestimates the
actual cost of getting to the goal state and the triangle property.
• Informedness: A search strategy which searches less of the state-
space in order to find a goal state is more informed.
• AO* search

43