![]() |
Moderated by Erik Sandewall. |
Graham WhiteSimulation, Ramification, and Linear Logic |
The
article
mentioned above has been submitted to the Electronic
Transactions on Artificial Intelligence, and the present page
contains the review discussion. Click for
more
explanations and for the webpage of theauthor, Graham White.
Overview of interactions
Q1. Tom Costello (1.10):
Dear Graham
On page 2 of your article, "Simulation, Ramification, and Linear
Logic" you suggest that effect axioms should have
It seems to me that many effect axioms will have preconditions that
say that the effect will occur in certain circumstances, unless there
is something that prevents it. This is naturally written as a
The left hand side side of this effect axiom is clearly equivalent to
a Yours, Tom Costello
A1. Graham White (3.10):
Dear Tom,
Thanks for your question. It seems to me that I would want first of all
to differentiate between your two formulations of the basic objection:
i) "some local properties ... are expressed as The first formulation has to do with local properties, which I take to be a fairly general, phenomenological notion; the second is to do with action preconditions, which is a notion internal to certain treatments of the frame problem. I'll deal with the second notion first. My approach doesn't really use action preconditions per se. I don't have anything like a result function: given linear logic terms s and a representing a situation and an action, there may or may not be a valid inference of the form
We now apply the ramification machinery that I described: that is,
we look for sequents corresponding to performing the action,
followed by a terminating sequence of ramification transitions,
such that we eventually end up with a situation of the
form Incidentally, I'm not at all sure about the phenomenological motivation of the concept of precondition. It seems to me that it conflates two quite distinct phenomena: the first is of actions (such as "opening the door") described by what Ryle called "success words", where it doesn't make sense to talk of performing them when they don't succeed. The other is of action descriptions such as "trying to open the door", where the possibility of failure is allowed for, and where we usually also have some intuitions about what happens in the case of failure. As Ryle (and I suppose also Wittgenstein) point out, the second case is rather more complex than the first, and probably needs a more elaborate description than simply giving preconditions. The first is the usual case in a great deal of everyday language, but, by its nature, does not need any explicit talk of preconditions (although one could, presumably, in many cases find implicit preconditions).
Your first objection is that many local concepts are in fact I hope this helps, anyway. Graham
Q2. Andreas Herzig (3.10):
Dear Graham, I appreciate the aims of the paper, viz. the discussion about the logical form and the proof-theoretic account of reasoning about actions as given in sections 1, 2.1.1, 2.4. I think that too little work has been done in the community on such fundamental issues. Basically you propose Linear Logic (LL) as a proof theory to reason about actions, following Girard who claimed from the beginning that LL would be much better suited for reasoning about actions and change than any other logical system. LL people have tried to support that claim, such as Masseron et al. (LNCS 427, 1990) or Bidoit et al. (JLC, 1996). The same has been tried also by people coming from Bibel's linear connection method - see e.g. Bibel's IJCAI'97 invited lecture, as well as work of Fronhofer and Grosse et al. that Bibel cites; see also the subsequent discussion at
This is my main criticism. What follows are more detailed comments.
Sections 2.2. The two-blocks Example 1 is similar to Lifschitz' two
switches example, I suppose. (Btw. on p.4, line 8 should be dropped.)
I guess circumscription doesn't give the solution, but several ones,
one of which you give in the table. (Btw. one Sections 2.3. I don't understand the difference between Example 1 and Examples 2 and 3. Where does the `support' concept come from? I need more comments here.
Section 2.4. The expression "equivalent in first order logic to theory Section 3.2. You claim your rewrite rules for the two blocks theory is `local data', in the sense that they remain valid `if we introduce new types of cause'. But what about introducing an action such as cutting or removing the string between the blocks? Then the rewrite rules `linking' the blocks do not hold any longer. Section 4.1. Wy don't you mention the cut rule here? (you talk about its elimination in the proof of Proposition 1). In the statement of Proposion 1, you don't say what ACI is. If you have cut, how can composition of rewrites be a problem? Cut is just doing that job, viz. chaining sequents. I guess this relates to my main criticism: in order to identify actions in proofs, you must group together sequences of rules related to the same action. This means that there is a new concept that is exterior to LL. (I think the problem of termination of sequences is similar.) Section 4.2. I don't understand how the introduction of modal operators solves the above problem. In the basic rewrite rule of Definition 1, I suppose the LL `times' operator is rather an ACI bullet.
I found it difficult to understand the exposition on termination. I suppose
termination refers to termination of a rewrite sequence corresponding to an
action. In the rule, the notation
A2. Graham White (28.10):
Dear Andreas, Thank you for your comments on my paper. I'll try to respond in order.
However, if you do want state constraints (if, for example, you want to do other things than simply generate the ramification behaviour from them), they can be added to my approach, and I've shown how to treat a simple case in my reply to Tom Costello. However, there are important conceptual (not mathematical) issues to be resolved first: in particular, there is an obvious distinction between state constraints which are required to hold during the ramification process, or only at the end of it.
Cut elimination is important, because, if you have it, you can show that the only proofs of the sequents that encode actions correspond to the changes that those actions produce; that is, it says that the linear logic connectives have their intuitive meaning. This is a theme in a tradition in the proof theory of intuitionism, starting with Martin-Löf; the question is, can you understand the logical connectives simply by their role in proofs? And the answer is, yes you can, if the system satisfies cut elimination: because then we only need finite data to decide whether we can apply a rule or not. But the cut rule breaks this, because we can apply it with any cut formula, which is an unbounded totality. So systems without cut can be understood, in some way, finitely, whereas systems with cut can't.
Anyway, I hope this helps. Thanks again for your questions. Graham White
Q3. Anonymous Referee 1 (27.3):
The following are my answers to the refereeing questions.
[1] Ray Reiter, "The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression," in: Artificial Intelligence and Mathematical Theory of Computation, Academic Press, 1991.
A3. Graham White (4.4):
Anonymous Referee 1 wrote:
However, Reiter's account starts from a statement of what he and Pednault describe as "effect axioms" (p. 360 of Reiter's article), which give, for each action and each fluent, conditions under which that fluent positively or negatively affects the fluent. These conditions, because they talk about all fluent-action pairs rather than just the fluents which are immediately affected by the action, are not concerned with the immediate or primary effects of actions but all of them. Now Reiter's paper does not explicitly consider the ramification problem, and, if we do not have ramification, it is entirely reasonable to suppose that actions can be described by effect axioms: actions then have no effects but their immediate effects. And it is certainly true that, in the absence of ramification, Reiter's solution does satisfy my desiderata (or, at least, the ones that I give in Table 1, apart, of course, for the requirement that the effect axioms should be local, which has little content in the absence of ramification). 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 effects, instead of just the immediate ones, then there is essentially no distinction between immediate and non-immediate effects. Neither can we hope to derive the unrestricted effect axioms from the local ones using merely classical logic (this, of course, is the assumption in Reiter's article; the effect axioms are supposed to yield all of the effects, local or non-local, using classical deduction). Consider the following example:
We want, of course, to conclude that the block becomes wet. However,
in order to do this, we have to conclude that location L is wet,
not in the initial state, but in the successor state. And we cannot
conclude this by classical logic alone; considerations of examples
like this (electrical circuits are a fruitful source) shows that,
if we have a chain of propagating effects, we must, in general,
solve the frame problem for the propagating causes up to stage
C3-1. Anonymous Referee 1 (13.4):
Dear author, You wrote:
[2] F. Lin and R. Reiter, State constraints revisited, J. of Logic and
Computation 4(5), 1995.
C3-2. The Author (27.4):
Here's my reply to the referee's remarks.
Let's start with what appears to be a misconception. The referee writes "state constraints and ramifications", as if the two were synonymous. They are not, and one of the articles he refers to (by Deneker et al.) explains why not ([6], pp. 3f.):
So there are examples which formalisms based on state constraints cannot cope with: this rules out the referee's reference [2]. Of the other approaches, [3], [4] and [6] suffer from the limitation (which Deneker et al., in [6], admit to) that multiple changes of the same fluent at the same time cannot occur. One can give well motivated examples which exhibit this behaviour: consider, for example, a modification of Deneker et al.'s counter example in which the counter is now connected to two of the output lines, and in which the input action may cause changes in either or both of them. The propagation of the effects may well result in the occurence of intermediate states of the counter when one of the output lines has had its effect but not the other. Similarly, the electrical circuit example in Thielscher's [5] (p. 341, Fig. 5) has intermediate states of fluents (namely, the light bulb being on) which are caused during the ramification process but which do not persist into the final state. Deneker et al. do describe such examples as "not well defined", but they do not argue for this restriction. So my approach, which correctly handles examples such as those given above, is more general than all of the cited approaches apart from Thielscher's [5], which also handles these approaches correctly. And regardless of the success or failure of my own approach, what we have done so far is to eliminate all but one of these supposedly "successful approaches to the Ramification Problem" by referring to arguments and examples found in the other ones. This makes me a little suspicious of the rules of this refereeing game as it is played in the AI community. After all, if I say "The sky is blue" and the referee says "No, you're wrong, the sky is green", then I may at least want to verify that the sky is, in fact, blue, just to check. But if the referee says "you're wrong, the sky is green AND the sky is red", then what do I reply? And if the referee cites supposedly "succesful approaches to the ramification problem", and not all of them can be simultaneously succesful because the later ones argue against the earlier ones (so that either the earlier ones are wrong, or the arguments and examples in the later ones are wrong); well, what can be concluded from that, other than that there are papers in the literature which disagree with mine (no surprise) and also with each other (also no suprise). What I want to insist on is the argument of my paper, and particularly the argument in Section 2.4. What I argue there is this: that the standard approach to these problems is unduly sensitive to vocabulary, because we can make formalisations, which seem to be adequate, of the same problem in vocabularies which seem to be logically equivalent (because they are equivalent in first order logic), and we find that when we apply the circumscription procedure to them, that one is successful and the other is not. And we seem to have no way of selecting one vocabulary rather than the other, other than that one gives a successful circumscription and the other does not. So this circumscription procedure does not seem to be anything that we can apply to a problem that we do not know the answer to: regardless of how adequate our formalisation might seem to be, we always have to face the possibility that there might be another formalisation (equivalent in first order logic, but using a different vocabulary) which gave different results under circumscription. We seem to have no way of differentiating between good vocabularies and bad, other than by looking at the results. Almost all of the cited approaches are, at least prima facie, susceptible to this sort of problem; they all rely, to some extent, on a preferred vocabulary -- explicitly in [2] and [3], because we have fluent-based circumscription; implicitly in [4], because of the definition of interpretations there as sets of fluents, and in [6] because of the use of reification in the definition of the fluent calculus. My own approach is not: I refer, in the article, to the fact that "in [the technical report] we show that we have a good notion of interpretation for theories of this sort, and that, in our example, we can change from the [one vocabulary to the other] without breaking anything". (p. 12 of the article). Furthermore, I have a semantics for my logic (also in the technical report); all of the above I am willing to expound at greater length if required (though I am still somewhat attached to the principle of separating the more philosophical and expository arguments from the mathematical details, and that was what I had hoped to accomplish in the separation between article and technical report). One could, finally, talk about the great computational advantages of approaches based on linear logic when compared to those based on circumscription or other of the conventional non-monotonic logics. So, finally, if you want a summary of what I think the advantages of my approach are, they would be:
C3-3. Murray Shanahan (28.4):
Here's a small contribution to the Graham White paper debate. First, let me point out that I haven't (I'm ashamed to say) got around to reading Graham's paper, yet. So I'm not in a position to have any overall opinion on its merits. But I have followed the debate, and this has led me to the following thought. Graham lists the following advantages of his approach.
Certainly (i) on its own, if true, suggests that the significance of the paper's contribution is sufficient for a journal. (I can't comment with respect to the other usual criteria for acceptance, not having read the paper.) But I think Graham is selling himself short. Merely to match the capabilities of existing formalisms using a radically different logic, namely linear logic, is itself a worthwhile contribution, assuming it's a non-trivial exercise. Redoing existing work in a very new way adds to our knowledge of the space of possible action formalisms, and could lead in all sorts of new directions. (Of course, the new way of doing things has to be radically different to be justified. Otherwise we end up with a proliferation of uninteresting variations on the same old theme.) Murray
Q4. Anonymous Referee 2 (27.3):
My recommendation as regards the acceptance of this paper for ETAI is no. Accordingly, I have perhaps to explain that. Roughly speaking, my answer is no, because there is a very little difference between the submitted and revised versions of the paper. On the other hand, the remarks, especially those made by Andreas Herzig, were quite important, and so they should be seriously taken into account in the final version. I am not going to be very detailed, but one example should illustrate this. Andreas writes:
I do not claim that the author cannot do certain things mentioned in the open disscussion phase. But his task is to convince me that he can. Since I am not convinced, my answer as regards the acceptance of the paper is no.
A4. Graham White (4.4):
Anonymous Referee 2 wrote:
I give (on p. 10 of my article or so) a logical system which is an
extension of linear logic by a modal operator We then prove, as I have said, cut elimination for this system; as with most such proofs, the proof of cut elimination proceeds by rather elementary stages but is extremely long-winded (28 subcases or so). Now we can consider our representation of ramification and actions. We first describe our actions by their primary effects, namely by linear logic formulae of the form
Now we can use the cut elimination theorem to show that the only valid proofs of a sequent of the form
i) Applications of (**) to
ii) Applications of the rules for * and
iii) Applications of either (*) or (**), corresponding in
either case to a ramification transition from
iv) The identity axiom on either
One can also prove that, in many cases, one can apply the rules
in any order one likes; one can formalise this in so-called
permutability theorems, saying that the applications of certain
rules can be permuted around each other. In the case of the
rules applied in this proof, we are free to permute rule applications
except for the obvious restriction, namely that if
However, the proof-theoretic restrictions here correspond to our
intuitive picture of what it is to perform an action in the presence
of ramification: that is, the initial situation may first undergo a
sequence of ramification transitions, then the action should accomplish
its effects, and finally there should be a sequence of ramification
transitions leading to the final situation. And in the "standard
case", as it were, of the ramification scenario, we start with
a situation So, in order to represent action in this system, we do not have to impose any artificial grouping of rules: the proof theory gives us only the proofs that correspond to realistic sequences of action and ramification.
Q5. Area Editor (29.3):
Before I draw the conclusions from these two referee's reports, first some observations on procedure, and in particular on the room for debate in the context of referee's reports. Referee reports may fall into three categories: content, criteria, and policy, where criteria commentary consists of questions to our standard questions to referees; content commentary concern the material in the article as such, and policy comments concern or touch on the meta level as to what requirements we ought to have for ETAI accepted articles. In the simplest case, the referees only return comment according to the criteria, and in this case the area editor has no reason to add anything. Comments on content are treated as part of the open review discussion, and may be responded to by the author(s) and by others in the usual way. Comments on procedure, finally, will be interpreted in the context of what has been stated by the ETAI policy committee and the area editorial committee for our area. As area editor I may relate referee's policy comments to our established policy. If it is not clear about the issue under consideration, then the question will be referred to either of the mentioned committees, for their decision. However the readership is welcome to contribute to the meta level discussion as well: the ETAI is still formative, and comments by readers will be very useful for the policy and editorial committees in their consideration. In the present case, Anonymous Referee 1 returned criteria comments, but jers answer to question 1 also goes into questions of content. I will therefore give the author and others an opportunity to respond before the decision is made. Anonymous Referee 2 refers to the lack of consideration of issues that have been brought up by Andreas Herzig in the review discussion; please note by the way that referee 2 is not identical to Andeas and does not work with him. The referee refers to the fact that the article relies on a technical report, and suggests that it ought to be self-contained instead. In fact, the ease of access to articles over the Internet has raised the question whether we ought to relax the habit that articles be self-contained, and instead encourage inclusion of material by explicit linking. This was up for debate a year ago, and the answer was inconclusive: different readers have different preferences. The invitation for reference articles in our ETAI area represents one distinct step in the direction of reducing self-containment. That case is a bit different however: reference articles are supposed to be logically included in their entirety, whereas the present author refers to an unspecified but local position in a long technical report. In the present case we agree with Referee 2 that Herzig's questions would have motivated a more extensive coverage in the article itself, in particular because of the length of the referenced technical report. The broader policy issue of self-containedness in articles will be referred to the policy committee and our area editorial committee. We will be back with the decision about the article after the author has had an opportunity to respond.
Q6. Area Editor (28.4):
The outcome of this refereeing process is inconclusive. By the conventional wisdom, journal reviewing is supposed to identify which papers are to receive the quality stamp of approval, and which are not. This works fine if the quality of an article can in fact be identified by the review reports. But what do we do if there is a considerable remaining uncertainty - not that the paper is "medium good", but at the end of refereeing we still do not know what is the case -- we do not have the basis for a reliable verdict? The present article is apparently such a case. Both the two anonymous referees were strongly critical of the article. The author has answered to their criticism, and defended his case well, but some questions do remain. A first and obvious question is - if the proposed approach (as is claimed) is superior to all previously published approaches except one which it does not surpass, should it then be accepted to the journal? Many may be tempted to say no, but then quite a number of articles in the literature of this field ought not to have been accepted, so precedent is not consistent with such an abstract principle. Murray Shanahan, in his statement today, argues that it is in fact worthwhile to publish more than one approach in such cases. This is in itself an important methodological question in our area, where some continued exchange of opinions may be useful. From the point of view of the editorial decision, the debate has answered some questions but raised some new ones. In particular, consider the author's argument in his concluding remark that his approach has also two other advantages, besides epxressiveness, namely its extensionality and its computational efficiency. The problem is that neither of these advantages is very much substantiated in the article. With respect to extensionality, it would be necessary to show the advantage in concrete comparison with the most natural alternatives. The article makes an argument about problems in alternative approaches due to intensionality, but the problems he describes can possibly be explained as due to the use of domain constraints in the examples he refers to. One would have liked to see an argument why Thielscher's approach (which is otherwise mentioned as the contender) does not have the proposed extensionality property. Similarly, the author makes a general argument that "there is a well-developed technology for implementing proof search in these systems", but again a more concrete comparison with implementations of the major alternative approach(es) would be needed in order to defend this argument. These are objections to the effect that the article's arguments are incomplete, and not necessarily wrong. Some of these questions might be resolved by continued debate, but we also need to get to a decision with respect to the journal acceptance. The discussion can continue anyway, regardless of whether the article is accepted or not. And finally we must observe that the use of linear logic in itself often arouses strong feelings in the community, so it may not be possible to arrive at a consensus. With this we return to the original question: what is the most appropriate decision when the quality of an article is undetermined, with a high degree of uncertainty in the estimate? If a journal is seen as a means of active communication between researchers, which presumably is how modern journals started, then controversial contributions ought to be very highly valued. On the other hand, if journals are assigned prestige levels based on the perceived quality of their articles, and other articles in the same journal are assigned a quality level based on the journal's prestige, then it is in the interest of other authors that only uncontested articles be accepted. We may regret the contemporary practice of evaluating articles based on the ranking of journals, both because that practice institutionalizes lack of insight, and because of its side-effects on the editorial policies of the journals, but it is a fact of life and can not be ignored. Our solution to this dilemma uses the fact that we also publish the Electronic News Journal on Reasoning About Actions and Change, besides the ETAI. The primary purpose of the News Journal is to publish, on a monthly basis, the debate contributions and debate notes that appeared in the Newsletters, so that they also obtain formal, published status and can be cited. In any case, it seems appropriate that Graham White's article ought to be accompanied by the discussion that we have had here. In that way, it becomes transparent that the article is taken seriously by the community, but that there are strong differences of opinion about the proposed approach, and it is left to each reader to consider the arguments pro and con, and to make her or his own assessment. The conclusion, therefore, is to decline the submitted article for the ETAI, but to offer the author that the article be published in the ENRAC (News Journal) for April, 1999 together with the discussion and the present concluding comment. The continued discussion will then appear in later issues of the News Journal, like for all other articles. |