Production system

Production system

A production system (or production rule 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 AI 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.

Basic operation

Rule interpreters generally execute a forward chaining 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.

Matching production rules against working memory

Production systems may vary on the expressive power of conditions in production rules. Accordingly, the pattern matching 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.

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 strategy ".

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 rewriting rules to the modeling of human cognitive processes, from term rewriting and reduction systems to expert systems.

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.

References

* Brownston, L., Farrell R., Kant E. (1985). "Programming Expert Systems in OPS5" Reading, Massachusetts: Addison-Wesley. ISBN 0-201-10647-7

* Waterman, D.A., Hayes-Roth, F. (1978). "Pattern-Directed Inference Systems" New York: Academic Press. ISBN 0127375503

* Klahr, D., Langley, P. and Neches, R. (1987). "Production System Models of Learning and Development". Cambridge, Mass.: The MIT Press.

See also

*Action selection mechanism
*Expert system
*Inference engine
*OPS5
*Rete algorithm


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • production system — ▪ industrial engineering Introduction       any of the methods used in industry to create goods and services from various resources. Underlying principles       All production systems, when viewed at the most abstract level, might be said to be… …   Universalium

  • Toyota Production System — The Toyota Production System (TPS) combines management philosophy and practices to form an integrated socio technical system at Toyota. The TPS organizes manufacturing and logistics for the automobile manufacturer, including interaction with… …   Wikipedia

  • Computer Animation Production System — The Computer Animation Production System (CAPS) is a proprietary collection of software programs, scanning camera systems, servers, networked computer workstations, and custom desks developed by The Walt Disney Company together with Pixar in the… …   Wikipedia

  • Toyota Production System — UK US noun [S] (ABBREVIATION TPS) PRODUCTION, MANAGEMENT ► a system for manufacturing, developed by Toyota® in Japan, based on lean manufacturing (= avoiding waste) and just in time production (= where parts are delivered exactly when needed):… …   Financial and business terms

  • Computer Animation Production System — Pour les articles homonymes, voir CAPS. Le Computer Animation Production System (CAPS) (ou système de production d animation par ordinateur) est une collection propriétaire de logiciel, système cinématographes, serveurs, stations de travail et… …   Wikipédia en Français

  • Computer Animation Production System — (CAPS)  это собственный набор программ, систем сканирующих камер, серверов и рабочих станций, разработанный The Walt Disney Company совместно с Pixar в конце 80 х. Он предназначался для того, чтобы компьютеризировать контуровку и заливку… …   Википедия

  • stockless production system — A production system that does not permit stocks to be held in the process. See just in time …   Big dictionary of business and management

  • Production leveling — Production leveling, also known as production smoothing or – by its Japanese original term – heijunka (平準化?),[1] is a technique for reducing the muda waste and vital to the development of production efficiency in the Toyota Production System and… …   Wikipedia

  • Production — may be:In Economics: * Production, the act of making products (goods and services) * Production, the act of manufacturing goods * Production as statistic, gross domestic productIn Entertainment: * Production, phase of filmmaking * Production,… …   Wikipedia

  • Production Systems Engineering — (PSE) is a recently developed branch of Engineering, which aims to provide rigorous quantitative methods for analysis and design, and continuous improvement of production systems.The main results of PSE are summarized in the textbook Production… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”