Module 2- Problem Solving

• Solving Problems by searching-Problem

solving Agents, Example problems, Searching
for solutions, Uninformed search strategies,
Informed search strategies, Heuristic functions
 Solving Problems by Searching

• Simple agents discussed were the reflex agents, which base

their actions on a direct mapping from states to actions.
• Such agents cannot operate well in environments for which
this mapping would be too large to store and would take too
long to learn.
• Goal-based agents, on the other hand, consider future
actions and the desirability of their outcomes.
• Such a goal-based agent called a problem-solving agent
 PROBLEM-SOLVING AGENTS
• Goal Based Agent
• Agent adopt a goal and aim at satisfying them
• Goals helps to organize behavior by limiting
the objectives that the agent is trying to
achieve and hence the actions it needs to
consider
 Steps require to solve a problem
• Goal Formulation
 based on the current situation and the agent’s performance
measure
 Organizes finite step to formulate a target/goals which require
some action to achieve the goal.
• Problem formulation
 process of deciding what actions and states to consider, given
a goal
 1. Goal formulation
• First step in problem solving is goal
formulation
• It is based on the current situation and the
agent’s performance measure
• The goal is formulated
 as a set of world states, in which the goal is
satisfied
• Reaching from initial state goal state
 Actions are required
 Components to formulate the associated
problem
A problem can be defined formally by five
components:
•Initial State
•Action
•Transition
•Goal Test
•Path Costing
 Properties of the Environment

• Observable: agent always knows the current state of

environment.
• Discrete: at any given state there are only finitely many
actions to choose from.
• Known: agent knows which states are reached by each
action.
• Deterministic: each action has exactly one outcome
 Search
• process of looking for a sequence of actions that
reaches the goal is called search
• A search algorithm takes a problem as input and
returns a solution in the form of an action sequence
• Once a solution is found, the actions it recommends
can be carried out.
• This is called the execution phase
• Thus, we have a simple “formulate, search, execute”
design for the agent.
 Searching Process

1. Formulate a goal and a problem to solve.

2. Agent calls a search procedure to solve it
3. Agent uses the solution to guide its actions
4. Do whatever the solution recommends typically,
the first action of the sequence
5. Then remove that step from the sequence.
6. Once the solution has been executed, the agent will formulate a new
goal.
 Open-loop system
• While the agent is executing the solution sequence it ignores
its percepts when choosing an action because it knows in
advance what they will be.
• An agent that carries out its plans with its eyes closed, so to
speak, must be quite certain of what is going on is an open
loop.
• ignoring the percepts breaks the loop between agent and
environment.
• Eg:- Bread toaster, Microwave Oven
A problem can be defined formally
by following components:
• initial state
• description of the possible actions available to
the agent.
Eg:- In(Ernakulam), the applicable actions are {Go(Thrissur),
Go(Palakkad),Go(Kozhikod)}.
• Transition model: description of what each action does,
specified by a function RESULT(s, a) that returns the state that
results from doing action a in state s
• Successor: any state reachable from a given state by
a single action
RESULT(In(Ernakulam),Go(Thrissur)) = In(Thrissur) .
• state space: the set of all states reachable from the
initial state by any sequence of actions.
• forms a directed network or graph in which the
nodes are states and the links between nodes are
actions.
6. path in the state space is a sequence of
states connected by a sequence of actions.
7. goal test, which determines whether a given
state is a goal state {In(Chennai)}.
8. path cost function that assigns a numeric cost
to each path.
• step cost of taking action a in state s1 to reach
state s2 is denoted by c(s1, a, s2 ).
• A solution to a problem is an action sequence
that leads from the initial state to a goal state.
• Solution quality is measured by the path cost
function, and an optimal solution has the
lowest path cost among all solutions.
 Formulating problems

•Abstraction
• the process to take out the irrelevant information
• leave the most essential parts to the description of the states

(Remove detail from representation)

• Conclusion: Only the most important parts that are
contributing to searching are used
Example: Romania
Single-state problem formulation
 Example Problems
