Comparing action descriptions based on semantic preferences
Thomas Eiter, Esra Erdem, Michael Fink, Ján Senko, Ag Wissensbasierte Systeme, Thomas Eiter, Esra Erdem, Michael Fink, Ján Senko · Sabanci University · 2006
Abstract. Incorporating new information into a knowledge base is an important problem which has been widely considered. In this paper, we study the problem in a formal framework for reasoning about action and change, in which action domains are described in an action language that has a transition-based semantics. Going beyond previous works, we consider (i) a richer action language that allows for non-deterministic, and concurrent actions, as well as the representation of indirect effects and dependencies between fluents, (ii) more general updates than elementary statements, and, most importantly, (iii) meta-level knowledge, such as observations, assertions, or general domain properties that remain invariant under change, expressed in an action query language. For this setting, we formalize a notion of update of an action domain description, relative to a generic preference relation on action domain descriptions that selects most preferred solutions. We study semantic and computational aspects of this notion, where we establish basic properties of updates and a decomposition result that gives rise to a divide and conquer approach to computing solutions 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