Correct text (misprint corrected): ******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 99010 Editor: Erik Sandewall 13.4.1999 Back issues available at http://www.ida.liu.se/ext/etai/rac/ ******************************************************************** ********* TODAY ********* The debate about the Levesque-Pirri-Reiter paper that was started by McCarthy and Hayes continues now with an extended comment by Graham White. Also the authors have decided to change the title of the paper (conditional on the approval of the area editor, which has been granted in this exceptional case). Furthermore in this issue, the Anonymous Referee 1 for Graham White's paper answers to White's rebuttal. At this point the author will get one more opportunity to answer, and then the accept/decline decision will be made. ********* 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: Graham White -------------------------------------------------------- I'd like to make an extended comment on the debate between McCarthy, Hayes, Reiter (et al.) concerning the nature of the situation calculus, and particularly as reflected in the last exchange between McCarthy and Reiter. First, a bit of explanatory background: I'm a mathematician (I did a doctorate in algebraic geometry at Oxford with Atiyah), and that's the way I tend to think of things. I know that mathematics tends to be regarded with extreme suspicion by the AI community, but that's my background, and I can't help it. It seems to me that one of the key assumptions behind the present stage of the debate is: (*) There is a difference between formalisms which express situations as histories and those which regard situations as snapshots. (**) Each choice of histories or snapshots expresses a different intuition about the nature of situations: e.g. Reiter writes >The principal intuition captured by our axioms is that situations are >histories .... Other intuitions are certainly possible >about the nature of situations. McCarthy and Hayes [mccarthyhayes69] >saw them as "snapshots" of a world. I wish to take issue with these, and particularly with (**). I don't think it's possible, in the present state of the formalism, even to express these questions, much less to answer them. The problem is this. In standard mathematical practice, one certainly does go through as stage of defining mathematical objects in some formal theory or other: this seems to correspond to what Reiter and his colleagues do when they define what situations are. But one *also* specifies, implicitly or explicitly, what it is for two such definitions to be equivalent. For example (and this example is taken from Benacerraf's article What Numbers Cannot Be) one can define the natural numbers both as a sequence of sets thus: \emptyset, {\emptyset}, {{\emptyset}}, {{{\emptyset}, {{{{\emptyset}}}}, ... or as a sequence of sets thus: \emptyset, {\emptyset}, {\emptyset, {\emptyset}}, {\emptyset, {\emptyset}, {\emptyset, {\emptyset}}}, ... Now clearly nothing hangs on this: the two definitions are clearly equivalent in any sense which matters. They can be regarded as two different implementations of the natural numbers. How (technically) do we express this equivalence? Several ways: i) By saying that they have "the same constructors" (i.e. we can establish a correspondence between the two sets of constructors, that the arities match up, and so on). This works under certain circumstances (that the two objects are both initial algebras for the functors defined by the constructors) which are fulfilled in this case; the constructors are, of course, zero and successor, and it's easy to see how to define them in each case. ii) One can show that a) the two objects are isomorphic, and b) that the isomorphisms are natural. This is a more general answer, but you need, in turn, to say what you mean by isomorphism (which probably involves saying what you mean by morphism in general). In our example, we're defining a natural number object in an already defined ambient category (namely the category of sets), so we already have answers to these questions. But in a more general case there may be work to do. So what I'm really worried about is this: do the "snapshot" and "history" definitions of situations express essentially different (i.e. non-isomorphic, or more exactly not naturally isomorphic) mathematical objects, or is the difference only notational, that is, analogous to the two definitions of the natural numbers above. And answering *this* question involves answering the prior one: what is an appropriate sense of isomorphism for these mathematical objects? More generally: what is an appropriate sense of morphism? Now Reiter here talks of constructors, and says, quite correctly, that his approach has constructors: for each action \alpha, we get a constructor do(a,s) which maps Actions \times Situations --> Situations. But can't we also define similar things for the snapshot view? If there are a number of actions that lead from a snaphsot-situation to its successor, then we also have a map Actions \times Situations --> Situations (and maybe it's only a partial map, but a partial map is still a morphism in some appropriately defined category, and maybe you can still establish suitable equivalences...) So I'm not convinced that there's anything in this distinction. As far as I can see this is not a straightforward question, because you can approach it from two different directions. One direction comes from the world of process algebras, labelled transition systems, and the like, and we get a definition of morphism here which basically comes from the notion of simulation. Reiter's constructors fit into this picture. But you can also approach it from the viewpoint of logic (or at least this is what people seem to have been trying to do all these years). And the logical viewpoint also gives you a way of mapping between theories (a mapping is, roughly speaking, an interpretation of one theory in another: but you have to be a little careful here because you actually have a two-category and not just a category). The culturally entrenched logics here are non-monotonic, which adds an extra complication because we cannot just carry over results from classical logic. (This applies particularly to circumscription-like theories, for which the input data is not just a classical theory but a classical theory *together with a set of literals to be circumscribed*. This set of literals breaks most of the interpretation relations between the underlying classical theories. For this reason the oft repeated statement that circumscription is "an extension of classical logic" is to be taken with a pinch of salt.) So, difficult questions. But answering them seems to be necessary if we are to know what sort of mathematical objects we are talking about. Here's a parallel. Quine said "no entity without identity", by which he meant that, in order to define some class of entities A, it wasn't enough just to say which objects were As; you also have to say when two As are the same A. One could also say (and the parallel is quite exact) "no mathematical object without isomorphism and equivalence"; that is, in order to be able to define a certain class of mathematical objects, it's not enough to be able to define instances of that class, but you also have to be able to say when to instances are isomorphic, and you also have to be able to say what the essential properties are that these objects satisfy, so that you can recognise when two candidate definitions are equivalent. Anyway, that's my .02 Euro's worth. Graham White -------------------------------------------------------- | FROM: Ray Reiter -------------------------------------------------------- Erik, In view of the tempest in a teapot that the title of our paper caused (Foundations for the situation calculus), can we change the official version to "Foundations for a calculus of situations"? Thanks, --Ray ======================================================== | AUTHOR: Graham White | TITLE: Simulation, Ramification, and Linear Logic | PAPER: http://www.ep.liu.se/ea/cis/1998/011/ | REVIEW: http://www.ida.liu.se/ext/etai/ra/rac/012/ ======================================================== -------------------------------------------------------- | FROM: Anonymous Referee 1 -------------------------------------------------------- Dear author, You wrote: >> ... And yet this work, >> which is among today's most cited papers in the area of Reasoning About >> Actions And Change, the author does not even mention, let alone compare >> it to his own method. > No, that's true, I don't, but I do cite Murray Shanahan's book > Solving the Frame Problem, which does contain a very clear and accurate > account, not only of Reiter's work, but also of the work of Pednault > and others which led up to it. If I am not mistaken then Shanahan's book is mentioned only in a footnote and only as a side remark, not for the purpose of referring to an extensive account of work related to your's. >> My only but serious concern is that existing >> solutions seem to satisfy all of the requirements and that the author >> fails to argue for merits of his approach in comparison. In particular >> Reiter's theory [1] of generating successor state axioms from simple >> effect axioms fits perfectly the author's desiderata. > But, I am talking about a case with ramification, so that Reiter's > methods do not apply; if we allow the effect axioms to talk about all But Reiter's approach has been extended to dealing with state constraints and ramifications [2,3]. Several other successful approaches to the Ramification Problem emerged during the past five years or so; I mention [4,5,6]. Repeating myself, I am missing convincing arguments why your approach is substantially different and superior in comparison. [2] F. Lin and R. Reiter, State constraints revisited, J. of Logic and Computation 4(5), 1995. [3] F. Lin, Embracing causality in specifying the indirect effects of actions, IJCAI 1995. [4] N. McCain and H. Turner, Causal theories of action and change, AAAI 1997. [5] M. Thielscher, Ramification and causality, AIJ 89, 1997. [6] M. Denecker etal, An inductive definition approach to ramifications, ETAI 3, 1999. ******************************************************************** 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.ida.liu.se/ext/etai/rac/ ********************************************************************