| Algorithm Optimally Orders Forward-Chaining Inference Rules |
|
|
| NASA’s Jet Propulsion Laboratory, Pasadena, California | |
| Jan 01 2008 | |
Requirements for exhaustive data-flow analysis are relaxed.
advertisement:
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. Login first to download.
|
