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.

The following article has been received by the present ETAI area, which means that it will be open for a three-month discussion period, followed by the closed peer-review decision on whether it will be accepted by the ETAI. All readers of this Newsletter are invited to participate in the discussion.

Please don't be shy to ask questions; it is actually in the author's interest to receive tough questions. Just like at an internal seminar, they give him or her a chance to show that he/she is able to answer well, and they give valuable feedback. Also, since the article has already been published (but not yet refereed), it is citable from now on, so tough questions do not deprive the author of being "on record" with the article.

Clicking the title of the article leads to the official cover page where it was published, with links e.g. to its full text. Clicking "[interactions]" leads to the on-going question-answer debate about the article, with options for submitting a question or comment to the present Newsletter editor.

Erik Sandewall

Logic-Based Modelling of Goal-Directed Behavior.

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.

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.

Unfortunately, there was an error in the URL for the received article by Alferes, Pereira, et al that was reported in our previous issue. The correct reference follows, together with the abstract for the article.

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

Dynamic Logic Programming.

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 P₁ ø P₂ ø ..., 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.

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.