Extending Reflective Architectures

Timothy M. LownieIJCAI 1989

Introduction

Automated theorem proving in first-order logic (FOL) has long been plagued by the "search-explosion" problem. While general-purpose inference engines are theoretically capable of solving complex problems, they often succumb to search-intensive processes, wasting significant computational resources exploring irrelevant logical paths. To mitigate this, researchers have explored "reflective" or "introspective" architectures—systems capable of reasoning about their own internal states to guide their search. However, implementing these in full FOL has historically faced two major hurdles: the complexity gap between the controller and the controlled process, and the syntactic fragility introduced by standard clausal forms.

In "Extending Reflective Architectures," Timothy M. Lownie proposes a novel framework to overcome these barriers. By utilizing a hierarchy of meta-circular processors and non-clausal resolution, the paper outlines a system that can declaratively reason about and optimize its own inference strategies without losing the semantic richness of the original problem.

The Architecture: A Tower of Meta-Circular Processors

The core of the proposed system is a Tower of Meta-Circular Processors (MCPs). This architecture organizes logic into a hierarchical stack ($L_0, L_1, L_2, \dots$):

  • $L_0$ (The Object Level): Contains the primary domain facts and rules (e.g., a specific knowledge base about family lineages).
  • $L_1$ (The Meta-Level): A meta-theory that describes the rules of engagement and inference strategies for $L_0$.
  • $L_2$ and beyond: Higher levels that describe how to reason about the level immediately below them.

This "procedural reflection," inspired by the work of Brian Cantwell Smith, treats the inference engine not as an opaque black box, but as a transparent program. Because each level $k$ is defined by the program at level $k+1$, the system's entire search behavior—such as switching from a depth-first search to a breadth-first search—can be altered simply by adding declarative sentences to a higher level of the tower.

Preserving Structure with Non-Clausal Resolution

A significant innovation in Lownie’s framework is the move away from traditional clausal form. Most provers force logical sentences into a rigid format of "OR" statements (clauses), which often destroys the original structure and semantic context of the problem. This makes it difficult for a control strategy to recognize patterns.

To solve this, the architecture employs Non-Clausal (NC) Resolution. NC-Resolution allows the system to maintain the original "shape" of logical sentences. For example, a definition for "Ancestor" remains recognizable as such, rather than being fragmented into disparate clauses. This structural preservation is vital for applying human-like strategies, such as prioritizing specific relational traversals over exhaustive search.

Connection Graphs and Control

Within this tower, the system organizes sentences into a connection graph. In this model, edges represent potential logical steps or resolvents. The task of "control" is redefined as the selection of edges within this graph. By representing the search space as a graph, the meta-level can use secondary inferences to identify the most promising edges to follow.

This approach provides several key advantages:

  1. Negation as a Control Tool: By supporting full FOL, the meta-level can explicitly represent negation. It can use this to prune the search tree by stating, "do NOT explore this path if property X is true."
  2. Unified Control: Both general search strategies (like BFS/DFS) and domain-specific heuristics are expressed through the same mechanism: indexing and selecting edges in the connection graph.
  3. Theory Resolution: The framework allows for the integration of specialized procedures, such as taxonomic reasoning, into the general engine as "subsidiary deduction rules."

Conclusion and Future Directions

Lownie’s work provides a formal blueprint for a reflective system that supports highly selective inference. By maintaining the semantic context of the knowledge base and providing a clear hierarchy for meta-reasoning, the architecture offers a path toward more efficient automated reasoning.

However, the paper acknowledges that "reasoning about reasoning" is not free. The primary limitation is the computational overhead incurred whenever the system pauses to decide its next move. While the framework demonstrates how to achieve unified control and deductive completeness, the practical challenge of minimizing this overhead remains a focus for future implementation and research. The transition from a theoretical "tower of logic" to a high-performance automated prover requires balancing the expressive power of the meta-levels with the raw efficiency of the underlying inference engine.

Summary updated

BibTeX
@inproceedings{lownie1989extending,
  author = {Timothy M. Lownie},
  title = {{Extending Reflective Architectures}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure