PROBLEM SOLVING IN AI
• The Process of finding a sequence of actions that transforms an initial state into a
goal state.
• An intelligent agent searches for a solution by exploring different possible
states.
START STATE INTERMEDIATE STATES GOAL STATE
PROBLEM FORMULATION
The process of converting a real-world problem into a well-defined computational problem
that an AI system can solve.
It is an important step in AI because it:
• Defines the objective of the problem.
• Identifies the constraints.
• Specifies the possible actions the AI agent can perform.
A well-formulated problem enables AI to apply search algorithms, optimization techniques,
and decision-making models efficiently.
Example: In AI-based route planning, the AI defines the starting location, destination, available
routes, and optimization criteria (shortest distance or least traffic) to determine the best route.
PROBLEM FORMULATION
Problem formulation consists of five key components:
1. Initial State
The starting point from which the AI system begins solving the problem.
Example:
The Tic-Tac-Toe board is empty before the game starts.
2. Action Set (or Successor Function)
Defines all possible actions that the AI agent can perform from the current state.
Example:
The AI can place its X in any one of the 9 empty cells on the board.
PROBLEM FORMULATION
3. Transition Model
- Describes how the current state changes after performing an action.
- Tells what happens after an action is performed
Example:
If the AI places X in the center cell, the board changes to a new state.
4. Goal State
The desired final state that the AI aims to achieve.
Example:
The AI wins by placing three X's (or O's) in a row, column, or diagonal.
5. Path Cost Function
Assigns a cost to each path and helps the AI choose the best solution.
Example:
The AI chooses the sequence of moves that leads to winning in the fewest moves.
TIC TAC TOE GAME
STEPS IN PROBLEM FORMULATION
Example: Tic-Tac-Toe Game
Step 1: Define the Problem Statement
Problem:
Develop an AI agent that plays Tic-Tac-Toe and wins the game whenever possible.
Step 2: Establish the Initial State and Goal State
Initial State:
The Tic-Tac-Toe board is empty.
Goal State:
The AI forms three identical symbols (X or O) in a row, column, or diagonal.
STEPS IN PROBLEM FORMULATION
Step 3: Determine Available Actions and Transition Model
Available Actions:
Place X (or O) in any empty cell.
Transition Model:
After placing the symbol in an empty cell, the board changes to a new state.
Step 4: Define Constraints and Path Cost
Constraints(Rules):
A symbol can be placed only in an empty cell.
Players take alternate turns.
Once a symbol is placed, it cannot be changed.
Path Cost:
The AI selects the sequence of moves that leads to winning in the minimum number of moves.
STATE SPACE SEARCH
• A State Space is the set of all possible states a system can be during the
problem solving process. [Initial State, Goal State, Intermediate State]
• Steps to solve a Problem:
- Define the Problem Precisely
- Analyse the Problem – Identify the possible actions & rules
- Identify all Possible Solutions
- Choose the Best Solution (min cost)
• Represented using Tuples:
{S, A, Action(S), Result(S,a), Cost(S,a)}
STATE SPACE SEARCH
{S, A, Action(S), Result(S,a), Cost(S,a)}
S → Set of all possible states (Start State, Intermediate States and Goal States)
A → Set of all possible actions
Action(S) → Action chosen in the current state
Result(S, a) → New state obtained after performing action a in state S
Cost(S, a) → Cost of performing action a to reach the new state
8 – PUZZLE PROBLEM
The 8-Puzzle Problem is a classic AI problem.
It consists of:
• A 3×3 grid
• 8 numbered tiles (1 to 8)
• 1 empty space, also called the blank tile Start State Goal State
The tiles are placed randomly on the board, and the blank space allows
tiles to move.
Objective of the Problem
The goal is to transform a given initial configuration into a predefined goal
configuration by sliding tiles into the blank space while following specific rules.
8 – PUZZLE PROBLEM
8 – PUZZLE PROBLEM
Initial State
The initial state is the starting arrangement of tiles provided as input to the AI system. This
configuration can be random, but not all configurations are solvable.
Goal State
The goal state is the desired final arrangement. AI systems compare each explored state against
the goal state to determine success.
The problem is considered solved only when the current state exactly matches the goal
state.
Rules and Constraints of the 8-Puzzle
• Only one tile can move at a time
• A tile can move only into the adjacent blank space
• Allowed movements: Up, Down, Left, Right
• Diagonal moves are not allowed
These rules define the legal actions available at each state.
8 – PUZZLE PROBLEM
Path Cost
Measures how expensive it is to reach a particular state from the initial state.
In the 8-puzzle problem:
Each move usually has a uniform cost of 1
Total path cost = number of moves taken
Example:
If the solution takes 12 moves, the path cost is:
Cost = 12
• Path cost is especially important for:
- Finding optimal solutions
- Comparing different solution paths
- Algorithms like Uniform Cost Search and A* search
STATE SPACE REPRESENTATION : 8 – PUZZLE
PROBLEM
Initial State
1 2 3
4 5
6 7 8
:
• S → Set of All Possible States
All the possible board arrangements (Start State, Intermediate States, and Goal State).
• A → Set of All Possible Actions
All possible moves that can be performed on the blank space.
Example: Move Up , Move Down , Move Left , Move Right
These are the possible actions available.
STATE SPACE REPRESENTATION : 8 – PUZZLE
PROBLEM
• Action(S) → Action Chosen
The specific action selected from the available actions in the current state.
For example, if the blank tile moves to the right, the chosen
So,
Action(S)
:
= Move Right
STATE SPACE REPRESENTATION : 8 – PUZZLE
PROBLEM
• Result(S,a) → Resultant State
The new state obtained after performing that action.
Example:
Before Action Action = Move Right
After Action
:
1 2 3
4 5
6 7 8
This new board is the Result(S,a)
STATE SPACE REPRESENTATION : 8 – PUZZLE
PROBLEM
• Cost(S,a) → Cost of the Action
The cost required to move from one state to another.
Example:
Moving the blank space Right takes 1 move.
So, Cost(S,a) = 1
: If it takes 8 moves to reach the goal, then
Total Cost = 8
VACUUM WORLD
(VACUUM CLEANER) AS
A PROBLEM SOLVING
AGENT IN AI
VACUUM CLEANER
A B A B
• No of States: 8
• Initial State: Any
• No of actions: 3
Left, Right, Suck
• Goal: Clean up all dirt
:
Goal states: {state 4, state 8}
• Path Cost:
Each step costs 1
VACUUM CLEANER
For the Vacuum World, a state depends on:
• The vacuum cleaner's location (A or B) = 2 States possible
• Whether Room A is Clean/Dirty = 2 states possible
• Whether Room B is Clean/Dirty = 2 states possible
There are 8 possible states (2x2x2 = 8)
:
Formula:
Number of States = Number of Agent Locations × 2^(Number of
Locations) = n x 2^n
= 2 × 2²
= 8 states
VACUUM CLEANER
Initial State
• The Initial State is where the agent starts.
• It can be any one of the eight states.
• Example:
Vacuum at A
Room A = Dirty
Room B = Dirty
:
Action Set
The Vacuum World has 3 actions:
• Left → Move to Room A
• Right → Move to Room B
• Suck → Clean the current room if it is dirty
VACUUM CLEANER
TRANSITION MODEL
• The Transition Model tells us what happens after performing an action.
• It describes how the system moves from one state to another.
:
VACUUM CLEANER
TRANSITION MODEL
Example: Another example:
• Current State • Current State
Vacuum → A Vacuum → A
Room A → Dirty Action = Right
Room B → Dirty ↓
Action = Suck • Next State
: ↓ Vacuum moves to B.
• Next State
Vacuum → A
Room A → Clean
Room B → Dirty
VACUUM CLEANER
GOAL STATE
Goal = Both rooms A and B are clean regardless of location of the
Vacuum Cleaner Agent.
So,
✔ Room A = Clean
✔: Room B = Clean
VACUUM CLEANER
PATH COST
• Path Cost is the total number of actions taken to reach the goal.
• Each action has a cost of 1.
Example: Solution:
Suck
Initial State ↓
Vacuum
: at A Right
Room A = Dirty ↓
Room B = Dirty Suck
Total actions = 3
Path Cost = 3
8-QUEENS PROBLEM
• The goal of 8-queens problem is to place 8 queens on the 8x8 chessboard such that
no queen attacks any other. (A queen attacks any piece in the same row, column or
diagonal).
• States: Any arrangement of 0 to 8 queens on board is a
state.
• Initial state: No queen on the board.
• Action: Add a queen to any empty square.
• Transition model: It returns the resulting state as per the
given state and actions.
(New Board Configuration is generated everytime we place
a Queen. New configuration = Next State)
• Goal State: 8 queens are on the board, none attacked.
• Path cost: The path cost is of no interest because only the
final state counts.
8-QUEENS PROBLEM