LiU Electronic Press
Full-text not available in DiVA
Author:
Bjäreland, Marcus (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (Linköping University, The Institute of Technology)
Title:
Two Aspects of Automating Logics of Action and Change: Regression and Tractability
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, The Institute of Technology
Publication type:
Licentiate thesis, monograph (Other academic)
Language:
English
Place of publ.: Linköping Publisher: Linköpings universitet
Pages:
83
Series:
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971; 674
Year of publ.:
1998
URI:
urn:nbn:se:liu:diva-74310
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-74310
ISBN:
91-7219-173-2
Local ID:
LiU-Tek-Lic 1998:09
Subject category:
Engineering and Technology
Abstract(en) :

The autonomy of an artificial agent (e.g. a robot) will certainly depend on its ability to perform "intelligent" tasks, such as learning, planning, and reasoning about its own actions and their effects on the enviroment, for example predicting the consequences of its own behaviour. To be able to perform these (and many more) tasks, the agent will have to represent its knowledge about the world.

The research field "Logics of Action Change" is concerned with the modelling of agents and dynamical, changing environments with logics.In this thesis we study two aspects of automation of logics of action and change. The first aspect, regression, is used to "reason backwards", i.e. to start with the last time point in a description of a course of events, and moving backwards through these events, taking the effects of all actions into consideration. We discuss the consequences for regression of introducing nondeterministic actions, and provide the logic PMON with pre- and postdiction procedures. We employ the classical computer science tool, the weakest liberal precondition operator (wlp) for this, and show that logical entailment of PMON is equivalent to wlp computations.

The second aspect is computational complexity of logics of action and change, which has virtually been neglected by the research community. We present a new and expressive logic, capable of expressing continuous time, nondeterministic actions, concurrency, and memory of actions. We show that satisfiability of a theory in this logic is NP-complete. Furthermore, we identify a tractable subset of the logic, and provide a sound, complete, and polynomial algorithm for satisfiability of the subset.

Note:

Thesis No 674. LiU-Tek-Lic 1998:09

Presentation:
1998-03-11, Belöningen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Degree:
Licentiate of Philosophy
Available from:
2012-01-24
Created:
2012-01-24
Last updated:
2013-12-05
Statistics:
29 hits