Exploring the Structure of Rule Based Systems

Clifford Grossner, Alun D. Preece, P. Gokul Chander, Thiruvengadam Radhakrishnan, Ching Y. SuenAAAI 1993

Abstract

Rule-based expert systems offer modularity but suffer from unpredictable interactions as they scale. This paper introduces Path Hunter, a tool that extracts formal execution paths to validate system design and detect hidden rule dependencies. By applying logical completions and rule abstractions, the authors demonstrate a scalable method for structural analysis, identifying design flaws in a complex 442-rule system.

Introduction

Rule-based systems are widely utilized for their modularity, where individual "if-then" rules represent discrete units of knowledge. However, as these systems grow, predicting their global behavior becomes challenging. Rules interact through a shared working memory, meaning a change in one rule can trigger unforeseen ripple effects. Traditional dependency mapping often results in "ghost" paths or suffers from combinatorial explosion. This research addresses these gaps by formalizing the concept of a "Rule Base Execution Path."

The Path Hunter Framework

The authors propose Path Hunter, a tool designed to extract meaningful threads of execution from large-scale expert systems. The methodology relies on several key formalisms:

  1. Rule Abstraction: Complex rules with multiple actions on the Right-Hand Side (RHS) are split into "abstract rules," ensuring each represents a single predictable action.
  2. Formal Dependencies: A rule A is said to depend on rule B if B asserts a fact required for A to fire.
  3. Logical Completions: To manage complexity, designers define "logical completions"—sets of predicates representing a completed sub-problem. Path Hunter restricts its search to paths terminating in these goals.
Table of abstracted rules showing inputs (I), outputs (A), and functional descriptions.

Case Study: The Blackbox Expert

The approach was validated using the Blackbox Expert, a system designed to solve the "Blackbox" puzzle. The original 442 CLIPS rules were expanded into 512 abstract rules. Path Hunter successfully identified 516 distinct execution paths within this system, mapping the complex dependencies between predicates and rule activations.

An execution path diagram from the Blackbox Expert system, showing the flow from initial predicates to final goal states.

Structural Validation and Results

The extraction of these paths provided a high-level debugging mechanism. The analysis revealed:

  • Orphaned Rules: Rules that were never part of any valid execution path, indicating design flaws where a rule's dependencies and assertions belonged to unrelated tasks.
  • Semantic Ambiguity: Instances where the same predicate was used inconsistently across different contexts, leading to unintended rule interactions.
  • Computational Feasibility: By grouping rules into 72 equivalence classes and utilizing logical completions, the tool avoided the combinatorial explosion typical of such analyses.

Conclusion

Path Hunter demonstrates that formalizing execution paths allows for rigorous structural validation of expert systems. Beyond debugging, these paths provide a foundation for predicting performance in Cooperative Distributed Problem Solving (CDPS) environments, where understanding inter-agent information requirements is critical.

Summary updated

BibTeX
@inproceedings{grossner1993exploring,
  author = {Clifford Grossner and Alun D. Preece and P. Gokul Chander and Thiruvengadam Radhakrishnan and Ching Y. Suen},
  title = {{Exploring the Structure of Rule Based Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}

Loading related content...

Figure