|
|
News Journal on Reasoning about Actions and Change |
| Vol. 1, Nr. 5 | Editor: Erik Sandewall | December 31.1997 |
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 |
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 second-last Newsletter issue for 1997 contains abstracts of three recent articles (not ETAI submitted) on reasoning about actions and change, and a comment that puts these articles in perspective.
Tomorrow's Newsletter will contain a summary of the state of articles presently under review, and a concluding editorial statement that summarizes the experience of the ETAI and of the present Newsletter during the past 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 |
The following articles have been received during the month of December, and review discussions have been opened for them.
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.
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.
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
The following is the discussion status at the end of the year for those articles that are currently being discussed.
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.
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.
Dated: 31.12.1997
Research note, received 31.10.1997. Status: No discussion so far.
Dated: 31.12.1997
Received 12.12.1997. Status: One question has been posed, not answered at this point.
Dated: 31.12.1997
Received 19.12.1997. Status: No discussion so far.
Other Publications |
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.
Debates |
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
|
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
plus, for analysing the properties of those,
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
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
References:
| c-kr-96-99 | Erik Sandewall. Assessment of ramification methods that use static domain constraints. [entry] Proc. International Conf on Knowledge Representation and Reasoning, 1996, pp. 99-110. |
| f-cis.linep.se-97-014 | Lars Karlsson and Joakim Gustafsson. Reasoning about actions in a multi-agent environment. Linköping University Electronic Press, 1997: [original publication] |
Calendar |
Conferences and Workshops |
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.
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.
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 |
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.