ARTIFICIAL

INTELLIGENCE

UNIT – II

Syllabus
Solving Problems by searching: Problem Solving Agents, Example problems,
Searching for Solutions, Uninformed Search Strategies, Informed search strategies, Heuristic
Functions.

Beyond Classical Search: Local Search Algorithms and Optimization Problems, Local
Search in Continues Spaces, Searching with Nondeterministic Actions, Searching with
partial observations, online search agents and unknown environments.

24
 Chapter – 1

Solving Problems by searching

25
2.1.1. Problem Solving Agents :
Problem formulation is the process of deciding what actions and states to consider, given a goal .

An important aspect of intelligence is goal-based problem solving.

The solution of many problems can be described by finding a sequence of actions that lead to a desirable goal.
Each action changes the state and the aim is to find the sequence of actions and states that lead from the initial
(start) state to a final (goal) state.

 What is Search?

Search is the systematic examination of states to find path from the start/root state to the goal state.
The set of possible states, together with operators defining their connectivity constitute the search space.
The output of a search algorithm is a solution, that is, a path from the initial state to a state that satisfies the
goal test.

(i) Problem Solving Agents:

A Problem solving agent is a goal-based agent .It decide what to do by finding sequence of actions that lead to
desirable states.
The agent can adopt a goal and aim at satisfying it.
Example : From Arad(Romania) to Bucharest

Goal formulation, based on the current situation and the agent’s performance measure, is the first step in
problem solving.
The agent’s task is to find out which sequence of actions will get to a goal state.
Problem formulation is the process of deciding what actions and states to consider given a goal.
An agent with several immediate options of unknown value can decide what to do by examining different
possible sequences of actions that leads to the states of known value, and then choosing the best sequence.

The process of looking for sequences actions from the current state to reach the goal state is called search.
The search algorithm takes a problem as input and returns a solution in the form of action sequence.
26
 Once a solution is found, the execution phase consists of carrying out the recommended action..
Simple “formulate, search, execute” design for the agent…

 The agent design assumes the Environment is:

– Static : The entire process carried out without paying attention to changes that might be occurring in the
environment.
– Observable : The initial state is known and the agent’s sensor detects all aspects that are relevant to the choice of
action.
– Discrete : With respect to the state of the environment and percepts and actions so that alternate courses of action
can be taken.
– Deterministic : The next state of the environment is completely determined by the current state and the actions
executed by the agent. Solutions to the problem are single sequence of actions.

(ii) Well-defined problems and solutions:

A well-defined problem can be described by:

i. Initial state
ii. Operator or successor function - for any state x returns s(x), the set of states reachable from x with one action
iii. State space - all states reachable from initial by any sequence of actions
iv. Path - sequence through state space
v. Path cost - function that assigns a cost to a path. Cost of a path is the sum of costs of individual actions along the
path
vi. Goal test - test to determine if at goal state
vii.The step cost of taking action ‘a’ to go from state x to state y is denoted by c(x,a,y). The step cost for Romania are
shown in next figure in route distances. It is assumed that the step costs are non negative.
viii.A solution to the problem is a path from the initial state to a goal state.
ix. An optimal solution has the lowest path cost among all solutions.

27
2.1.2. Example Problems:
 Toy vs Real World problems…

A toy problem is intended to illustrate or exercise various problem-solving methods.

It can be given a concise, exact description and hence is usable by different researchers to compare the
REALWORLD performance of algorithms.
A real-world problem is one whose solutions people actually PROBLEM care about. Such problems tend not
to have a single agreed-upon description, but we can give the general flavor of their formulations.

1. Toy Problems:
 Example 1: Vaccum world

i. States: The agent is in one of two locations.,each of which might or might not contain dirt. Thus there are 2 x
22 = 8 possible world states.
ii. Initial state: Any state can be designated as initial state.
iii. Successor function : This generates the legal states that results from trying the three actions (left, right, suck).
The complete state space is shown in figure.
iv. Goal Test : This tests whether all the squares are clean.
v. Path test : Each step costs one ,so that the the path cost is the number of steps in the path.

28
 States?: integer dirt and robot locations (ignore dirt amounts etc.)
Actions?: Left, Right, Suck, NoOp
Goal test?: no dirt
Path cost?: 1 per action (0 for NoOp)

Example 2:The 8-puzzle:

An 8-puzzle consists of a 3x3 board with eight numbered tiles and a blank space.
A tile adjacent to the blank space can slide into the space. The object is to reach the goal state ,as shown in
Figure.

 The problem formulation is as follows :

i. States : A state description specifies the location of each of the eight tiles and the blank in one of the nine
squares.

ii. Initial state : Any state can be designated as the initial state. It can be noted that any given goal can be
reached from exactly half of the possible initial states.

iii. Successor function : This generates the legal states that result from trying the four actions(blank moves
Left,Right,Up or down).
29
 iv. Goal Test : This checks whether the state matches the goal configuration shown in figure(Other goal
configurations are possible).

v. Path cost : Each step costs 1,so the path cost is the number of steps in the path.

The 8-puzzle belongs to the family of sliding-block puzzles, which are often used as test problems for new
search algorithms in AI. This general class is known as NP-complete.

The 8-puzzle has 9!/2 = 181,440 reachable states and is easily solved.

The 15 puzzle ( 4 x 4 board ) has around 1.3 trillion states, an the random instances can be solved optimally in
few milli seconds by the best search algorithms.

The 24-puzzle (on a 5 x 5 board) has around 1025 states ,and random instances are still quite difficult to solve
optimally with current machines and algorithms.

i. States?: Integer locations of tiles (ignore intermediate positions)

ii. Actions?: Move blank left, right, up, down (ignore unjamming etc.)

iii. Goal test?: Goal state (given).

iv. Path cost?: 1 per move.

[Note: optimal solution of n-Puzzle family is NP-hard]

 Example 3: 8 Queen Problem:

The goal of 8-queens problem is to place 8 queens on the chessboard such that no queen attacks any other.(A
queen attacks any piece in the same row, column or diagonal).

An Incremental formulation involves operators that augments the state description, starting with an empty
state for 8-queens problem, this means each action adds a queen to the state.

A complete-state formulation starts with all 8 queens on the board and move them around.

In either case the path cost is of no interest because only the final state counts.

 The first incremental formulation one might try is the following :

i. States : Any arrangement of 0 to 8 queens on board is a state.

ii. Initial state : No queen on the board.
iii. Successor function : Add a queen to any empty square.
iv. Goal Test : 8 queens are on the board, none attacked.
In this formulation, we have 64, 63…57 = 3 x 1014 possible sequences to investigate.
A better formulation would prohibit placing a queen in any square that is already attacked.

30
 States : Arrangements of n queens ( 0 <= n < = 8 ), one per column in the left most columns ,with no queen
attacking another are states.
Successor function : Add a queen to any square in the left most empty column such that it is not attacked by
any other queen.
This formulation reduces the 8-queen state space from 3 x1014 to just 2057,and solutions are easy to find.

2. Real-world Problems:
i. Route finding problem
ii. Airline Travel problem
iii. Touring problems
iv. Travelling salesperson problem
v. VLSI Layout
vi. ROBOT Navigation
vii.Automatic Assembly problem
viii.Internet searching

(i) Route-Finding Problem :

▪ Route-Finding Problem is defined in terms of specified locations and transitions along links between them.
Route-finding algorithms are used in a variety of applications.

▪ Some, such as Web sites and in-car systems that provide driving directions.

▪ Others, such as routing video streams in computer networks, military operations planning, and airline travel-
planning systems, involve much more complex specifications.

 Consider the airline travel problems that must be solved by a travel-planning Web site:

• States: Each state obviously includes a location (e.g., an airport) and the current time. Furthermore, because the cost
of an action (a flight segment) may depend on previous segments, their fare bases, and their status as domestic or
international, the state must record extra information about these “historical” aspects.

• Initial state: This is specified by the user’s query.

• Actions: Take any flight from the current location, in any seat class, leaving after the current time, leaving enough
time for within-airport transfer if needed.

Transition model: The state resulting from taking a flight will have the flight’s destination as the current location and
the flight’s arrival time as the current time.

• Goal test: Are we at the final destination specified by the user?

• Path cost: This depends on monetary cost, waiting time, flight time, customs and immigration procedures, seat
quality, time of day, type of airplane, frequent-flyer mileage awards, and so on.

31
(ii) Touring problems :

Touring problems are closely related to route-finding problems, but with an important difference. Consider, for
example, the problem “Visit every city at least once, starting and ending in Bucharest”.

(iii) Traveling Salesperson Problem (TSP) :

▪ The traveling salesperson problem (TSP) is a touring problem in which each city must be visited exactly
once.

▪ The aim is to find the shortest tour.

The problem is known to be NP-hard, but an enormous amount of effort has been expended to improve the capabilities
of TSP algorithms.

