- computational components of data,
- operations and
- control
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
- consisting of appropriate information for the particular task.
- information in these databases may be structured using knowledge representation schemes.
- 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.
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.
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.