Problem
Solving in AI
Introduction to Problem
Solving
• Problem Solving means the analysis of how
computers can be made to find solutions in
specific domains.
• Problem solving techniques can been applied to
describe the situations that can be encountered
• Various “States” are used to solve a problem
• Collection of such states for a given problem is
called as “Problem Space”
Various Types of States
Initial State: Goal or Solution State: Failure or Impossible State:
State from where the problem States that are considered as These are the states which are
solving starts the solution to the problem considered as a failure for
Can be one or multiple problem
Problem Solving
• Defined as a way in which an agent finds a sequence of actions
that achieves its goals
• Agent has to execute set of actions in sequence to achieve a goal
• Problem formulation requires abstracting away real world details
to define a state space
• The step of abstraction is performed by an agent called “Problem
Solving Agent”
Problem Solving Agent
Intelligent Agents acts in such a Problem solving agent is
way that they goes through
sequence of states to maximizes the form of Goal Based
the performance measures. Agents
Structure of Problem Solving
Agent
• Goal State
• A state that describes the objective that the
agent is trying to achieve is called as the “Goal
State”
• Action
• When there is a transition between the states
an “Action” is said to be performed.
• Thus, agent has to find that which action will take
it to the goal state and before that it has to
decide that which actions and stated to consider
Steps in Problem Solving by Problem
Solving Agent
Goal Formulation: Problem Formulation: Choosing the Best Sequence:
This is the first step in Process of deciding what Agent in a particular state can take many
possible action to move to next state
problem solving on the actions and states to be
It has to choose the move that help it to
basis of current situation considered for achieving a move closest to the goal
and agent’s performance goal Next action chosen is called “Best Action”
measures Sequence of such a best actions is called a
“Best Sequence”
Problem Formulation
Initial State: Successor Function: Goal Test: Path Cost:
State with which the Function that gives the Determines whether Function that assigns
agent starts in. description of all the given state is a Goal numeric value to each
possible actions State or not. path
available to the agent.
Analyse the problem to get
Step 1:
the starting and goal state
Find the data about the
Step 2:
starting and goal state
Algorith Step 3:
Find the production rules to
move from initial to goal state
m of Step 4:
Select some rules that can be
applied to data
Problem
Apply those rules to initial
Step 5: state and proceed to get the
next state
Solving
Determine some new generated
Step 6:
states after applying the rules
Achieve some information
Step 7:
about the goal state
Step 8: Exit
AI Technique Procedural Techniques
It implements symbolic reasoning It implements numeric processing
processing
Implements heuristics search Implements algorithmic search
Conventional techniques techniques
Problem Solution steps are not explicit Solution steps are explicit
VS
AI Problems Knowledge is imprecise Knowledge is precise
It requires frequent modifications Modifications are rare
It works on or implements inferential It works on or implements repetition
mechanism mechanism
It has a large knowledge base It has a large database
Results are usually satisfactory Results are usually optimal