(iv) VLSI layout problem :

▪ A VLSI layout problem requires positioning millions of components and connections on a chip to minimize
area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield.

▪ The layout problem comes after the logical design phase and is usually split into two parts:

→ Cell layout

→ Channel routing.

➔ Cell layout :

▪ In cell layout, the primitive components of the circuit are grouped into cells, each of which performs some
recognized function.

→ Channel routing :

▪ Channel routing finds a specific route for each wire through the gaps between the cells.

(v) Robot Navigation :

▪ Robot navigation is a generalization of the route-finding problem described earlier.

▪ Rather than following a discrete set of routes, a robot can move in a continuous space with (in principle) an
infinite set of possible actions and states.

▪ For a circular robot moving on a flat surface, the space is essentially two-dimensional.

(vi) Automatic assembly sequencing :

▪ Automatic assembly sequencing of complex objects by a robot was first demonstrated by FREDDY
(Michie, 1972).

▪ Progress since then has been slow but sure.

▪ In assembly problems, the aim is to find an order in which to assemble the parts of some object. If the
32
 wrong order is chosen, there will be no way to add some part later in the sequence without undoing some of
the work already done.

▪ Checking a step in the sequence for feasibility is a difficult geometrical search problem closely related to
robot navigation.

▪ Another important assembly problem is protein design, in which the goal is to find a sequence of amino
acids that will fold into a three-dimensional protein with the right properties to cure some disease.

2.1.3. SEARCHING FOR SOLUTIONS :

▪ A solution is an action sequence, so search algorithms work by considering various possible action
sequences.

▪ The possible action sequences starting at the initial state form a search tree with the initial state at
the root; the branches are actions and the nodes correspond to states in the state space of the
problem.

▪ The diagram shows the first few steps in growing the search tree for finding a route from Arad to
Bucharest.

▪ By expanding the current state , and thereby generating a new set of states.

▪ Each of these six nodes is a leaf node, that is, a node with no children in the tree.

▪ The set of all leaf nodes available for expansion at any given
point is called the frontier(Many authors call it the open list)

the frontier of each tree consists of those nodes with bold outlines.

▪ The process of expanding nodes on the frontier continues until either a solution is found or there are
no more states to expand.

33
▪ Search algorithms all share this basic structure; they vary primarily
according to how they choose which state to expand next—the so-called search strategy.

▪ Loopy paths are a special case of the more general concept of redundant paths, which exist
whenever there is more than one way to get from one state to another.

▪ As every step moves a state from the frontier into the explored region while moving some states
from the unexplored region into the frontier, we see that the algorithm is systematically
examining the states in the state space, one by one, until it finds a solution.

(i) Infrastructure for search algorithms :

▪ Search algorithms require a data structure to keep track of the search tree that is being constructed.
34
 ▪ For each node n of the tree, we have a structure that contains four components:

• n.STATE: the state in the state space to which the node corresponds;

• n.PARENT: the node in the search tree that generated this node;

• n.ACTION: the action that was applied to the parent to generate the node;

• n.PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the
node, as indicated by the parent pointers.

 Queue :
▪ Now that we have nodes, we need somewhere to put them.

▪ The frontier needs to be stored in such a way that the search algorithm can easily choose the next
node to expand according to its preferred strategy.

▪ The appropriate data structure for this is a queue.

▪ The operations on a queue are as follows:

• EMPTY?(queue) returns true only if there are no more elements in the queue.

• POP(queue) removes the first element of the queue and returns it.

• INSERT(element, queue) inserts an element and returns the resulting queue.

▪ Queues are characterized by the order in which they store the inserted nodes.

▪ Three common variants are

▪ The first-in, first-out or FIFO queue, which pops the oldest element of the queue;

▪ LIFO QUEUE the last-in, first-out or LIFO queue (also known as a stack), which pops the newest
element

▪ PRIORITY QUEUE of the queue; and the priority queue, which pops the element of the queue with
the highest priority according to some ordering function.

(ii) Measuring problem-solving performance:

▪ Before we get into the design of specific search algorithms, we need to consider the criteria that
might be used to choose among them.

▪ We can evaluate an algorithm’s performance in four ways:

→ Completeness: Is the algorithm guaranteed to find a solution when there is one?

→ Optimality: Does the strategy find the optimal solution,

→ Time complexity: How long does it take to find a solution?

→ Space complexity: How much memory is needed to perform the search?

35
2.1.4. Uninformed Search strategies :
Uninformed Search Strategies have no additional information about states beyond that provided in the
problem definition.

 There are six uninformed search strategies as given below:

i. Breadth-first search
ii. Uniform-cost search
iii. Depth-first search
iv. Depth-limited search
v. Iterative deepening search
vi. Bi-directional search
1. Breadth-first search(BFS):
Breadth-first search is a simple strategy in which the root node is expanded first, then all successors of the
root node are expanded next, then their successors, and so on.

In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are
expanded.

Breath-First-Search is implemented by calling TREE SEARCH with an empty fringe that is a first-in-first out
(FIFO) queue, assuring that the nodes that are visited first will be expanded first.

In other words, calling TREE-SEARCH (problem, FIFO-QUEUE()) results in breadth-first-search.

The FIFO queue puts all newly generated successors at the end of the queue, which means that Shallow nodes
are expanded before deeper nodes.

 BFS Algorithm…

Example for BFS Algorithm…

36
  Properties of BFS…

 Time and memory requirements….

2. Uninform-cost Search(UCS)…
Instead of expanding the shallowest node, uniform-cost search expands the node ‘n’ with the lowest path cost.
Uniform-cost search does not care about the number of steps a path has, but only about their total cost.
Expand least-cost unexpanded node.
We think of this as having an evaluation function:g(n), which returns the path cost to a node n.
fringe = queue ordered by evaluation function,lowest first.
Equivalent to breadth-first if step costs all equal
Complete and optimal.
Time and space complexity are as bad as for breadth-first search.

 UCS Algorithm:

37
 Process…

38
 Properties of UCS….

3. Depth First Search(DFS)…

Depth-first-search always expands the deepest node in the current fringe of the search tree.
The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors.
As those nodes are expanded, they are dropped from the fringe ,so then the search “backs up” to the next
shallowest node that still has unexplored successors.
 Implementation:
fringe = LIFO queue, i.e., put successors at front.

39
  Properties of Depth First Search(DFS):

Complete? - No: Fails in infinite-depth spaces, spaces

with loops. Modify to avoid repeated states along
Path complete infinite spaces
Time?? : O(bm): Terrible if m is much larger than ‘d’, but
if solutions are dense, may be much faster than
breadth first search.
Space?? : O(bm), i.e., linear space!
Optimal?? : No

4. Depth-Limited Search…
The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first
search with a predetermined depth limit ‘l’.
That is, nodes at depth ‘l’ are DEPTH-LIMITED treated as if they have no successors. This approach is called
depth limited search.
The SEARCH depth limit solves the infinite-path problem.
Unfortunately, it also introduces an additional source of incompleteness if we choose ‘l’ < d, that is, the

40
 shallowest goal is beyond the depth limit. (This is likely when d is unknown.)

Depth-limited search will also be non-optimal if we choose ‘l’ > d.

Its time complexity is O(b) and its space complexity is O(b). Depth-first search can be viewed as a
special case of depth-limited search with‘l’ =∞.

5. Iterative deepening depth-first search…

Iterative deepening search (or iterativedeepening-depth-first-search) is a general strategy often used in
combination with depth-first-search,that finds the better depth limit.
It does this by gradually increasing the limit – first 0,then 1,then 2, and so on – until a goal is found.
This will occur when the depth limit reaches d, the depth of the shallowest goal node.
Iterative deepening combines the benefits of depth-first and breadth-first-search.
Like depth-first-search, its memory requirements are modest;O(bd) to be precise.

In general, iterative deepening is the preferred uninformed search method when the search space is large and
the depth of the solution is not known.

 Four iterations of iterative deepening search on a binary tree in shown below.

41
 Properties of IDS….

42
6. Bi-directional search…
The idea behind bidirectional search is to run two simultaneous searches – one forward from the initial state
and the other backward from the goal, stopping when the two searches meet in the middle.

The motivation is that bd/2 + bd/2 much less than or the area of the two small circles is less than the area of one
big circle centered on the start and reaching to the goal.

 Example Graph:

43
2.4.7 Comparing uninformed search strategies…

2.1.5. Informed or Heuristic search strategies…

Informed search strategy is one that uses problem-specific knowledge beyond the definition of the problem
itself.
It can find solutions more efficiently than uninformed strategy.
Best-first search is an instance of general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is
selected for expansion based on an evaluation function f(n).
The node with lowest evaluation is selected for expansion, because the evaluation measures the distance to the
goal.
This can be implemented using a priority-queue, a data structure that will maintain the fringe in ascending
order of fvalues.
A heuristic function or simply a heuristic is a function that ranks alternatives in various search algorithms at
each branching step basing on an available information in order to make a decision which branch is to be
followed during a search.
The key component of Best-first search algorithm is a heuristic function, denoted by h(n):
h(n) = estimated cost of the cheapest path from node n to a goal node.

Heuristic function are the most common form in which additional knowledge is imparted to the search
algorithm.

 Heuristic Searching methods…

i. Greedy Best First search
ii. A* search

44
iii. Memory-bounded heuristic search(RBFS)

1. Greedy Best First search…

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to
a solution quickly.
It evaluates the nodes by using the heuristic function f(n) = h(n).
Taking the example of Route-finding problems in Romania , the goal is to reach Bucharest starting from the
city Arad.
We need to know the straight-line distances(SLD) to Bucharest from various cities as shown in Figure.
For example, the initial state is In(Arad) ,and the straight line distance heuristic hSLD(In(Arad)) is found to be
366.

The figure shows the progress of greedy best-first search using hSLD to find a path from Arad to Bucharest.

The first node to be expanded from Arad will be Sibiu, because it is closer to Bucharest than either Zerind or
Timisoara.
45
 The next node to be expanded will be Fagaras, because it is closest.

Fagaras in turn generates Bucharest, which is the goal.

FINAL PATH : Arad → Sibiu → Fagaras → Bucharest.

 Greedy search Algorithm…

46
2. A* Search…
A* is very efficient search strategy and it is the most widely used form of best-first search.
Basic idea is to combine uniform cost search and greedy search.
The evaluation function f(n) is obtained by combining g(n) = the cost to reach the node, and h(n) = the cost
to get from the node to the goal :
f(n) = g(n) + h(n).
(or)
f (n) = g(n) + h(n) where
– g(n) is path cost of n;
– h(n) is expected cost of cheapest solution from n.
It Aims to minimise overall cost.
Algorithm for A* search stratergy:

47
FINAL PATH: Arad →Sibiu →Rimnicu→ Pitesti →Bucharest.

48
 Optimality of A*…

A search is both complete and optimal.

The algorithm is identical to UNIFORM-COST-SEARCH except that A uses g + h instead of g.
A* is optimal in precise sense—it is guaranteed to find a minimum cost path to the goal.
There are a set of conditions under which A* will find such a path:
1. Each node in the graph has a finite number of children.
2. All arcs have a cost greater than some positive .
3. For all nodes in the graph h(n) always underestimates the true distance to the goal.

 Conditions for the Optimality…

