A history based approximate epistemic action theory for efficient postdictive reasoning

We propose an approximation of the possible worlds semantics (PWSPWS) 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   (HPXHPX).Due to the linear number of state variables, HPXHPX features a comparably low computational complexity. Specifically, we show that HPXHPX can solve the projection problem in polynomial (tractable) time. It can solve planning problems in NP, while e.g. for the action language AkAk[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.