Abstract
Marianne Winslett's foundational research explores the problem of updating an artificial agent's beliefs when new information contradicts existing, potentially incomplete knowledge. This paper introduces a polynomial-time "Observation Algorithm" for belief revision, bridging the gap between complex logical semantics and efficient computation. By formalizing the update process through model-theoretic semantics, Winslett provides a method to "minimally change" a knowledge base while maintaining consistency across all possible worlds.
Introduction
In classical Artificial Intelligence, an agent maintains a Knowledge Base (KB) representing its understanding of the world. A fundamental challenge arises when the agent receives new information: how should the KB be updated? While simple updates are straightforward, the problem becomes significantly more complex when the agent's knowledge is incomplete or when new observations flatly contradict prior beliefs. This process, known as belief revision, requires the agent to prune false possibilities without inadvertently deleting unrelated information.
The Challenge of Incomplete Information
Consider an agent in a "Blocks World" scenario. If the agent knows "Block A is on Block B or Block C," and then learns "Block A is now on the floor," it must update its KB to reflect this new reality. Previous methods, such as Levesque’s TELL operation, were limited to information consistent with the existing KB. Winslett addresses the more realistic and difficult scenario where new observations may contradict the old state, requiring a principled approach to "minimal change."
The Observation Algorithm
Winslett formalizes the KB as an Extensional Belief Theory using first-order logic. To avoid the computational explosion of updating every possible world individually, she proposes a three-step syntactic algorithm:
- Make History: Atoms that might change are replaced with internal "history predicates" ($H_R$), effectively "freezing" the previous state.
- Define the Observation: The new information is added to the KB.
- Restrict the Observation: Logical formulas are added to ensure that the truth values of atoms only change if they were directly affected by the new observation, thereby preserving as much of the "old world" as possible.
Semantic Correctness and the Commutative Diagram
A key contribution of the paper is the "Commutative Diagram of Correctness." Winslett argues that a KB update algorithm is only correct if the result of updating the KB as a whole is identical to the union of results obtained by updating every possible world (model) the KB could represent.
This diagram illustrates the relationship between a theory $T$, its set of alternative worlds $\mathcal{A}$, and their respective updated states $T'$ and $\mathcal{A}'$ following an observation. The algorithm ensures that the path from $T$ to $T'$ via the Observation Algorithm matches the semantic transition from $\mathcal{A}$ to $\mathcal{A}'$.
Results and Complexity
The paper demonstrates that for KBs without Skolem constants (null values), the Observation Algorithm runs in $O(k \log R)$ time, where $k$ is the size of the new information and $R$ is the number of distinct atoms. This efficiency makes it comparable to standard database updates. Winslett provides a formal proof (Theorem 1) that the algorithm is both correct and complete relative to the intended "alternative worlds" semantics.
However, the paper also highlights the inherent complexity of incompleteness. While the algorithm is polynomial, the size of the KB can grow significantly if there are many unifications between new information and existing incomplete beliefs. Furthermore, the focus remains on extensional beliefs (direct observations); updating intensional beliefs (derived rules) remains a more difficult open problem.
Conclusion
Winslett’s work provides a rigorous framework for belief revision that balances logical soundness with computational feasibility. By using syntactic "tricks" like history predicates to achieve semantic results, the paper laid the groundwork for future research in knowledge representation and the management of evolving information systems.
Summary updated