News Journal on Reasoning about Actions and Change

This News Journal invites announcements of research software systems pertaining to the area of actions and change. We believe that the development and diffusion of software systems representing the state of the art in research is now very important in this research area. Also, the electronic communication medium is particularly appropriate for this purpose.

VITAL: Visualization and Implementation of Temporal Action Logics

Visual Temporal Action Logic, Version 1.0, is a prototype implementation (in Java) of a research tool used to construct, reason about and visualize action scenario descriptions.  Currently, action scenarios are visualized in terms of the trajectories or histories associated with each of the logical models for the scenario. For more information about the implementation, read the Description and User's Guide.

The implementation currently available on these web pages is from January, 1997.  There are a few known bugs in the user interface, but other than that, this version is relatively stable.  In the next version, the implementation will be updated for Java 1.1. We expect the new version to be available in June. The Description and User's Guide will be updated incrementally.

The system is accessed through the VITAL project web page.

The DLS Algorithm: A Quantifier Elimination Technique

The DLS algorithm, developed by Patrick Doherty, Witold Lukaszewicz, and Andrzej Szalas, and implemented by Joakim Gustafsson, is a 2nd-order formula reduction algorithm based on a quantifier elimination technique which is a generalization of Ackermann's Lemma. The algorithm takes as input a 2nd-order formula and either returns a logically equivalent 1st-order formula, or terminates with failure. Failure does not imply that there isn't a logically equivalent 1st-order formula, just that there may not be one or there is but the algorithm can not find it. The algorithm can be applied to circumscription axioms, including nested circumscription, and has been applied to reducing 2nd-order action theories to their first-order equivalents.

The algorithm may be accessed and tested through the DLS Project page, which also contains references and links to the published articles describing the algorithm.

The following debate contributions have been received since the previous issue of this News Journal. (This section contains debate about general issues, not related to a particular article or group of articles. See also the Debate About Contributions section below).

We illustrate this News Journal section by repeating a few contributions from a debate that started in the ECSTER Colloquium.

Continuing a general debate on approaches to reasoning about actions and change

Several approaches to reasoning about actions and change co-exist at present in the literature. The major divide seems to be between the situation calculus on one hand, and approaches using explicit time on the other hand. It may not be easy for the readers of this literature to see how the different approaches relate, and what are their respective weaknesses and strengths. Sometimes, it is even difficult for the researchers in the area to make this analysis. For example, in this recent KR paper, Ray Reiter writes:

There have been a few earlier papers on formalizing natural actions and continuous time. Shanahan's approach [30] is embedded in the event calculus (Kowalski and Sergot [11]); Sandewall [27] relies on a temporal logic. Accordingly, these proposals are difficult to compare with ours, based as it is on the situation calculus.

After a suggestion by Ray, this News Journal invites researchers in this area to an on-line debate on different approaches to reasoning about actions and change. The purpose of the debate is to clarify what are the major alternative approaches to reasoning about actions and change in contemporary research, and also to identify and compare the capabilities and the limitations of those approaches.

A separate debate page has been set up and will contain successive debate contributions. It presently contains an introduction by Erik Sandewall and position statements by Murray Shanahan, Rob Miller, and Vladimir Lifschitz. All contributions which are sent to the present editor will be added to the debate page.

Also, for readers who wish to receive each debate contribution as an E-mail message, we are going to set up a mailgroup. Send a message to the Newsletter editor in order to be included in this mailgroup.

Initial statements in the Newsletter Debate

We repeat here the initial statements that were published in the previous issue of the ECSTER Newsletter.

Current Research on Reasoning About Actions and Change: Topics for a Debate

Erik Sandewall

Several approaches to reasoning about actions and change co-exist at present in the literature. The major divide seems to be between the situation calculus on one hand, and approaches using explicit time on the other hand. It may not be easy for the readers of this literature to see how the different approaches relate, and what are their respective weaknesses and strengths. Sometimes, it is even difficult for the researchers in the area to make this analysis. For example, in this recent KR paper, Ray Reiter writes: ... read the continuation here.

Reasoning about Actions: A Position Statement

Murray Shanahan

AI needs an action formalism that is expressive, and that incorporates a solution to the frame problem that's robust in the face of the phenomena it can represent. The formalism should be expressive enough to represent at least the following phenomena.

1. Actions with indirect effects (ramifications)
2. Concurrent action
3. Non-deterministic action
4. Narrative time
5. Continuous change

A rigorous argument that the formalism in question solves the frame problem should be supplied.

Here comes the controversial bit. ... read the continuation here.

Comparing Action Formalisms: A Position Statement

Rob Miller

Here are some fairly miscellaneous thoughts about comparing alternative approaches to Reasoning about Action. ...

(1) When comparing and evaluating formalisms, we need to be careful not to form too strong associations between particular methodologies (e.g. deduction and entailment methods, default reasoning techniques) and particular ontologies. I can think of a few occasions... (2) As a community, we should be encouraging work on comparing action formalisms and ontologies, and we should be critical of papers which don't contain adequate comparisons with other work (and especially with work based on different ontologies). There is now a fair body of work exploring how the Event Calculus and the Situation Calculus correspond, so there's really no excuse for lack of comparisons in this case at least. ... read the continuation here.

Approaches to Reasoning About Actions: A Position Statement

Vladimir Lifschitz

1. Explicit time vs. the situation calculus. The following situation calculus formula seems to have no counterpart in languages with explicit time:

value(f,result(a1,s)) = value(f,result(a2,s)). (1)

It says that the value of f at the next instant of time does not depend on which of the actions a1, a2 is going to be executed. For instance,...

4. Why are there so many action languages? An action language is a formal model of the part of natural language that is used for describing the effects of actions. Whenever we improve our understanding of that part of natural language, this improved understanding may be expressed by defining a new dialect of "script-A." I expect that...

6. Explicit information about causal directions. Causality differs from material implication in that it is not contrapositive... ... read the continuation here.

The following debate contributions about Received research articles have arrived since the previous issue of this News Journal. None in this issue.

See below for the conference program of several conferences during this summer: FAPR-97 (combined with ECSQARU), AAAI-97, and IJCAI-97 including the NRAC-97 workshop.

None at this point.

The following articles on reasoning about Actions and Change have appeared in other journals or conferences since the previous issue of this News Journal.

TIME-97

The full list of accepted papers is now available for TIME-97.

FAPR-97

The conference program containing the full list of accepted papers is now available for FAPR-97.

NRAC-97 workshop at IJCAI

The preliminary workshop program is now available for the Workshop on Nonmonotonic Reasoning, Action and Change, to be held at this year's IJCAI.

AAAI-97

The conference program is now available for this year's AAAI. Among the papers at this conference, the following ones appear to fall directly within the area of actions and change, as far as one can guess from the title and the authors. The list of those papers has also been included in the bibliography of the Actions and Change Colloquium.

c-aaai-97-Costello

Tom Costello:
Beyond Minimizing Change.

c-aaai-97-Lobo

Jorge Lobo, Gisela Mendez and Stuart R. Taylor:
Adding Knowledge to the Action Description Language A.

c-aaai-97-McCain

Norman McCain, Hudson Turner:
Causal Theories of Action and Change.

c-aaai-97-McIlraith

Sheila A. McIlraith:
Representing Actions and State Constraints in Model-Based Diagnosis.

c-aaai-97-Myers

Karen L. Myers:
Abductive Refinement of Plan Sketches.

c-aaai-97-Schwalb

Eddie Schwalb:
Temporal Reasoning with Resolution and Constraint Propagation.

c-aaai-97-Shanahan

Murray P. Shanahan:
Noise, Non-Determinism and Spatial Uncertainty.

IJCAI-97

The preliminary conference program and list of accepted papers are now available for this year's IJCAI.

Among the more 200 papers at this conference, 20 appear to fall directly within the area of actions and change, as far as one can guess from the title and the authors. The list of those 20 papers has been compiled using the ACRES database.

Since what is shown here is a prototype for demonstration purposes, some general remarks about it may be of interest.

Independence of the areas and area editors: The News Journals are not supposed to be all alike. Each area within ETAI will organize its own News Journal, and may do it differently and/or add more kinds of material besides the one shown in this example.

Importance of the bibliographic database: Our database of current A I literature is very important for the activities within the ETAI areas. From the point of view of appearance, the News Journals and the Bibliographic Resource serve complementary roles: one provides information update, the other provides access to the information repository. However, both rely on the same database, and the present News Journal issue has illustrated how this will work. For example, the raw data for the list of relevant (for us) articles at IJCAI was obtained from the official IJCAI program which is posted on the net, using a process which is almost fully automated except, of course, for the very selection of what articles are to be included. (The fact that authors are listed without their first names is due to a peculiarity in that particular data source). More about the ideas behind this are found in the description of the bibliographic resource.