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.
Don't have an account?
Overview
The document titled "Algorithm Optimally Orders Forward-Chaining Inference Rules" (NPO-42003) from NASA's Jet Propulsion Laboratory (JPL) discusses a novel algorithm designed to enhance the efficiency of knowledge-based systems, particularly in the context of forward-chaining inference rules. The algorithm leverages data flow path analysis, a technique originally developed for optimizing code sequences in compilers, to improve the execution of inference systems.
Traditional data flow analysis, while effective in compilers, is not ideally suited for inference systems due to the potential for ubiquitous execution of rules. The proposed algorithm performs a comprehensive producer/consumer analysis of each antecedent and consequence clause within a knowledge base. This analysis allows for the optimal ordering of rules, which minimizes inference cycles and significantly accelerates execution times. The integration of this algorithm into JPL's Spacecraft Health Inference Engine (SHINE) demonstrated a marked reduction in inference cycles, particularly for knowledge bases that were previously unordered.
The document highlights the common practice of developing knowledge bases in an ad hoc manner, which often leads to inefficient execution due to the sensitivity of rule order. The algorithm addresses this issue by providing a systematic approach to organizing rules, thereby enhancing the performance of SHINE and other expert systems used in various JPL projects.
Additionally, the document notes that while the data flow decomposition of a knowledge base can yield an optimal representation, it typically requires special-purpose hardware for execution. This requirement can lead to performance trade-offs, as SHINE's optimal decomposition necessitates serial execution, which can be a bottleneck.
To mitigate the limitations associated with serial execution, the algorithm significantly improves performance for large knowledge bases on conventional hardware. The advancements achieved through this technology have benefitted multiple JPL projects, showcasing its practical applications in real-world scenarios.
Overall, the document serves as a technical support package that not only details the algorithm's development and integration into SHINE but also emphasizes its broader implications for knowledge-based systems across various fields. For further inquiries or information, the document provides contact details for JPL's Innovative Technology Assets Management.
