AI Problem Characteristics

To choose the most appropriate method for solving a problem, it is necessary to analyze
the problem along several key dimensions.

1) Is the problem decomposable?

 A problem is decomposable if it can be divided into smaller sub-problems.

 Each sub-problem can be solved separately.

Example:

 Mathematical Integration

 Towers of Hanoi

 Matrix Multiplication

2) Can solution steps be ignored or undone?

Problems are classified into three types:

a) Ignorable Problems

 Solution steps can be ignored.

 No need to backtrack.

Example: Theorem Proving

b) Recoverable Problems

 Solution steps can be undone.

 Backtracking is possible.

Example: 8-Puzzle

c) Irrecoverable Problems

 Solution steps cannot be undone.

 Decisions are final.

Example: Chess

3) Is the universe predictable?

 The result of every action is known.

 Entire plan can be generated in advance.

Example: 8-Puzzle

b) Uncertain-Outcome Problems

 The result of actions cannot be predicted exactly.

 Requires probability or plan revision.

Example: Bridge Game, Robot control

4) Is a good solution absolute or relative?

a) Any Path Problems

 Any solution path is acceptable.

Example: Logical reasoning problems

b) Best Path Problems

 The optimal solution must be found.

Example: Travelling Salesman Problem

5) Is the solution a state or a path?

a) State Solution

 Only the final state matters.

Example: Natural Language Understanding

b) Path Solution

 Sequence of steps to reach goal matters.

Example: Water Jug Problem, 8-Puzzle

6) What is the role of knowledge?

 Some problems require little knowledge.

 Some require extensive domain knowledge.

 Chess – knowledge constrains search

 Newspaper political analysis – large knowledge required

7) Does the task require human interaction?

a) Solitary Problem

 No intermediate communication required.

b) Conversational Problem

 Requires interaction between human and computer.

Example: Theorem proving with human assistance

This format is suitable for a 10–12 mark exam answer.

If you want, I can also give a shorter 5-mark version.

A Production System is a basic building block which describes an AI problem and also
describes the method of searching for the goal.

It provides the desired goal by applying a set of rules to move from an initial state to a
goal state.

Components of a Production System

1. Set of Rules

o Each rule has:

 Left side (condition or pattern)

 Right side (action to be performed)

Format:

IF (condition) THEN (action)

2. Knowledge Base

o Contains information about the problem.

o Some information is permanent, some is specific to the current problem.

3. Control Strategy

o Determines the order in which rules are applied.

o Resolves conflicts when multiple rules match.

4. Rule Applier

o Applies selected rules to change the state.

Categories (Characteristics) of Production Systems

Production systems are classified based on two properties:

 Monotonic vs Non-Monotonic

 Partially Commutative vs Non-Partially Commutative

1) Monotonic Production System

 No rule application blocks future rule applications.

Example: Theorem Proving

2) Non-Monotonic Production System

 Application of a rule may prevent the later application of another rule.

 Changes may restrict future moves.

Example: Robot Navigation

3) Partially Commutative Production System

 If a sequence of rules transforms state X to Y,

 Any allowable permutation of those rules also transforms X to Y.

 Order of rule application is not critical.

Example: 8-Puzzle, Blocks World

4) Non-Partially Commutative Production System

 Order of rule application matters.

 Changing the order may produce di erent results.

Example: Chemical Synthesis

5) Commutative Production System

 A system that is both:

o Monotonic

o Partially Commutative

Four Categories of Production Systems

Partially Commutative Theorem Proving Robot Navigation

Not Partially Commutative Chemical Synthesis Bridge

Conclusion

Production systems provide a structured way to represent and solve AI problems using
rules, knowledge base, and control strategy. Their classification helps in selecting
suitable implementation methods.

This answer is suitable for 10–15 marks in exams.

If needed, I can also give a short 5-mark answer.

Water-Jug Problem

Problem

is “You are given two jugs, a 4-litre one and a 3-litre one. One neither has any

measuring markers on it. There is a pump that can be used to fill the jugs with water.
How can

you get exactly 2 litres of water into 4-litre jug?”

The state space for the problem can be described as a set of states, where each state
represents

the number of gallons in each state. The game start with the initial state described as a
set of

ordered pairs of integers:

x = 0, 1, 2, 3, or 4

y = 0, 1, 2, 3

• Start state: (0, 0) i.e., 4-litre and 3-litre jugs is empty initially.

• Goal state: (2, n) for any n that is 4-litre jug has 2 litres of water and 3-litre jug has any

value from 0-3 since it is not specified.

• Attempting to end up in a goal state. explain this in

Water–Jug Problem – Explanation

Problem Statement

You are given:

 One 4-litre jug

 One 3-litre jug

 No measuring marks on either jug

 A pump to fill water

Goal:
Get exactly 2 litres of water in the 4-litre jug.

Understanding the Solution

To solve this problem in AI, we represent it using a State Space Approach.

1) What is a State?
A state represents the amount of water in both jugs at any time.

We represent it as:

(𝑥, 𝑦)

Where:

 x = amount of water in 4-litre jug

 y = amount of water in 3-litre jug

Possible values:

 x = 0, 1, 2, 3, 4

 y = 0, 1, 2, 3

So each combination like (0,0), (4,3), (2,1) etc. is a state.

2) Start State

Initially both jugs are empty.

(0, 0)

This means:

 4-litre jug has 0 litres

 3-litre jug has 0 litres

3) Goal State

We want exactly 2 litres in the 4-litre jug.

So goal state is:

(2, 𝑛)

Where:

 4-litre jug must contain 2 litres

 3-litre jug can contain anything (0 to 3 litres)

Examples of goal states:

 (2,1)

 (2,2)

 (2,3)

4) How Do We Reach the Goal? (Intuitive Steps)

We use operations like:

 Fill a jug completely

 Empty a jug

 Pour water from one jug to another

One possible solution path:

1. Fill 3-litre jug → (0,3)

2. Pour into 4-litre jug → (3,0)

3. Fill 3-litre jug again → (3,3)

4. Pour into 4-litre jug until full → (4,2)

5. Empty 4-litre jug → (0,2)

6. Pour 2 litres from 3-litre jug into 4-litre jug → (2,0)

Now we have:

(2, 0)

Goal achieved

Why This is Important in AI?

 The problem is solved using State Space Search

 Each water configuration is a state

 We search from initial state to goal state

 This is an example of a path-finding problem

 It can be solved using:

o Depth First Search (DFS)

In Simple Words

Think of it like exploring all possible water combinations until you find the one where the
4-litre jug contains exactly 2 litres.

If you want, I can also draw the state space tree explanation for better understanding.