Introduction
In the development of artificial intelligence during the 1980s, the "frame problem"—the challenge of representing how most facts remain unchanged after an action—stood as a significant hurdle. John McCarthy’s theory of circumscription emerged as a primary solution, offering a formal method for non-monotonic reasoning by minimizing the extension of "abnormality" predicates. However, traditional circumscription faced two primary obstacles: the mathematical complexity of second-order logic and a lack of flexibility in handling priorities, such as the preference for earlier events in temporal reasoning.
In "Pointwise Circumscription: Preliminary Report," Vladimir Lifschitz introduces a novel framework that addresses these issues by shifting from a global minimization strategy to a "pointwise" approach.
The Shift to Pointwise Minimization
Traditional circumscription is "global" in that it seeks models where a predicate $P$ is minimal across its entire extension. Lifschitz proposes instead that we consider minimization at individual points. Under this view, a predicate $P$ is minimized if, for every point $x$, it is impossible to change the value of $P(x)$ from true to false without violating the underlying axioms.
This shift is formally represented as an infinite conjunction of local conditions, typically expressed through universal quantification ($\forall x$). By focusing on individual points, the framework allows for a more granular control over how and where predicates are allowed to vary.
Methodology and Axiomatized Policies
A core innovation of this paper is the introduction of "variable domains" and "axiomatized policies."
Variable Domains
Pointwise circumscription allows other predicates or functions to vary only on specific parts of their domain during the minimization process. This is achieved using $\lambda$-expressions, which specify the exact coordinates where a predicate is permitted to "wiggle" or change value to accommodate the minimization of the target predicate.
Policies as Axioms
Perhaps the most significant contribution is the integration of reasoning policies directly into the logic. In previous iterations of circumscription, priorities (e.g., "prefer the past") were often handled via metamathematical policies external to the logical system. Lifschitz introduces a policy predicate ($V$) that allows these priorities to be written as standard axioms. For example, an axiom can specify that when minimizing a predicate at time $t$, the system is only allowed to vary values at future times $t' > t$.
Key Insights
The pointwise approach yields several theoretical and practical advantages:
- First-Order Equivalence: Lifschitz demonstrates that in many common cases—specifically when the minimized predicate appears only "positively" in the axioms—pointwise circumscription is equivalent to global circumscription. Crucially, this version can be expressed in first-order logic, making it significantly more accessible for automated theorem provers.
- Modularity: The framework is inherently modular. Users can define distinct minimization strategies for every predicate within a system, rather than applying a single, monolithic minimization rule.
- Solving Temporal Challenges: The paper specifically addresses the temporal reasoning challenges posed by Hanks and McDermott. By utilizing a policy axiom that permits variation only in the "future" relative to the point of minimization, the logic naturally selects intuitive models where changes occur as late as possible.
Results and Theoretical Unification
The paper proves that pointwise circumscription is not merely a new tool but a unifying framework. Lifschitz shows that both parallel (joint) minimization and prioritized minimization can be treated as special cases of the pointwise approach.
The report culminates in a "General Case" formula (Formula 11), which provides a unified definition for minimizing any predicate or function symbol while allowing for arbitrary variation on other symbols. This formula serves as a foundational definition for the new theory.
Conclusion and Future Directions
While "Pointwise Circumscription: Preliminary Report" provides a robust theoretical foundation, it remains a preliminary work. The author notes that full mathematical proofs were reserved for future publications. Furthermore, while the framework allows for policies to be defined as axioms, the selection of these policies still involves a degree of trial and error. Nonetheless, by bringing priorities into the logic itself and simplifying the computational requirements through first-order logic, Lifschitz's work represents a major step forward in the formalization of common-sense reasoning.
Summary updated