Updating action domain descriptions (Q622109)

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-solutions'' which approximate them. The applicability of presented algorithms and the usefulness of the theoretical results on the decomposability of the update problem are illustrated in the context of the Zoo World. The authors argue that their results go beyond previous results in the literature, and provide a semantic and computational basis for developing systems that incorporate new information into action descriptions in an action language in the presence of additional constraints. They state that the presented generic framework can be instantiated to different settings reflecting different intuitions or criteria for solution preference.