title   
  

Updating action domain descriptions

Eiter, Thomas and Erdem, Esra and Fink, Michael and Senko, Jan (2010) Updating action domain descriptions. Artificial Intelligence, 174 (15). pp. 1172-1221. ISSN 0004-3702

This is the latest version of this item.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1016/j.artint.2010.07.004

Abstract

Incorporating new information into a knowledge base is an important problem which has been widely investigated. In this paper, we study this problem in a formal framework for reasoning about actions and change. In this framework, action domains are described in an action language whose semantics is based on the notion of causality. Unlike the formalisms considered in the related work, this language allows straightforward representation of non-deterministic effects and indirect effects of (possibly concurrent) actions, as well as state constraints; therefore, the updates can be more general than elementary statements. The expressivity of this formalism allows us to study the update of an action domain description with a more general approach compared to related work. First of all, we consider the update of an action description with respect to further criteria, for instance, by ensuring that the updated description entails some observations, assertions, or general domain properties that constitute further constraints that are not expressible in an action description in general. Moreover, our framework allows us to discriminate amongst alternative updates of action domain descriptions and to single out a most preferable one, based on a given preference relation possibly dependent on the specified criteria. We study semantic and computational aspects of the update problem, and establish basic properties of updates as well as a decomposition theorem that gives rise to a divide and conquer approach to updating action descriptions under certain conditions. Furthermore, we study the computational complexity of decision problems around computing solutions, both for the generic setting and for two particular preference relations, viz. set-inclusion and weight-based preference. While deciding the existence of solutions and recognizing solutions are PSPACE-complete problems in general, the problems fall back into the polynomial hierarchy under restrictions on the additional constraints. We finally discuss methods to compute solutions and approximate solutions (which disregard preference). Our results provide a semantic and computational basis for developing systems that incorporate new information into action domain descriptions in an action language, in the presence of additional constraints.

Item Type:Article
Uncontrolled Keywords:Knowledge representation; Reasoning about actions and change; Theory change; Action languages; Preference-based semantics
Subjects:UNSPECIFIED
ID Code:14264
Deposited By:Esra Erdem
Deposited On:24 Aug 2010 09:59
Last Modified:25 May 2011 14:17

Available Versions of this Item

Repository Staff Only: item control page