Using Constraints to Model Disjunctions in Rule-Based Reasoning

Bing Liu, Joxan JaffarAAAI 1996

Abstract

Traditional forward-chaining rule-based systems, while effective for deterministic "If-Then" reasoning, often struggle to handle logical disjunctions. When faced with partial information—such as knowing that either fact $A$ or fact $B$ is true without knowing which—standard systems typically fail to trigger relevant rules or require an inefficient explosion of rule permutations. This paper introduces CFR (Constraint Forward Reasoning), a framework that integrates Constraint Satisfaction Problem (CSP) techniques into forward-chaining engines. By representing disjunctions as constraint variables with discrete domains, CFR allows for reasoning over ambiguous data, supports complex "what-if" searches, and maintains efficiency through arc-consistency algorithms.

Introduction

Rule-based expert systems have long served as a cornerstone of artificial intelligence, particularly in domains requiring high-level knowledge representation. However, their reliance on explicit facts in working memory creates a significant limitation: the inability to handle disjunctions ($A \vee B$) effectively. In a standard system, a rule requiring $A$ will not fire if the system only knows $A \vee B$. While Constraint Logic Programming (CLP) addressed similar issues for backward-chaining languages like Prolog, a robust equivalent for data-driven, forward-chaining systems has been largely absent. This paper proposes a hybrid architecture that treats disjunctions not merely as logical operators, but as data structures within a constraint-solving framework.

The Problem of Disjunctions in Forward Chaining

In traditional logic, if a system knows $A \vee B$ and possesses the rules "If $A$ then $C$" and "If $B$ then $C$," it should logically conclude $C$. However, a forward-chaining engine typically looks for an exact match in its working memory. To handle this, developers often resort to writing redundant rules or manually splitting the search space, both of which lead to maintenance difficulties and combinatorial explosions in complex domains. The challenge lies in allowing the system to reason with "partial information" without prematurely branching the search.

Methodology: The CFR Framework

1. CSP-Disjunctions

The authors redefine disjunctions as constraint variables with specific domains. They categorize these into two types:

  • Exclusive ($\oplus$): Exactly one atom in the set is true (e.g., a person is either a teacher or a soldier, but not both).
  • Inclusive ($\vee$): At least one atom in the set is true (e.g., a person’s friends are a subset of a known group).

2. Integrated Architecture

The CFR prototype, implemented in Common Lisp, consists of three primary components:

  • Working Memory: A unified repository for traditional facts, disjunctive variables, and constraints.
  • Rule Interpreter: A forward-chaining engine that processes standard logic.
  • Constraint Solver: An engine utilizing arc-consistency algorithms (such as AC-3 and AC-5) to prune the domains of disjunctive variables.

3. Bidirectional Interaction

The core innovation of CFR is the synergy between the rule engine and the constraint solver. Rule chaining can generate new constraints or prune the domains of existing variables. Conversely, when the constraint solver narrows a variable's domain to a single value through propagation, that value is promoted to a "certain fact," which can then trigger further rules. This creates a feedback loop that automates deductions that would otherwise require manual intervention.

Because local consistency (arc consistency) does not always guarantee a global solution, CFR includes a choice-making mechanism. The system can make a "guess" on a variable's value, push the current state onto a choice stack, and proceed. If a logical contradiction is reached (e.g., a variable's domain becomes empty), the system backtracks to the last valid state.

Key Insights

Disjunction as Data

By treating an "OR" statement as a variable rather than a control-flow split, CFR maintains a single, ambiguous state. This allows the system to defer expensive branching until absolutely necessary, significantly improving search efficiency.

Partial Information Testing

CFR introduces specialized functions like test_in. This allows a rule to fire if the potential values of a variable fall within a specific set, even if the final value is not yet determined. This enables the system to make high-level deductions based on the boundaries of what is possible.

Forward-Chaining Advantage

Unlike CLP, which is goal-driven, CFR is data-driven. This makes it more suitable for real-time expert systems where the goal is to see what conclusions can be drawn from a changing set of initial facts, rather than proving a specific hypothesis.

Results and Discussion

The authors demonstrated CFR using a complex reasoning task involving professors, their academic degrees, and the subjects they teach. The system successfully performed automatic deductions, such as identifying that if two professors are constrained to teach the same subject, any restriction placed on one professor's domain must immediately propagate to the other.

Key results include:

  • Efficiency: The use of AC-5 for domain pruning effectively mitigated the combinatorial explosion typically associated with disjunctive reasoning.
  • Expressiveness: The system handled natural language-style constraints (e.g., "If John or Albany is the capital...") that traditional forward-chaining systems cannot process without significant workarounds.

Limitations and Future Work

While CFR represents a significant step forward, the authors identify several areas for improvement. The current prototype is primarily optimized for disjunctions that share a similar predicate structure (e.g., differing only in their final argument). Furthermore, the system assumes that the user will not introduce direct logical contradictions (e.g., $A$ and $\neg A$), as the current solver focuses on constraint consistency rather than general logical consistency. Future research will focus on expanding the framework to handle more generalized constraints and larger-scale performance benchmarking.

Summary updated

BibTeX
@inproceedings{liu1996using,
  author = {Bing Liu and Joxan Jaffar},
  title = {{Using Constraints to Model Disjunctions in Rule-Based Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure