Approximate postdictive reasoning with answer set programming
2015 (English)In: Journal of Applied Logic, ISSN 1570-8683, E-ISSN 1570-8691, Vol. 13, no 4, p. 676-719Article in journal (Refereed) Published
Abstract [en]
We present an answer set programming realization of the h-approximation (HPX) theory [8] as an efficient and provably sound reasoning method for epistemic planning and projection problems that involve postdictive reasoning. The efficiency of HPX 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 HPX is incomplete. In this paper, we use the implementation of HPX to investigate the incompleteness issue and present an empirical evaluation of the solvable fragment and its performance. We find that the solvable fragment of HPX is indeed reasonable and fairly large: in average about 85% of the considered projection problem instances can be solved, compared to a PWS-based approach with exponential complexity as baseline. In addition to the empirical results, we demonstrate the manner in which HPX 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.
Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 13, no 4, p. 676-719
Keywords [en]
Commonsense reasoning; Action and change; Epistemic reasoning; Answer set programming
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-64159DOI: 10.1016/j.jal.2015.08.002ISI: 000366072400003Scopus ID: 2-s2.0-84960474374OAI: oai:DiVA.org:oru-64159DiVA, id: diva2:1174429
Note
Funding Agencies:
German Research Foundation (DFG) via International Research Training Group on Semantic Integration of Geospatial Information (IRTG-SIGI) GRK 1498
Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of European Commission 611553
German Academic Exchange Service (DAAD) via FITweltweit programme
German Research Foundation (DFG), as part of the Spatial Cognition Research SFB/TR 8
2018-01-152018-01-152018-01-18Bibliographically approved