Production Systems for Modeling Human Behaviour | Artificial Intelligence

In this article we will discuss about:- 1. Origin and Role of Production Systems 2. Architecture of Production Systems 3. Algorithm of Problem Solving 4. Issues.

Origin and Role of Production Systems:

The origin of the production systems dates back to 1943 when they were proposed by Emil Post for the first time. Since then they have undergone various modifications, but the basic idea has remained the same.

The concept re-emerged in the context of natural language processing in 1957 by Chomsky. Production systems were proposed for modeling human solving behaviour by Newell and Simmons in 1972 and since then, Alan Newell has been one of the chief proponents of the production systems as a useful tool for problem solving in AI. Production systems are frequently referred to as inferential systems, Rule-based systems or simply productions.

Role of Production Systems:

1. A powerful knowledge representation scheme production systems represent not only knowledge but also action. 

2. The bridge connecting AI research to expert systems. Production systems provide a language in which the representation of expert knowledge (in a domain) is very natural.

3. They provide a heuristic model for human behaviour.

4. They are good way to model the strong data-driven nature of intelligent action. As new inputs enter the data base the behaviour of the system changes.

5. New rules can be easily added to account for new situations without disturbing the rest of the system. This is important since no AI program is ever complete. Although sometimes confusion arises from interaction among rules it is often less severe than the corresponding complications of modifying the straight-line code.

Architecture of Production Systems:

A typical architecture of a production system consists of three main components:

1. Rules base (Knowledge base)

2. Global data base

3. Control structure

Transforming a problem statement into these components of the production system is often called problem representation. There are several ways to represent a problem; selecting a good representation is one of important arts involved in applying AI techniques to practical problems. So, let us discuss each data structure of production system.

1. Rule Set:

The knowledge representation in production systems is decoded in a declarative form which comprises a set of rules of the form:

Situation → action

The situation→ action rules are often called production-rules or IF-THEN rules. A system which uses this form of knowledge is called a production system.

The underlying idea which led to this form of representation is derived from the observation that human experts think in IF-THEN patterns while solving a problem.

For example, if your car does not start, your reasoning process might be of the following form:

First you will check the starter. If the starter does not work then the battery might be flat. But there may be other reasons for the starter of the car not working. Starter might be broken, while the battery is in order. To find out what’s wrong you have to check for other symptoms (facts, situations or beliefs) using the logical operation AND.

This is explained below:

IF the starter does not work

AND the head lights are dim

AND the ignition and oil pressure light don’t come on

THEN the battery might be flat

It may be noted that we cannot be absolutely sure that our conclusion is right, because the battery connections might be poor.

So you could state the conclusion in the following form:

THEN the battery might be flat OR the battery connection poor. It would also be possible to use a certainty factor and say: THEN there is a strong evidence 0.9 that the battery is flat. The factor can range from 0.0 (certainly wrong) to 1.0 (certainly right).

This kind of reasoning is called inexact reasoning. The above example has illustrated that human reasoning often consists of IF-THEN rules (with certainly factor attached).

The rules have the following general form:

The antecedent part is also called condition part or left hand side (LHS).

The consequence part of a production rule is also called action part or right hand side (RHS).

When LHS matches, the designated condition in the production rule action will be taken. The application of the rule changes the data base.

This definition of production rules is quite general.

It also covers a family of general production system interpreters, including:

(a) Basic production system languages such as OPS5.

(b) More complex systems called expert system shells, which provide complete environments for the construction of knowledge based expert systems.

(c) General problem solving architectures like SOAR, a system based on a specific set of cognitively motivated hypothesis about the nature of problem solving.

All of these systems provide the overall architecture of a production system and allow the programmer to write rules which define particular problems to be solved.

2. Global Database:

The global database is the central data structure used by the production system. Depending upon the application this database (not to be confused with database of DBMS) may be as simple as a small matrix of numbers or as complex as a large relational indexed file structure.

The global database can be accessed by all the rules (no part of the database is local to any of the rules, in particular). Each rule has a precondition (situation) which is either satisfied or not by the global database.

If the precondition is satisfied, the rule can be applied. Application of the rules changes the data base as a result it is a dynamic structure continually changing as a result of operation of production rules, so it is also called working memory or short-term memory.

3. Control Structure or Control Strategy/Interpreter:

It is essentially an interpreter program to control the order in which the production rules are fixed and resolve conflicts, if more than one rule becomes applicable simultaneously. This structure repeatedly applies rules to the data base until a description of the goal state is produced.

The process of identifying the rules which are tried until some sequence of them is found produces a data satisfying the termination condition (goal) is called SEARCH PROCESS. Efficient control strategies require enough knowledge about the problem being solved so that the rule (or sequence of rules) selected has a good chance of being the most appropriate.

Two major kinds of control strategies are:

i. Irrevocable and

ii. Tentative.

In an irrevocable control strategy an acceptable rule is selected and applied irrevocably without provision for reconsideration later. In a tentative control strategy, an applicable rule is selected (arbitrarily or based upon some good reason), the rule is applied, with a provision to return later to this point in the computation to apply some other rule.

The tentative strategy can farther be subdivided into back tracking and graph- search control (or trees). Backtracking is a process in which the control strategy can be tentative. Herein a rule is selected and if it does not lead to a solution, the intervening steps are for gotten and another rule is selected instead. The backtracking strategy can be used regardless of how much or how little knowledge is available for choice of rules.

It no knowledge is available, rules can be selected according to some arbitrary scheme. Ultimately, control will backtrack to select the appropriate rule. Obviously, if good rule-selection knowledge can be used, backing up for selecting the alternative rules will occur less often, naturally making the process more efficient. In the graph search control strategy provision is made for keeping track of the effects of several sequences of rules simultaneously. Various kinds of graph structures and graph searching procedures are used in this type of control.

Graphs (or trees to be more specific) are extremely useful structures for keeping track of the effects of several sequences of rules. As an example once again consider water jug problem. We can keep track of the various rules applied and the database produced by data structure called search tree.

An example of such a tree in Fig. 2.6 in which various rules can be applied corresponding to links or directed arcs to descendent nodes, representing the states which can be reached by just one move from the initial state. This tree continues to be generated by the graph-search control strategy, until a database is produced which satisfies the termination condition.

In the (Fig. 2.6) we show all applicable rules being applied to every state description. Such an indecisive control strategy is grossly inefficient because the resulting tree grows too rapidly. An intelligent control strategy would grow a much narrower tree, using its special knowledge to focus the growth of the tree towards the goal.

Example Production System-8-Puzzle Problem:

A simple and perhaps familiar problem of this sort, useful for illustrating basic ideas is the 8-puzzle. The 8-puzzle consists of eight numbered, movable tiles set in a 3 x 3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell or, we could say, to move the empty cell.

Such a puzzle is illustrated in Fig. 2.10. Only two configurations of tiles are given. Consider the problem of changing the initial configuration into the goal configuration. A solution to the problem is an appropriate sequence of moves, such as “move tile 6 up move tile 8 down, etc.”

To solve a problem using a production system, we must specify the global database, the rules and the control strategy. Transforming a problem statement into these three components of a production system is often called the representation of problem in AI. Usually there are several ways to represent a problem. Selecting a good representation is one of important arts involved in applying AI techniques to solve non-trivial practical problems.

For the 8-puzzle and certain other problems, we can easily identify three elements of the problem which correspond to these three components of a production system. In the 8-puzzle each tile configuration is a state. The set of all possible configurations is the space of problem states or the problem space.

Once the problem states have been conceptually identified, we must construct a computer representation, or description of them. This description is then used as the global database of production system. For the 8-puzzle, a straight forward description is a 3 × 3 array or matrix of numbers.

The initial global database is thus description of the initial problem state. Virtually any kind of data structure can be used to describe states. These include symbol strings, vectors, sets of arrays, trees and lists. Sometimes, as in the 8-puzzle, the form of the data structure bears a close resemblance to some physical property of the problem being solved.

A move transforms one problem state into another state. The 8-puzzle is conveniently interpreted as having the following four moves. Move empty space (blank) to the left, move blank up move blank to the right, and move blank down. These moves are modeled by production rules which operate on the state descriptions in the appropriate manner.

The rules have preconditions which must be satisfied by a state description in order for them to be applicable to that state description. As an example, the precondition for the rule associated with “move blank up” requires the pre-condition that the blank space must not already be in the top row.

UP → Blank not in Top row.

Similar, production rules can be formed for down, left and right move.

In the 8-puzzle problem, we are asked to produce a particular problem state, namely, the goal state shown in Fig. 2.10. We can also deal with problems for which the goal is to achieve anyone of an explicit list of problem states. A further generalization is to specify some true/false condition on states to serve as a goal condition.

Then the goal would be to achieve any state satisfying this condition. Such a condition implicity defines some set of goal states, in the 8-puzzle, we might want to achieve any tile configuration for which the sum of the numbers labeling the tiles in the first row is 6. In our language of states, moves and goals, a solution to a problem is a sequence of moves which transforms an initial state into a goal state.

The goal condition forms the basis for the termination condition of the production system. The control strategy repeatedly applies rules to state descriptions until a description of a goal state is produced. It also keeps track of the rules which have been applied so that it can compose them into the sequence representing the problem solution.

In certain problems, we want the solution to be subject to certain additional constraints. For example, we may want the solution to our 8-puzzle problem having the smallest number of moves. In general we ascribe a cost to each move and then attempt to find a solution having minimal cost.

Algorithm of Problem Solving by Production Systems:

The basic production system algorithm for solving a problem like the water jug problem or 8-puzzle can be written in non-deterministic form as follows:

1. DATA ← initial database.

2. Until DATA satisfies the termination condition,

3. Begin

4. Select some rule, R, in the set of rules that can be applied to DATA

5. DATA← add action part of fired rule to database.

6. End

Issues Involved in Solving Problem Using Space Representation:

A good problem solution requires an efficient control strategy and good representations for problem states, moves, and goal conditions. The representation of a problem has a great influence on the effort needed to solve it. Obviously we should prefer representations with small state spaces.

There are many examples of seemingly difficult puzzles which, when represented appropriately, have trivially small state spaces. Sometimes a given state space can be collapsed by recognizing that certain rules can be discarded or that rules can be combined to make more powerful ones. Even when such simple transformations cannot be achieved, it is possible that a complete reformulation of the problem will result in a smaller space.

The process required in representing a problem initially and then improving given representations are still poorly understood. It seems that desirable shifts in a problem’s representation depend on experience gained in attempts to solve it in a given representation.

This experience allows us to recognize the occurrence of simplifying notions, such as symmetries, or useful sequences of rules which ought to be combined into macro-rules. For example, the solution of water jug problem requires as many as 12 rules given in Fig. 2.3., but the two solution given here were found deploying 6 rules.

Most of the rules are never applicable to any given state description for one reason or the other. After this fact becomes apparent to us, as problem solver, we would discover the better representation involving ‘filling’ and ’emptying’ the jugs. The reader should look for such symmetries and simplifications for 8-puzzle problem.