PROBLEM SOLVING AND SEARCH
Classical Approach
The classical approach takes hit and trial
method to have solution of a problem.
The intelligent species use this approach to
solve problems at hand.
It is also called a generate and test approach.
There is a process of solution generation.
Classical Approach
Then the solution is verified.
If found correct it is adopted and we finish.
Otherwise we discard the solution and pick a
new solution to verify.
This process iterates until we pick a correct
solution.
Representing a problem for solution.
Problems generally represented as graphs
Problem solving ~ searching a graph
Two representations
(1) State space (usual graph)
(2) AND/OR graph
What is State Space?
State space = Directed graph
Nodes ~ Problem situations
Arcs ~ Actions, legal moves
Problem = ( State space, Start, Goal condition)
Note: several nodes may satisfy goal condition
Solving a problem ~ Finding a path
Problem solving ~ Graph search
Problem solution ~ Path from start to a goal node
Intelligent Agent’s approach
Intelligent agents are supposed to maximize the
performance measure.
This can be achieved by adopting a goal.
Goals help organize behavior by limiting the
objectives that the agent is trying to achieve.
Goal formulation is based on the current
situation and the agent’s performance measure
(It is the first step in problem solving).
Intelligent Agent’s approach
Goal could be a set of states.
The agent’s task is to find out which sequence
of actions will get it to a goal state.
Problem representation is the process of
deciding what sorts of actions and states to
consider, given a goal.
Intelligent Agent’s approach
An agent with several immediate options of
unknown value can decide what to do by first
examining different possible sequences of
actions that lead to a states of known value,
and then choosing the best sequence.
Looking for such a sequence is called Search.
A searching algorithm takes a problem as input
and returns solution in the form of action
sequence.
A problem from blocks world
Find a sequence of robot moves to re-arrange blocks
Blocks world state space
Start
Goal
Examples of representing problems
in state space
Blocks world planning
8-puzzle, 15-puzzle
8 queens
Travelling salesman
Set covering
How can these problems be represented by graphs?
Propose corresponding state spaces
8-puzzle
State spaces for optimisation
problems
Optimisation: minimise cost of solution
In blocks world:
actions may have different costs
(blocks have different weights, ...)
Assign costs to arcs
Cost of solution = cost of solution path
More complex examples
Making a time table
Production scheduling
Grammatical parsing
Interpretation of sensory data
Modelling from measured data
Finding scientific theories that account for
experimental data
SEARCH METHODS
Uninformed techniques:
systematically search complete graph,
unguided
Informed methods:
Use problem specific information to guide
search in promising directions
What is “promising”?
Domain specific knowledge
Heuristics
Basic search methods - uninformed
Depth-first search
Breadth-first search
Iterative deepening
Informed, heuristic search
Best-first search
Hill climbing, steepest descent
Algorithm A*
Beam search
Algorithm IDA* (Iterative Deepening A*)
Algorithm RBFS (Recursive Best First
Search)
Direction of search
Forward search: from start to goal
Backward search: from goal to start
Bidirectional search
In expert systems:
Forward chaining
Backward chaining
Depth-first search
Properties of depth-first search
program
Is not guaranteed to find shortest solution first
Susceptible to infinite loops (should check for
cycles)
Has low space complexity: only proportional to
depth of search
Only requires memory to store the current path
from start to the current node
When moving to alternative path, previously
searched paths can be forgotten
Iterative deepening search
Depth-limited search may miss a solution if
depth-limit is set too low
This may be problematic if solution length not
known in advance
Idea: start with small MaxDepth and increase
MaxDepth until solution found
Breadth-first search
•Guaranteed to find shortest solution first
•best-first finds solution a-c-f
•depth-first finds a-b-e-j
A breadth-first search program
Breadth-first search completes one level
before moving on to next level
Has to keep in memory all the competing paths
that aspire to be extended to a goal node
A possible representation of candidate paths:
list of lists
Easiest to store paths in reverse order;
then, to extend a path, add a node as new
head (easier than adding a node at end of list)
Candidate paths as list of lists
a
b c
d e f g
[[[c,a],
[d,b,a],
[[ [a] ][d,b,a],
[b,a], initial
[e,b,a],
[c,a] list[f,c,a],
][e,b,a]of candidate
after [g,c,a]
] expanding
after ] paths
a
expanding b
On each iteration: Remove first candidate path,
extend it and add extensions at end of list
Complexity of basic search methods
For simpler analysis consider state-space as a tree
Uniform branching b
Solution at depth d
Number of nodes at level n : bn
Time and space complexity orders
Shortest
solution
Time Space guaranteed
Breadth-first bd bd yes
Depth-first bdmax dmax no
Iterative deepening bd d yes
That’s All
Thank You
28
