ACP: Reason Maintenance and Inference Control for Constraint Propagation Over Intervals

Walter HamscherAAAI 1991

In the early 1990s, AI researchers faced a significant challenge: making automated reasoning both precise and efficient when dealing with numeric ranges. Walter Hamscher’s 1991 paper, "ACP: Reason Maintenance and Inference Control for Constraint Propagation Over Intervals," introduced Assumption-based Constraint Propagation (ACP). This system addresses a fundamental problem in knowledge representation—maintaining logical consistency as numeric intervals are iteratively refined.

The Challenge of Interval Reasoning

Consider a financial model where sales are estimated between \$1M and \$1.2M. As new data arrives, this range might narrow to \$1.1M–\$1.15M. In a standard reasoning system, this refinement creates several issues:

  1. Subsumption: Narrower intervals make wider ones redundant, but the wider ones must be preserved if the assumptions leading to the narrower range prove false.
  2. Redundancy: Algebraic constraints (e.g., $A = B + C$) can be solved in multiple directions, leading to redundant computations.
  3. Reflection: Circular reasoning where a variable's value is used to derive itself, potentially causing infinite loops.

The ACP Architecture

ACP integrates interval constraint propagation with an Assumption-based Truth Maintenance System (ATMS). It employs several novel techniques to manage the complexity of interval updates.

Shadowing and Label Updates

Instead of deleting wider intervals, ACP "shadows" them. A node is considered active only if no more specific (narrower) interval exists in the current context. This allows the system to focus on the most precise data while maintaining the underlying logical dependencies.

Trace of node and label updates illustrating the shadowing technique.

Essential Support Sets (ESS)

To prevent "reflection" or circularity, ACP calculates an Essential Support Set (ESS) for every deduction. The ESS is a list of nodes that are strictly necessary for a deduction to hold. If a variable's own previous state appears in its ESS, the system identifies a circular dependency and terminates that line of reasoning.

Experimental Evaluation

The authors evaluated ACP using real-world financial models, ranging from 116 to 158 variables across multiple logical contexts. The goal was to determine which combination of control strategies—Shadowing (S), Essential Support (E), and Dependency-based pruning (D)—offered the best performance.

Execution time in seconds across different control strategies.

The results demonstrated that the ESS (E) strategy is particularly effective. It significantly reduced the number of intermediate bindings while maintaining a runtime nearly as fast as systems with no reflection checking. While the number of shadowing justifications could theoretically grow quadratically, empirical tests showed near-linear scaling ($1.5k$), proving ACP's viability for complex, real-world applications.

Conclusion

ACP represents a milestone in combining qualitative logical reasoning with quantitative interval constraints. By distinguishing between "true" and "active" facts and using heuristic checks like ESS, it tames the combinatorial explosion inherent in constraint satisfaction problems, providing a robust framework for financial analysis and beyond.

Summary updated

BibTeX
@inproceedings{hamscher1991acp,
  author = {Walter Hamscher},
  title = {{ACP: Reason Maintenance and Inference Control for Constraint Propagation Over Intervals}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure