|
| Moderated by Erik Sandewall. |
Hector Levesque, Fiora Pirri, and Ray ReiterFoundations for the Situation Calculus |
The
article
mentioned above has been submitted to the Electronic
Transactions on Artificial Intelligence, and the present page
contains the review discussion. Click here for
more
explanations and for the webpage of theauthors: Hector Levesque, Fiora Pirri, and Ray Reiter.
Overview of interactions
Q1. John McCarthy (30.3):
I have a grumble about the title of the article by Reiter, et. al. about situation calculus. It presents a particular system of the situation calculus, and therefore can't quite serve as a reference article.
A1. Ray Reiter (3.4):
John McCarthy wrote:
John's grumble about our title -- Foundations for the Situation Calculus -- is perhaps justified. A better title might have been "Foundations for a Calculus of Situations". If Erik will permit it, maybe we can make that change in the archival copy. Hector suggested that if only we were centred in Denmark, we could have used something like "Foundations for the Copenhagen Interpretation of the Situation Calculus". Too bad. C1-1. Ray Reiter (13.4):
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,
John McCarthy's 'grumble' in ENRAC 30.3 (99007) raises a general issue of nomenclature. The following scenario is quite a common one. A formal term of art becomes generally used to refer to something in the literature which was invented or introduced by someone. After some time has elapsed, however, another author or group re-adopts or re-uses the term in a somewhat different sense, and this second sense is then widely used by a related community, or among a different generation of researchers. This has happened for example to the word "ontology", which is now widely used in the, er, ontology community to refer to what philosophical logicians (who originally had possession of the word) called "axiomatic theories". In our community it has happened to "situation", which is now widely taken to mean what Reiter (et. al.) defines it to be, ie a finite sequence of actions, and its cognates such as "situation calculus", which Reiter (et al) uses to refer to a particular formalization developed at Toronto in the last decade. Neither of these meanings are what these terms meant before Reiter changed the language. The result of such alterations in meaning is pernicious only if people fail to realize that it has happened, or are unclear about which sense they intend when they use the term; but when this does happen, a great deal of confusion, not to mention emotional heat, can be generated. Once introduced into a community, terminology has a life of its own, and nobody can expect to exert a kind of eternal authority over it. But any useage of such a term should clarify which sense is meant; and any writing which purports to be a definitive survey of a topic must be especially careful about such ambiguities, and to make clear to a reader that the word has changed in meaning. Evidently what Reiter and his co-authors mean by "situation calculus" isn't what John McCarthy invented. Regardless of the relative merits of the calculi being referred to, a survey with that title should at least clarify and respect the way that the terminology was used for about a quarter of a century before Reiter re-defined it. Pat Hayes A2. Ray Reiter (3.4):
Pat Hayes wrote:
Pat and John's complaints raise some interesting issues about the importance of fully axiomatizing one's intuitions, something that the reasoning-about-actions community has been carefull to do. In their KR'98 paper, John and Tom Costello spelled out a different variant of the sitcalc to the "Toronto interpretation". To my knowledge, this is the only other fully specified sitcalc story, and now there is the possibility of looking at the pros and cons of the two approaches. It would be very interesting to see an axiomatization of the intuitions underlying the earlier "situations-as-snapshots" view. Probably other interpretations are possible of John's original sitcalc language, or extensions to it. Situations are not like the natural numbers; there seems to be no standard interpretation for them, and maybe this discussion will encourage others to step forward with alternative axiomatizations reflecting their intuitions. It remains to be seen whether, after the dust settles, something like "the Peano situation calculus" will emerge.
C2-1. John McCarthy (3.4):
I see that I didn't make my grumble clear. I think the Reiter, et. al. system is one situation calculus formalism. I think that a reference article should be broader.
C3-1. Graham White (13.4):
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 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:
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
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
Graham White's extended comments (Enrac 13.4) are interesting, but not for the reason I suspect he had in mind. White, as he says, is approaching the entire discussion from a mathematical perspective. If things like situations (whatever they are), world-states, actions and histories were indeed mathematical structures, then his remarks would be apposite: it would be good professional practice to ask what the appropriate morphisms were between them, for example, and what would count as isomorphism. But they aren't mathematical structures, and this entire game we are playing here isn't mathematics. We are using logic not to describe mathematical structures, but to describe aspects of nature. This isnt a matter of looking on mathematics with 'extreme suspicion', by the way. (I have a mathematical training myself, and find the logical security of mathematics comforting, if anything.) The point is that what we are wanting to do is more like science than mathematics. There is a real world out there, and our job is to try to describe it adequately. Many people in action reasoning, in fact, see their task as rigorously empirical, and advocate testing their logical theories by incorporating them into actual physical robots with measurable behaviour. Having made that analogy, however, let me immediately modify it. What we often find ourselves doing isnt science so much as a kind of pre-science: the kind of conceptual analysis that precedes an exact science. We are still sometimes arguing about what our words mean. But whether it is scientific or pre-scientific, it is always directed towards, and inspired by, something in the actual world, not by mathematical criteria. 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. One can find examples of many famous finite groups all over the place: the Klein group, for example, is revealed in the possible orientations of a rectangular card. Now, contrast this with a concept like 'banana'. Even an optimistic mathematician would surely not expect the be able to reconstruct bananas within set theory (even up to isomorphism), or give a sensible account of banana-morphisms. Actions and world-states are more like bananas than groups. White's examples make the contrast very clear. He uses the example of the natural numbers:
First, note that the idea of natural number preceded both of these set-theoretical constructions. In fact, it preceded the idea of 'set' by several centuries, if not millenia. (Its easy to forget that the great success of logicism in modern foundations of mathematics tends to produce a historical revision of ideas that go back a very long way into human history; modern accounts of mathematical structure are written from a perspective which identifies mathematical domains with their modern reconstructions in set theory from the 1920s, or (still more sophisticated) in category theory from the 1950s.) So even in mathematics, I think that the formalisations tend to be driven by pre-formal intuitions. But why would we expect that actions would form a category, or be definable (even up to isomorphism) in set theory? I see no reason to suppose they would, and several good reasons to suppose not. But even if they did, there is still a further question to ask, which is how that mathematical structure fits onto the actual world we are aiming to describe. An example. Consider a ball bouncing on a table. We could say that each period between two bounces is a 'state' of the ball, and that each bounce is a state-transition (one where it might lose a little energy, say, producing a lower bounce next time.) Or, we could say that each moment of contact with the table was a 'state', and each trajectory between bounces a state-transition. These might well be isomorphic structures (finite total orders) in White's mathematical sense, but they kinds of axioms one will write about the 'states' and 'actions' will be very different in the two cases; and if someone is thinking in one way when talking to someone else who is thinking the other way, mutual incomprehension may well result. (Ray Reiter and I are conducting a discussion offline to see if we are misunderstanding each other in exactly this way.)
Pat Hayes PS a minor note:
Of course there is nothing in this as a distinction. The
C3-3. Graham White (5.5):
Here's my reply to Pat Hayes. First to correct his misapprehension of where I'm coming from: he writes
Now to business. Hayes writes:
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):
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: Anyway, that's that. Graham White
Q4. John McCarthy (5.5):
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
1. It is not elaboration tolerant w/r to what might have happened
before
2. The induction scheme can obtained relative to any situation. We
introduce
3. We need to compare a situation with situations that it isn't
convenient to consider as having arisen from 4. We can use the context mechanism proposed in cite{McC93} to put the big bang interpretation in its place. We have
When the context John McCarthy Q5. Anonymous Reviewer 1 (5.5):
Recommendation: Accept. (This report was written before the open discussion about the article had started. The stated date refers to when the report was made public.) 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.
Q6. Anonymous Reviewer 2 (5.5):
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.
|