An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

John Grant, Francesco Parisi, Austin Parker, V. S. Subrahmanian*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form "Object o is/was/will be in region r at time t with probability in the interval [ℓ, u]". In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.

Original languageEnglish (US)
Pages (from-to)72-104
Number of pages33
JournalArtificial Intelligence
Issue number1
StatePublished - Jan 2010
Externally publishedYes


  • Belief revision
  • Reasoning about motion
  • Spatio-temporal logics
  • Uncertainty management

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'An AGM-style belief revision mechanism for probabilistic spatio-temporal logics'. Together they form a unique fingerprint.

Cite this