Production system
Encyclopedia
A production system is a computer program typically used to provide some form of artificial intelligence
, which consists primarily of a set of rules about behavior. These rules, termed productions, are a basic representation
found useful in automated planning
, expert systems and action selection
. A production system provides the mechanism necessary to execute productions in order to achieve some goal for the system.
Productions consist of two parts: a sensory precondition (or "IF" statement) and an action (or "THEN"). If a production's precondition matches the current state
of the world, then the production is said to be triggered. If a production's action is executed
, it is said to have fired. A production system also contains a database, sometimes called working memory
, which maintains data about current state or knowledge, and a rule interpreter. The rule interpreter must provide a mechanism for prioritizing productions when more than one is triggered.
algorithm for selecting productions to execute to meet current goals, which can include updating the system's data or beliefs
. The condition portion of each rule (left-hand side or LHS) is tested against the current state of the working memory.
In idealized or data-oriented production systems, there is an assumption that any triggered conditions should be executed: the consequent actions (right-hand side or RHS) will update the agent's knowledge, removing or adding data to the working memory. The system stops processing either when the user interrupts the forward chaining loop; when a given number of cycles has been performed; when a "halt" RHS is executed, or when no rules have true LHSs.
Real-time and expert systems, in contrast, often have to choose between mutually exclusive productions --- since actions take time, only one action can be taken, or (in the case of an expert system) recommended. In such systems, the rule interpreter, or inference engine
, cycles through two steps: matching production rules against the database, followed by selecting which of the matched rules to apply and executing the selected actions.
algorithm which collects production rules with matched conditions may range from the naive -- trying all rules in sequence, stopping at the first match -- to the optimized, in which rules are "compiled" into a network of inter-related conditions.
The latter is illustrated by the RETE
algorithm, designed by Charles L. Forgy
in 1983, which is used in a series of production systems, called OPS and originally developed at Carnegie Mellon University
culminating in OPS5
in the early eighties. OPS5 may be viewed as a full-fledged programming language for production system programming.
.
Here again, such strategies may vary from the simple -- use the order in which production rules were written; assign weights or priorities to production rules and sort the conflict set accordingly -- to the complex -- sort the conflict set according to the times at which production rules were previously fired; or according to the extent of the modifications induced by their RHSs. Whichever conflict resolution strategy is implemented, the method is indeed crucial to the efficiency and correctness of the production system.
rules to the modeling of human cognitive processes, from term rewriting and reduction systems to expert system
s.
P1: $$ -> *
P2: *$ -> *
P3: *x -> x*
P4: * -> null & halt
P5: $xy -> y$x
P6: null -> $
In this example, production rules are chosen for testing according to their order in this production list. For each rule, the input string is examined from left to right with a moving window to find a match with the LHS of the production rule. When a match is found, the matched substring in the input string is replaced with the RHS of the production rule. In this production system, x and y are variables matching any character of the input string alphabet. Matching resumes with P1 once the replacement has been made.
The string "ABC", for instance, undergoes the following sequence of transformations under these production rules:
$ABC (P6)
B$AC (P5)
BC$A (P5)
$BC$A (P6)
C$B$A (P5)
$C$B$A (P6)
$$C$B$A (P6)
*C$B$A (P1)
C*$B$A (P3)
C*B$A (P2)
CB*$A (P3)
CB*A (P2)
CBA* (P3)
CBA (P4)
In such a simple system, the ordering of the production rules is crucial. Often, the lack of control structure makes production systems difficult to design. It is, of course, possible to add control structure to the production systems model, namely in the inference engine, or in the working memory.
(p Holds::Object-Ceiling
{(goal ^status active ^type holds ^objid <O1>) <goal>}
{(physical-object
^id <O1>
^weight light
^at <p>
^on ceiling) <object-1>}
{(physical-object ^id ladder ^at <p> ^on floor) <object-2>}
{(monkey ^on ladder ^holds NIL) <monkey>}
-(physical-object ^on <O1>)
-->
(write (crlf) Grab <O1> (crlf))
(modify <object1> ^on NIL)
(modify <monkey> ^holds <O1>)
(modify <goal> ^status satisfied)
)
In this example, data in working memory is structured and variables appear between angle brackets. The name of the data structure, such as "goal" and "physical-object", is the first literal in conditions; the fields of a structure are prefixed with "^". The "-" indicates a negative condition.
Production rules in OPS5 apply to all instances of data structures that match conditions and conform to variable bindings. In this example, should several objects be suspended from the ceiling, each with a different ladder nearby supporting an empty-handed monkey, the conflict set would contain as many production rule instances derived from the same production "Holds::Object-Ceiling". The conflict resolution step would later select which production instances to fire.
Note that the binding of variables resulting from the pattern matching in the LHS is used in the RHS to refer to the data to be modified. Note also that the working memory contains explicit control structure data in the form of "goal" data structure instances. In the example, once a monkey holds the suspended object, the status of the goal is set to "satisfied" and the same production rule can no longer apply as its first condition fails.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, which consists primarily of a set of rules about behavior. These rules, termed productions, are a basic representation
Knowledge representation
Knowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
found useful in automated planning
Automated planning and scheduling
Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...
, expert systems and action selection
Action selection
Action selection is a way of characterizing the most basic problem of intelligent systems: what to do next. In artificial intelligence and computational cognitive science, "the action selection problem" is typically associated with intelligent agents and animats—artificial systems that exhibit...
. A production system provides the mechanism necessary to execute productions in order to achieve some goal for the system.
Productions consist of two parts: a sensory precondition (or "IF" statement) and an action (or "THEN"). If a production's precondition matches the current state
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
of the world, then the production is said to be triggered. If a production's action is executed
Execution (computers)
Execution in computer and software engineering is the process by which a computer or a virtual machine carries out the instructions of a computer program. The instructions in the program trigger sequences of simple actions on the executing machine...
, it is said to have fired. A production system also contains a database, sometimes called working memory
Working memory
Working memory has been defined as the system which actively holds information in the mind to do verbal and nonverbal tasks such as reasoning and comprehension, and to make it available for further information processing...
, which maintains data about current state or knowledge, and a rule interpreter. The rule interpreter must provide a mechanism for prioritizing productions when more than one is triggered.
Basic operation
Rule interpreters generally execute a forward chainingForward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
algorithm for selecting productions to execute to meet current goals, which can include updating the system's data or beliefs
BDI software agent
The Belief-Desire-Intention software model is a software model developed for programming intelligent agents. Superficially characterized by the implementation of an agent's beliefs, desires and intentions, it actually uses these concepts to solve a particular problem in agent programming...
. The condition portion of each rule (left-hand side or LHS) is tested against the current state of the working memory.
In idealized or data-oriented production systems, there is an assumption that any triggered conditions should be executed: the consequent actions (right-hand side or RHS) will update the agent's knowledge, removing or adding data to the working memory. The system stops processing either when the user interrupts the forward chaining loop; when a given number of cycles has been performed; when a "halt" RHS is executed, or when no rules have true LHSs.
Real-time and expert systems, in contrast, often have to choose between mutually exclusive productions --- since actions take time, only one action can be taken, or (in the case of an expert system) recommended. In such systems, the rule interpreter, or inference engine
Inference engine
In computer science, and specifically the branches of knowledge engineering and artificial intelligence, an inference engine is a computer program that tries to derive answers from a knowledge base. It is the "brain" that expert systems use to reason about the information in the knowledge base for...
, cycles through two steps: matching production rules against the database, followed by selecting which of the matched rules to apply and executing the selected actions.
Matching production rules against working memory
Production systems may vary on the expressive power of conditions in production rules. Accordingly, the pattern matchingPattern matching
In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
algorithm which collects production rules with matched conditions may range from the naive -- trying all rules in sequence, stopping at the first match -- to the optimized, in which rules are "compiled" into a network of inter-related conditions.
The latter is illustrated by the RETE
Rete algorithm
The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper...
algorithm, designed by Charles L. Forgy
Charles Forgy
Dr Charles L. Forgy is a computer scientist, known for developing the Rete algorithm used in his OPS5 and other production system languages used to build expert systems.- Early Life :Dr...
in 1983, which is used in a series of production systems, called OPS and originally developed at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
culminating in OPS5
OPS5
OPS5 is a rule-based or production system computer language, notable as the first such language to be used in a successful expert system, the R1/XCON system used to configure VAX computers....
in the early eighties. OPS5 may be viewed as a full-fledged programming language for production system programming.
Choosing which rules to evaluate
Production systems may also differ in the final selection of production rules to execute, or fire . The collection of rules resulting from the previous matching algorithm is called the conflict set , and the selection process is also called a conflict resolution strategyConflict resolution strategy
Conflict resolution strategies are used in production systems to help in choosing which production rule to fire. The need for such a strategy arises when the conditions of two or more rules are satisfied by the currently known facts.-Categories:...
.
Here again, such strategies may vary from the simple -- use the order in which production rules were written; assign weights or priorities to production rules and sort the conflict set accordingly -- to the complex -- sort the conflict set according to the times at which production rules were previously fired; or according to the extent of the modifications induced by their RHSs. Whichever conflict resolution strategy is implemented, the method is indeed crucial to the efficiency and correctness of the production system.
Using production systems
The use of production systems varies from simple string rewritingRewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. What is considered are rewriting systems...
rules to the modeling of human cognitive processes, from term rewriting and reduction systems to expert system
Expert system
In artificial intelligence, an expert system is a computer system that emulates the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of a developer as is the case in...
s.
A simple string rewriting production system example
This example shows a set of production rules for reversing a string from an alphabet that does not contain the symbols "$" and "*" (which are used as marker symbols).P1: $$ -> *
P2: *$ -> *
P3: *x -> x*
P4: * -> null & halt
P5: $xy -> y$x
P6: null -> $
In this example, production rules are chosen for testing according to their order in this production list. For each rule, the input string is examined from left to right with a moving window to find a match with the LHS of the production rule. When a match is found, the matched substring in the input string is replaced with the RHS of the production rule. In this production system, x and y are variables matching any character of the input string alphabet. Matching resumes with P1 once the replacement has been made.
The string "ABC", for instance, undergoes the following sequence of transformations under these production rules:
$ABC (P6)
B$AC (P5)
BC$A (P5)
$BC$A (P6)
C$B$A (P5)
$C$B$A (P6)
$$C$B$A (P6)
*C$B$A (P1)
C*$B$A (P3)
C*B$A (P2)
CB*$A (P3)
CB*A (P2)
CBA* (P3)
CBA (P4)
In such a simple system, the ordering of the production rules is crucial. Often, the lack of control structure makes production systems difficult to design. It is, of course, possible to add control structure to the production systems model, namely in the inference engine, or in the working memory.
An OPS5 production rule example
In a toy simulation world where a monkey in a room can grab different objects and climb on others, an example production rule to grab an object suspended from the ceiling would look like:(p Holds::Object-Ceiling
{(goal ^status active ^type holds ^objid <O1>) <goal>}
{(physical-object
^id <O1>
^weight light
^at <p>
^on ceiling) <object-1>}
{(physical-object ^id ladder ^at <p> ^on floor) <object-2>}
{(monkey ^on ladder ^holds NIL) <monkey>}
-(physical-object ^on <O1>)
-->
(write (crlf) Grab <O1> (crlf))
(modify <object1> ^on NIL)
(modify <monkey> ^holds <O1>)
(modify <goal> ^status satisfied)
)
In this example, data in working memory is structured and variables appear between angle brackets. The name of the data structure, such as "goal" and "physical-object", is the first literal in conditions; the fields of a structure are prefixed with "^". The "-" indicates a negative condition.
Production rules in OPS5 apply to all instances of data structures that match conditions and conform to variable bindings. In this example, should several objects be suspended from the ceiling, each with a different ladder nearby supporting an empty-handed monkey, the conflict set would contain as many production rule instances derived from the same production "Holds::Object-Ceiling". The conflict resolution step would later select which production instances to fire.
Note that the binding of variables resulting from the pattern matching in the LHS is used in the RHS to refer to the data to be modified. Note also that the working memory contains explicit control structure data in the form of "goal" data structure instances. In the example, once a monkey holds the suspended object, the status of the goal is set to "satisfied" and the same production rule can no longer apply as its first condition fails.
Related systems
- CLIPSCLIPSCLIPS is a public domain software tool for building expert systems. The name is an acronym for "C Language Integrated Production System." The syntax and name was inspired by Charles Forgy's OPS...
: public domain software tool for building expert systems. - d3webD3webd3web is a free, open-source platform for knowledge-based systems .Its core is written in Java using XML and/or Office-based formats for the knowledge storage....
: free, open-source platform for knowledge-based systems (expert systems). - ILOG rulesILOGILOG is an international software company owned by IBM. It creates enterprise software products for supply chain, business rule management, visualization and optimization....
: a business rule management system. - JBoss DroolsDroolsDrools is a business rule management system with a forward chaining inference based rules engine, more correctly known as a production rule system, using an enhanced implementation of the Rete algorithm....
: a open-source business rule management system (BRMS). - JESSJess programming languageJess is a rule engine for the Java platform - it is a superset of CLIPS programming language, developed by Ernest Friedman-Hill of Sandia National Labs. It was first written in late 1995....
: a rule engine for the Java platform - it is a superset of CLIPSCLIPSCLIPS is a public domain software tool for building expert systems. The name is an acronym for "C Language Integrated Production System." The syntax and name was inspired by Charles Forgy's OPS...
programming language. - PrologPrologProlog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
: a general purpose logic programming language. - LisaLisp-based Intelligent Software AgentsThe Lisa project is a platform for the development of Lisp-based Intelligent Software Agents. Lisa is a production-rule system implemented in the Common Lisp Object System , and is heavily influenced by CLIPS and the Java Expert System Shell .At its core is a reasoning engine based on an...
: a rule engine written in Common Lisp. - DTRulesDTRulesDTRules is Open Sourced Rules Engine written entirely in Java. DTRules executes Decision tables directly, and utilizes a Domain Specific Language for expressing the conditions and actions within the Decision Tables....
: a Decision Table based, open-sourced rule engine for Java. - OpenL TabletsOpenL TabletsOpenL Tablets is a business rule management system and a business rules engine based on table representation of rules. Engine implements optimized sequential algorithm...
: business centric rules and open source BRMS.
See also
- Action selection mechanism
- Expert systemExpert systemIn artificial intelligence, an expert system is a computer system that emulates the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of a developer as is the case in...
- Inference engineInference engineIn computer science, and specifically the branches of knowledge engineering and artificial intelligence, an inference engine is a computer program that tries to derive answers from a knowledge base. It is the "brain" that expert systems use to reason about the information in the knowledge base for...
- L-systemL-systemAn L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
- OPS5OPS5OPS5 is a rule-based or production system computer language, notable as the first such language to be used in a successful expert system, the R1/XCON system used to configure VAX computers....
- Production Rule RepresentationProduction Rule RepresentationThe Production Rule Representation is a proposed standard of the Object Management Group to provide a vendor-neutral rule-model representation in UML for production rules as used in forward-chaining rule engines.- History :...
- Rete algorithmRete algorithmThe Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper...