The work in our book ``Features and Fluents'' as well as a number of earlier and later papers has used an ontology based on three distinct categories: a , a notion of , and which are used for characterizing the world's change of state in a succinct way. Actions and events are similar, but by definition, actions have been invoked by the current agent, whereas events are ``acts of nature'' or, at least, exogenous to the agent at hand. Since we are not alone in having used this combination of concepts, and since the term ``features and fluents'' is anyway a bit ideosyncratic, we prefer now to talk of the TSAT or time/state/action/trajectory ontology. The following are the key notions and major types in TSAT ontology: The is defined as a set of timepoints over which certain operations have been defined. Most of the concrete (proofs about the properties of entailment methods, etc) have used the non-negative integers as the time domain, but the general definition allows for using continuous time and/or forward-branching time. Some of the methods make essential use of continuous time; some of the proofs generalize easily to branching time. The is defined as a Cartesian product of times corresponding values. When we say ``feature'', many people would say ``fluent'' or ``state variable''. However, we try to be precise about the feature/fluent distinction: a fluent is a , and therefore a mapping from timepoints to corresponding values, which in fact are feature values. In the propositional case, where one does not identify distinct objects, a feature is the same as a fluent symbol. If objects are allowed, an entity such as may be a feature; is then a feature-valued function; a state may map this feature to a corresponding value (for example, 38); and a fluent corresponding to this feature may map timepoints to corresponding values, such as 38. Thus, features are obtained by reification of certain functions. The major reason for doing this reification is that, besides the obvious need for a relation which expresses that a certain feature has a certain value at a certain time , which actually is written , we also need to define other predicates on features, in particular, the occlusion predicate which ``allows'' the feature to change its value at time . The consists of symbolic or reified entities, just like the features are. If the agent at hand is a helicopter, then may be the action of moving vertically to a position 40 meters above ground. Actions are presumed to take place over an interval of time, so each instance of an action has a and a . The expression says that the action is invoked, or starts, at time and terminates at time . In the TSAT ontology, the effects of an action are characterized in some of the following related ways: : A mapping from starting state and action to result state. This means that actions are deterministic and are performed over a single time-step. : A mapping from starting state and action to a set of result states. Compared to the previous case, this means that the action is nondeterministic. : A mapping from starting state and action to a set of structures containing states, called . For integer time, a trajectory is a finite sequence of states; for real time, it is a mapping from a finite interval [] to states; and for branching time, it is a corresponding branching structure. Compared to the previous case, this means that actions have a duration in time, and that there are intermediate states within the action's execution period. : A combination of two mappings, namely an which maps starting state and action to a set of result states, like in case (2), and a on states times states. The idea is that the eventual result of performing an action is to apply the invocation function to the starting state and the action, to select one of the members of the set obtained, and to then obtain successors according to the transition relation until a quiescent state has been reached. This is used as a basis for analysing ramification. The action-language ontologies, such as cal-A (Lifschitz xx) and its successors, characterize points in history by what actions have led up to that point, rather than by a numerical measure as is the case in TSAT ontology. The same holds for most uses of the situation calculus: a situation is usually defined as a sequence of actions (Ginsberg xx, Reiter xx). Notice, however, that some authors have defined a situation as the complete state of the world at some point in time (Baker xx, Costello xx). Even in those cases, the only way of getting from one state to another is by means of doing an action, which means that states in the inner part of an action's interval are not represented. Action languages have gone through a number of extensions and generation shifts before they included the expressiveness for distinct objects, nondeterminism, and concurrent actions. All of this is intrinsic in the TSAT ontology. The original event calculus (Kowalski xx) only represented events as such, and did not explicitly refer to timepoints in the language (nor in the semantics since no denotational semantics was ever provided). In the last few years, researchers in the event-calculus tradition have switched to a TSAT ontology but with one particular choice of nonmonotonic inference operation, namely, one which is similar to original event calculus. Additional comments about how these approaches compare will follow after the list of results. Every approach must eventually be measured by the results that are obtained when it is used. We believe that in a competitive comparison, an approach should be given credit (a) when its way of addressing a particular problem is clearly more concise and elegant than in alternative approaches, and (b) when a technique was first introduced in the approach in question - presumably an indication that the approach was conducive to obtaining the result. The following is a catalogue of results that have been obtained in the TSAT approach, including both of those reasons for credit. Note that the list is not balanced with respect to workload: some of the items involve a lot of work and several publications, others represent relatively little work and one or a few publications. Representation of hybrid change (mixed discrete and continuous change) (Sandewall, c-kr-89-xxx). In this work, we used the trajectory ontology as the basis for identifying restrictions which guarantee that each of a number of different entailment methods gives the correct result for scenarios involving actions and change, or that it does not. In this work, given the difficulties of obtaining regular range of applicability for ramification methods, we compare range of soundness pairwise between ramification methods based on minimization. Thus, given two distinct such methods, we are able to say that the set of models selected by one is always a subset of the set of models selected by the other. Doherty and Lukaszewicz, sometimes in cooperation with Szalas, have developed powerful techniques for rewriting the second-order axioms in the PMON entailment method to a larger set of corresponding first-order axioms. These techniques are considerably more general than the earlier results by Lifschitz. A separate page describes these results in more detail. Write about VITAL etc here... One of the concrete indications of the strength of an approach is that developments within it are transferred to and incorporated in other approaches. This has happened in the following cases: The study of complexity in reasoning about actions and change has only started in the last year. A class of scenarios where the computation of consistence is polynomial was identified in c-ijcai-97-xxx. Independent and concurrently published work by Liberatore (f-cis.liu.se-97-8) identified polynomially decidable classes within the cal-A language. Although neither of the results appears to subsume the other, the work in the TSAT framework has the advantage of allowing concurrency and continuous time (with appropriate restrictions, of course) within the polynomially decidable class. The cal-A language is not able to express such scenarios. As a basis for the determination of range of applicability for entailment methods, we defined a taxonomy of scenarios using categories such as In c-xxx-xxx-xxx, Thielscher identified which subset of our ontological structure corresponds to the original action description language, cal-A. See also the section about comparison of approaches, below. The operative description of an action is one which can be used as a program for executing the action. For robotic and other real-world environments, the operative definition has to use continuous time and continuous feature values. The declarative action-description may simply be a set of precondition - postcondition pairs, or it may also include characterization of the state of the world at intermediate times within the duration of the action. Discrete-valued features are preferred. In c-ecai-96-xxx (long abstract) and j-aicom-96-xxx (full paper) we described a systematic way of relating operative and declarative action descriptions, in such a way that the latter can be inferred from the former. In c-aaai-92-xxx, Dean used a TSAT framework with continous time and discontinuity minimization for a control application. In c-nrac-97-xxx, (Michail) used a TSAT framework for characterizing the movements of objects in a simple virtual-reality world. Besides using the TSAT ontology, we have also adopted a for defining researchable issues. This is a separate choice, since it would be possible to use the TSAT using the older (example-driven) methodology. Conversely, systematic methodology could be used with every representation scheme, although it only makes sense if that representation scheme is sufficiently expressive. For example, it would not be very interesting with classical situation calculus, but it could conceivably be used with the extension of SC that allows the use of a narrative timeline (c-aaai-9x-xxx). Anyway, we have only used it for the TSAT ontology. Research in knowledge representation has a long tradition of using common-sense examples to support proposed representation schemes. Although this may be appropriate in the very first stage of addressing a new and difficult problem area, it is quite obvious that it is not sufficient in the long run. We have advocated and used a where proposed logics, including the entailment method that defines how nonmonotonic conclusions are drawn, are analyzed with respect to , that is, one proves sufficient conditions for the logic to obtain exactly the intended set of conclusions. The action language cal-A and its successors were also introduced in order to serve as a basis for analysing and validating logics of actions and change. The following are the major differences between our approach and theirs. The action-language research relates languages on two distinct levels: the action language and the formulation in logic. Each of the two levels has its own syntax and its own semantics. In our case, we use one single language (the multi-sorted first-order logic with timepoints, features, actions, etc as sorts) and two distinct semantics. Our for the logical language corresponds to the semantics of the action language; its corresponds to the semantics of the logic language in the action-language approach. Later variants of action languages, such as cal-AR which allows for ramification, use a semantics that relies on a preference relation between models and obtaining the set of minimal models. We do not allow such devices in the underlying semantics, on the grounds that minimization is not sufficiently convincing intuitively, and that it is useless for relating to low-level, operational action descriptions (cf. item xx above). For addressing ramification we use a causation-chain formalization instead. The action-language research introduces new variants of action languages at a rapid rate, and at each step, results are proven which apply for all scenarios that can be expressed in the language at hand. As successively stronger results are developed, new and more expressive languages must be defined. In our case, we defined a much larger ontological class from the start, and looked for results which applied to an identified that class - hence the need for an ``ontological taxonomy'' and the results about ``range of applicability''. We see the following advantages with this: on the range of applicability, that is, to prove that under certain conditions a given logic give the intended results. In many cases, the upper bound is equal to the previously verified, sufficient conditions for applicability, which means that the true range of applicability has been determined completely. As just noted, we reject the use of model minimization in the underlying semantics. Therefore, the levels of description in our approach are somewhat different from the levels of description in the action language approach. For us, the following levels are recognized: of the ontological class presently being addressed. This is what specifies the current ontology; it is supposed to be a kind of abstract simulation of the world that is being modelled, through which the set of is defined. which specifies how to cut down the set of classical models for the scenario description to a smaller set, the set of . The entailment method is correct for the scenario if the set of selected models equals the set of intended models. through which a scenario description is converted to a set of logical formulae that can used in an existing deduction system. Most of the work in our approach has considered transformations via circumscription formulations to a corresponding set of first-order formulae which can be used with monotonic deduction. Bertossi and Bedrax-Weiss have defined an underlying semantics for Reiter's variant of the situation calculus (r-xxx-xx-xxx). This is not the place for a detailed history of TSAT approaches in knowledge representation and artificial intelligence; only a few key events will be mentioned. (A more comprehensive history may be written separately). John McCarthy's early work established the situation calculus as the primary ontology for symbolic A.I. It was first formulated in some brief research notes (r-xxx-xx-xxx and r-xxx-xx-xxx), and did not appear in published form until later (c-xxx-xx-xxx). However, the concept was widely known and generally accepted. It was possible to twist the notions of SC by assuming one single action which represented a tick of the clock, effectively simulating integer time within the SC. This was done by a number of early authors; see e.g. c-mi-73-xxx and c-xx-xxx-xxx. However, the major systems at the time tended to use the situation calculus, for example Green's deductive planning system (c-ijcai-71-xxx) and Winograd's SHRDLU system (c-ijcai-73-xxx). Probably the first author to argue the use of explicit metric time for reasoning about actions and change was Shoham (c-ecai-86-xxx). In his book (b-88-Shoham), he uses an ontology like the one described here, with the only exception that actions and events are considered as two special cases of a more general concept. (Add references to additional articles here). As said above, our systematic methodology involves the choice of an ontological space that is going to last for a while, subdividing it using an ontological ontology, working with this structure, and then proceeding to a larger ontological space at distinct occasions and not too often. The question then arises how one is to choose the extent of the ontology at every such occasion. Two considerations have appeared to be relevant for us in this respect: intuitive naturalness and ease of proofs. Two concrete situations from the development of the Features and Fluents work may illustrate how naturalness and ease of proof may interact. When the work was first started, I first defined an underlying semantics that included both discrete and continuous time as special cases. This was trivial as far as the definitions went, but it turned out that the proofs of range of applicability became messy, and that the two cases of discrete and continuous time often had to be treated separately. I therefore decided to restrict the analysis to the discrete case, and to leave the continuous case for later. (However, the basic definitions in the book still cover both discrete and continuous time). The other example concerns the use of linear vs branching time. I always thought that linear time is the only natural choice if nondeterministic actions are allowed, since it means that every interpretation represents one possible history through time in the simplest possible fashion. Branching time allows one to have several possible histories in a single interpretation, but this does not help much since every combination of nondeterministic outcomes of actions in any of those paths through the tree will anyway be represented as a different interpretation. However, looking back at the proofs in a fairly late stage of writing the book, it became clear that the same proofs would go through just as well in the case of branching metric time. Such a generalization was therefore added to the text (chapter 6, section 6.6), and the proofs were modified or provided with addenda for the variant of branching time. These two examples illustrate how the natural guiding line of intuition can be modified by ease of proof. As proofs are developed, naturalness may have to be compromised in order to obtain as strong results as possible. Check publication lists of the following: Patrick/Witold/etc Others locally Tommy and Lennart Leopoldo Bertossi, Tanja Bedrax-Weiss Peter Grunwald Michael Thielscher Pavlos Peppas, Michail Prokopenko (My own) (more ?)