Unit-3: - Heuristic Search Techniques

Heuristic Search
 Heuristic search is class of method which is used in order to search a solution
space for an optimal solution for a problem.
 This is a kind of a shortcut as we often trade one of optimality, completeness,
accuracy, or precision for speed. A Heuristic (or a heuristic function) takes a look
at search algorithms.
 At each branching step, it evaluates the available information and makes a
decision on which branch to follow. It does so by ranking alternatives.
 The Heuristic is any device that is often effective but will not guarantee work in
every case.
Heuristic Search Techniques
a. Direct Heuristic Search Techniques in AI(Uniformed Search)
Other names for these are Blind Search, Uninformed Search, and Blind Control
Strategy. These aren’t always possible since they demand much time or
memory. They search the entire state space for a solution and use an arbitrary
ordering of operations. Examples of these are Breadth First Search (BFS) and
Depth First Search (DFS).
Example
 b. Weak Heuristic Search Techniques in AI(Informed Search)
Other names for these are Informed Search, Heuristic Search, and Heuristic
Control Strategy. These are effective if applied correctly to the right types of
tasks and usually demand domain-specific information. We need this extra
information to compute preference among child nodes to explore and expand.
Each node has a heuristic function associated with it. Examples are Best First
Search (BFS) and A*.

Heuristic Function
 If there are no specific answers to a problem or the time required to find one is
too great, a heuristic function is used to solve the problem.
 The aim is to find a quicker or more approximate answer.
 A heuristic is a function that determines how near a state is to the desired state.
 For example, the problem might be finding the shortest driving distance to a point.
A heuristic cost would be the straight-line distance to the point.
 Generate-and- Test
 Generate and Test Search is a heuristic search technique based on Depth First
Search with Backtracking which guarantees to find a solution if done
systematically and there exists a solution.
 In this technique all the solution are generate and tested for best solution.
 It ensure that best solution checked from all possible generator solution.
 It is also known as British Museum Search Algorithm.

Constraint Satisfaction

 It is a search procedure that operates in a space of constraint sets.

 Constraint satisfaction problem in AI have goal of discovering some problem
state that satisfies a given set of constraints

Process
 Constraints are discovered and propagated throughout the system.
 If still there is no solution search begins
 A guess is node about something and added as new constraint.

V= [variables {V1,V2,…Vn}

D = Domains {D1,D2,.Dn}
CSP
C= Constraints (specify allowable
combination of value)
 C=(Scope , Relation)
Scope= set of variables that participate in constraint.
Relation = Defines values that variable can take.
Suppose : V1 and V2

A B

Domains
Values of V1 and V2 can’t be same.
C ={ (V1 , V2) , V1= V2}

 Intelligent Backtracking method is used to solve CSP.

Ex. Node colouring

A B

C D

Solution
V={A, B,C,D}
D={Red , Green , Blue}
C={Adjacent node should not be same colour}
 A B C D
Initial R , G, B R , G, B R , G, B R , G, B
R G,B G,B G,B
R G G,B B
R G B -
R G G B

A= Red B = Green C= Green B= Blue.

Hill Climbing
 Hill climbing algorithm is a local search algorithm which continuously moves in
the direction of increasing elevation/value to find the peak of the mountain or best
solution to the problem. It terminates when it reaches a peak value where no
neighbour has a higher value.
 Hill climbing algorithm is a technique which is used for optimizing the
mathematical problems. One of the widely discussed examples of Hill climbing
algorithm is Traveling-salesman Problem in which we need to minimize the
distance traveled by the salesman.
 It is also called greedy local search as it only looks to its good immediate
neighbour state and not beyond that.
 A node of hill climbing algorithm has two components which are state and value.
 Hill Climbing is mostly used when a good heuristic is available.
 In this algorithm, we don't need to maintain and handle the search tree or graph
as it only keeps a single current state.

Features of Hill Climbing:

 Generate and Test variant: Hill Climbing is the variant of Generate and Test
method. The Generate and Test method produce feedback which helps to decide
which direction to move in the search space.
 Greedy approach: Hill-climbing algorithm search moves in the direction which
optimizes the cost.
 No backtracking: It does not backtrack the search space, as it does not remember
the previous states.

Limitation of Hill Climbing Algorithm

1. Local Maximum: A local maximum is a peak state in the landscape which is
better than each of its neighboring states, but there is another state also present
which is higher than the local maximum.

2. Plateau: A plateau is the flat area of the search space in which all the neighbor
states of the current state contains the same value, because of this algorithm does
not find any best direction to move. A hill-climbing search might be lost in the
plateau area.

3. Ridges: A ridge is a special form of the local maximum. It has an area which is
higher than its surrounding areas, but itself has a slope, and cannot be reached in a
single move.
Example: solve this example using hill climbing search

solution
h(x) = +1 for all the blocks in the support structure if the block is correctly
positioned otherwise -1 for all the blocks in the support structure.
 Best-First Search
Greedy best-first search algorithm always selects the path which appears best at
that moment. It is the combination of depth-first search and breadth-first search
algorithms. It uses the heuristic function and search. Best-first search allows us
to take the advantages of both algorithms. With the help of best-first search, at
each step, we can choose the most promising node. In the best first search
algorithm, we expand the node which is closest to the goal node and the closest
cost is estimated by heuristic function, i.e.

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

Were, h(n)= estimated cost from node n to the goal.

The greedy best first algorithm is implemented by the priority queue.

Algorithm
Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n),
and places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node
or not. If any successor node is goal node, then return success and terminate the
search, else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and
then check if the node has been in either OPEN or CLOSED list. If the node has not
been in both list, then add it to the OPEN list.
Step 7: Return to Step 2.

Advantages:
 Best first search can switch between BFS and DFS by gaining the advantages of
both the algorithms.
 This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages:
 It can behave as an unguided depth-first search in the worst case scenario.
 It can get stuck in a loop as DFS.
 This algorithm is not optimal.
Example

Expand the nodes of S and put in the CLOSED list

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]

Iteration 2: Open [E, F, A], Closed [S, B]

: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]
: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S---> B----->F ---- > G

Means-Ends Analysis
 We have studied the strategies which can reason either in forward or backward,
but a mixture of the two directions is appropriate for solving a complex and
 large problem. Such a mixed strategy, make it possible that first to solve the
major part of a problem and then go back and solve the small problems arise
during combining the big parts of the problem. Such a technique is called
Means-Ends Analysis.
 Means-Ends Analysis is problem-solving techniques used in Artificial
intelligence for limiting search in AI programs.
 It is a mixture of Backward and forward search technique.
 The MEA technique was first introduced in 1961 by Allen Newell, and Herbert
A. Simon in their problem-solving computer program, which was named as
General Problem Solver (GPS).
 The MEA analysis process centered on the evaluation of the difference
between the current state and goal state.
How means-ends analysis Works:
The means-ends analysis process can be applied recursively for a problem. It is
a strategy to control search in problem-solving. Following are the main Steps
which describes the working of MEA technique for solving a problem.
a) First, evaluate the difference between Initial State and final State.
b) Select the various operators which can be applied for each difference.
c) Apply the operator at each difference, which reduces the difference
between the current state and goal state.

Operator Subgoaling
 we create the subproblem of the current state, in which operator can be applied,
such type of backward chaining in which operators are selected, and then sub
goals are set up to establish the preconditions of the operator is called Operator
Subgoaling.
 The operators we have for this problem are:
 Move
 Delete
 Expand
Example of Mean-Ends Analysis:

[Link] the initial state: In the first step, we will evaluate the initial state
and will compare the initial and Goal state to find the differences between both
states.

2. Applying Delete operator: As we can check the first difference is that in goal
state there is no dot symbol which is present in the initial state, so, first we will
apply the Delete operator to remove this dot.

3. Applying Move Operator: After applying the Delete operator, the new state
occurs which we will again compare with goal state. After comparing these states,
there is another difference that is the square is outside the circle, so, we will apply
the Move Operator.
4. Applying Expand Operator: Now a new state is generated in the third step,
and we will compare this state with the goal state. After comparing the states there
is still one difference which is the size of the square, so, we will apply Expand
operator, and finally, it will generate the goal state.

AO* Search
Best-first search is what the AO* algorithm does. The AO* method divides any
given difficult problem into a smaller group of problems that are then resolved
using the AND-OR graph concept. AND OR graphs are specialized graphs that
are used in problems that can be divided into smaller problems. The AND side
of the graph represents a set of tasks that must be completed to achieve the main
goal, while the OR side of the graph represents different methods for
accomplishing the same main goal.
 The start state and the target state are already known in the knowledge-based
search strategy known as the AO* algorithm, and the best path is identified by
heuristics.
Working of AO* algorithm:
The evaluation function in AO* looks like this:
f(n) = g(n) + h(n)
f(n) = Actual cost + Estimated cost
here,
f(n) = The actual cost of traversal.
g(n) = the cost from the initial node to the current node.
h(n) = estimated cost from the current node to the goal state.

Example
Problem Reduction
a solution to a problem can be obtained by decomposing it into smaller sub-
problems. Each of this sub-problem can then be solved to get its sub-solution.
These sub-solutions can then be recombined to get a solution as a whole. That is
called is Problem Reduction. This method generates arc which is called as AND
arcs. One AND arc may point to any number of successor nodes, all of which
must be solved for an arc to point to a solution.
Problem Reduction algorithm:
1. Initialize the graph to the starting node.
2. Loop until the starting node is labelled SOLVED or until its cost goes above
FUTILITY:
(i) Traverse the graph, starting at the initial node and following the current best
path and accumulate the set of nodes that are on that path and have not yet been
expanded.
(ii) Pick one of these unexpanded nodes and expand it. If there are no
successors, assign FUTILITY as the value of this node. Otherwise, add its
successors to the graph and for each of them compute f'(n). If f'(n) of any node
is O, mark that node as SOLVED.
(iii) Change the f'(n) estimate of the newly expanded node to reflect the new
information provided by its successors. Propagate this change backwards
through the graph. If any node contains a successor arc whose descendants are
all solved, label the node itself as SOLVED.

A* Search
A* Algorithm is one of the best and popular techniques used for path finding
and graph traversals.
A lot of games and web-based maps use this algorithm for finding the shortest
path efficiently.
It is essentially a best first search algorithm.
 It maintains a tree of paths originating at the start node.
 It extends those paths one edge at a time.
  It continues until its termination criterion is satisfied.

A* Algorithm extends the path that minimizes the following function-

f(n) = g(n) + h(n)
Here,

 ‘n’ is the last node on the path.

 g(n) is the cost of the path from start node to node ‘n’.
 h(n) is a heuristic function that estimates cost of the cheapest path from
node ‘n’ to the goal node.

Example :Find the most cost-effective path to reach from start state A to final
state J using A* Algorithm.

Heuristic value
A 10
B8
C5
D7
E3
F6
G5
H3
I1
J0

Solution
Step -01
f(B) = 6 + 8 = 14
f(F) = 3 + 6 = 9
Path- A → F

Step-02:
f(G) = (3+1) + 5 = 9
f(H) = (3+7) + 3 = 13
Path- A → F → G

Step-03:
f(I) = (3+1+3) + 1 = 8

Path- A → F → G → I

Step-04:
f(E) = (3+1+3+5) + 3 = 15
f(H) = (3+1+3+2) + 3 = 12
f(J) = (3+1+3+3) + 0 = 10

Path- A → F → G → I → J

Final Path A → F → G → I → J