Radial Restraint: A Semantically Clean Approach to Bounded Rationality for Logic Programs

Benjamin Nathan Grosof, Terrance SwiftAAAI 2013 · DOI

In the field of Declarative Logic Programming (LP), there has long been a tension between the expressive power of logical functions and the practical need for computational decidability. While functions like father(father(X)) are essential for representing recursive structures, they can create an infinite "Herbrand universe," leading inference engines into infinite loops.

Presented at AAAI 2013, "Radial Restraint" offers a formal framework for "bounded rationality" that resolves this conflict without sacrificing logical soundness.

The Problem: Unsoundness in Modern Logic Systems

In practice, developers often manage infinite recursion using "hacks" such as timeouts or term-depth limits. When an engine hits these limits, it typically treats the result as "False." However, in systems using Well-Founded Semantics (WFS), this approach is dangerous.

Because WFS supports negation-as-failure, incorrectly labeling a complex term as "False" can lead the system to conclude that its negation is "True." This results in unsoundness, where the system provides logically incorrect answers simply because it reached a resource limit. Radial Restraint addresses this by introducing a semantically sound way to handle complexity bounds.

The Radial Restraint Framework

Radial Restraint is parameterized by a "norm" (a measure of term complexity, such as depth) and an abstraction function. The core mechanism involves two primary steps:

  1. Abstraction and Undefinedness: When a term exceeds a predefined complexity bound (the "radius"), it is replaced by an abstraction using position variables. Crucially, instead of being marked False, these abstracted atoms are assigned the truth value undefined.
  2. SLG$_{ABS}$ Resolution: The authors extended standard SLG resolution to incorporate these abstractions. This new algorithm, SLG$_{ABS}$, performs both "subgoal abstraction" and "answer abstraction" to ensure termination.
The SLG_ABS resolution forest illustrates how different subgoals interact and where undefined abstractions are introduced to maintain decidability.

Key Insights: The "Third Value" Solution

The fundamental breakthrough of this approach is using the WFS "undefined" value to represent terms that are "too complex to compute." This preserves logical integrity where binary (True/False) systems fail. By treating abstracted variables as universally quantified, a single "undefined" sentence can represent an infinite set of complex terms.

This detail of a resolution tree shows a term exceeding the radius being abstracted to an 'undefined_abs' value, preventing an infinite loop while remaining logically sound.

Furthermore, if the chosen norm is "finitary" (meaning only a finite number of terms exist below any given bound), the system is guaranteed to reach a fixed point and terminate. This effectively transforms an undecidable problem into a decidable one.

Empirical Results and Scalability

The method was implemented in the XSB Prolog engine and evaluated against large-scale datasets, including college-level cell biology data from the SILK Project and the OpenRuleBench suite. Key findings include:

  • Performance: The overhead for maintaining depth-counters during answer abstraction was remarkably low, measured at only 0–4% in linear recursion benchmarks.
  • Scalability: The implementation successfully scaled to knowledge bases containing more than 100 million rules and facts.
  • Complexity: SLG$_{ABS}$ maintains the same asymptotic complexity as the best-known algorithms for WFS (worst-case quadratic in the size of the ground-instantiated rulebase).

Conclusion and Future Directions

Radial Restraint provides a robust foundation for resource-managed AI agents. While it guarantees decidability and soundness, future work remains in automating the selection of optimal bounds ($k$) and developing "justification mechanisms" to help users understand why a specific result was returned as undefined. By integrating these syntactic bounds with wall-clock timeouts, researchers aim to create even more resilient logic-based reasoning systems.

Summary updated

BibTeX
@inproceedings{grosof2013radial,
  author = {Benjamin Nathan Grosof and Terrance Swift},
  title = {{Radial Restraint: A Semantically Clean Approach to Bounded Rationality for Logic Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8682},
}
Figure