liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Two Aspects of Automating Logics of Action and Change: Regression and Tractability
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
1998 (English)Licentiate thesis, monograph (Other academic)
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.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 1998. , 83 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 674
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-74310Local ID: LiU-Tek-Lic 1998:09ISBN: 91-7219-173-2 (print)OAI: diva2:482632
1998-03-11, Belöningen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)

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

Available from: 2012-01-24 Created: 2012-01-24 Last updated: 2013-12-05Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Bjäreland, Marcus
By organisation
KPLAB - Knowledge Processing LabThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Total: 102 hits
ReferencesLink to record
Permanent link

Direct link