• Distinguishing between toy and real-world
problems
• Toy Problem is intended to illustrate or
exercise various problem solving methods.
E.g., puzzle, chess, etc.
• A real-world problem is one whose solutions
people actually care about.
E.g., Design, planning, etc.
 Toy problems
a)Vacuum World
• States: The state is determined by both the agent location
and the dirt locations.
The agent is in one of two locations, each of which might or
might not contain dirt.
Thus, there are 2 × 22 = 8 possible world states.
A larger environment with n locations has n · 2n states.
Toy Problem – Vaccum World
Toy-Problem – 8 puzzle
 8 puzzle
• States – Description mentions the location of each
tiles
• Initial State – any state
• Actions - left,right,up,down
• Transition model – Given a state & action,this
returns the resulting state.
• Goal test – checks whether this state matches the
goal configuration
• Path Cost – Each step cost 1(number of steps in the
path)
8-Puzzle
• 8-puzzle has 9!/2 = 181, 440 reachable states and is
easily solved.
• 15-puzzle (on a 4×4 board) has around 1.3 trillion
states, and random instances can be solved optimally
in a few milliseconds by the best search algorithms.
• 24-puzzle (on a 5 × 5 board) has around 1025
states, and random instances take several hours to
solve optimally.
 Toy Problem - 8-queens problem
• goal of the 8-queens problem is to place
eight queens on a chessboard such that no
queen attacks any other.
• A queen attacks any piece in the same row,
column or diagonal.
 There are two main kinds of
formulation
• An incremental formulation
• A complete-state formulation
 An incremental formulation

• involves operators that augment the state

description starting from an empty state
• Each action adds a queen to the state
• States:
 any arrangement of 0 to 7 queens on board
• Successor function:
• add a queen to any empty square
 An incremental formulation
• States: • Transition model:
Any arrangement of 0 Returns the board with
to 7 queens on the a queen added to the
board is a state. specified square.
• Initial state: No queens • Goal test: 8 queens are
on the board. on the board, none
• Actions: Add a queen to attacked.
any empty square. • we have 64 ・ 63 ・ ・ ・
57 ≈ 1.8×1014 possible
sequences to investigate
 A complete-state formulation
• starts with all 8 queens on the board
• move the queens individually around
• States:
 any arrangement of 8 queens, one per column in the
leftmost columns
• Operators: move an attacked queen to a row,
not attacked by any other
• the right formulation makes a big difference
to the size of the search space
 A complete-state formulation
• States: All possible arrangements of n queens
(0 ≤ n ≤ 8), one per column in the leftmost n
columns, with no queen attacking another.
• Actions: Add a queen to any square in the
leftmost empty column such that it is not
attacked by any other queen.
• reduces the 8-queens state space from
1.8×1014 to just 2,057, and solutions are easy
to find.
 Another Toy Problem
• starting with the
number 4, a sequence
of factorial, square
root, and floor
operations will reach
any desired positive
integer.
• For example,we can
reach 5 from 4 as
follows:
 Real-world problems
• Route-finding problems
• Touring problems (visit every city atleast once)
• Traveling Salesman problem (each city must be
visited exactly once)
• VLSI layout problem
• Robot navigation
• Automatic assembly sequencing (find an order in
which to assemble the parts of some object)
• Internet searching
 Searching for solution
• A solution is an action sequence
• so search algorithms work by considering
various possible action sequences.
• possible action sequences starting at the
initial state form a search tree with the initial
state at the root.
• branches are actions and the nodes
correspond to states in the state space of the
problem.
Search tree for finding a route from Arad to Bucharest
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.
The process of expanding nodes on the frontier continues
until either a solution is found or there are no more states to
expand.
• Search algorithms all share this basic structure;
called search strategy.
• Loopy path: path from Arad to Sibiu and back to
Arad again is a repeated state in the search tree,
generated in this case by a loopy path.
• Loopy paths are a special case of redundant
paths, which exist whenever there is more than
one way to get from one state to another.
• Frontier is the reached but unexpanded states
because we can expand only them.
• a search strategy has two components:
– rule(s) to decide whether or not to place the node
in the frontier
– rule(s) to choose the next frontier node for
expansion
 TREE-SEARCH Algorithm
• with a data structure called the explored set
(also known as the closed list), which
remembers every expanded node.
• Newly generated nodes that match previously
generated nodes ones in the explored set or
the frontier can be discarded instead of being
added to the frontier
Tree-Search algorithm
 GRAPH-SEARCH algorithm
• Each state appears in the graph only once.
But, it may appear in the tree multiple times.
• contains at most one copy of each state
• Don’t add a node if its state has already been
expanded or a node pointing to the same
state is already in the frontier.
8
 Infrastructure for search
algorithms
• Search algorithms require a data structure to keep track of
the search tree that is being constructed.
• 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.
• :
 Search Algorithm using Queue Data
Structure
• 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 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
• Three common variants of queue are
◦ first-in, first-out or FIFO queue, which pops the oldest element of the queue;
• ◦ last-in, first-out or LIFO queue (also known as a stack), which pops the newest
element of the queue
• ◦ priority queue, which pops the element of the queue with the highest priority
according to some ordering function
 Measuring problem-solving
performance
• 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?
• Complexity is expressed in terms of three quantities: b, the branching
factor or maximum number of successors of any node; d, the depth of the
shallowest goal node and m, the maximum length of any path in the
state space.
DIFFERENT TYPES OF SEARCHING
 Different types of Searching
• Uninformed Search
• Informed Search
 Uninformed Search Strategies
• no additional information about states beyond
that provided in the problem definition
• All they can do is generate successors and
distinguish a goal state from a non-goal state.
• do not take into account the location of the
goal.
• ignore where they are going until they find a
goal and report success.
 1. Breadth-First search
• root node is expanded first, then all the successors of the root
node are expanded next, then their successors, and so on.
• Breadth-first search is an instance of the general graph-search
algorithm in which the shallowest unexpanded node is chosen
for expansion
• achieved very simply by using a FIFO queue for the frontier
new node
• the goal test is applied to each node when it is generated rather
than when it is selected for expansion
• breadth-first search always has the shallowest path to every
node on the frontier
• Ans:- {S,A,B,C,D,G,H,E,F,I,K}
Breadth-First search
 Problem solving performance-BFS
• Complete
• Not optimal one
• Time Complexity(Then the total number of
nodes generated is b + b2 + b3 + ··· + bd = O(bd))
• Space Complexity (O(bd))
 Breadth-First search
• the memory requirements are a bigger problem for breadth-
first search than is the execution time
• One might wait 13 days for the solution to an important
problem with search depth 12, but no personal computer has
the petabyte (1015) of memory it would take.
• If your problem has a solution at depth 16, then it will take
about 350 years for breadth-first search to find it.
• In general, exponential-complexity search problems cannot be
solved by uninformed methods for any but the smallest
instances.
 2. Uniform-cost search
• Instead of expanding the shallowest node, uniform-cost
search expands the node n with the lowest path cost g(n).
• This is done by storing the frontier as a priority queue ordered
by g.
• the goal test is applied to a node when it is selected for
expansion
• because the first goal node that is generated may be on a
suboptimal path
• a test is added in case a better path is found to a node
currently on the frontier
• The successors of Sibiu are
Rimnicu Vilcea and Fagaras, with
costs 80 and 99, respectively.
• 80 + 97 = 177.
• least-cost node is now Fagaras, so
it is expanded, adding Bucharest
with cost 99 + 211 =310.
• Now a goal node has been
generated, but uniform-cost
search keeps going, choosing
Pitesti for expansion and adding a
second path to Bucharest with
cost 80+ 97+ 101 = 278.
Problem solving performance-UCS
• Complete: guaranteed provided the cost of every step exceeds
some small positive constant ε
• Optimal: optimal path to that node has been found. because
step costs are nonnegative, paths never get shorter as nodes
are added.
• uniform-cost search expands nodes in order of their optimal
path cost.
• Time Complexity: # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε)) where C* is the cost of the optimal solution
• Space Complexity: # of nodes with g ≤ cost of optimal solution,
O(bceiling(C*/ ε))
Depth-first search
 Depth-first search
