Progressing Epistemic States through Sensing and Action

34 concepts25 papers

For an autonomous agent to operate effectively in a changing world, it must maintain an internal model of its environment. This model—the agent's epistemic state—cannot remain static. As the agent interacts with the world, its knowledge and beliefs must evolve.

In formal AI frameworks, this evolution is driven by two distinct types of interactions: ontic actions, which physically alter the state of the world (like moving a box), and epistemic actions, which alter the agent's internal state without changing the physical world (like reading a sensor). The core challenge of epistemic state progression is designing formalisms that allow an agent to update its beliefs efficiently, consistently, and accurately in response to both types of actions.

The Possible-Worlds View of Sensing

To understand how an epistemic state updates, it helps to view an agent’s knowledge through the lens of possible worlds. At any given moment, an agent may not know the exact state of the universe, but it can imagine a set of mutually exclusive possibilities—situations that are consistent with everything it has observed so far.

When an agent performs a physical action, every single one of these possible worlds changes according to the laws of physics. But when an agent performs a sensing action, the physical worlds themselves remain untouched. Instead, sensing acts as a filter.

As formalized by Scherl et al. and Lakemeyer et al., a sensing action provides an observation about the current situation. Upon receiving this information, the agent discards all possible worlds where the sensed property contradicts the observation. The agent's uncertainty shrinks because its epistemic state is pruned down to only those worlds that match reality. This foundational mechanism was integrated into early action description languages like $\mathcal{A}_k$ by the authors of Adding Knowledge to the Action Description Language A to explicitly model how information-gathering actions reduce environmental uncertainty.

The Frame Problem for Knowledge

In classical AI, the frame problem asks how to efficiently represent what does not change when an action occurs. When tracking knowledge, this problem becomes doubly complex: we must ensure that physical actions do not inadvertently destroy existing knowledge, and that sensing actions do not inadvertently alter physical facts.

Scherl et al. solved this by introducing a successor state axiom for epistemic fluents within the Situation Calculus. This axiom mathematically defines the accessibility relation between possible situations after any given action. It guarantees that if an agent knows a fact, and a physical action occurs that does not affect that fact, the agent continues to know it.

[Initial Epistemic State] 
       │
       ├─► Ontic Action (e.g., Move Box) ──► [Worlds shift physically; knowledge preserved]
       │
       └─► Epistemic Action (e.g., Sense) ─► [Worlds filtered; uncertainty reduced]

As systems scale to multi-agent environments or complex games, these axioms must also govern nested beliefs (e.g., "What does Player A think Player B knows?"). Belle et al. demonstrated that by treating information gain as a direct logical consequence of actions, an agent can dynamically derive complex information sets from the rules of the environment. However, tracking this information over time requires vigilance against stale data. To prevent an agent from relying on outdated observations, Traverso et al. introduced explicit propositions to track the "freshness" of information, automatically invalidating past sensor data the moment a physical action takes place.

Moving Forward: The Power of Progression

When an agent needs to evaluate what it knows in the present moment, it has two choices: look backward or compute forward.

  • Regression works backward. It takes a query about the current state and unwinds the entire history of actions until it reaches the initial state. While mathematically elegant, the computational cost grows with the history of the agent.
  • Progression computes forward. It calculates a brand-new knowledge base immediately after an action occurs, allowing the agent to discard the historical details.

For long-lived autonomous agents, progression is vital. Schwering et al. and Lakemeyer et al. formalized progression by redefining truth conditions so that an updated knowledge base represents a state of "only-knowing" the exact results of the latest action. This allows the agent to maintain a sharp, current representation of reality without re-evaluating its entire history.

However, planning with incomplete information and sensing actions is notoriously difficult. As Baral et al. noted, sensing actions force a planner to branch its strategy based on multiple potential observation outcomes, drastically increasing computational complexity. To keep progression tractable, researchers turn to knowledge compilation. Bienvenu et al. and Wan et al. showed that by compiling an agent's knowledge into specialized epistemic normal forms, updates can be processed in polynomial time. This transformation ensures that real-time decision-making remains feasible, even when operating without restrictive closed-world assumptions.

Unifying Logic with Noisy Realities

The possible-worlds model works perfectly when sensors are flawless, but real-world sensors are noisy and imperfect. To bridge this gap, classical logical frameworks must be unified with probabilistic reasoning.

Bacchus et al. and Bacchus et al. achieved this by assigning numerical weights to possible worlds within a logical structure. When an agent receives a noisy sensor reading, a successor-state axiom scales the weights of these worlds according to a likelihood function rather than completely eliminating them. This elegant formulation ensures that logical updates following an observation are mathematically identical to Bayesian conditioning.

[Possible Worlds with Weights] ──► [Noisy Observation] ──► [Axiom Scales Weights via Likelihood]

This interplay between logic and probability operates in both directions. While weights can quantify logical worlds, logical structures can also refine probabilities. Acar et al. demonstrated that observing a logical consequence within an ontology (such as a concept subsumption) serves as hard evidence that can prune inconsistent contexts, immediately sharpening the agent's remaining probability estimates. For complex, open-ended interactions like dialogue management, Lison showed that first-order logical rules can be applied directly to probabilistic belief states, aggregating probabilities across distributions to prune the action space and make decision-making scalable.

Correcting Mistakes: Belief Revision and Degradation

What happens when an agent's sensors mislead it, or the world changes while it isn't looking? A robust epistemic system must handle belief revision—the ability to recover when an observation flatly contradicts current beliefs.

Schwering et al. extended successor state axioms to conditional beliefs, providing formal rules for how an agent's internal model rewrites itself when confronted with surprising data. Rather than relying on heavy, specialized revision operators, Engesser et al. demonstrated that belief revision can be elegantly modeled through the dynamics of observation actions and conditional effects. When an agent initiates active observation of a misperceived fact, the transition logic automatically "flips" the internal belief status to align with reality.

Furthermore, Engesser et al. introduced a mechanism where knowledge degrades into mere belief the moment an active observation link is severed. This captures a vital intuition: an agent can be certain of a state while looking at it, but must acknowledge that its belief may become outdated once it turns away.

Finally, tracking these shifting mental states is not limited to an agent's internal perspective; it can also be used externally to track other entities. For instance, Sclar et al. applied these propagation mechanics to language models by maintaining explicit, recursive symbolic graphs of character beliefs. By automatically populating a character's local belief graph when they enter a new environment, the system successfully simulates the natural acquisition and progression of knowledge through observation.

Key Foundational Work

Reasoning about Noisy Sensors in the Situation Calculus (1995) — contributed 2 concept elements to this direction.
The Frame Problem and Knowledge-Producing Actions (1993) — contributed 2 concept elements to this direction.
Reasoning about Noisy Sensors (and Effectors) in the Situation Calculus (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_epistemic_state_progression_eb3ae2b6,
  title = {epistemic state progression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/epistemic-state-progression/rdr_eb3ae2b63c4f4582aeae1edb0c2b2a01},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_epistemic_state_progression_eb3ae2b6_v1,
  title = {epistemic state progression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/epistemic-state-progression/rdr_eb3ae2b63c4f4582aeae1edb0c2b2a01/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake