Options
A history based approximate epistemic action theory for efficient postdictive reasoning
Publikationstyp
Journal Article
Date Issued
2015-12
Sprache
English
Author(s)
Journal
Volume
13
Issue
4
Start Page
720
End Page
769
Citation
Journal of Applied Logic 13 (4) : 720-769 (2015-12)
Publisher DOI
Scopus ID
We propose an approximation of the possible worlds semantics (PWS) of knowledge with support for postdiction - a fundamental inference pattern for diagnostic reasoning and explanation tasks in a wide range of real-world applications such as cognitive robotics, visual perception for cognitive vision, ambient intelligence and smart environments. We present the formal framework, an operational semantics, and an analysis of soundness and completeness results therefrom. The advantage of our approach is that only a linear number of state-variables are required to represent an agent's knowledge state. This is achieved by modeling knowledge as the history of a single approximate state, instead of using an exponential number of possible worlds like in Kripke semantics. That is, we add a temporal dimension to the knowledge representation which facilitates efficient postdiction. Since we consider knowledge histories, we call our theory h-approximation (HPX). Due to the linear number of state variables, HPX features a comparably low computational complexity. Specifically, we show that HPX can solve the projection problem in polynomial (tractable) time. It can solve planning problems in NP, while e.g. for the action language Ak [48] this is Σ2P-complete. In addition to the temporal dimension of knowledge, our theory supports concurrent acting and sensing, and is in this sense more expressive than existing approximations.
Subjects
Action and change
Commonsense reasoning
Epistemic reasoning