Rule-Based Systems

Production Systems (Rule-Based Expert Systems)

The production system is a problem-solving methodology that is modeled after a system described by Post in 1943. This model has the following characteristics:

  1. Production rules are a computationally universal machine (they could do anything)

  2. They separate the domain knowledge of the system from the control process

  3. Domain Knowledge takes the form of rules

  4. The flow of control is the select-execute (recognize-act, situation-action) cycle. The decision strategy can evaluate the entire state of the system before making a control flow change. Compare with FSMs.

  5. Some authors claim that production systems model the thinking of human beings, evidenced by protocols

  6. Has the following standard parts:

Parts of the Standard Production (Rule-Based) System

  1. Rule Interpreter - Picks all the rules that apply to the current system state

  2. Conflict Resolution - From the list of rules choosen by the Rule Interpreter as applicable, choose the one to fire

  3. Execution - Performs the action indicated by selected rule

  4. Working Memory - Contains all the facts that have been deduced or given to the system

  5. Rule Base - All the domain knowledge or expertise of this system

What are the conditions and the actions of a Rule:

  1. Conditions - In the standard system, the conditions are matched against the facts in the data base

  2. Actions - In standard system, actions write facts into the data base but could conceivably do anything, like write in its own rules.

Production Systems (Rule-Based Expert Systems)

  1. Rules are a particular kind of Knowledge Representation

  2. Production Systems are a methodology that do Problem Solving using Rules as their Knowledge Representation

Rules

Typical Rules usually are a set of condition-action pairs of the form:

Note that there is no necessary restriction on the number of conditions or actions

Just what a condition and action is specifically we will have to investigate

Said another way: RBS consist of:

The control strategy searches through the space of rules from a given initial state, applies valid rule(s) until it reaches the final state.
(an aside: production systems demonstrate the data-drived nature of intelligence (new input/behavior change). Rules can easily be added (systems are never complete))

Forward Chaining

Forward Chaining is one control strategy commonly used in Production Systems and has the following characteristics

  1. It matches against the condition half of the rules (commonly called the left-hand side or LHS) and executes the action of the chosen rule

  2. It is a data-driven process, matching world facts to the conditions of the rules

  3. It is a deductive process, adding facts to the knowledge base which it believes to be true

  4. It finishes the process when no more condition parts of a rule match against anything in the data base (Note: one can have a problem with repeating rules that were once true)

gifs from AI-depot tutorial

Backward Chaining

Backward Chaining is another common control strategy used in Production Systems. It has the following characteristics:

  1. Backward Chaining matches against the action parts of a list of rules (commonly called the right-hand side or RHS). If such a match is found, the system tries to establish the conditions of the matched rule. If these new conditions are not in the data base, they are matched against the action half of all the rules

  2. It is a goal-driven process, trying to establish a fact by finding all the rules that could confirm it

  3. It is a hypothesize and match reasoning

  4. It finishes when a subgoal cannot be established or the goal is established

gifs from AI-depot tutorial

Try the Bartender example

Rules continued

Laird worked with Newell (of the General Problem Solver (GPS) fame) in making SOAR in the early 80's. About this time rules were really big but people were wanting more control over which rules were chosen. The idea of meta-rules (late 70's) became prominent.
Soar used the basics of rule-based systems but wanted more intelligent control. They established the concept of chunking (inspired by Miller's Magic Number 7) as a learning mechanism that acquires rules from goal-based experience. Soar is a general problem-solving architecture with a rule-based memory that can acquire search-control knowledge (strategy acquisition) and operator implementation rules. Soar has evolved over the past 20 years and is still alive and continues to grow using continued modern approaches (e.g., episodic memory and parallelism). See a comparison between Soar and rule-based systems

AI-depot tutorial (also has getting rules from decision trees)

aigamedev.com has a tutorial on rule-based systems too (with game info)