Abstract
In early symbolic AI, Reason Maintenance Systems (RMS) were primarily designed for discrete logical assertions. This paper presents an extension of these systems to accommodate numerical inequalities and interval-based reasoning. By utilizing "memterms" and prioritized "signal functions," the proposed architecture maintains dependencies for continuous values without the overhead of total belief retraction, enabling efficient updates in spatial and temporal reasoning domains.
Introduction
Traditional Reason Maintenance Systems (RMS) manage evolving databases of beliefs by tracking dependencies. If a conclusion $C$ is derived from premises $A$ and $B$, the retraction of $B$ necessitates the removal of $C$. While effective for discrete logic, this "all-or-nothing" approach is poorly suited for numerical inequalities. For instance, if $X > 10$ is believed because $X = 15$, deleting the specific fact $X = 15$ should not necessarily invalidate $X > 10$ if other supporting evidence (e.g., $X = 12$) exists.
McDermott (1983) addresses this by developing a system that handles "fuzzy" intervals and coordinate shifts efficiently, ensuring that minor numerical updates do not trigger catastrophic erasures of valid logical conclusions.
Methods: Memterms and Data-Dependency Nodes
The core of the system relies on several abstractions designed to bridge discrete logic and continuous values:
- The
ddnode(Data-Dependency Node): These represent assertions equipped with "signal functions." When a node's status changes (e.g., from believed to not believed), it triggers code to handle the transition. - Memterms (Memory Terms): These structures represent numerical variables. They store Weak Values (
wvals), which are assertions that a value lies within a specific interval, and Strong Values (svals), which represent the narrowest known interval.
As shown in the figure above, a derivation like $A = B + C$ is managed through a DD-note that links the intervals of the constituent variables. The system computes the intersection of all active wvals to determine the current belief about a variable's range.
- Prioritized Agendas: To manage updates, signal functions are placed in a prioritized queue. High-priority tasks involve recomputing bounds to verify if an inequality still holds, while lower-priority tasks handle background maintenance. This prioritization allows the system to "patch" a belief before dependent logic is affected.
Key Insights: The Infinite Proofs Problem
A significant challenge in numerical reasoning is that an inequality like $X > 4$ can be supported by an infinite number of specific values. Listing every possible proof is impossible. McDermott’s solution is to use the RMS to trigger a "re-deduction" only when the current proof fails.
The figure illustrates how a specific numerical range for an income leads to a generalized inequality, which then supports a logical fact (e.g., "Fred is rich"). If the specific range $N1$ changes, the system re-evaluates $N2$ rather than immediately discarding $N3$.
Furthermore, the paper introduces the concept of Invariants via Queues. By processing the recomputation queue in a strict order, the system ensures that the database remains consistent from the perspective of lower-level logic, even during volatile numerical updates.
Results and Implementation
The system was implemented in NISP and applied to spatial and temporal reasoning tasks at Yale. Key results include:
- Robustness: The architecture successfully extended data-dependency techniques to numerical domains without requiring a complete redesign of the underlying RMS.
- Efficiency: Prioritized signal functions effectively "hide" numerical volatility, preventing unnecessary re-indexing of facts when coordinates shift slightly.
Limitations
Despite its successes, the system faces challenges with circular derivations (e.g., $A=B+C$ and $B=A-C$), which it currently avoids by assuming a non-circular tree structure. Additionally, in complex models, the system relies on heuristics to find "good" derivations that yield narrow, useful intervals rather than trivial, wide ones. Managing these heuristics and queue priorities remains a complex task for the developer.
Summary updated