Abstract
This paper presents a formal extension of the Situation Calculus to incorporate knowledge-producing actions, such as sensing and reading, while providing a robust solution to the frame problem. By integrating Moore’s possible-worlds semantics with Reiter’s successor state axioms, the authors introduce a single epistemic axiom that governs how an agent’s knowledge evolves. This framework ensures that agents can reason about their own learning processes, maintain memory over time, and distinguish between actions that change the world and actions that merely provide information.
1. Introduction
In classical artificial intelligence planning, the Frame Problem represents the challenge of efficiently representing the persistence of facts. When an agent performs an action, most properties of the world remain unchanged; however, a purely logical approach often requires an exhaustive list of "frame axioms" to confirm these non-changes. Raymond Reiter previously addressed this for physical actions using successor state axioms, which provide a compact way to describe the necessary and sufficient conditions for a property (a fluent) to change.
However, autonomous agents do not only interact with the world physically; they also perform sensing actions. Reading a document or checking a sensor changes the agent's knowledge without altering the physical state of the environment. Prior to this work, there was no unified way to integrate these knowledge-producing actions into the Situation Calculus without reintroducing the complexities of the frame problem for the agent's internal state. This paper bridges that gap.
2. Formal Framework
The authors combine two distinct traditions in AI: Reiter’s Situation Calculus (a logic for representing change) and Moore’s Possible-Worlds Semantics (a logic for representing knowledge).
2.1 The Epistemic Fluent ($K$)
The core of the proposal is the introduction of a binary epistemic fluent, $K(s', s)$. This relation is interpreted as: "Situation $s'$ is considered possible by the agent when they are actually in situation $s$." An agent is said to "know" a proposition if that proposition holds true in every situation $s'$ that is $K$-related to the current situation $s$.
2.2 The Successor State Axiom for Knowledge
The paper’s primary innovation is the successor state axiom for $K$. This axiom defines the $K$ relation in a successor situation, $do(a, s)$, based on the previous situation $s$ and the action $a$:
- Physical Actions: If $a$ is a standard action (e.g.,
move), the agent updates their possible worlds by assuming the action occurred in all of them. This ensures the agent knows the action was performed. - Sensing Actions: If $a$ is a sensing action (e.g.,
sense_p), the agent filters their possible worlds. Only those situations $s'$ where the truth value of $p$ matches the actual truth value of $p$ in the current reality are retained. This effectively "prunes" the agent's uncertainty.
3. Reasoning and Regression
To make this logic computationally useful, the authors extend the technique of regression. Regression allows a complex query about a future situation to be transformed, step-by-step, into a query about the initial state ($S_0$). By proving that knowledge-based queries can be regressed, the authors demonstrate that an automated reasoner can determine if an agent will know something after a sequence of actions (e.g., "Will I know the safe combination after I read the note?") by looking only at the starting conditions and the logic of the actions.
4. Key Insights and Properties
The framework yields several elegant properties that simplify the design of intelligent agents:
- Emergent Memory: Memory is not a separate programmed feature. Because of the way the $K$ fluent is updated, facts known in situation $s$ naturally persist into $do(a, s)$ unless an action specifically alters the truth of that fact. The agent "remembers" by default.
- Physical/Epistemic Separation: The authors formally prove that knowledge-producing actions have no effect on physical fluents. Merely observing a system does not change its physical properties, solving the "frame problem" for sensing.
- Persistence of Introspection: If an agent’s knowledge base starts with certain logical properties—such as positive introspection (knowing that you know)—the successor state axiom ensures these properties are preserved through any sequence of actions.
- Unified Planning: By treating knowledge as a fluent, agents can treat "getting information" as a prerequisite for other actions. An agent can plan to "go to the library to find the map" because it can reason about the epistemic state it will reach after the sensing action.
5. Conclusion and Future Work
The paper provides a rigorous foundation for agents that must both act and learn. While highly influential, the authors note several areas for expansion. The current model focuses on knowledge (which is necessarily true) rather than belief (which may be corrected). Transitioning to a theory of belief requires handling cases where an agent's observations contradict their prior assumptions. Additionally, the framework is currently limited to a single agent and does not account for indexical knowledge (e.g., "I am here now") or multi-agent epistemic reasoning.
Summary updated