Expert system compilation method

• US 5,442,792 A
• Filed: 06/10/1994
• Issued: 08/15/1995
• Est. Priority Date: 08/07/1992
• Status: Expired due to Fees

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Chun, Robert K.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Richey, Michael T.
• Application Number:
  US08/258,359
• Time in Patent Office: 431 Days
• Field of Search: 395/650, 395/700
• US Class Current: 717/155
• CPC Class Codes: G06F 9/4496 Unification in logic programming
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: Y10S 706/922 Computer program preparation

Abstract

A computer implemented compilation method or compiler and translator that automatically converts an interpretive rule-based expert system into compact, compiled, parallel Ada code. The present compiler customizes the compiled code for each desired knowledge base to produce just the minimum amount of Ada code needed to provide equivalent functionality to one pass of the inference engine. After parsing, a data dependency analysis is performed on a rule base to identify segments that can be executed in parallel. These segments are then compiled by a code generator to make use of Ada'"'"'s multi-tasking capabilities. The present invention accelerates the execution speed of the compiled code, reduces memory requirements for the compiled code, and enables expert systems to be efficiently embedded into real-time procedural systems, especially those using Ada software and parallel processing hardware. The present invention also includes code slicing techniques that are applied to rule bases that extends the translation capability of the present compilation method to encompass backward chaining in rule-based expert systems. In contrast to conventional approaches, the present approach provides a customized translation for each individual expert system, yielding minimal procedural code that is highly efficient in terms of both execution speed and memory requirements. This makes it more feasible to embed the expert system into a real-time application where high execution speed and low memory usage are critical.

Claims

1. A computer implemented method for generating compiled multi-tasking procedural expert system object code from a pre-existing rule based expert system that includes a knowledge base having rules and a comprehensive inference engine, the method comprising the steps of:

parsing the knowledge base into intermediate forms including test, read, and write matrices which represent the rules of the knowledge base;

analyzing the intermediate forms as to data and control dependencies to pre-order the rules and to identify rules that are data independent and to extract parallelism among the rules, and on the basis of such analysis;

(a) merging sequentially ordered single rules into merged rules when possible thereby collapsing two or more single rules into a single merged rule and increasing efficiency by eliminating intermediate variables from computation;

(b) ordering and clustering into respective data independent clusters single rules and merged rules that must be fired sequentially such that single rules and merged rules that must be fired sequentially are ordered and clustered in the same cluster; and

(c) grouping data independent clusters into a predetermined number of data independent groups of clusters, wherein the predetermined number depends on the hardware on which the procedural expert system object code is to be executed;

synthesizing in procedural code the functional behavior of only the portion of the comprehensive inference engine that is used by the knowledge base;

generating multi-tasking procedural source code implementing said data independent groups of clusters of rules and merged rules and said portion of said comprehensive inference engine synthesized in procedural code such that said data independent groups of clusters will be executed in parallel; and

generating compiled multi-tasking procedural expert system object code from said source code.

2. A computer implemented method for generating compiled multi-tasking procedural expert system object code from a pre-existing rule based expert system that includes a knowledge base having rules and a comprehensive inference engine, the method comprising the steps of:

parsing the knowledge base into intermediate forms including test, read, and write matrices which represent the rules of the knowledge base

analyzing the intermediate forms as to data and control dependencies to pre-order the rules and to identify rules that are data independent and to extract parallelism among the rules, and on the basis of such analysis;

(a) merging sequentially ordered single rules into merged rules when possible thereby collapsing two or more single rules into a single merged rule and increasing efficiency by eliminating intermediate variables from computation;

(b) ordering and clustering into respective data independent clusters single rules and merged rules that must be fired sequentially such that single rules and merged rules that must be fired sequentially are ordered and clustered in the same cluster; and

(c) grouping data independent clusters into a predetermined number of data independent groups of clusters, wherein the predetermined number depends on the hardware on which the procedural expert system object code is to be executed;

synthesizing in procedural code the functional behavior of only the portion of the comprehensive inference engine that is used by the knowledge base;

generating multi-tasking procedural source code implementing said data independent groups of clusters of rules and merged rules and said portion of said comprehensive inference engine synthesized in procedural code such that said data independent groups of clusters will be executed in parallel;

generating compiled multi-tasking procedural expert system object code from said source code; and

code slicing said procedural system object code pursuant to user supplied output variables to produce a minimal representation of the object code sufficient to compute the user specified output variables.

3. A computer implemented method for generating compiled multi-tasking procedural expert system object code from a pre-existing rule based expert system that includes a knowledge base having rules and a comprehensive inference engine, the method comprising the steps of:

parsing the knowledge base into intermediate forms including test, read, and write matrices which represent the rules of the knowledge base;

code slicing said intermediate forms pursuant to user supplied output variables to produce a minimal representation of the knowledge base rules in intermediate form sufficient to compute the user specified output variables;

analyzing the remaining minimal intermediate forms as to data and control dependencies to pre-order the rules and to identify rules that are data independent and to extract parallelism among the rules, and on the basis of such analysis;

(a) merging sequentially ordered single rules into merged rules when possible thereby collapsing two or more single rules into a single merged rule and increasing efficiency by eliminating intermediate variables from computation;

(b) ordering and clustering into respective data independent clusters single rules and merged rules that must be fired sequentially such that single rules and merged rules that must be fired sequentially are ordered and clustered in the same cluster; and

(c) grouping data independent clusters into a predetermined number of data independent groups of clusters, wherein the predetermined number depends on the hardware on which the procedural expert system object code is to be executed;

synthesizing in procedural code the functional behavior of only the portion of the comprehensive inference engine that is used by the knowledge base;

generating multi-tasking procedural source code implementing said data independent groups of clusters of rules and merged rules and said portion of said comprehensive inference engine synthesized in procedural code such that said data independent groups of clusters will be executed in parallel; and

generating compiled multi-tasking procedural expert system object code from said source code.