2008

Algorithm Optimally Orders Forward-Chaining Inference Rules

Requirements for exhaustive data-flow analysis are relaxed.

People typically develop knowledge bases in a somewhat ad hoc manner by incrementally adding rules with no specific organization. This often results in a very inefficient execution of those rules since they are so often order sensitive. This is relevant to tasks like Deep Space Network in that it allows the knowledge base to be incrementally developed and have it automatically ordered for efficiency.

Although data flow analysis was first developed for use in compilers for producing optimal code sequences, its usefulness is now recognized in many software systems including knowledge-based systems. However, this approach for exhaustively computing data-flow information cannot directly be applied to inference systems because of the ubiquitous execution of the rules. An algorithm is presented that efficiently performs a complete producer/consumer analysis for each antecedent and consequence clause in a knowledge base to optimally order the rules to minimize inference cycles.

An algorithm was developed that optimally orders a knowledge base composed of forwarding chaining inference rules such that independent inference cycle executions are minimized, thus, resulting in significantly faster execution. This algorithm was integrated into the JPL tool Spacecraft Health Inference Engine (SHINE) for verification and it resulted in a significant reduction in inference cycles for what was previously considered an ordered knowledge base. For a knowledge base that is completely unordered, then the improvement is much greater.

This work was done by Mark James of Caltech for NASA’s Jet Propulsion Laboratory.

The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42003.

This Brief includes a Technical Support Package (TSP).

Algorithm Optimally Orders Forward- Chaining Inference Rules (reference NPO-42003) is currently available for download from the TSP library.

Please Login at the top of the page to download.

 

White Papers

How To Guide for the Most Common Measurements
Sponsored by National Instruments
Fundamentals of Vector Network Analysis Primer
Sponsored by Rohde and Schwarz A and D
Unique Method for Orifice Production
Sponsored by Bird Precision
A Brief History of Modern Digital Shaker Controllers
Sponsored by Crystal Instruments
Simulation of the ballistic perforation of aluminum plates with Abaqus/Explicit
Sponsored by Simulia
Telematics: An Industry Game-Changer
Sponsored by SAP

White Papers Sponsored By: