Reasoning about Noisy Sensors and Effectors in the Situation Calculus

By Fahiem Bacchus, Joseph Y. Halpern, Hector J. Levesque. 1995

Abstract Agents interacting with an incompletely known world need to be able to reason about the effects of their actions, and to gain further information about that world they need to use sensors of some sort. Unfortunately, both the effects of actions and the information returned from sensors are subject to error. To cope with such uncertainties, the agent can maintain probabilistic beliefs about the state of the world. With probabilistic beliefs the agent will be able to quantify the likelihood of the various outcomes of its actions and is better able to utilize the information gathered from its error-prone actions and sensors. In this paper, we present a model in which we can reason about an agent's probabilistic degrees of belief and the manner in which these beliefs change as various actions are executed. We build on a general logical theory of action developed by Reiter and others, formalized in the situation calculus. We propose a simple axiomatization that captures an agent's state of belief and the manner in which these beliefs change when actions are executed. Our model displays a number of intuitively reasonable properties.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Situation Calculus: A Case for Modal Logic (2010, background): “Besides knowledge and time, which we will turn to in a moment, there have been a number of other extensions of the situation calculus, dealing with issues like concurrency [44] or probabilities [1].”
PREGO: An Action Language for Belief-Based Cognitive Robotics in Continuous Domains (2014, methodology): “As argued in (Bacchus, Halpern, and Levesque 1999), the same representational limitations also apply to most probabilistic formalisms, such as Kalman Filters and Dynamic Bayesian Networks (Boyen and Koller 1998).11 Finally, recent work on relational probabilistic languages (Richardson and Domingos…”
How to Progress Beliefs in Continuous Domains (2014, methodology): “The unrestricted nature of the speciﬁ-cation of the p ﬂuent, for example, which we inherit from (Bacchus, Halpern, and Levesque 1999), allows for agents whose beliefs are not determined by a unique distribution.”
A Logical Theory of Localization (2015, background): “and ψ denotes (v + tan θ ∈ [1, 2]) ∨ (v + tan θ ∈ [3, 4]) ∨ (v + tan θ ∈ [7, 8]).”
Reasoning about Deterministic Actions with Probabilistic Prior and Application to Stochastic Filtering (2010, methodology): “Current approaches to probabilistic ﬁltering with PDDL or situation calculus (e.g., (Reiter 2001; Bacchus, Halpern, and Levesque 1999; Hajishirzi and Amir 2008)) use traditional ﬁltering methods as subroutines for reasoning about sequences of deterministic actions with probabilistic priors.”
A First-Order Logic of Probability and Only Knowing in Unbounded Domains (2016, background): “Similarly, in a robotic setting (Bacchus, Halpern, and Levesque 1999), some outcomes are more likely than others, perhaps due to error prone actuators.”
ALLEGRO: Belief-Based Programming in Stochastic Dynamical Domains (2015, methodology): “…a logical account for reasoning about probabilistic degrees of ∗Partially funded by the FWO project on Data Cleaning and KU Leuven’s GOA on Declarative Modeling for Mining and Learning. belief against noise in a continuous setting, building on an earlier discrete model [Bacchus et al., 1999].”
Reasoning about Probabilities in Unbounded First-Order Dynamical Domains (2017, background): “The first-order nature of the logic allows us to capture domains quite beyond standard probabilistic formalisms − see [Bacchus et al., 1999; Belle and Levesque, 2015], for example − but to illustrate the features of the language, we will focus on two variants using a simple 1-dimensional robot.”