UNIT II

PROBLEM SOLVING
Topics
• Heuristic search strategies
• Heuristic functions.
• Local search and optimization problems
• Local search in continuous space
• Search with non-deterministic actions
• Search in partially observable
environments
• Online search agents and unknown environments
Heuristic Search Strategies

• A heuristic is a technique that is used to solve a problem faster than the

classic methods. These techniques are used to find the approximate
solution of a problem when classical methods do not. Heuristics are said
to be the problem-solving techniques that result in practical and quick
solutions.
• Heuristics are strategies that are derived from past experience with
similar problems. Heuristics use practical methods and shortcuts used to
produce the solutions that may or may not be optimal, but those solutions
are sufficient in a given limited timeframe.
In the informed search we will discuss two main algorithms which are given
below:
1. Best First Search Algorithm(Greedy search).
2. A* Search Algorithm
Best- First Search
• A very general approach is called best-first search, in which we choose a
node, n, with minimum value of some Best-first search evaluation function,
f(n).
• On each iteration we choose Evaluation function a node on the frontier with
minimum f(n) value, return it if its state is a goal state, and otherwise apply
EXPAND to generate child nodes.
• Each child node is added to the frontier if it has not been reached before, or is
re-added if it is now being reached with a path that has a lower path cost than
any previous path.
• The algorithm returns either an indication of failure, or a node that represents
a path to a goal.
Greedy Best- First Search
• Greedy best-first search is a form of best-first search that expands first the
node with the Greedy best-first search 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).
The greedy best first algorithm is implemented by the priority queue. Best
first search 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: Consider the below search problem, and we will traverse it using
greedy best-first search. At each iteration, each node is expanded using
evaluation function f(n)=h(n) , which is given in the below table.
Consider the below search problem, and we will traverse it using greedy best-
first search.
At each iteration, each node is expanded using evaluation function f(n)=h(n) ,
which is given in the below table.
In this search example, we are using two lists which are OPEN and CLOSED
Lists. Following are the iteration for traversing the above 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]
Time Complexity: The worst case time complexity of Greedy best first search is
O(bm).
Space Complexity: The worst case space complexity of Greedy best first search
is O(bm). Where, m is the maximum depth of the search space.
Complete: Greedy best-first search is also incomplete, even if the given state
space is finite.
Optimal: Greedy best first search algorithm is not optimal.
A* Search Algorithm
• The most common informed search algorithm is A ∗ search
(pronounced “A-star search”)
• A A*search best-first search that uses the evaluation function
f(n) = g(n) +h(n)
• Where g(n) = the path cost from the initial state to node n,
h(n) =the estimated cost of the shortest path from n to a goal
state, f(n) = estimated cost of the best path that continues from n to a
goal.
Example
• Consider the following graph.
• The numbers written on edges represent the distance between the nodes.
• The numbers written on nodes represent the heuristic value.
• Find the most cost-effective path to reach from start state A to final state J using A*
Algorithm.
Solution:
Step1:
• We start with node A.
• Node B and Node F can be reached from node A.
• A* Algorithm calculates f(B) and f(F).
f(B) = 6 + 8 = 14
f(F) = 3 + 6 = 9
Since f(F) < f(B), so it decides to go to node F.
• Path- A → F
• Step 2: Node G and Node H can be reached from node F.
• A* Algorithm calculates f(G) and f(H).
f(G) = (3+1) + 5 = 9
f(H) = (3+7) + 3 = 13
Since f(G) < f(H), so it decides to go to node G.
• Path- A → F → G
• Step 3: Node I can be reached from node G.
• A* Algorithm calculates f(I).
f(I) = (3+1+3) + 1 = 8
It decides to go to node I.
• Path- A → F → G → I
• Step 4: Node E, Node H and Node J can be reached from node I.
• A* Algorithm calculates f(E), f(H) and f(J).
f(E) = (3+1+3+5) + 3 = 15
f(H) = (3+1+3+2) + 3 = 12
f(J) = (3+1+3+3) + 0 = 10
• Since f(J) is least, so it decides to go to node J.
• Path- A → F → G → I → J
• This is the required shortest path from node A to node J.
• A* algorithm returns the path which occurred first, and it does not search
for all remaining paths.
• The efficiency of A* algorithm depends on the quality of heuristic.
• Complete: A* algorithm is complete as long as:
Branching factor is finite.
Cost at every action is fixed.
• Optimal: A* search algorithm is optimal if it follows below two
conditions:
• Admissible: the first condition requires for optimality is that h(n) should be an
admissible heuristic for A* tree search. An admissible heuristic is optimistic in
nature. (i.e. the cost it estimates to reach the goal is not higher than the lowest
possible cost from the current point in the path.)
• Consistency: Second required condition is consistency for only A* graph-search.
If the heuristic function is admissible, then A* tree search will always find the
least cost path.
Local search and optimization problems

• The search algorithms we have seen so far, more often concentrate on

path through which the goal is reached. But if the problem does not
demand the path of the solution and it expects only the final configuration
of the solution then we have different types of problem to solve.
• The local search algorithm searches only the final state, not the path to get
here.
• For example, 8-queens problem,
• We care only about finding a valid final configuration of 8 queens (8
queens arranged on chess board, and no queen attack can attack other
queens) and not the path from initial state to final state.
• Local search algorithm operates by searching from a start state to a
neighboring states, without keeping track of the paths, nor the set of states
that have been reached.
• They are not systematic- they might never explore a portion of the search
space where the solution actually resides. They searches only the final
state.
Local Search Algorithms
1. Hill climbing Algorithm.
2. Simulated Annealing.
3. Local Beam Search.
4. Evolutionary Algorithm- Genetic Algorithm.
Hill Climbing Algorithm
• Hill climbing algorithm is a Heuristic Search algorithm which continuously
moves in the direction of increasing value to find the peak of the mountain or
best solution to the problem.
• It keeps track of one current state and on each iteration moves to the
neighboring state with highest value-that is, it heads in the direction that
provides the steepest ascent.
Different regions in the State Space Diagram:
• Local maximum: It is a state which is better than its neighboring state
however there exists a state which is better than it(global maximum). This
state is better because here the value of the objective function is higher than its
neighbors.
• Global maximum: It is the best possible state in the state space diagram. This
is because, at this stage, the objective function has the highest value.
• Plateau/flat local maximum: It is a flat region of state space where
neighboring states have the same value.
• Ridge: It is a region that is higher than its neighbors but itself has a slope. It is
a special kind of local maximum.
• Current state: The region of the state space diagram where we are currently
present during the search.
• Shoulder: It is a plateau that has an uphill edge.
Problems in 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.
• Solution: Backtracking technique can be a solution of the local maximum in
state space landscape. Create a list of the promising path so that the algorithm
can backtrack the search space and explore other paths as well.
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.
• Solution: The solution for the plateau is to take big steps or very little steps
while searching, to solve the problem. Randomly select a state which is far away
from the current state so it is possible that the algorithm could find non-plateau
region.
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.
Solution: With the use of bidirectional search, or by moving in different
directions, we can improve this problem.
Types of Hill Climbing:
1. Simple Hill Climbing.
2. Steepest-Ascent Hill Climbing.
3. Stochastic Hill Climbing.
Simple Hill Climbing:
Simple hill climbing is the simplest way to implement a hill climbing
algorithm. It only evaluates the neighbor node state at a time and selects
the first one which optimizes current cost and set it as a current state.
It only checks it's one successor state, and if it finds better than the current
state, then move else be in the same state. This algorithm has the following
features:
Algorithm for Simple Hill Climbing:
• Step 1: Evaluate the initial state, if it is goal state then return success and
Stop.
• Step 2: Loop Until a solution is found or there is no new operator left to
apply.
• Step 3: Select and apply an operator to the current state.
• Step 4: Check new state:
• If it is goal state, then return success and quit.
• Else if it is better than the current state then assign new state as a current state.
• Else if not better than the current state, then return to step2.
• Step 5: Exit.
Steepest-Ascent hill climbing:
• The steepest-Ascent algorithm is a variation of simple hill climbing algorithm. This
algorithm examines all the neighboring nodes of the current state and selects one
neighbor node which is closest to the goal state. This algorithm consumes more time
as it searches for multiple neighbors
Algorithm for Steepest-Ascent hill climbing:
• Step 1: Evaluate the initial state, if it is goal state then return success and stop, else
make current state as initial state.
• Step 2: Loop until a solution is found or the current state does not change.
• Let SUCC be a state such that any successor of the current state will be better than it.
• For each operator that applies to the current state:
• Apply the new operator and generate a new state.
• Evaluate the new state.
• If it is goal state, then return it and quit, else compare it to the SUCC.
• If it is better than SUCC, then set new state as SUCC.
• If the SUCC is better than the current state, then set current state to SUCC.
• Step 5: Exit.
Stochastic hill climbing:
• Stochastic hill climbing does not examine for all its neighbor before moving.
Rather, this search algorithm selects one neighbor node at random and
decides whether to choose it as a current state or examine another state.
2. Simulated Annealing:
• A hill-climbing algorithm which never makes a move towards a lower value
guaranteed to be incomplete because it can get stuck on a local maximum.
And if algorithm applies a random walk, by moving a successor, then it may
complete but not efficient. Simulated Annealing is an algorithm which
yields both efficiency and completeness.
• In mechanical term Annealing is a process of hardening a metal or glass to a
high temperature then cooling gradually, so this allows the metal to reach a
low-energy crystalline state. The same process is used in simulated annealing
in which the algorithm picks a random move, instead of picking the best
move.
• If the random move improves the state, then it follows the same path.
Otherwise, the algorithm follows the path which has a probability of less
than 1 or it moves downhill and chooses another path.
• Simulated Annealing(SA) is very useful for situations where there are a lot
of local minima.
3. Beam Search Algorithm:
• Beam search is a heuristic search algorithm that explores a
graph by expanding the most optimistic node in a limited
set. Beam search is an optimization of best-first
search that reduces its memory requirements.
• Best-first search is a graph search that orders all partial
solutions according to some heuristic. But in beam search,
only a predetermined number of best partial solutions are
kept as candidates. Therefore, it is a greedy algorithm.
• Beam search uses breadth-first search to build its search
tree. At each level of the tree, it generates all successors of
the states at the current level, sorting them in increasing
order of heuristic cost. However, it only stores a
predetermined number (β), of best states at each level
called the beamwidth. Only those states are expanded
Components of Beam Search
• A beam search takes three components as its input:
1.A problem to be solved,
2.A set of heuristic rules for pruning,
3.And a memory with a limited available capacity.
• The problem is the problem to be solved, usually represented as a graph, and
contains a set of nodes in which one or more of the nodes represents a goal.
The set of heuristic rules are rules specific to the problem domain and prune
unfavorable nodes from memory regarding the problem domain.
• The memory is where the "beam" is stored, memory is full, and a node is to
be added to the beam, the most costly node will be deleted, such that the
memory limit is not exceeded.
4. Genetic Algorithm:
• Genetic Algorithms(GAs) are adaptive heuristic search algorithms that
belong to the larger part of evolutionary algorithms. Genetic algorithms are
based on the ideas of natural selection and genetics.
• These are intelligent exploitation of random searches provided with
historical data to direct the search into the region of better performance in
solution space. They are commonly used to generate high-quality
solutions for optimization problems and search problems.
• Genetic algorithms simulate the process of natural selection which means
those species that can adapt to changes in their environment can survive and
reproduce and go to the next generation.
• In simple words, they simulate “survival of the fittest” among individuals of
consecutive generations to solve a problem. Each generation consists of a
population of individuals and each individual represents a point in search
space and possible solution. Each individual is represented as a string of
character/integer/float/bits. This string is analogous to the Chromosome.
Foundation of Genetic Algorithms
• Genetic algorithms are based on an analogy with the genetic structure and
behavior of chromosomes of the population. Following is the foundation of GAs
based on this analogy –
1.Individuals in the population compete for resources and mate
2.Those individuals who are successful (fittest) then mate to create more offspring
than others
3.Genes from the “fittest” parent propagate throughout the generation, that is
sometimes parents create offspring which is better than either parent.
4.Thus each successive generation is more suited for their environment.
Search space
• The population of individuals are maintained within search space. Each
individual represents a solution in search space for given problem. Each
individual is coded as a finite length vector (analogous to chromosome) of
components. These variable components are analogous to Genes. Thus a
chromosome (individual) is composed of several genes (variable
components).

Fitness Score
• A Fitness Score is given to each individual which shows the ability of an
individual to “compete”. The individual having optimal fitness score (or
near optimal) are sought.
Operators of Genetic Algorithms
• Once the initial generation is created, the algorithm evolves the generation
using following operators –
1) Selection Operator: The idea is to give preference to the individuals with
good fitness scores and allow them to pass their genes to successive
generations.
2) Crossover Operator: This represents mating between individuals. Two
individuals are selected using selection operator and crossover sites are chosen
randomly. Then the genes at these crossover sites are exchanged thus creating a
completely new individual (offspring). For example –
3) Mutation Operator: The key idea is to insert random genes in offspring
to maintain the diversity in the population to avoid premature convergence.
For example –

The whole algorithm can be summarized as –

Local Search in Continuous Space
• The distinction between discrete and continuous environments pointing out
that most real-world environments are continuous.
• A discrete variable or categorical variable is a type of statistical variable
that can assume only fixed number of distinct values.
• Continuous variable, as the name suggest is a random variable that assumes
all the possible values in a continuum.
• Which leads to a solution state required to reach the goal node.
• But beyond these “Classical search algorithms”, we have some “local
search algorithms” where the path cost does not matters, and only focus
on solution-state needed to reach the goal node.
• Example: Greedy BFS Algorithm.
Search with non-deterministic actions

• When the environments is partially observable or non deterministic (or

both), the future percepts cannot be determined in advance, and the
agent’s future actions will depend on those future percepts.
Nondeterministic problems:
Transition model is defined by RESULTS functions that returns a set of
possible outcome states; Solution is not a sequence but a contingency plan
(strategy), E.g. : [Suck, if State =5 then [Right, Suck ] else[]];
In non-deterministic environments, agents can apply AND-OR search to
generate contingent plans that reach the goals regardless of which outcomes
occur during execution.
AND-OR Search Trees
OR nodes: In a deterministic environment, the only branching is
introduced by the agent’s own choices in each state, we call these nodes
OR nodes.
AND nodes: : In a non-deterministic environment, branching is also
introduced by environment’s choice of outcome for each action, we all call
these nodes AND nodes.
AND-OR nodes: OR nodes and AND nodes alternate. States nodes are
OR nodes where some action must be chosen. At the AND nodes(shown as
circles), every outcome must be handled.
A solution(shown in bold lines) for AND-OR Search problem is a subtree
that
1) Has a goal node at every leaf;
2) Specifies one action at each of its OR nodes;
3) Includes every outcome branch at each of its AND nodes.
Search in partially observable environments

• Search in partially observable environments refers to situations where an

agent doesn't have complete information about the state of the
environment.
• In such cases, the agent must rely on indirect evidence or incomplete data
to make decisions. These environments pose unique challenges for AI, as
the agent must estimate the current state based on observations and past
actions, often using techniques like belief states, probabilistic reasoning
(e.g., Bayesian networks), or Partially Observable Markov Decision
Processes (POMDPs) to make informed decisions.
Online search agents and unknown environments

• An online search agent operates by interleaving computation and action:

first it takes an action and then it observes the environment and computes
the next action.
• Online search is a good idea in dynamic or semi dynamic domains-
domains where there is a penalty for sitting around and computing too long.
• Online search is an even better idea for stochastic domains. (The term
"online" is commonly used in computer science to refer to algorithms that
must process input data as they are received, rather than waiting for the
entire input data set to become available.)
• In general, an offline search would have to come up with an exponentially
large contingency plan that considers all possible happenings, while an
online search need only consider what actually does happen.
• For example, A chess playing agent is well-advised to make its first move
long before it has figured out the complete course of the game.
• Online search is a necessary idea for an exploration problem, where the
states and actions are unknown to the agent.
• An agent in this state of Ignorance must use its actions as experiments to
determine what to do next, and hence must interleave computation and
action.
• The canonical example of online search is a robot that is placed in a new
building and must explore it to build a map that it can use for getting from
A to B.
• Methods for escaping from labyrinths-required knowledge for aspiring
heroes of antiquity-are also examples of online search algorithms. Spatial
exploration is not the only form of exploration, however.