Artifitial Intelligence: Chapter 3 Problem Solving - Introduction to Production Systems

In AI programs there is a clean separation of -

• computational components of data,
• operations and
• control

Search forms the core of many intelligent processes. So it is useful to structure AI programs in a way that facilitates describing the search process.

Production System
A formalism for structuring AI programs which facilitates search process. It consists of

• Initial or start state of the problem
• Final or goal state of the problem

It consists of one or more databases

• consisting of appropriate information for the particular task.
• information in these databases may be structured using knowledge representation schemes.

Set of production rules

• each consisting of a left side that determines the applicability of the rule and
• a right side that describes the action to be performed if the rule is applied.
• These rules operate on the databases.
• Application of rules change the database.

A control strategy is one that specifies the order in which the rules will be applied when several rules match at once.


In addition to its usefulness as a way to describe search, the production model has other advantages as a formalism in AI.

• It is a good way to model the strong state driven nature of intelligent action. As new inputs enter the database, the behavior of the system changes.s
• New rules can easily be added to account for new situations without disturbing the rest of the system, which is quite important in real-time environment.

Example: Water Jug Problem
Given two jugs, a 4-gallon and 3-gallon having no measuring markers on them. There is a pump that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into 4-gallon jug.
Solution: State space for this problem can be described as the set of ordered pairs of integers (X, Y) such that X represents the number of gallons of water in 4-gallon jug and Y for 3-gallon jug.
1.Start state is (0,0)
2.Goal state is (2, N) for any value of N.
Following are the production rules for this problem.
Production Rules:
R1:(X, Y | X < 4)                        ==> (4, Y){Fill 4-gallon jug}
R2:(X, Y | Y < 3)                        ==> (X, 3){Fill 3-gallon jug}
R3:(X, Y | X > 0)                        ==> (0, Y){Empty 4-gallon jug}
R4:(X, Y | Y > 0)                        ==> (X, 0){Empty 3-gallon jug}
R5:(X, Y | X+Y >= 4 ΛY > 0)    ==> (4, Y –(4 –X)){Pour water from 3-gallon jug into 4-gallon jug until 4-gallon jug is full}
R6:(X, Y | X+Y >= 3 ΛX > 0)    ==> (X –(3 –Y), 3){Pour water from 4-gallon jug into 3-gallon jug until 3-gallon jug is full}
R7:(X, Y | X+Y <= 4 ΛY > 0)    ==> (X+Y, 0){Pour all water from 3-gallon jug into 4-gallon jug }
R8:(X, Y | X+Y <= 3 ΛX > 0)    ==> (0, X+Y){Pour all water from 4-gallon jug into 3-gallon jug }

Superficial Rules: {May not be used in this problem}
R9:(X, Y | X > 0) ==> (X –D, Y){Pour some water D out from 4-gallon jug}
R10:(X, Y | Y > 0) ==> (X, Y -D){Pour some water D out from 3-gallon jug}

Steps involved in solving the water jug problem

Number of Steps	Rules applied	4-g jug 3-g jug
1	Initial State	0 0
2	R2 {Fill 3-g jug}	0 3
3	R7 {Pour all water from 3 to 4-g jug }	3 0
4	R2 {Fill 3-g jug}	3 3
5	R5 {Pour from 3 to 4-g jug until it is full}	4 2
6	R3 {Empty 4-gallon jug}	0 2
7	R7 {Pour all water from 3 to 4-g jug}	2 0 (Goal State)

Points to be noted

• There are initial and final description of the problem.
• There are more than one ways of solving the problem.
• One would exercise a choice between various solution paths based on some criteria of goodness or on some heuristic function.
• There are set of rules that describe the actions called production rules.
• Left side of the rules is current state and right side describes new state that results from applying the rule.