Formulating Problems in Artificial Intelligence

Problem Formulation is one of the most fundamental concepts in Artificial Intelligence. Before an AI system can solve a problem, it must first convert the real-world situation into a formal representation that a computer can understand and search.

In simple words:

Problem formulation is the process of defining a problem in terms of states, actions, goals, and costs so that an AI agent can search for a solution.

This topic comes immediately before “Searching for Solutions” in your syllabus because an AI system cannot search effectively until the problem has been properly formulated.

1. Why Problem Formulation is Important

Suppose we tell a computer:

“Go from Ludhiana to Delhi using the best route.”

A computer cannot directly solve this statement.

We need to define:

Where are we starting?
Where do we want to go?
What actions are possible?
What locations can we visit?
What is the cost?
What does “best” mean?

After formulation, the problem might become:

Initial State → Ludhiana

Actions → Travel to connected cities

Goal State → Delhi

Cost → Distance / Time / Fuel

Solution → Sequence of cities from Ludhiana to Delhi

Now a search algorithm can solve it.

2. Basic Idea

The complete process is:

Real-World Problem
        ↓
Problem Formulation
        ↓
State Representation
        ↓
Actions / Operators
        ↓
Goal Definition
        ↓
Cost Definition
        ↓
Search
        ↓
Solution

Therefore:

Problem Formulation → Search → Solution

3. Definition

Exam Definition

Problem formulation in Artificial Intelligence is the process of representing a problem as a set of states, actions, initial state, goal state, transition model, and path cost so that an AI agent can apply search techniques to find a solution.

4. Components of a Problem Formulation

A classical AI problem can generally be defined using the following components:

Initial State
State Space
Actions / Operators
Transition Model
Goal Test
Path Cost

Let’s understand each one.

5. Initial State

The initial state describes the situation in which the problem begins.

For example, in the Water Jug Problem:

4L Jug = 0
3L Jug = 0

So:\[ Initial\ State=(0,0) \]

In the 8-Puzzle:

1 2 3
4 _ 6
7 5 8

is an initial state.

In route planning:

Initial State = Ludhiana

6. State

A state describes a particular situation at any point during problem solving.

For example, in Water Jug:

(3,2)

means:

4L Jug → 3 litres
3L Jug → 2 litres

In the 8-Puzzle:

1 2 3
4 5 6
7 _ 8

is a state.

In route planning:

Current location = Chandigarh

is a state.

7. State Space

The state space is the collection of all possible states that can be reached from the initial state by applying valid actions.

For example:

Initial State
     ↓
 ┌───┼───┐
 ↓   ↓   ↓
 S1  S2  S3
     ↓
   ┌─┼─┐
   ↓ ↓ ↓
  S4 S5 S6

All these states together form the state space.

Definition

State space is the set of all possible states and configurations that can be reached while solving a problem.

8. Actions / Operators

An action is an operation that changes the current state into another state.

For example, in the Water Jug Problem:

Fill Jug
Empty Jug
Pour Jug A → Jug B
Pour Jug B → Jug A

In the 8-Puzzle:

Move Blank Up
Move Blank Down
Move Blank Left
Move Blank Right

In route planning:

Travel from City A → City B

Actions are sometimes called:

Operators
Moves
Actions
Successor functions

9. Transition Model

The transition model describes what happens when an action is applied to a state.

In simple words:

It tells the AI what new state will result from performing a particular action.

For example:

Current State:
(0,3)

Action:

Pour 3L Jug → 4L Jug

New state:

(3,0)

Therefore:

Current State
      +
    Action
      ↓
  New State

10. Goal State

The goal state is the desired final state.

For example:

Water Jug

Goal:

Exactly 2 litres

8-Puzzle

Goal:

1 2 3
4 5 6
7 8 _

8-Queens

Goal:

8 queens placed
+
No two queens attack each other

Route Planning

Goal:

Reach Delhi

11. Goal Test

The goal test checks whether the current state satisfies the desired objective.

For example:

Current State = (2,0)
Goal = 2 litres

Therefore:

Goal Test → TRUE

In the 8-Puzzle:

Current:
1 2 3
4 5 6
7 8 _

Goal:
1 2 3
4 5 6
7 8 _

Therefore:

Goal Test → TRUE

12. Path Cost

A problem may have many possible solutions.

The AI may need to select the least expensive solution.

The cost can be:

Number of moves
Distance
Time
Fuel
Money
Computational cost
Risk

For example, in route planning:

Route A → 300 km
Route B → 250 km
Route C → 400 km

If the objective is minimum distance:

Best route = Route B

The total cost of a sequence of actions is called the path cost.\[ Path\ Cost = \sum Cost(Action_i) \]

13. Formal Representation

A classical AI problem can be represented as:\[ P=(S,A,Result,s_0,G,C) \]

where:

\(S\) = Set of states
\(A\) = Set of actions
\(Result(s,a)\) = Result of applying action \(a\) to state \(s\)
\(s_0\) = Initial state
\(G\) = Goal test
\(C\) = Path cost

Some textbooks use slightly different notation, but the underlying idea is the same.

14. Example — Water Jug Problem

Let’s formulate the Water Jug problem.

Problem

We have a 4-litre jug and a 3-litre jug. Measure exactly 2 litres.

1. Initial State

\[ (0,0) \]

2. States

\[ (x,y) \]

where:\[ 0\leq x\leq4 \]

and\[ 0\leq y\leq3 \]

3. Actions

Fill 4L jug
Fill 3L jug
Empty 4L jug
Empty 3L jug
Pour 4L → 3L
Pour 3L → 4L

4. Goal

x = 2 OR y = 2

5. Cost

Usually:\[ Cost(each\ action)=1 \]

Therefore, the AI can search the state space.

15. Example — 8-Puzzle

Initial State

1 2 3
4 _ 6
7 5 8

Goal State

1 2 3
4 5 6
7 8 _

Actions

Move blank up
Move blank down
Move blank left
Move blank right

Transition

Move blank and exchange it with the adjacent tile.

Goal Test

Compare current state with the goal state.

Cost

Usually:\[ 1\text{ per move} \]

Now the problem is ready for BFS, DFS, A*, etc.

16. Example — 8-Queens

Initial State

Empty 8 × 8 board

State

Partial placement of queens.

Actions

Place a queen in a safe position.

Constraints

No two queens can share:

Row
Column
Diagonal

Goal

8 queens placed
without conflicts

This formulation allows the use of:

Backtracking
DFS
CSP
Hill Climbing
Genetic Algorithms

17. Example — Route Finding

Suppose an AI must find a route from:

Ludhiana → Delhi

Initial State

Ludhiana

States

Ludhiana
Chandigarh
Ambala
Panipat
Karnal
Delhi
...

Actions

Travel between connected cities.

Goal

Delhi

Cost

Could be:

Distance

or:

Travel Time

or:

Fuel Cost

The formulation changes depending on the objective.

18. Problem Formulation and Search

These two concepts are closely related.

Problem Formulation

Defines:

What is the problem?

Search

Determines:

How can we find the solution?

For example:

Problem:
Reach Delhi from Ludhiana

       ↓

Formulation:
Initial = Ludhiana
Goal = Delhi
Actions = Travel
Cost = Distance

       ↓

Search:
BFS / DFS / Uniform Cost / A*

       ↓

Solution:
Ludhiana → Chandigarh → Ambala → Delhi

19. Why Good Problem Formulation Matters

A problem can be formulated in different ways.

A good formulation reduces unnecessary complexity.

For example, suppose we are solving 8-Queens.

Instead of allowing queens anywhere on the board, we can impose:

Place exactly one queen in each row.

Now we only need to decide the column.

Instead of:\[ 64^8 \]

possible arbitrary placements, we can represent the problem more efficiently.

If we require one queen per row, the raw assignments are:\[ 8^8 \]

And if we also require different columns:\[ 8! \]

This illustrates how a good representation can dramatically reduce the search space.

20. State Abstraction

Abstraction means ignoring unnecessary details.

Suppose a route-planning AI needs to find the shortest route.

It may represent a city as:

City = Chandigarh

It doesn’t necessarily need to represent:

Number of buildings
Weather at every building
Traffic light at every intersection
Every individual vehicle

unless those details affect the problem.

Therefore:

A good problem formulation includes relevant information and ignores irrelevant information.

21. Choosing the Right State Representation

State representation is extremely important.

For example:

Water Jug

Use:\[ (x,y) \]

8-Puzzle

Use:

Board configuration

8-Queens

Use:

[Column1, Column2, ..., Column8]

Route Finding

Use:

Current city

The representation should make the problem:

Easy to understand
Easy to manipulate
Efficient to search

22. Problem Formulation vs Problem Solving

These are different concepts.

Problem Formulation	Problem Solving
Defines the problem	Finds solution
Defines states	Explores states
Defines actions	Applies actions
Defines goal	Tests goal
Defines costs	Minimizes/compares costs
Happens before search	Uses search algorithms

So:

Formulate First
      ↓
Search Second
      ↓
Solution

23. Types of Problems in AI

After formulation, AI problems can have different characteristics.

1. Single-State Problems

The agent knows its current state accurately.

Example:

8-Puzzle

2. Multiple-State Problems

The agent may not know exactly which state it is in.

3. Contingency Problems

The result of an action may depend on uncertain conditions.

4. Exploration Problems

The agent does not initially know the environment and must learn about it.

These are more advanced than the classical toy problems in your syllabus.

24. Deterministic vs Uncertain Problems

Deterministic

The result of an action is predictable.

Example:

8-Puzzle:
Move blank right
      ↓
Known new state

Uncertain

The result may vary.

For example:

Robot moves forward
      ↓
Could encounter obstacle

Therefore, the formulation must include uncertainty or possible outcomes.

25. Good Problem Formulation

A good AI problem formulation should:

1. Be precise

The initial and goal states should be clearly defined.

2. Be complete

All important actions should be included.

3. Avoid unnecessary details

Irrelevant information should be removed.

4. Have manageable state space

The representation should reduce unnecessary states.

5. Define cost appropriately

The cost should reflect what “best solution” means.

26. Example: Travelling Problem

Suppose:

Find the cheapest route from City A to City D.

Poor formulation

Travel from A to D.

This is too vague.

Better formulation

Initial State = City A

States = All reachable cities

Actions = Travel along available roads

Transition = Move to connected city

Goal = City D

Cost = Travel cost

Now a search algorithm can solve it.

27. General Problem Formulation Diagram

This is an important diagram for your MCA students:

                  REAL-WORLD PROBLEM
                         │
                         ↓
                 PROBLEM FORMULATION
                         │
        ┌────────────────┼────────────────┐
        ↓                ↓                ↓
   Initial State      Actions          Goal State
        │                │                │
        └────────────────┼────────────────┘
                         ↓
                  Transition Model
                         │
                         ↓
                    State Space
                         │
                         ↓
                    Path Cost
                         │
                         ↓
                  SEARCH ALGORITHM
                         │
                         ↓
                      SOLUTION

28. Relationship with AI Agent

In classical AI, an agent perceives the environment and selects actions to achieve a goal.

Environment
     ↓
  Current State
     ↓
Problem Formulation
     ↓
Search
     ↓
Action
     ↓
Environment

For example, a navigation agent:

Current Location
       ↓
Goal = Destination
       ↓
Possible Routes
       ↓
Search
       ↓
Best Route
       ↓
Travel

29. Important Terms for Examination

Students should remember these terms:

I-S-A-T-G-C

I → Initial State
S → State Space
A → Actions
T → Transition Model
G → Goal Test
C → Cost

This is an easy way to remember the major components.

30. Exam-Oriented Answer

Question: What is Problem Formulation in AI?

Problem formulation is the process of converting a real-world problem into a formal representation that can be solved by an AI system. It defines the initial state, possible states, actions or operators, transition model, goal test, and path cost. Once a problem has been formulated, an AI search algorithm such as BFS, DFS, Uniform Cost Search, Greedy Best-First Search or A can be applied to find a solution.*

Components:

1. Initial State
2. State Space
3. Actions / Operators
4. Transition Model
5. Goal State / Goal Test
6. Path Cost

Example:

For the 8-Puzzle:

Initial State
      ↓
1 2 3
4 _ 6
7 5 8

Actions
↓
Move blank

State Space
↓
All reachable board configurations

Goal
↓
1 2 3
4 5 6
7 8 _

Cost
↓
Number of moves

Final takeaway

Problem formulation tells the AI exactly what needs to be solved, what states are possible, what actions can be performed, what constitutes success, and what cost should be minimized. It is the foundation on which AI search and problem-solving are built.

Flow to remember:
Real Problem → Formulation → States + Actions + Goal + Cost → Search → Solution.

Formulating problems

Formulating Problems in Artificial Intelligence

1. Why Problem Formulation is Important

2. Basic Idea

Problem Formulation → Search → Solution

3. Definition

Exam Definition

4. Components of a Problem Formulation

5. Initial State

6. State

7. State Space

Definition

8. Actions / Operators

9. Transition Model

10. Goal State

Water Jug

8-Puzzle

8-Queens

Route Planning

11. Goal Test

12. Path Cost

13. Formal Representation

14. Example — Water Jug Problem

Problem

1. Initial State

2. States

3. Actions

4. Goal

5. Cost

15. Example — 8-Puzzle

Initial State

Goal State

Actions

Transition

Goal Test

Cost

16. Example — 8-Queens

Initial State

State

Actions

Constraints

Goal

17. Example — Route Finding

Initial State

States

Actions

Goal

Cost

18. Problem Formulation and Search

Problem Formulation

Search

19. Why Good Problem Formulation Matters

20. State Abstraction

21. Choosing the Right State Representation

Water Jug

8-Puzzle

8-Queens

Route Finding

22. Problem Formulation vs Problem Solving

23. Types of Problems in AI

1. Single-State Problems

2. Multiple-State Problems

3. Contingency Problems

4. Exploration Problems

24. Deterministic vs Uncertain Problems

Deterministic

Uncertain

25. Good Problem Formulation

1. Be precise

2. Be complete

3. Avoid unnecessary details

4. Have manageable state space

5. Define cost appropriately

26. Example: Travelling Problem

Poor formulation

Better formulation

27. General Problem Formulation Diagram

28. Relationship with AI Agent

29. Important Terms for Examination

I-S-A-T-G-C