Combining Opinions About the Order of Rule Execution

Jeffrey A. BarnettAAAI 1991

Introduction

In the development of expert systems, a recurring challenge is the management of "traffic control." When multiple rules are triggered simultaneously—forming a conflict set—the system must decide on an execution sequence. Historically, this was handled by rigid control knowledge. However, as systems grew more complex, different sources of control knowledge often provided conflicting advice. Jeffrey A. Barnett’s 1991 paper addresses this by applying formal belief calculus to merge these disparate opinions into a single, optimal execution agenda.

Methodology: Dempster-Shafer and Plausibility

The author utilizes the Dempster-Shafer (D-S) belief calculus, a framework for reasoning with uncertainty that offers more flexibility than traditional probability. In this model, a "primitive opinion" is defined as a preference for rule $a$ to execute before rule $b$ with a specific weight $w$. These opinions are treated as simple support functions and combined using Dempster’s Rule of Combination.

A critical contribution of the paper is the argument for using Plausibility (Pl) rather than Belief (Bel) as the primary metric for selecting an agenda. In D-S theory, Belief is often too restrictive; if even one piece of evidence contradicts an agenda, its Belief score drops to zero. Plausibility is more stable, allowing for a nuanced ranking even when contradictions exist.

Comparison of Plausibility scores for different rule permutations across three models.

As shown in the table above, Plausibility scores degrade gracefully across different permutations ($\pi$), providing a continuous measure of quality that avoids the "all-or-nothing" pitfalls of standard Belief measures.

Graph-Theoretic Formulation

The paper makes a significant bridge between AI control logic and classical graph theory. By representing pairwise preferences as directed arcs in a graph, the task of resolving preference loops (e.g., $a > b, b > c, c > a$) is transformed into a graph optimization problem.

Graph representation of rule execution preferences with weighted edges.

The author proves that maximizing the Plausibility of an agenda is mathematically equivalent to solving the Weighted Feedback Edge-Set problem. In this context, the goal is to find an ordering that minimizes the total weight of "violated" preferences (edges that point backward in the agenda).

The Approximation Algorithm

Because the Weighted Feedback Edge-Set problem is NP-complete, finding the absolute best agenda is computationally prohibitive for large rule sets. To address this, Barnett introduces a "hill-climbing" style approximation algorithm. This algorithm iteratively moves rules within the agenda to find local optima, effectively breaking cycles by removing the "lightest" conflicting edges.

Empirical evaluations using randomly generated test cases (with $n$ ranging from 3 to 200) showed that the algorithm runs in approximately $O(n^3)$ time. This makes it practical for real-world expert systems where exhaustive search ($n!$) is impossible. Furthermore, the variance in Plausibility between different starting points was minimal, suggesting the local optimization is robust at finding near-optimal solutions.

Key Insights and Stability

One of the paper's most practical insights is the "measure of stability" provided by local optima. The author notes that sub-agendas of locally optimal agendas are themselves locally optimal. This property is vital for dynamic environments; if a system is interrupted or needs to replan mid-stream, the remaining portion of the agenda remains high-quality, allowing for economical re-optimization.

Limitations and Future Work

While the model is robust, it relies on the assumption that weights ($w$) for opinions are pre-defined, leaving the question of how to derive these weights to future research. Additionally, the model focuses on pairwise preferences, which may not capture more global constraints, such as limits on the total number of rules of a specific type that can be executed in sequence. Despite these limitations, the work provides a rigorous mathematical foundation for conflict resolution in complex rule-based systems.

Summary updated

BibTeX
@inproceedings{barnett1991combining,
  author = {Jeffrey A. Barnett},
  title = {{Combining Opinions About the Order of Rule Execution}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure