Research on Features and Fluents

This page was prepared in 1996 (with a minor update in 1997) and gives an overview, for that point in time, of research in Linköping and elsewhere that uses and extends the "Features and Fluents" Framework for reasoning about actions and change.

An up-to-date (for year 2005) presentation of our research in this area as well as related research can be found at the CAISOR website .

We have retained the contents of the present page without change except for this addition to its introduction.

Context, history, and participants

Until the end of 1995, the work in Linköping in this area was done in the Laboratory for Reprentation of Knowledge in Logic (RKLLAB) in the Department of Computer and Information Science (IDA) at Linköping University. From 1.1.1996, the RKLLAB was split up into three parts; the Features-and-Fluents part of the research was continued in the Knowledge Processing Laboratory.

The present page describes work up to mid-1995, and when the present tense is used in the following text it refers to that time. For additional work after that date, please refer to the home pages of Erik Sandewall and of the Knowledge Processing Laboratory.

The following resident researchers participate in this work:

We cooperate in joint work and mutual visits with the following researchers at other universities: We also include references to work, pertaining to the "Features and Fluents" Framework, by the following researchers:

Recent research publications - underlying semantics and assessments for strict inertia

Volume I of Erik Sandewall's monograph Features and Fluents has been published by Oxford University Press. The book is a comprehensive presentation of the systematic approach to reasoning about actions and change. A list of the key results in the book are obtained by clicking here. Bibliographic and ordering information are obtained by clicking here. A list of errata is obtained by clicking here.

The major aspects of the approach have been summarized in the following journal article. Erik Sandewall: The Range of Applicability of Some Non-monotonic Logics for Strict Inertia. Journal of Logic and Computation, Vol. 4, No. 5, pp. 581-615, 1994. [Click here for abstract only].

An survey of the general topic of nonmonotonic logicist methods for reasoning about actions and change has been written by Erik Sandewall and Yoav Shoham as a chapter in the Handbook of Logic in Artificial Intelligence and Logic Programming (Dov Gabbay et al, editors). Click here for bibliographic and ordering information.

Michael Thielscher, from the Technical University of Darmstadt, has analyzed and compared in his paper An Analysis of Systematic Approaches to Reasoning about Actions and Change the Features and Fluents framework and the Action Description Language A developed by M. Gelfond and V. Lifschitz. He has presented two equivalence results for ontological subclasses and elaborated the major differences. The ultimate aim of his analysis shall be a proposal about a combination of the two frameworks to obtain a powerful semantics which profits from the merits of both the FFF approach as well as the Action Description Language.

Choong-ho Yi has completed his licentiate thesis Reasoning about Concurrent Actions in the Trajectory Semantics. He generalizes the FFF underlying semantics to allow for concurrent actions, even in the case of actions with extended duration. This means that actions may occupy intervals of time that overlap in non-trivial manners, and that intermediate effects of one action may influence the latter part of the execution of another action. He investigates the range of applicability of prototypical chronological minimization with and without filtering, and shows that it is correct under the conditions which apply for sequential actions, provided that the actions do not interact. The thesis will be defended on March 24, 1995.

A summary of Choong-ho Yi's results appears in the article Towards the assessment of logics for concurrent actions, which will be presented at the 1995 AAAI Spring Symposium.

Recent research publications - circumscription and implementation

Patrick Doherty, working with Witold Lukaszewicz and Andrzej Szalas at the University of Warsaw, work on implementation techniques for the entailment methods that have been assessed in Features and Fluents. As the first step, Doherty and Lukaszewicz showed how several of the entailment methods that were analyzed in Features and Fluents can be reexpressed using circumscription [Patrick Doherty and Witold Lukaszewicz: Circumscribing Features and Fluents, presented at ICTL 1994].

Doherty then showed, in Reasoning about actions and change using occlusion (presented at ECAI 1994), how the circumscriptive version of PMON can be reduced to a first-order formulation. PMON is one of the most general methods that were assessed in Features and Fluents. For a detailed technical report on PMON and its extensions, see Doherty, Notes on PMON Circumscription . [Click here for abstract only]. A significant generalization of the method used by Doherty will be presented at IJCAI-95 in a joint article between Doherty, Lukaszewicz, and Szalas. For an extended technical report, see Computing Circumscription Revisited: A Reduction Algorithm . [Click here for abstract only]. They provide a general algorithm which can be used in an algorithmic manner to reduce circumscription axioms to 1st-order formulas. The class of 2nd-order formulas, and analogously the class of circumscriptive theories which can be reduced, provably subsumes those covered by existing results. The article demonstrates the generality of the algorithm using circumscriptive theories with mixed quantifiers, variable constants, non-separate formulas, and formulas with n-ary predicate variables. It also analyzes the strength of the algorithm and compares it with existing approaches providing formal subsumption results.

Recent research publications - ramification

An extension of the systematic approach from "Features and Fluents" to the case of ramification is presented in Reasoning about actions and change with ramification, by Erik Sandewall. This article will appear in the memorial volume, Springer Lecture Notes Volume 1000 (to appear in September, 1995). Additional details are obtained from the following departmental report: Systematic comparison of approaches to ramification using restricted minimization of change, also by Erik Sandewall. One section of Notes on PMON Circumscription (mentioned above) is also devoted to an extension of PMON for ramification. See also the work of Peppas listed below.

Recent research publications - reconstruction of approaches to planning

Lars Karlsson has completed his licentiate thesis Specification and Synthesis of Plans Using the Features and Fluents Framework. Using a view of plan construction as an abduction operation in the Features-and-fluents framework, he reconstructs several existing planners in a precise fashion, namely STRIPS, TWEAK, NONLIN, and SNLP. The thesis was defended on February 17, 1995. An earlier and shorter version of the thesis contents, without the SNLP reconstruction, was published as a departmental report, Specification and Synthesis of Plans Using the Features and Fluents Framework. [Click here for abstract only].

Alternative approaches (in our group)

This heading will list research in our group using alternative approaches.

Pavlos Peppas, who has visited from Macquarie University, Australia during three months, has completed a departmental report with the title Epistemic Entrenchment and the Possible Models Approach. [Click here for abstract only].

Other research on reasoning about actions and change

The following are pointers to the home pages for some other research groups that address the same topic: reasoning about actions and change.

Stanford: John McCarthy.

From Fangzhen Lin: The following papers are available in or
(Only accessible as ftp). Comments are welcome. This is a link to the above html address, but it is not operational at present.

Progress reports and plans

An overview of FFF-related research in Linköping is available as Erik Sandewall (ed): Overview of current research in RKLLAB (Linköping) using the Features and Fluents Framework.

Earlier research publications

The following is a list of earlier papers in our research on nonmonotonic logics for actions and change.

Erik Sandewall: An Approach to the Frame Problem, and its Implementation. In Machine Intelligence, Vol. 7, pp. 195-204. Edinburgh University Press, 1972.

Erik Sandewall: Non-monotonic entailment for reasoning about time and action. Technical report in three parts. Department of Computer and Information Science, Linköping University, 1988.

Erik Sandewall: A decision procedure for a theory of actions and plans. In Zbigniew Ras (ed): Methodologies for Intelligent Systems, Vol. IV. North-Holland, 1989.

Erik Sandewall: Filter Preferential Entailment for the Logic of Action in almost Continuous Worlds. International Joint Conference on Artificial Intelligence, 1989.

Erik Sandewall: Systematic assessment of temporal reasoning methods for use in autonomous agents. In Zbigniew Ras (ed): Methodologies for Intelligent Systems, Vol. VI, pp. 558-570, North-Holland, 1993

Erik Sandewall: The role of temporal reasoning subsystems in the architecture of autonomous robots. In G. Rzevski et al. (eds): Artificial Intelligence in Engineering, Vol. VIII, pp. 3-6. Computational Mechanics Publications/ Elsevier, 1993.

Erik Sandewall: Nonmonotonic temporal logics and autonomous agents: each contributes to the rigorous basis of the other. In O. Herzog et al (eds): Grundlagen und Anwendungen der Kuenstlichen Intelligenz. Proceedings of the German A.I. conference. Springer Verlag, 1993.