• Depth-first search always expands the deepest node in the
current frontier of the search tree.
• 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
frontier, so then the search “backs up” to the next deepest
node that still has unexplored successors.
• Depth-first search uses a LIFO queue
• A LIFO queue means that the most recently generated node
is chosen for expansion.
 Problem solving performance-DFS
1. Completeness:
• depth-first search is implemented with a recursive function
that calls itself on each of its children in turn.
• properties of depth-first search depend strongly on whether
the graph-search or tree-search version is used.
• graph-search version, which avoids repeated states and
redundant paths, is complete infinite state spaces because it
will eventually expand every node.
• The tree-search version, on the other hand, is not complete
2) Not optimal
• depth- first search will explore the entire left
subtree even if node C is a goal node.
3) Time complexity
• depth-first graph search is bounded by the size of the state
space
• A depth-first tree search, on the other hand, may generate all
of the O(bm) nodes in the search tree,
• where m is the maximum depth of any node; this can be
much greater than the size of the state space.
• m itself can be much larger than d (the depth of the
shallowest solution) and is infinite if the tree is unbounded
4) Space complexity
• For a state space with branching factor b and maximum depth
m, depth-first search requires storage of only O(bm) nodes.
 Backtracking search
• A variant of depth-first search called backtracking search uses still
less memory
• only one successor is generated at a time rather than all successors;
• each partially expanded node remembers which successor to
generate next.
• Only O(m) memory is needed rather than O(bm).
• Backtracking search facilitates the idea of generating a successor by
modifying the current state description directly rather than copying
it first.
• This reduces the memory requirements to just one state description
and O(m) actions.
• For this to work, we must be able to undo each modification when
we go back to generate the next successor
 Depth-limited search
• depth-first search with a predetermined depth limit l
• nodes at depth l are treated as if they have no successors.
• depth limit solves the infinite-path problem.
• It also introduces an additional source of incompleteness if
we choose l<d, that is, the shallowest goal is beyond the
depth limit.
• will also be non optimal if we choose l>d.
• time complexity is O(bl )and its space complexity is O(bl )
• Iterative deepening is the preferred uninformed search
method when the search space is large and the depth of the
solution is not known.
• Iterative deepening search is analogous to breadth-first
search in that it explores a complete layer of new nodes at
each iteration before going on to the next layer.
• time complexity of O(bd) asymptotically the same as breadth-
first search.
 INFORMED (HEURISTIC) SEARCH
STRATEGIES
• problem-specific knowledge beyond the
definition of the problem itself.
• can find solutions more efficiently than an
uninformed strategy.
 BEST-FIRST SEARCH
• instance of the general TREE-SEARCH or GRAPH-SEARCH
algorithm in which a node is selected for expansion based on
an evaluation function, f(n).
• evaluation function is construed as a cost estimate, so the
node with the lowest evaluation is expanded first.
• implementation of best-first graph search is identical to that
for uniform-cost search except for the use of f instead of g to
order the priority queue
• choice of f determines the search strategy
• Most best-first algorithms include as a
component of f a heuristic function, denoted
h(n):
h(n) = estimated cost of the cheapest path
from the state at node n to a goal state.
• if n is a goal node, then h(n)=0.
 Greedy best-first search
• tries to expand the node that is closest to the
goal, on the grounds that this is likely to lead
to a solution quickly.
• It evaluates nodes by using just the heuristic
function; that is, f(n) = h(n).
 Greedy best-first search- Route finding
problems in Romania
• straight line distance
heuristic, Hsld
• If the goal is Bucharest,
we need to know the
straight-line distances
to Bucharest
• Hsld is correlated with
actual road distances
and is, therefore, a
useful heuristic
 A* search: Minimizing the total
estimated solution cost
• It evaluates nodes 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)
• g(n) -> path cost from the start node to node n
• h(n) -> estimated cost of the cheapest path from n
to the goal
• f(n) = estimated cost of the cheapest solution
through n
• if we are trying to find the cheapest solution, a reasonable
thing to try first is the node with the lowest value of g(n) +
h(n).
• It turns out that this strategy is more than just reasonable:
provided that the heuristic function h(n) satisfies certain
conditions,
• A∗ search is both complete and optimal.
• The algorithm is identical to UNIFORM-COST-SEARCH except
that A∗ uses g + h instead of g.
Progress of an A∗ tree search
 Conditions for optimality:
Admissibility
• 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.
• g(n) is the actual cost to reach n along the current path, and
• f(n) = g(n) + h(n), we have as an immediate consequence that
f(n) never overestimates
• the true cost of a solution along the current path through n.
• Admissible heuristics are by nature optimistic
because they think the cost of solving the problem is
less than it actually is
• Eg, straight-line distance Hsld that we used in getting
to Bucharest is an admissible heuristic
– because the shortest path between any two
points is a straight line
– Straight line cannot be an overestimate
 Conditions for optimality:
Consistency
• 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 not
greater than the step cost of getting to n plus the
estimated cost of reaching the goal from n :
• h(n) ≤ c(n, a, n ) + h(n )
• This is a form of the general triangle inequality (each
side of a triangle cannot be longer than the sum of
other to sides)
 Optimality of A*
• the tree-search version of A∗ is optimal if h(n) is admissible,
while the graph-search version is optimal if h(n) is
consistent.
• Pruning eliminates possibilities from consideration without
having to examine them
• A∗ is optimally efficient for any given consistent heuristic.
 no other optimal algorithm is guaranteed to expand fewer nodes than A∗
 This is because any algorithm that does not expand all nodes with f(n) <
C∗ runs the risk of missing the optimal solution.
 Contours in the state space
• Inside the contour labeled 400, all nodes have f(n) less than or
equal to 400, and so on.
• A∗ expands the frontier node of lowest f-cost, we can see
that an A∗ search fans out from the start node, adding nodes
in concentric bands of increasing f-cost.
• Contours – labelled region
 Disadvantages of A* Algorithm
• 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 catch is that,for most problems, number
of states within the goal contour search space
is still exponential in the length of the
solution.
 Admissible Heuristics
• h1 = the number of misplaced tiles.
• h2 = the sum of the distances of the tiles from
their goal positions.
 Properties of a Heuristic search
Algorithm
• Admissible Condition: An algorithm is said to be admissible, if it
returns an optimal solution.
• Completeness: An algorithm is said to be complete, if it terminates
with a solution (if the solution exists).
• Dominance Property: If there are two admissible heuristic
algorithms A1 and A2 having h1 and h2 heuristic functions,
then A1 is said to dominate A2 if h1 is better than h2 for all the
values of node n.
• Optimality Property: If an algorithm is complete, admissible,
and dominating other algorithms, it will be the best one and will
definitely give an optimal solution.
 Heuristic Performance
• Experiments on sample problems can determine the number
of nodes searched and CPU time for different strategies.
• One other useful measure is effective branching factor:
• If a method expands N nodes to find solution of depth d, and
a uniform tree of depth d would require a branching factor of
b* to contain N nodes, the effective branching factor is b*
• N = 1 + b* + (b*)2 + ...+ (b*)d
• Q) Perform BFS search in the problem given
below to reach goal node G from source node
S.
A 12
B 4
C 7
D 3
E 8
F 2
S 4
H 9
I 13
G 0
• CLOSED LIST – already expanded
• OPEN LIST – to be expanded
 Best First Search - Algorithm
• Step1:- Place starting node in OPEN List
• Step2:- If OPEN list is empty, stop & return failure
• Step3:- Remove n from OPEN list who has lowest
h(n) and placed it in closed list
• Step4:- Expand node n & generate its successor
• Step5:- Check each successor for goal node or not, if

goal node return goal

If not, for each successor node check evaluation
function f(n) & if it is in OPEN/CLOSED list.
Step 6:- If not in both list add to OPEN list and
go to step 2