1. The first condition we require for optimality is that h(n) be an admissible heuristic.
An admissible heuristic is one that never overestimates the cost to reach the goal.
2. A second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for
applications of A to graph search.
 A heuristic h(n) is consistent if, for every node n and every successor n` of n generated by any action a, the
estimated cost of reaching the goal from n is no greater than the step cost of getting to n plus the estimated
cost of reaching the goal from n.

 Problems in A*…
Computation time, A ’s main drawback.
Because it keeps all generated nodes in memory (as do all GRAPH-SEARCH algorithms), A usually runs
out of space long before it runs out of time.

For this reason, A is not practical for many largescale problems.

There are, however, algorithms that overcome the space problem without sacrificing optimality or
completeness, at a small cost in execution time.

3. Memory-bounded Heuristic search…

Recursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the
Operation of standard best-first search, but using only linear space.

Its structure is similar to that of a recursive depth first search, but rather than continuing indefinitely down the
current path, it uses the f-limit variable to keep track of the f-value of the best alternative path.
If the current node exceeds this limit, the recursion unwinds back to the alternative path.
As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value—the
best f-value of its children.
In this way, RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide
whether it’s worth reexpanding the subtree at some later time.

49
 RBFS Algorithm…

 Stages in RBFS Algorithm…

50
 RBFS Evaluation :

RBFS is a bit more efficient than IDA* Still excessive node generation (mind changes).
Like A*, optimal if h(n) is admissible. Space complexity is O(bd).
IDA* retains only one single number (the current f-cost limit).
Time complexity difficult to characterize Depends on accuracy if h(n) and how often best path changes.
IDA* and RBFS suffer from too little memory.

2.1.6. HEURISTIC FUNCTIONS :

▪ The 8-puzzle was one of the earliest heuristic search problems.

▪ The object of the puzzle is to slide the tiles horizontally or vertically into the empty space until the
configuration matches the goal configuration .

▪ The average solution cost for a randomly generated 8-puzzle instance is about 22 steps. The
branching factor is about 3.

▪ When the empty tile is in the middle, four moves are possible; when it is in a corner, two; and when
it is along an edge, three.

This means that an exhaustive tree search to depth 22 would look at about

51
• A graph search would cut this down by a factor of about 170,000 because only 9!/2 = 181, 440 distinct states
are reachable.

▪ The corresponding number for the 15-puzzle is roughly , so the next order of business is to find a good
heuristic function.

▪ If we want to find the shortest solutions by using A , we need a heuristic function that never overestimates
the number of steps to the goal.

• There is a long history of such heuristics for the 15-puzzle; here are two commonly used candidates:

• h1 = the number of misplaced tiles. All of the eight tiles are out of position, so the start state would have h1 =
8.

h1 is an admissible heuristic because it is clear that any tile that is out of place must be moved at least once.

• h2 = the sum of the distances of the tiles from their goal positions.

Because tiles cannot move along diagonals, the distance we will count is the sum of the horizontal and
vertical distances.

• This is sometimes called the city block distance or Manhattan distance.

(i) 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,

▪ For example, if A finds a solution at depth 5 using 52 nodes, then the effective branching factor is 1.92.

52
 (ii) Generating admissible heuristics from relaxed problems :

▪ We have seen that both h1 (misplaced tiles) and h2 (Manhattan distance) are fairly good heuristics for the 8-
puzzle and that h2 is better.

▪ How might one have come up with h2? Is it possible for a computer to invent such a heuristic mechanically.

h1 and h2 are estimates of the remaining path length for the 8-puzzle, but they are also perfectly accurate path
lengths for simplified versions of the puzzle.

▪ If the rules of the puzzle were changed, so that a tile could move anywhere instead of just to the adjacent
empty square, then h1 would give the exact number of steps in 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 number of steps in the shortest solution.

▪ A problem with fewer restrictions on the actions is called a relaxed problem.

“the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem”.

▪ Furthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle
inequality and is therefore consistent .

▪ 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 A to square B if

▪
→ A is horizontally or vertically adjacent to B and B is blank,
We can generat e t hree relaxed problems by removing one or bot h of t he condit ions:

(a) A tile can move from square A to square B if A is adjacent to B.

(b) A tile can move from square A to square B if B is blank.

(c) A tile can move from square A to square B.

From (a), we can derive h2 (Manhattan distance). The reasoning is that h2 would be the proper score if we
moved each tile in turn to its destination.

From (c), we can derive h1 (misplaced tiles) because it would be the proper score if tiles could move to their
intended destination in one step.

(iii) Generating admissible heuristics from subproblems : (Pattern databases)

▪ Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem.

▪ For example, a subproblem of the 8-puzzle instance is

53
 ▪ The subproblem involves getting tiles 1, 2, 3, 4 into their correct positions.

▪ Clearly, the cost of the optimal solution of this subproblem is a lower bound on the cost of the complete
problem.

▪ It turns out to be more accurate than Manhattan distance in some cases.

▪ The idea behind pattern databases is to store these exact solution costs for every possible subproblem
instance—in our example, every possible configuration of the four tiles and the blank.

▪ Then we compute an admissible heuristic hdb for each complete state encountered during a search simply by
looking up the corresponding subproblem configuration in the database.

▪ The database itself is constructed by searching back from the goal and recording the cost of each new pattern
encountered .

▪ Each database yields an admissible heuristic, and these heuristics can be combined, and by taking the
maximum value.

A combined heuristic of this kind is much more accurate than the Manhattan distance .

▪ One might wonder whether the heuristics obtained from the 1-2-3-4 database and the 5-6-7-8 could be added,
since the two subproblems seem not to overlap.

▪ Would this still give an admissible heuristic? The answer is no.

▪ So,we record not the total cost of solving the 1-2-3-4 subproblem, but just the number of moves involving 1-
2-3-4. Then it is easy to see that the sum of the two costs is still a lower bound on the cost of solving the entire
problem.

▪ This is the idea behind disjoint pattern databases.

With such databases, it is possible to solve random 15-puzzles in a few milliseconds .

(iv) Learning heuristics from experience :

▪ Experience” here means solving lots of 8-puzzles, for instance. Each optimal solution to an 8-puzzle problem
provides examples from which h(n) can be learned.

Each example consists of a state from the solution path and the actual cost of the solution from that point.
From these examples, a learning algorithm can be used to construct a function h(n) that can (with luck) predict
solution costs for other states that arise during search.

54