A history based approximate epistemic action theory for efficient postdictive reasoning

• 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 A(k) [48] this is Sigma(P)(2)-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.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

Commonsense reasoning; Action and change; Epistemic reasoning

Publication and Content Type

ref (subject category)

art (subject category)