Belief change with noisy sensing in the situation calculus

Jianbing Ma, Weiru Liu, Paul MillerUAI 2011

TL;DR

This paper tackles the challenge of agents reasoning about dynamic environments when their sensors are unreliable. They extend the situation calculus framework to handle "noisy sensing" by adjusting the plausibility of different world states rather than discarding them, enabling more robust belief updates and reasoning.

What Problem Does This Paper Address?

Reasoning about dynamic environments is crucial for intelligent agents. The situation calculus is a powerful formal language for this, but it traditionally assumes perfect sensing. In real-world scenarios, sensors are often noisy, meaning they can provide incorrect information. Previous work on belief change within the situation calculus, like Shapiro et al. [22], assumed accurate sensing. When faced with noisy sensor data, these frameworks can lead to inconsistencies, forcing the agent to stop reasoning. For example, if an agent senses a light is "on" but the true state is "off," a framework that discards states not matching the sensor reading might incorrectly eliminate the true state, leading to an unresolvable paradox. This paper aims to bridge this gap by developing a framework that can gracefully handle noisy sensing actions.

Methods

The core of this paper's contribution lies in extending the situation calculus with a non-fixed plausibility operator. Instead of discarding situations that don't match a sensor reading (as in prior work), their approach adjusts the "plausibility value" of these situations. This is achieved by introducing a successor state axiom for plausibility. When a sensing action is performed:

  • If the sensor reading matches the situation, the plausibility of that situation's successor is increased (meaning its rank decreases).
  • If the sensor reading doesn't match, the plausibility of that situation's successor is decreased (its rank increases).

This flexible adjustment of plausibility values allows the framework to retain all possible situations, even those that initially seem inconsistent with sensor readings. This prevents the agent from reaching an unresolvable state of inconsistency. The paper also redefines the belief operator to reflect this new plausibility mechanism, ensuring that beliefs are held at the most plausible situations.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Noisy Sensing Doesn't Necessarily Halt Reasoning: The most significant insight is that noisy sensing doesn't have to lead to an agent's reasoning capabilities being completely shut down. By adjusting plausibilities instead of discarding states, the agent can continue to reason.
  • Rarity of Noise is Key: The paper demonstrates that if noisy sensing actions are rare (i.e., the ratio of noisy to accurate sensing is small), an agent can still reliably detect the actual situation in the long run. Even when noise is more frequent, there's still a chance to identify the true state.
  • Unified Framework for Belief Change: The proposed framework elegantly handles various forms of belief change, including nested beliefs, belief introspection, mistaken beliefs, belief revision, and belief update, all within a single, coherent system.
  • Subsumption of Prior Work: When all sensing actions are accurate, the proposed framework produces the same beliefs as the prior work by Shapiro et al. [22], demonstrating its generality and correctness.

Key Results

The paper presents several theoretical results:

  • Noisy Sensing Tolerance: The framework is shown to tolerate noisy sensing. Specifically, if the probability of noisy sensing actions is low, the agent can eventually detect the actual situation with high probability. Even with frequent noisy sensing, there's a non-negligible chance of identifying the true state.
  • Belief Introspection: The framework supports positive and negative belief introspection, meaning an agent can reason about its own beliefs and lack thereof.
  • Belief Revision and Update: The paper proves that belief revision and update, crucial for adapting beliefs to new information, are handled adequately by the framework. For instance, if a sensing action indicates a proposition is true, the agent will believe it after the action.

Limitations and Future Work

  • Space Limitation: The authors mention that due to space limitations, they haven't provided detailed comparisons with various existing belief change postulates (e.g., AGM, KM, DP). However, they assert that their framework satisfies most of these postulates, particularly DP's C2 postulate, which was not definable in prior work.
  • Multiple Agents: The current framework is designed for a single agent. Extending it to handle multiple agents is identified as a key area for future work.
  • Realizing Past Errors: Investigating whether an agent can realize that a previous sensing action was inaccurate (a form of belief introspection related to error detection) is another promising future direction.
  • Connection to POMDPs: The authors suggest exploring the relationship between their framework and Partially Observable Markov Decision Processes (POMDPs), which are relevant for sequential decision-making under uncertainty.

Summary updated

BibTeX
@inproceedings{ma2011belief,
  author = {Jianbing Ma and Weiru Liu and Paul Miller},
  title = {{Belief change with noisy sensing in the situation calculus}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure