Updating action domain descriptions
type: Item
instance of: scholarly article
title: Updating action domain descriptions
zbMATH Open document ID: 1225.68251
author: Thomas Eiter
author: Esra Erdem
author: Michael Fink
author: Ján Senko
published in: Artificial Intelligence
publication date: 2011-01-31T00:00:00Z
review text: This paper deals with the problem of reasoning about actions and change. It discusses updating action descriptions with new information in the context of action languages, where knowledge about the domain in terms of observations and other constraints is respected. A formal notion of an action update problem is introduced. Given an action description, the new information, and a set of desired constraints, a solution to the update problem based on some preference relation over action descriptions, is defined. Unlike other formalisms tackling the same problem, the presented framework allows a straightforward representation of non-deterministic and indirect effects of possibly concurrent actions. The authors argue that the expressivity of the presented formalism allows for more general updates of action domain descriptions than elementary statements. This makes it possible to discriminate against alternative updates of action domain descriptions in order to determine the most preferable one. Semantic and computational properties of action updates are studied, and basic properties of solution preferences are established. Special forms of updates serving as tests for the suitability of the notions are proposed, and conditions under which computing a solution to an action update problem can be structurally decomposed is discussed. A decomposition theorem that allows for divide-and-conquer approach to updating action descriptions under certain conditions is presented. The paper also studies the computational complexity of the action update problem. It states that under certain assumptions about the cost of deciding whether the set of domain constraints is satisfied by an action description, deciding the existence of some solution to an action update problem is PSPACE-complete in general. However, the problem falls back into the polynomial hierarchy under restrictions of some additional constraints. The paper further discusses algorithms for computing solutions and ``pre-so…
Mathematics Subject Classification ID: 68T30
Mathematics Subject Classification ID: 68T27
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5843084
zbMATH Keywords: knowledge representation
zbMATH Keywords: reasoning about actions and change
zbMATH Keywords: theory change
zbMATH Keywords: action languages
zbMATH Keywords: preference-based semantics
reviewed by: Neli Zlatareva
describes a project that uses: CCalc
MaRDI profile type: Publication
full work available at URL: j.artint.2010.07.004
OpenAlex ID: W2013831071
Wikidata QID: Q38496874
cites work: Representing the Zoo World and the Traffic World in the language of the Causal Calculator
cites work: On the logic of theory change: Partial meet contraction and revision functions
cites work: Computational Logic in Multi-Agent Systems
cites work: Q4708906
cites work: Dynamic updates of non-monotonic knowledge bases
cites work: Knowledge updates: Semantics and complexity issues
cites work: Q4494325
cites work: A unified model of qualitative belief change: a dynamical systems perspective
cites work: Nonmonotonic reasoning: From complexity to algorithms
cites work: A Unified View of Belief Revision and Update
cites work: Merging Logic Programs under Answer Set Semantics
cites work: Comparing Action Descriptions Based on Semantic Preferences
cites work: Comparing action descriptions based on semantic preferences
cites work: A logic programming approach to knowledge-state planning
cites work: On the complexity of propositional knowledge base revision, updates, and counterfactuals
cites work: Default reasoning from conditional knowledge bases: Complexity and tractable cases
cites work: Q4385542
cites work: On the revision of preferences and rational inference processes
cites work: Belief revision: A critique
cites work: Q4242055
cites work: Nonmonotonic causal theories
cites work: Knowledge-level analysis of belief base operations
cites work: A textbook of belief dynamics. Theory change and database updating
cites work: Q4343990
cites work: Q4028812
cites work: The complexity of optimization problems
cites work: The complexity of belief update
cites work: Q4536337
cites work: Q4298260
cites work: Q4518818
cites work: Q3198888
cites work: Q4779807
cites work: An abductive framework for computing knowledge base updates
cites work: Logic Programming and Nonmonotonic Reasoning
cites work: Bounded Query Classes
cites work: Q3995235
cites work: Q4708198
DBLP publication ID: journals/ai/EiterEFS10
DOI: 10.1016/J.ARTINT.2010.07.004
description: scientific article; zbMATH DE number 5843084