******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 99013 Editor: Erik Sandewall 5.5.1999 Back issues available at http://www.etaij.org/rac/ ******************************************************************** ********* TODAY ********* The reports of the two anonymous referees have now arrived for the reference article by Levesque, Pirri, and Reiter; the present Newsletter contains the referee reports in full. Both referees recommend that the article should be accepted, but both also suggest certain changes to it. The article will therefore be accepted, but the authors are given the option of revising it, taking the recent discussion and the referees' comments into account. We also have two more discussion items for the article: a remark by John McCarthy, and an answer by Graham White to Pat Hayes (who in turn wrote in response to Graham's earlier contribution in the discussion about the article by Levesque et al). Both referee's reports were written before today's discussion, of course, and the report of Anonymous Referee 1 actually arrived several weeks ago. Graham White has accepted the invitation to publish his article "Simulation, Ramification, and Linear Logic" in the April, 1999 issue of the News Journal on Reasoning about Actions and Change. Camilla Schwind has contributed an extended summary of the article "Causality in Action Theories" that she submitted recently. The summary is in latex/postscript format and can be accessed as usual from the discussion page for her article. The list of accepted papers for the NRAC workshop at this summer's IJCAI conference is also included in the present Newsletter. ********* ETAI PUBLICATIONS ********* --- DISCUSSION ABOUT RECEIVED ARTICLES --- The following debate contributions (questions, answers, or comments) have been received for articles that have been submitted to the ETAI and which are presently subject of discussion. To see the full context, for example, to see the question that a given answer refers to, or to see the article itself or its summary, please use the web-page version of this Newsletter. ======================================================== | AUTHOR: Hector Levesque, Fiora Pirri, and Ray Reiter | TITLE: Foundations for the Situation Calculus | PAPER: http://www.ep.liu.se/ea/cis/1998/018/ | REVIEW: http://www.ida.liu.se/ext/etai/ra/rac/017/ ======================================================== -------------------------------------------------------- | FROM: John McCarthy -------------------------------------------------------- I have no grumble about the new title. Here are some comments on the substance of the article. The paper presents a big bang interpretation of the situation calculus. Everything started with S0. 1. It is not elaboration tolerant w/r to what might have happened before S0. 2. The induction scheme can obtained relative to any situation. We introduce Can-future(s0,s), where the variable s0 can be any initial situation. The axiom schema is phi(s0) \land (\forall a\ s)(phi(s) \rightarrow phi(result(a,s))) \rightarrow (\forall s)(Can-future(s0,s) \rightarrow phi(s)). 3. We need to compare a situation with situations that it isn't convenient to consider as having arisen from S0. One example comes from counterfactuals. "If another car had come over the hill while you were passing, there would have been a head-on collision." There is no need to consider the hypothetical situation as arising from S0. 4. We can use the context mechanism proposed in \cite{McC93} to put the big bang interpretation in its place. We have c0: Ist(Bigbang,Is-situation(s)) \equiv Can-future(s0,s). When the context Bigbang is entered, the LPR big bang induction schema holds. -------------------------------------------------------- | FROM: Graham White -------------------------------------------------------- Here's my reply to Pat Hayes. First to correct his misapprehension of where I'm coming from: he writes > I have a mathematical training myself, and find the logical > security of mathematics comforting, if anything. Now I am a mathematician, not a logician, and for my taste I find that there's far too much logic in AI, and far too little mathematics. My background is in category theory, but I also have a great love of the mathematics of the nineteenth century; I'll be expressing myself in terms of category theory, but much of what I say would, I would imagine, be comprehensible to people like Felix Klein or Elie Cartan. Hayes' historical perspective seems to involve an inexorable growth in sophistication ("mathematical domains with their modern reconstructions in set theory from the 1920s, or (still more sophisticated) in category theory from the 1950s") whereas as far as I'm concerned things got very boring from Hilbert till the end of the second world war and picked up again after that. Now to business. Hayes writes: > To see the difference, take a mathematical concept such as 'group', and > ask how one could know a group if one met it. Something is a group just > when it satisfies the group axioms. The axioms are all there is: > anything that satisfies the group axioms is a group, by definition." "how one could know a group if one met it"? Well, there are two questions here: i) What sort of things are groups? Hayes says "Something is a group just when it satisfies the group axioms. The axioms are all there is". Well, no. Here's Hayes' definition (maybe): > a group is a set with a composition law such that ... and here's my definition: > a group is a category with one object in which every morphism > is an isomorphism and there are, of course, innumerable others. Part of the reason for this multiplicity is that we want to use some definitions in some circumstances and some in others: for example, my definition works for things such as algebraic groups, or formal groups, where there is no underlying set. The other question is, of course, ii) What is this particular group, for example, the Klein four-group? Also in this case, it's not simply the case that something "just is" the Klein four-group or not: Hayes describes it as "the possible orientations of a rectangular card", but you can also describe it with a multiplication table, or a Cayley diagram, or a matrix representation, and so on. And in each case it's a non-trivial question whether these definitions are equivalent, or whether some item, given in some way or other, fulfils some particular one of these definitions. In either case, there is a difference between how things are presented and how they are: we can present things in all sorts of different ways, but they can turn out to be essentially the same. We cannot go by the mere appearance of the definitions. Now this is entirely similar to real life: I can think of hardly any area in which one does not have to make any distinction between how things appear and how they are. There is, it seems to me, no subject (say "ontology") with enough authority to say "It is simply an ontological distinction that X is not Y". (If you think that ontology will deliver you stuff like this, then you ought to come to terms with Quine.) If we want to talk about the sort of empirical investigation that Hayes talks about -- of comparison between formalism and reality ("testing their logical theories by incorporating them into actual physical robots with measurable behaviour") -- then we are relying on implicit ideas about identity, on both sides. If we are testing whether formal theory A fits phenomenon X, then we had better be able to say what it is, on the side of reality, for X to be the same as Y (despite appearances), and, on the level of formalism, for A to be the same as B (despite appearances, or notation, or whatever). Otherwise we cannot claim to be doing science. All the notation, and all the measurement, in the world will not save us if we cannot answer these questions. So why category theory? Nothing special hangs upon it: but two reasons why it is useful. The first is that it provides a treatment, within mathematics, of the difference between how things are presented and how things are. This is why category theory is useful: people use it in subjects (such as algebraic topology) where things can be presented in many different ways, but maintain an essential unity despite that. We don't need to use category theory for this: other areas of mathematics play similar roles (for example, the spectral theory of operators plays an entirely similar role within quantum theory), but category theory has the advantage of being fairly topic-neutral and adaptable. The second is this. Category theory is behind several of the most successful areas of modern mathematics (algebraic geometry, differential geometry, algebraic topology), and what these applications of category theory have in common is this: they are all mathematical treatments of qualitative phenomena. They are very successful: the proof of Fermat's last theorem (though the final result is about numbers) is an offshoot of work in these qualitative areas. Many of the problems of artificial intelligence are problems of formalising qualitative phenomena, and AI seems to lack conceptual tools for dealing with the qualitative (Hayes, for example, takes it for granted that experiment involves measurement, and seems in the field to be a general tendency to confuse the qualitative with the approximate). Category theory provides a range of technical tools which are qualitative, successful, and richly structured. You might, of course, say -- and Hayes seems to be tending in this direction -- that this is all mathematics, and Real Life is somewhat different, and that AI is a study of Real Life. To which I would like to reply: i) in that case, why are AI publications so full of ugly formulae? and ii) my argument relies on one respect in which mathematics tends to be similar to Real Life, namely that, in both cases, you have to be careful about the distinction between how things are presented and how things really are. In neither case can you jump to conclusions about essential identity, or difference, merely because of notational, or presentational, differences; and this was the point that got me started in the first place. Anyway, that's that. Graham White -------------------------------------------------------- | FROM: Anonymous Reviewer 1 -------------------------------------------------------- Recommendation: Accept. (This report was written before the open discussion about the article had started.) I find the article to be very well written and quite interesting. Particularly interesting is the section on Metatheory for the situation calculus which provides a better theoretical understanding of the logical language. In general I think that the article fits its purpose. Namely, to provide a common standard for the general KR audience to the approach based on the situation calculus for the specification of action theories. I find that the article, however, has an important shortcoming. The article is self centered, focusing only on the work of the authors. There is a great deal of work based on the situation calculus that is not touched upon in the article. The authors might argue that this body of work is not well established to be considered part of the foundations of the language. I refer to the work on causality, narratives, and other contributions by many authors (McIlraith, Miller, Shanahan, Pinto, Lin, etc.). I don't believe that the authors should extend their article to incorporate a detailed discussion of this work. However, the article should provide pointers for the research related to the situation calculus, and mention its relevance. For example, with regards to causality, it should state what the problem and intended solutions are and point to the right references. -------------------------------------------------------- | FROM: Anonymous Reviewer 2 -------------------------------------------------------- This article should be accepted. It covers a major (possibly the largest single approach to reasoning about action) area, is written by the very best qualified people, and is technically accurate. This is not to say that it could not be improved. I hope the following points help improve the article. Sadly this paper does not really meet the refereeing criteria for reference articles. I believe that, in some ways, previous articles, or the article that the first part of the paper is taken from, provide better reference sources. While the article definitely represents a tradition - the Toronto School - it does not meet fully three of the other four conditions. Namely, it does not capture the assumptions, motivations, and notations used in the Toronto School, it would not always enable one to skip the introductory definitions in other papers, and it is not pedagogical, or at least not to the standard of some of the authors other papers, rather it is full of detailed technical points, without explanations or intuition. The article consists of two sections, the first is a cut down version of an article to appear in another journal. The theorems stated in the paper are proved in the article under review by another journal, proofs are omitted from the reference article, (as one would expect). The first section of the paper is less an introduction to the tradition, than the particular definitions needed for a very technical paper. In particular, no general motivations or assumptions are specified. For instance, the paper deals mainly with *basic action theories*. These are introduced by the two sentences, "Our concern here is with axiomatizations for actions and their effect that have a particular syntactic form. These are called *basic action theories*, and we next describe these." This is insufficient introduction. A definition of uniform formulas follows. Here I digress as this bears on another weakness of the paper. The original terminology for uniform (in Reiter's The frame problem in the situation calculus) was *simple*. McIlraith continues to use simple as late as 1997. In G. De Giacomo, R. Reiter and M. Soutchanski. Execution monitoring of high-level robot programs, the phrase "whose only situation term is s" is used instead. (This is an error, as bound occurrences of s are not allowed in general.) I mention this only as an example of how the paper introduces new terminology, without relating it to the original terminology, or explaining in any way why we should care about this definition, e.g. why it is correct, but "whose only situation term is s" is not. The rest of section 4 is other definitions, save for four paragraphs, a restatement of the definition of *uniform*, an example of an action precondition axiom, a comment on early work, and the claim that the consistency property is sufficient. None of these provide any idea of why this tradition arose. Effect axioms are never mentioned. Neither are frame axioms. No reasons why basic action theories are useful, might arise in practice, are a good subset to study, or are amenable to study are given. This should be compared with Reiter's paper, "The frame problem in the situation calculus", which essentially covers the same ground, but introduces effect axioms, frame axioms, the completeness assumption for preconditions, the explanation closure assumption, general positive and negative effect axioms, the completeness assumption, and a clear explanation of why regression is important (planning and Green etc.). That paper provides a much better reference paper for these points than the paper currently under review. The first half of the paper fails refereeing criteria 2, in that it does not specify the assumptions, motivations, and notations used in the approach. The lack of some background is not the only failing of the paper. Perhaps the greatest failing of the paper is to provide something that could be used as a reference. This is most clearly shown by the second part of the paper. This is written in an entirely different style, without formal definitions. The first thing this section does is to throw out the earlier definitions. They first add two new symbols to the situation calculus. Earlier, much care was made in stating that symbols like this were disallowed. The entire definition of the language of the situation calculus is fashioned to deny the existence of new predicates on situations. Next, the definitions of section 3, where 4 foundational axioms were given are changed. Only two axioms remain from the 4 foundational axioms, the unique name axioms. The other foundational axioms are changed drastically. (Perhaps this shows that the other foundational axioms should be divided into parts.) Thus the basic definitions of section 2 and 3 do not serve even until the end of the paper. The paper also contains a definition of Golog, which is essentially a notational variant of dynamic logic. The claimed difference, procedures, are a well known alternative to using a fixed point operator. The semantics of dynamic logic and Golog are isomorphic. If there is anything else to Golog, as I believe there is, it is not clear from the paper. ********* FORTHCOMING EVENTS ********* --- PROGRAM FOR NRAC WORKSHOP AT IJCAI --- Papers accepted for presentation -------------------------------- Giuseppe De Giacomo, Riccardo Rosati Minimal Knowledge Approach to Reasoning about Actions and Sensing Enrico Giunchiglia, Vladimir Lifschitz Action Languages, Temporal Action Logics and the Situation Calculus Paolo Liberatore BReLS: a System for Revising, Updating, and Merging Knowledge Bases Maria Cravo, Joao Cachopo, Ana Cachopo, Joao Martins Permissive Belief Revision (preliminary report) Alberto Finzi, Fiora Pirri A preliminary approach to Perception in Theory of Actions Sergio Brandano K-RACi Eyal Amir Directed Object-Oriented First-Order Logic Mikhail Prokopenko, Marc Butler Tactical Reasoning in Multi-Agent Systems: a Case Study Papers accepted for workshop notes only --------------------------------------- Jixin Ma An Approach to the Frame Problem Based on Set Operations Hisashi Hayashi Abductive Constraint Logic Programming with Constructive Negation Norman Foo, Dongmo Zhang Convergency of Iterated Belief Changes Massimo Franceschet, Angelo Montanari Pairing Transitive Closure and Reduction to Efficiently Reason about Partially Ordered Events Pedro Matos, Joao Martins Non-situation calculus: relating STRIPS and situation calculus Pedro Cabalar, Ramon Otero Pertinence and Causality John Bell Primary and Secondary Events ******************************************************************** This Newsletter is issued whenever there is new news, and is sent by automatic E-mail and without charge to a list of subscribers. To obtain or change a subscription, please send mail to the editor, erisa@ida.liu.se. Contributions are welcomed to the same address. Instructions for contributors and other additional information is found at: http://www.etaij.org/rac/ ********************************************************************