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:
- 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.
- Formal Dependencies: A rule A is said to depend on rule B if B asserts a fact required for A to fire.
- 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.
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.
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