Approximate postdictive reasoning with answer set programming

We present an answer set programming realization of the h-approximation (HPXHPX) theory [8] as an efficient and provably sound reasoning method for epistemic planning and projection problems that involve postdictive reasoning. The efficiency of HPXHPX stems from an approximate knowledge state representation that involves only a linear number of state variables, as compared to an exponential number for theories that utilize a possible-worlds based semantics. This causes a relatively low computational complexity, i.e, the planning problem is in NP under reasonable restrictions, at the cost that HPXHPX is incomplete. In this paper, we use the implementation of HPXHPX to investigate the incompleteness issue and present an empirical evaluation of the solvable fragment and its performance. We find that the solvable fragment of HPXHPX is indeed reasonable and fairly large: in average about 85% of the considered projection problem instances can be solved, compared to a PWSPWS-based approach with exponential complexity as baseline. In addition to the empirical results, we demonstrate the manner in which HPXHPX can be applied in a real robotic control task within a smart home, where our scenario illustrates the usefulness of postdictive reasoning to achieve error-tolerance by abnormality detection in a high-level decision-making task.