Vol. 1, Nr. 5 Editor: Erik Sandewall December 31.1997


The ETAI is organized and published under the auspices of the
European Coordinating Committee for Artificial Intelligence (ECCAI).

Contents of this issue

Today

Introductory statements in daily newsletters

ETAI Publications

Received research articles
Discussion about received articles
Articles presently under review

Other Publications

Research articles

Debates

NRAC Panel Discussion on Ontologies for Actions and Change

Calendar

Forthcoming conferences and workshops

Conferences and Workshops

Common Sense 1998

Editorial issues

A Note on Procedure

Today

Introductory statements in daily newsletters

Dated: 3.12.1997

After a long period of no conference announcements, several have arrived during the last few days. The present newsletter contains a list of all four of them, with hot links to the plaintext variant of their call-for-papers (the same as has been circulated by email) and to the cfp in HTML that is posted on the web by the organizers. These links are also available from the conference calendar of the present Colloquium.

Dated: 9.12.1997

The ontology discussion is now focussing on the choice between action languages and direct use of logic, an issue that was originally raised by Tom Costello in a question to Tony Kakas and Rob Miller for their article on the action language E. In one of our recent issues, Vladimir Lifschitz responded to earlier contributions by Erik Sandewall and Patrick Doherty, and posed a question based on three concrete scenario examples. Erik Sandewall's answer follows in the present issue.

Dated: 19.12.1997

Today's issue contains an additional submitted article, this time one authored by the present editor, as well as a comment about the refereeing procedure for such cases. It furthermore contains an addendum and correction to the link to a submitted article in our previous issue, and the full workshop program for the forthcoming Common Sense workshop.

The present Newsletter will gladly receive questions and discussions about articles in our area that have been published elsewhere, be it at a workshop or in a journal. If there is some aspect of such a paper that you would like to discuss, then send us a note. We will first check with the author whether she or he is willing to engage in public discussion, and then open the public question-period or debate.

Dated: 23.12.1997

Recommended reading for Christmas: Michael Thielscher's article "A Theory of Dynamic Diagnosis" which was received by this ETAI area on October 7, and Marie-Odile Cordier's discussion contribution on this article which follows in the present Newsletter issue, where she also relates Michael's approach to her own. Additional contributions to this discussion are welcome, particularly before January 7 since the period for open discussion is set to be three months.

Dated: 27.12.1997

The present Newsletter issue contains questions/comments by Wolfgang Nejdl to Michael Thielscher re his ETAI article. Some of Wolfgang's points actually coincide with points that were made by Marie-Odile Cordier and which were included in the previous Newsletter issue (23.12). In fact, the two contributions must have been written concurrently; Wolfgang's mail did also arrive on the 23, but we don't send out more than one Newsletter a day, and Christmas has occurred in-between.

Dated: 30.12.1997

The last Newsletter issue for 1997 contains abstracts of three recent articles (not ETAI submitted) on reasoning about actions and change, and a concluding editorial statement that summarizes the experience of the ETAI and of the present Newsletter during the past year. Some new initiatives will be advertised in the first Newsletters during 1998.

At this point, I want to thank the Newsletter's contributors and readers for their participation in this enterprise since its start, and to send the best wishes for the new year. It has been a true pleasure to work with you, and I look forward to even more (inter)action and change during the coming year.

Dated: 31.12.1997

The last Newsletter of this year contains a summary of the present status of the four articles and one research note that are presently under review in the ETAI area "Reasoning about Actions and Change". These have not been our only activities during the past months: we have had two panel discussions, one invited discussion (about Wolfgang Bibel's IJCAI paper), and several kinds of information has been transmitted through the present Newsletter. However, the status summary will serve both as a reminder that review of articles is our "core business", and as an encouragement for all to continue the discussion during the coming year.

At the end of the year it is appropriate to look back and to summarize. The present issue therefore also contains an editorial remark about the experience and the conclusions from the first year of ETAI and ENRAC activities.

At this point, I want to thank the Newsletter's contributors and readers for their participation in this enterprise since its start, and to send the best wishes for the new year. It has been a true pleasure to work with you, and I look forward to even more (inter)action and change during the coming year.

Dated: 31.12.1997

The development of the Electronic Transactions on Artificial Intelligence turns out to be an exploratory activity, even more than what we had anticipated when it started. The original idea was to create a new publication medium for scientific articles which would make the best use of the Internet availability. We foresaw a number of changes to the conventional practices that have been developed for paper-based journals, and in particular, we emphasized the importance of separating publishing (in the sense of "making public" and "making available") from the scientific quality control, that is, from the reviewing and refereering process. We also emphasized the importance of opening one part of the reviewing process, so that the traditional, confidential peer review would be replaced by a combination: an open discussion part where reviewers appear without the shroud of anonymity, and after it a rapid pass/fail decision by anonymous referees.

Finally, and maybe the most important of all, we emphasized the importance of having a publication medium where the authors retain the copyright of their articles, unlike what is the case in conventional journal publishing. The insight that this is a very important question has spread rapidly in our community during the past year.

These concepts were presented in the spring of 1997, and the ETAI was formally announced in May. In comparison with what we expected, there has been a small minus and a big plus. The minus is that the start was slower that we had thought: it took a while before papers started coming. However, I believe that the number of contributions will increase when the paper version of the ETAI begins to spread. The ETAI is "electronic" in the sense that it is stored and transmitted electronically, but noone expects you to read long, technical papers directly from the screen, and the paper printouts of the ETAI issues do look like any other journal. Professional-looking issues containing professional-quality articles will be our best advertisement.

The plus is that a whole new layer of communication concepts have evolved during the second half of 1997. Three layers can be identified here:

It is my firm conviction that we are just at the beginning of a very important development. Certainly we will see a lot more of it during the coming year. The future is bright!


ETAI Publications

Received research articles

The following articles have been received during the month of December, and review discussions have been opened for them.

José Júlio Alferes, João Alexandre Leite, Luís Moniz Pereira, Halina Przymusinska, and Teodor Przymusinski

Dynamic Logic Programming.


[Interactions]

Abstract: In this paper we investigate updates of knowledge bases represented by logic programs. In order to represent negative information, we use generalized logic programs which allow default negation not only in their bodies but also in their heads.

We start by introducing the notion of an update P ø U of a logic program P by another logic program U. Subsequently, we provide a precise semantic characterization of P ø U, and study some basic properties of program updates. In particular, we show that our update programs generalize the notion of interpretation update.

We then extend this notion to sequences of logic programs updates P1 ø P2 ø ..., defining dynamic program updates, thereby introducing the paradigm of dynamic logic programming. This paradigm significantly facilitates modularization of logic programming, and thus modularization of non-monotonic reasoning as a whole.

Suppose that we are given a set of logic program modules, each describing a different state of our knowledge of the world. Different states may represent different time points or different sets of priorities or perhaps even different viewpoints. Consequently, program modules may contain mutually contradictory as well as overlapping information. The role of the dynamic program update is to use the mutual relationships existing between different states to precisely determine, at any given state, the declarative and the procedural semantics of the combined program, resulting from all these modules.

Erik Sandewall

Logic-Based Modelling of Goal-Directed Behavior.


[Interactions]

Abstract: We address the problem of characterizing goal-directed robotic behavior using a logic of actions and change. Our approach is based on distinguishing two kinds of actions: procedural actions which are defined in a mechanistic way, and goal-directed actions which are performed through a process involving tries, possibly failures, and corrective action and new tries until the goal has been reached. (The definition of procedural actions may be done external to the logic, for example through differential equations, or through a conventional programming language). For both kinds of actions, the logic expresses explicitly whether the action succeeds or fails. Each execution of a goal-directed action is also characterized by a number of breakpoints where some sub-action has been completed and a new sub-action for getting to the desired goal is selected. The logic is used for characterizing the selection of sub-actions at breakpoints, and the success or failure of the goal-directed action in terms of the success or failure of the sub-actions. The article describes how goal-directed actions can be modelled by an extension of existing results on logics of actions and change.

Discussion about received articles

There have been contributions to the discussions about the following research articles. Please refer to their respective interaction pages to review the discussion.

Michael Thielscher
A Theory of Dynamic Diagnosis

José Júlio Alferes, João Alexandre Leite, Luís Moniz Pereira, Halina Przymusinska, and Teodor Przymusinski
Dynamic Logic Programming

Articles presently under review

The following is the discussion status at the end of the year for those articles that are currently being discussed.

Michael Thielscher

A Theory of Dynamic Diagnosis.


[summary]
[Interactions]

Abstract: Diagnosis is, in general, more than a mere passive reasoning task. It often requires to actively produce observations by performing a test series on a faulty system. We present a theory of diagnosis which captures this dynamic aspect by appealing to Action Theory. The reactions of a system under healthy condition are modeled as indirect effects, so-called ramifications, of actions performed by the diagnostician. Under abnormal circumstances - i.e., if certain aspects or components of the system are faulty-one or more of these ramifications fail to materialize. Ramifications admitting exceptions is shown to giving rise to a hitherto unnoticed challenge - a challenge much like the one raised by the famous Yale Shooting counter-example in the context of the Frame Problem. Meeting this challenge is inevitable when searching for "good" diagnoses. As a solution, we adapt from a recent causality-based solution to the Qualification Problem the key principle of initial minimization. In this way, when suggesting a diagnosis our theory of dynamic diagnosis exploits causal information, in addition to possibly available, qualitative knowledge of the a priori likelihood of components to fail.

Some of the results in this paper have been preliminarily reported in (Thielscher, 1997a).

Dated: 31.12.1997

Received 7.10.1997. Status: Two recent question-contributions, awaiting answer.

Antonis Kakas and Rob Miller

Reasoning about Actions, Narratives and Ramification.


[summary]
[Interactions]

Abstract: The Language E is a simple declarative language for describing the effects of action occurrences within a given narrative, using an ontology of actions, time points and fluents (i.e. properties which can change their truth values over time). This paper shows how E may be extended to deal with ramifications. More precisely, we show how Language E domain descriptions can include statements describing permanent relationships or constraints between fluents, and how the model theoretic semantics of E can be extended in an intuitive way to ensure that the effects of actions are appropriately propagated via such statements, whilst retaining E's simple approach to the frame problem. We also show how Event Calculus style logic programs may be used to compute consequences of such domain descriptions using standard SLDNF, even when only incomplete information is given about some initial state of affairs. Because of E's generality, these techniques are easily adaptable to other formalisms for reasoning about actions, such as the Language A and the Situation Calculus.

Various Prolog program listings associated with this paper are also available from http://www.dcs.qmw.ac.uk/~rsm/abstract15.html

Dated: 31.12.1997

Received 16.10.1997. Status: The article has given rise to extensive discussion.

Paolo Liberatore

Compilability of Domain Descriptions in the Language A.


[Interactions]

Dated: 31.12.1997

Research note, received 31.10.1997. Status: No discussion so far.

José Júlio Alferes, João Alexandre Leite, Luís Moniz Pereira, Halina Przymusinska, and Teodor Przymusinski

Dynamic Logic Programming.


[Interactions]

Dated: 31.12.1997

Received 12.12.1997. Status: One question has been posed, not answered at this point.

Erik Sandewall

Logic-Based Modelling of Goal-Directed Behavior.


[Interactions]

Dated: 31.12.1997

Received 19.12.1997. Status: No discussion so far.


Other Publications

Research articles

Dated: 30.12.1997

The following three articles from the Doherty group have been published recently, and describe how they deal with (in turn) concurrency, qualification, and ramification. In particular, these articles provide the detailed answers to Vladimir Lifschitz's questions to Sandewall and Doherty, in the ENRAC Newsletter of 27.11.

The first two articles have been submitted for reviewing in another journal (not ETAI), and can therefore not be included among the articles presently being reviewed by ETAI. We have had some previous cases where the present Newsletter included references and links to current articles that are in the publication channel for elsewhere, for example the papers by Judea Pearl and his group (ENRAC 97002, 22.9.1997). We would like to encourage readers to make use of this possibility of making their current work known to the community.

The third article mentioned below is a documentation of the details of the approach: precise definition of the logic, solutions for test examples, and so forth. This is the kind of material that is not traditionally published by our journals or conferences, but which is important for any detailed analysis of an approach, and for comparisons between approaches. It is therefore reference material in the strong sense of the word: appropriate to use as a reference in conventional articles, and in order to document the details of the method being proposed. Again, we welcome similar documentations from all our readers.

Lars Karlsson and Joakim Gustafsson

Reasoning about actions in a multi-agent environment

Published by Linköping University ElectronicPress on 1997-11-14. Permanently available at http://www.ep.liu.se/ea/cis/1997/014/.

Abstract: In this paper we present TAL-C, a logic of action and change for multi-agent environments which has a first-order semantics and proof theory. It is demonstrated how TAL-C can represent (cases of) a number of phenomena related to action concurrency: action duration, interference between one action's effects and another action's execution, bounds on concurrency, and conflicting, synergistic and cumulative effects of concurrent actions. A central idea is that most of the dynamics of the world is encoded in dependency laws relating to specific features instead of encoded directly in action laws. Thus, treatment of different types of interaction can be customized for specific features.

Patrick Doherty and Jonas Kvarnström

Tackling the Qualification Problem using Fluent Dependency Constraints: Preliminary Report

Published by Linköping University ElectronicPress on 1997-12-19. Permanently available at http://www.ep.liu.se/ea/cis/1997/016/.

Abstract: Recently, a great deal of progress has been made using nonmonotonic temporal logics to formalize reasoning about action and change. In particular, much focus has been placed on the proper representation of non-deterministic actions and the indirect effects of actions. One popular approach to representing the indirect effects of actions has been via the use of causal rules which in a more general sense can be viewed as fluent dependency constraints. Although fluent dependency constraints have been used primarily under a loose causal interpretation, we show that when interpreted in a broader sense they provide a flexible means for dealing with a number of other representational problems such as the qualification problem and the ramification constraints as qualification constraints problem, in addition to the standard ramification problem. More importantly, the use of fluent dependency constraints for different purposes does not involve additions to the base nonmonotonic temporal logic, TAL, used here, but simply the addition of several macro operators to an action language used to represent action scenarios or narratives. The payoff is that TAL has already been shown to offer a robust approach to representing action scenarios which permit incomplete specifications of both state and the timing of actions, non-deterministic actions, actions with duration, concurrent actions, use of both boolean and non-boolean fluents, and solutions to the frame and ramification problems for a wide class of action scenarios. In addition, all circumscribed action scenarios in these classes and the more general class involving qualification considered in this paper can be shown to be reducible to the first-order case. Finally, a restricted entailment method for this new class of scenarios is fully implemented. In the paper, we present a challenge example which incorporates all these features, propose a distinction between weak and strong qualification with a representation of both, and provide a visualization of the preferred entailments using a research tool VITAL for querying and visualizing action scenarios.

Patrick Doherty

PMON+: A Fluent Logic for Action and Change: Formal Specification, Version 1.0

Published by Linköping University ElectronicPress on 1997-12-19. Permanently available at http://www.ep.liu.se/ea/cis/1997/020/.

Abstract: This report describes the current state of work with PMON, a logic for reasoning about actions and change, and its extensions. PMON has been assessed correct for the K-IA class using Sandewall's Features and Fluents framework which provides tools for assessing the correctness of logics of action and change. A syntactic characterization of PMON has previously been provided in terms of a circumscription axiom which is shown to be reducible to a first-order formula. This report introduces a number of new extensions which are also reducible and deal with ramification. This report is intended to provide a formal specification of the PMON family of logics and the surface language L(SD) used to represent action scenario descriptions. It should be considered a working draft. The title of the report has a version number because both the languages and logics are continually evolving. Since this document is intended as a formal specification which is used by our group as a reference for research and implementation, it is understandably brief as regards intuitions and applications of the language and logics defined. We do provide a set of benchmarks and comments concerning these which can serve as a means of comparing this formalism with others. The set of benchmarks is not complete and is only intended to provide representative examples of the expressivity and use of this particular family of logics. We describe its features and limitations in other publications by our group which can normally be found at http://www.ida.liu.se/labs/kplab/.


Debates

NRAC Panel Discussion on Ontologies for Actions and Change

The following is an additional contribution during December to a discussion that started in the previous months.

From: Erik Sandewall on 9.12.1997

Vladimir,

You wrote (ENRAC 27.11)

  I'd like to understand this better. The need to define new action languages arises when we want to describe aspects of reasoning about action that have not been understood in the past. Here are some examples.

...

These phenomena could not be described in the original action language  A  and in some of its successors. New, more expressive languages had to be designed. I am wondering what the status of examples 1-3 in the F&F framework is. Would you be able to formalize them in your original language, which you described as sufficiently expressive right from the start?

Yes. By the original language I then mean a first-order language having three predicates:

    Holds(t,f,v)   feature f has value v at time t
    Occurs(s,t,e)  event e takes place over the interval [s,t]
    Occlude(t,f)   the fluent f is occluded at time t
The fuller picture is as follows. Recall that we use

  1. a surface language, SD, for writing scenario descriptions conveniently
  2. a base language, presently chosen as the first-order language FL with the three relations  Holds ,  Occurs , and  Occlude 
  3. the macro expansion from SD to FL
  4. the classical semantics of FL (straightforward)
  5. proof methods using circumscription or tableau methods and operating on the FL representation of scenarios

    plus, for analysing the properties of those,

  6. ontologies characterizing the phenomena at hand (e g ramification, concurrency) (and also, clear expression of epistemological assumptions)
  7. underlying semantics based on the respective ontologies, defining the set of intended models for a given scenario description
  8. entailment methods for obtaining an approximation to the set of intended models, for example by imposing preferences on the set of classical models
  9. relationships between proof methods and entailment methods (in principle, entailment methods are implemented as proof methods)

The interesting thing is that quite a number of phenomena, including the ones that occur in your examples, can be accomodated within the same base language FL. Sometimes it is useful to extend the surface language SD with more macros, in order to obtain convenient expressivity, but the proof methods survive the extension since they are defined for FL.

To see how it works in more detail, a recent reference for your first two examples (involving concurrency and ramification, respectively) is a recent article by Lars Karlsson and Joakim Gustafsson, [f-cis.linep.se-97-014] As for qualification and the qualification/ramification tradeoff, this is the topic of a paper by Patrick Doherty that is just about ready. In fact, within our lab it is mostly Patrick and his colleagues and students that work on these issues and extend the limits with respect to expressivity as well as proof methods. In the course of their work, the approach is now being renamed from PMON to TAL (for Temporal Action Logics). There will be more details about this in Patrick's forthcoming answer to your questions to him.

The three relations in FL have been with us all the time since 1988-89, although their usage has been extended along the way. Also, in some of the publications the  Occurs  relation has been viewed as a 'macro'. That simplifies things and is sufficient for some purposes, but not always.

Whereas FL has been remarkably able to accomodate additional phenomena (including not only the ones in your questions, but also things having to do with mixed continuous/ discrete behaviors, imperfect sensors, etc), it has certainly been necessary to revise items 6 through 9. In fact, it is part of the basic idea that the formal ontology and underlying semantics should represent those phenomena as clearly as possible. This is the topic that I focus on in my own work. Sometimes the entailment method is developed and assessed first, and "implemented" afterwards as a proof method; sometimes it is the other way around. The approach to concurrency in the recent PMON-TAL work, for example, has not yet been analyzed wrt range of applicability and on the basis of an underlying semantics. There is some earlier work (by Choong-ho Yi) which does provide a reasonable candidate for an underlying semantics for concurrent actions, but so far it has only been used for analysing the case of independent concurrency.

With respect to ramification, my KR-96 paper [c-kr-96-99] and a related paper [s-stock-97-239] describe a formal ontology for causal-chain ramification, where one microevent (= elementary change) causes another one, which causes another one, all within one and the same main event or action. A number of entailment methods are assessed on the basis of that ontology. However, there are also other kinds of ramification that do not fit into that framework, for example, those based on physical connections between objects. It seems to me that the notion of ramification is too crude to allow a single ontological analysis.

With respect to qualification, no underlying semantics has been proposed. My belief is that even more than for ramification, a serious ontological analysis of qualification needs to identify a number of different cases which have entirely different character, and which deserve different logical treatment. However, this does not of course prevent one from proceeding with the work on representation and proof methods for qualification.

Erik


Calendar

Forthcoming conferences and workshops

LAP-98: Language Action Perspective on Communication Modelling.


Conferences and Workshops

Common Sense 1998

Dated: 19.12.1997

The following papers have been accepted for presentation at Common Sense 98. Postscript versions of individual papers are available at http://www.dcs.qmw.ac.uk/conferences/CS98/CS98Papers.html


Contexts as Relativized Definitions: a Formalization via Fixed Points

Gianni Amati and Fiora Pirri

We present a novel account of contexts, formalized as fixed point equations in the modal logic QKD4Z. This offers the ability to represent consistency and provability at the object level, with which one can then represent various relationships that must hold between different contexts, such as inheritance, disjointness, compatibility, etc. The logic also offers the ability to name contexts and to obtain explicit sentential representations for these by solving suitable fixed point equations. We illustrate our approach by examples concerning default inheritance of contexts, contradictory contexts, and integration of multiple contexts.


Point-sensitive Circumscription

Eyal Amir

A decade ago, Pointwise Circumscription was proposed as a tool for formalizing common sense. In this paper, we revisit some of its uses and examine some cases in which it does not yield the intended behavior. Specifically, we explore the cases in which unsatisfiability may result from the presence of multiple minimal models (for McCarthy's Circumscription). Then, we present a form of circumscription, called Point-Sensitive Circumscription, that is a generalization of McCarthy's Circumscription and Lifschitz's Generalized Pointwise Circumscription. We illustrate how Point-Sensitive Circumscription handles these cases without losing the control over selective fine-grained variance of predicates and functions. Last, we compare the two tools and their potential uses in formalizing Theories of Action.


Sceptical Logic Programming Based Default Reasoning - Defeasible Logic Rehabilitated

Grigoris Antoniou, D. Billington and M. J. Maher

There is a nonmonotonic logic which: (i) is suitable for default reasoning; (ii) came right from the beginning with an implementation; and (iii) is more general than other approaches which have been proposed recently. In fact this logic has been known for over 10 years now: it is Nute's defeasible logic. Despite these obvious advantages the logic is not in the mainstream of nonmonotonic reasoning, mainly because it has not been studied sufficiently as a formal system, and because its relationship to other formalisms has not been studied up to now.

This paper seeks to change the perception of defeasible logic. In particular, it presents the logic in a formal setting, derives several properties, including representational results, and gives an operational semantics. Finally the paper discusses some relationships of defeasible logic to other default reasoning approaches.


A Relational Model Of Movement

Philippe Balbiani and Luis Fariñas del Cerro

This paper presents a relational model of movement based on the notion of mobile moving about with constant speed. Three basic relations between mobiles are considered: (1) "Sometime or other, the mobiles x and u meet up somewhere", (2) "The position of the encounter between x and u and the position of the encounter between y and v are equal" and (3) " The moment of the encounter between x and u precedes the moment of the encounter between y and v".


Chronological Minimisation and Explanation

John Bell

This paper discusses chronological minimisation and the problem of representing common sense explanatory causal reasoning. The background of chronological minimisation is briefly surveyed. Then prioritised chronological minimisation is introduced. Finally, it is show that this can be used as a basis for representing explanation.


Seeing is Believing

John Bell and Zhisheng Huang

In this paper we present a formal common sense theory of perception and belief. We begin with a logical analysis of perception, and present formal semantics for a modal perception operator. We then consider the relationship between perception and belief, and in particular the question of when perception should lead to belief change. Our theory is intended to apply to both to high-level, mental, perception in humans and to perception at many levels in artificial agents, but especially at the level of the symbolic interface between a vision system and a belief system.


Minimizing the Effects of Actions

Tom Costello

The frame problem -- representing the default that the only effects of actions are those mentioned -- is a central problem in knowledge representation. This default can be captured, using circumscription, by minimizing the set of change formulas that are true, where a change formula is a formula that states that, under certain circumstances, an event causes a fluent to change its value. This approach handles domain constraints and arbitrary disjunctions correctly, unlike previous proposals. It applies a single circumscription policy to the entire theory, rather than use ad-hoc methods that depend on applying several circumscriptions or splitting up the theory before circumscription is applied.


Quantifiers and Operations on Modalities and Contexts

Tom Costello and Anna Patterson

We can reason about theories, as well as in them. Many natural phenomena can be captured by theories, often by introducing a modality, true just of the theory. Rather than treat these phenomena as the sentences true in this modality, we can treat the entire theory or modality as an object. This point of view was proposed by McCarthy, who proposed calling these reified modalities contexts.

Contexts, viewed as theories or modalities, have structural properties, and associated natural structural operations, such as union and intersection. These structural properties are most naturally captured by an algebra, a set of operations that can be applied to contexts to form new contexts.

We introduce an algebra, reminiscent of relation or dynamic algebra, but which acts on modalities, not relations. This algebra allows us to construct new modalities from simpler modalities. We use the natural correspondence between a modality and the underlying accessibility relation. The operations on modalities are induced by operations on the underlying relations.

Thus we have a larger space of modalities than just those that are explicitly named. We add quantifiers that range over modalities, so that we can state propositions like, ``no context with the property P exists'', or ``all contexts obey Q''. We give an axiomatization of these quantifiers which we show is complete with respect to a natural semantics.


Execution Monitoring of High-Level Robot Programs

Giuseppe De Giacomo, Ray Reiter and Mikhail Soutchanski

Imagine a robot that, for whatever reason, is performing a sequence of actions according to some program, and is determined to complete this execution, no matter what exogenous events occur in the world while it is executing this program. An example of this setting, which we treat in this paper, is a robot executing a program to build a tower of blocks in an environment inhabited by a (sometimes) malicious agent who might arbitrarily move some block when the robot is not looking. The robot is equipped with sensors, so it can observe when the real world fails to conform to its internal representation of what the world would be like in the absence of malicious agents. We will understand the execution monitor as a mechanism that gets output from sensors, compares sensor measurements with its internal model and, if necessary, invokes a recovery procedure to make things right again. Our purpose in this paper is to provide a situation calculus-based, purely logical account of such an execution monitor, together with a Prolog implementation for it. To illustrate the theory and implementation, we consider a standard blocks world as an environment in which a robot is executing a Golog program to build a suitable tower.


An Action Language Based on Causal Explanation: Preliminary Report

Enrico Giunchiglia and Vladimir Lifschitz

Action languages serve for describing changes that are caused by performing actions. We define a new action language C, based on the theory of causal explanation proposed recently by McCain and Turner, and illustrate its expressive power by applying it to a number of examples. The mathematical results presented in the paper relate C to the Baral-Gelfond theory of concurrent actions.

See also the later version of this article.


Local Models Semantics, or Contextual Reasoning = Locality + Compatibility

Fausto Giunchiglia and Chiara Ghidini

In this paper we present a new semantics, called Local Models Semantics, and use it to provide a foundation to reasoning with contexts. This semantics captures and makes precise the two main intuitions underlying contextual reasoning: (i) reasoning is mainly local and uses only part of what is potentially available (e.g. what is known, the available inference procedures), this part is what we call context (of reasoning); however (ii) the context may change and there is compatibility among the reasoning performed in different contexts. We validate our semantics by formalizing two important forms of contextual reasoning: reasoning with viewpoints and reasoning about belief.


Ramifications and Sufficient Causes

Peter Grünwald

Most `causal' approaches to reasoning about action have not addressed the basic question of causality: what has to be the case in the world in order for the assertion `A causes B' to be valid? Pearl's recent causal theories based on _structural equations_ do provide an answer to this question. In this paper, we extend Pearl's formalism so that the typical problems encountered in common sense reasoning about action can be represented in it. The resulting theory turns out to be a powerful tool for handling the ramification problem. It also provides new insights into actions with non-deterministic and/or `disjunctive' effects and it may help bridge the conceptual gap between `causal' and `non-causal' approaches to common sense temporal reasoning.


Local Change: A Preliminary Report

Sven Ove Hansson and Renata Wassermann

An agent can usually hold a very large amount of beliefs. However, only a small part of these beliefs is used at a time. Efficient operations for belief change should affect the beliefs of the agent locally, that is, the changes should be performed only in the relevant part of the beliefs. In this paper we generalize the operations for belief change defined by Hansson. We obtain representation theorems for the operations based on a generic consequence operator $C$ that does not need to be classic. We define a local consequence operator that only considers the relevant part of a belief base and show that this operator can be used to define local versions of the operations for belief change.


Reasoning about Change over Time: Actions, Events, and their Effects

Brian Knight, Taoxin Peng and Jixin Ma

This paper presents a new formalism for reasoning about change over time. The formalism derives a clean separation between the notion of states and situations. It allows more flexible temporal causal relationships than do other formalisms for reasoning about causal change, such as the situation calculus and the event calculus. It includes effects that start during, immediately after, or some time after their causes, and which end before, simultaneously with, or after their causes. A formal distinction between actions, action-types and events is proposed, which allows the expression of common-sense causal laws at high level. It is shown how these laws can be used to deduce state change over time at low level, when events occur under certain preconditions hold. Two problems that beset most interval-based temporal systems, i.e., the so-called dividing instant problem and intermingling problem, are absent from the formalism.


Representing Beliefs in a Situated Event Calculus

Francois Lévy and Joachim Quantz

This paper proposes an extension of the event calculus which allows the representation of alternative situations (states-of-affairs) and beliefs. The basic idea of this situated event calculus is to use the notion of situations as developed in Situation Semantics, a linguistically motivated semantic theory. Instead of having events of the form 'Happens(Action,Time)' all events occur relative to a specific situation: 'Happens(Action,Time,Sit)'. In other words, an event can happen in one situation and not happen in an otherwise similar situation.

Situations can thus be viewed as collections of events and are used here to represent beliefs: a person adopting a situation has knowledge of all the events occurring in it and believes all the fluents holding in it (i.e. all consequences of the events). Changing beliefs are modeled by adopting different situations. By using a circumscribed version of the event calculus and modeling 'adopt' and 'believes' as ordinary events and fluents, the frame problem is easily overcome, both wrt beliefs and "physical" fluents.

See also the later version of this article.


Elaboration Tolerance

John McCarthy

A formalism is elaboration tolerant to the extent that it is convenient to modify a set of facts expressed in the formalism to take into account new phenomena or changed circumstances. Representations of information in natural language have good elaboration tolerance when used with human background knowledge. Human-level AI will require representations with much more elaboration tolerance than those used by present AI programs, because human-level AI needs to be able to take new phenomena into account.

The simplest kind of elaboration is the addition of new formulas. Next comes changing the values of parameters. Adding new arguments to functions and predicates represents more of a change. However, elaborations not expressable as additions to the object language representation may be treatable as an addition at a meta-level expression of the facts.

Elaboration tolerance requires nonmonotonic reasoning, although nonmonotonic reasoning is not the focus of this article. Representing contexts as objects in a logical formalism that can express relations among contexts should also help.

We use the missionaries and cannibals problem and about 20 variants as our Drosophila in studying elaboration tolerance in logical AI.

The present version has only some parts of a situation calculus formalization. However, the English language elaborations listed are enough to serve as a challenge to logical AI formalisms claiming elaboration tolerance.


Circumscriptions From What They Cannot Do

Yves Moinard and Raymond Rolland

We show that, in the finite propositional case, traditional circumscriptions can be fully described only from the formulas which can never come as a result of the given circumscription (the ``inaccessible formulas''). Some work has already been done on the subject. Siegel and Forget have introduced the general notion of X-logic, and they have considered the case of finite propositional circumscriptions. However, their result is restricted to the case where no varying proposition appears, which is known to be a severe restriction in terms of expressivity. We extend this result in the finite propositional case to any cumulative preferential entailment, thus in particular to any ``traditional circumscription'', that is we allow varying propositions. Moreover, we describe the smallest possible set which can be used for this purpose.

We exhibit a spectacular duality between the traditional approach of a given cumulative preferential entailment, and the approach through the inaccessible formulas of this preferential entailment, i.e. the X-logic approach.

We extend these results outside the framework of pure propositional preferential entailments.


Multi-context Argumentative Agents

Simon Parsons, Carles Sierra and Nick Jennings

We propose a new approach to designing agents based upon multi-context systems and argumentation. This approach allows the development of agent architectures which have a formal model in logic and a direct link between that model and its implementation. To exemplify our approach, we describe a case study of this relationship for a particular class of agent model (namely the strong realist Belief-Desire-Intention model).


Causality in Theories of Action

Javier Pinto

Causation is a concept that plays an essential role in reasoning with commonsense. It is a property inherent to the dynamics of changing environments. Therefore, it should follow that causation should also play an essential role in the theories of action and change. However, in this article we postulate that causation is a form of abstraction. As a consequence of this view, one should not attempt to model causation as a primitive relationship between entities. Rather, causation should be viewed as an abstract relationship, which can be derived from observations (as a correlation) or derived from our knowledge of the structure of the world.

In this article, we explore the modeling of two types of problems where causation appears to be necessary. We illustrate the problems with some simple examples found in the literature. We show that by decreasing the level of abstraction one can obtain the right results.


Towards a Formalization of the Spatial Semantic Hierarchy

Emilio Remolina and Ben Kuipers

The Spatial Semantic Hierarchy (SSH) comprises a set of distinct representations of space, each with its own ontology, each with its own mathematical foundation, and each abstracted from the levels below it. In particular, the SSH topological level is abstracted from the SSH causal level. The method used to abstract the SSH topological level has usually been defined as an abduction task, described in procedural terms according to the current implementation of the SSH. In this paper we define the circumscriptive theories associated with the SSH causal and topological levels. These theories are used to formalize the SSH abduction task and prove our implementation correct. Moreover, these theories show how topological information is used to dictate spatial distinctions that cannot be derived from causal information alone.


Steady Versus Stabilizing State Constraints

Michael Thielscher

A new distinction between two kinds of state constraints is introduced and proved important for solving the Ramification Problem in Reasoning about Actions. Steady constraints never, not even for an instant, cease to being in force. As such they give rise to truly instantaneous indirect effects of actions. Stabilizing state constraints, on the other hand, may be suspended for a short period of time after an action has occurred. Indirect effects deriving from these constraints materialize with a short causal lag. Carelessly mixing these two types of indirect effects is shown to producing erroneous conclusions. On the basis of the existing theory of causal relationships we illustrate how to deal with the distinction appropriately.


A Nonmonotonic Observation Logic (Abridged Version)

Frans Voorbraak

A variant of Reiter's default logic is proposed as a logic for reasoning with (defeasible) observations. Traditionally, default rules are assumed to represent generic information and the facts are assumed to represent specific information about the situation, but in this paper, the specific information derives from defeasible observations represented by (normal free) default rules, and the facts represent (hard) background knowledge. Whenever the evidence underlying some observation is more refined than the evidence underlying another observation, this is modelled by means of a priority between the default rules representing the observations. We thus arrive at an interpretation of prioritized normal free default logic as an observation logic, and we propose a semantics for this observation logic. Finally, we discuss how the proposed observation logic relates to the multiple extension problem and the problem of sensor fusion.

See also the full version of this article.


Balls and String: Simulations and Theories

Graham White

I discuss the philosophical distinction between simulation and theory using a physical example. I also outline the connection between simulations and the semantics of linear logic, and show how Girard's Fixpoint Theorem, in Linear Logic, can be used to give a flexible and modular simulation-based approach to modelling change.


Editorial issues

A Note on Procedure

Dated: 19.12.1997

In any journal, a special procedure is needed when the editor himself or herself submits an article. In the case of ETAI's procedure for discussion and refereeing, no special procedure seems to be required for the discussion phase, since the entire discussion is done in public anyway. When we get to the refereeing phase, I will ask the area editor for one of the adjacent ETAI areas to be in charge of the refereeing.

If some reader should feel a need to communicate a message to the present editor without revealing his identity, then please relay through the area editor of one of the other ETAI areas, or through the ETAI policy committee.


Edited by Erik Sandewall, Linköping University, Sweden. E-mail ejs@ida.liu.se.