: Regression and Tractability
Bjäreland, Marcus 1998 (English)Licentiate thesis, monograph (Other academic)
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, pages
Linköping: Linköpings universitet, 1998. 83 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 674
National CategoryEngineering and Technology
Identifiersurn:nbn:se:liu:diva-74310 (URN)LiU-Tek-Lic 1998:09 (Local ID)91-7219-173-2 (ISBN)oai:DiVA.org:liu-74310 (OAI)diva2:482632 (DiVA)
1998-03-11, Belöningen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Thesis No 674. LiU-Tek-Lic 1998:092012-01-242012-01-242013-12-05Bibliographically approved