oru.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A history based approximate epistemic action theory for efficient postdictive reasoning
International Computer Science Institute, Berkeley, United States.
University of Bremen, Bremen, Germany. (AASS)ORCID iD: 0000-0002-6290-5492
2015 (English)In: Journal of Applied Logic, ISSN 1570-8683, E-ISSN 1570-8691, Vol. 13, no 4, p. 720-769Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 13, no 4, p. 720-769
Keywords [en]
Commonsense reasoning; Action and change; Epistemic reasoning
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-64160DOI: 10.1016/j.jal.2015.08.001ISI: 000366072400004Scopus ID: 2-s2.0-84960472980OAI: oai:DiVA.org:oru-64160DiVA, id: diva2:1174421
Note

Funding Agencies:

German Research Foundation (DFG) via the 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 the European Commission  611553 

German Academic Exchange Service (DAAD) via the FITweltweit programme  

German Research Foundation (DFG), as part of the Spatial Cognition Research  SFB/TR 8 

Available from: 2018-01-15 Created: 2018-01-15 Last updated: 2018-01-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Bhatt, Mehul

Search in DiVA

By author/editor
Bhatt, Mehul
In the same journal
Journal of Applied Logic
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf