|Moderated by Erik Sandewall.|
A Logical Account of the Common Sense Informatic Situation for a Mobile Robot
mentioned above has been submitted to the Electronic
Transactions on Artificial Intelligence, and the present page
contains the review discussion. Click for
explanations and for the webpage of theauthor, Murray Shanahan.
Overview of interactions
Q1. Paulo Eduoardo Santos (1.8):
1- In section 1, when defining the assimilation of sensor data, it is
proposed a background theory
2- If so, why include in the theory
3- All along the paper, Circumscription is done in parts of theories (rather than in the whole theory). I understand it is done 'by construction' since the chosen version of Event Calculus considered, is the one defined using forced separation (as presented in Shanahan's book "Solving the Frame Problem" [b-Shanahan-97]. My question is why do we have to circumscribe parts of the theories in the way presented, and not in any other way? Is there any formal justification for using forced separation ?
4- At the beginning of section 9 we read:
In another paper by Shanahan "What Sort of Computation Mediates Best between Perception and Action" [Shanahan-96] we read:
I have two questions about these statements: first, by assuming a logic programming approach, aren't we contradicting the last statement above? and, if it is not to have a theorem prover implementing the logic-based description of the system, what is exactly the role of logic in this framework?
My last question is about computational complexity:
In the framework presented in the paper under discussion two important points are 'explanation by adbuction' and 'circumscribing theories'. As presented in [c-stacs-93-Eiter] the complexity of logic-based abduction is NP-hard (for the problem of finding an abductive explanation with the additional constraint that it has to contain a predefined letter p); the results about complexity of Circumscription are not much more impressive (as can be seen in [j-jlp-17-127].
My question is, taking into account these complexity results, can we still apply this framework in robotics ?
Paulo Eduardo Santos
[Shanahan-96] Murray Shanahan, What Sort of Computation Mediates Between Perception and Action?, Working notes of the AAAI Fall Symposium on Embodied Cognition, 1996.
Many thanks for the questions.
The technique is similar to what Erik Sandewall calls filtered preferential entailment. I think I've seen Erik provide a carefully argued justification of this technique in one of his papers. Perhaps he will remind us where to find it.
On the whole, as I argue in the other paper you quote from, I think it's preferable to take a more theorem proving approach, in which case the logic is more intimately related to the implementation. But this approach is hard when we're dealing with difficult mathematical objects like the plane, as in this paper. In my current work, however, I have a simpler description of the robot's environment, and a logic programming implementation of sensor data assimilation is more feasible.
My feeling is that complexity results should be used only as a guideline, and a disappointing complexity result rarely justifies the wholesale rejection of an approach. This is because the complexity results are worst-case, while in actual usage, a technique is often confined to a narrow, tractable sub-class of problems that no-one has pinned down yet.
In fact the use of circumscription to overcome the frame problem here is a case in point. The form of the theories we're interested in guarantees that the circumscriptions always reduce to predicate completions, which can be handled efficiently by Prolog.
Moreover, in the context of robotics, I think there's another argument that worst-case complexity results are misleading. No robot should be allowed unlimited computation time for any reasoning task before that task is suspended to sense the world and respond reactively to it. And ultimately, the world always moves on and renders old, unfinished reasoning tasks irrelevant. (I used to spend a lot of time thinking about the mind-body problem in philosophy, no doubt a "computationally intractable problem". Now I have children, and don't have time for such luxuries.) A robot's designer needs to organise things so that most reasoning tasks the robot sets out to perform can be completed in a short time. And if, once in a while, the robot is unfortunate enough to hit on one that would take the lifetime of the universe to solve, who cares? It'll soon give up on it when it has to dodge a falling rock or grab a passing robot of the opposite sex :-)
I hope this answers your questions, and thanks for taking the time to read my paper.
It was nice (but a little exhaustive :-) ) reading your paper. I hope the following feedback will be useful.
In this paper you have initially (Section 2-5) expressed using logic: actions and their effects, occurrences of robots actions, initial value of fluents, event calculus axioms, domain constraints, formulation of continuous change using the release predicate, representation of space and shape, and axioms about triggered events.
Given information on occupies (at the initial situation) the formulation can predict occurrence of triggered events. You rightly argue that an abductive method can make conclusions about occupies when told about (or when it senses) triggered events. This is the basic essence of the first part of the paper I like the detailed logical formulation.
Some of the questions and suggestions that I have about this part are as follows:
(i) I think that in general a robot does not really sense events, rather it notices changes in certain fluent values (in say resistors linked to the sensors) from which it abduces the occurrences of triggered events. Nevertheless, it is ok with me to skip this part and directly talk about robots observing triggered events. But a clarification would help.
(ii) Since you mention several times (abstract, Section 2, etc.) that you use a novel solution to the frame problem using `Releases' it will be nice if you say about it a little more than what is said in Section 2 (just after EC 5). (You do use it in axioms in later sections, but you don't discuss them.)
Although from the illustrations I can appreciate the use of `Releases' in formulating continuous change, its utility in formulating constraints is not clear to me. For example, why not eliminate B4 and instead of `Releases' have `Terminates' in the head of rule E2.
To me the advantage of having constraints such as B4 is that by having it we avoid explicit compilation of it to effect axioms. I.e. we can use constraints for automatically deducing effects indirectly. But if we have both B4 and E2 then we are not really avoiding the compilation, as E2 is like an effect axiom.
(iii) I am not sure if `Bearing' is a standard geometrical notion. Perhaps an intuitive meaning of it will help. Or may you can use the more familiar notion of `slope'.
(iv) You say (just after Sp3): ``the term
(v) I think in axiom (B3) you are assuming velocity to be one. If you do please mention it.
(vi) The sentence after (B6). In it you explain
(vii) When defining
(viii) I am not clear about the intuition behind the notion of partial completion in Section 5; especially in the text after (5.7).
For example in proposition 5.8, I would encode the intuition ``bump switches are not tripped at any other time'' by
Also, why not use the standard Clark's completion and explain the
Clark's completion of
(ix) In section 6 you logically express a region as a list of straight lines. (You say it just before Bo3.) Is there any particular reason you use lists instead of sets. If not, since you already use set notation in the rest of your formulation, by using sets here also, you might avoid additional axioms such as Bo3 and Bo4
(x) Also (Bo3) is a fixpoint expression and you probably need (as needed when defining transitive closure) to minimize `Members' to get the right models.
(Recall that the logic program
You are not minimizing `Members' in Proposition 6.2. Or perhaps I am missing something.
(xi) In Section 7 you first take into account noise and formulate it and later define preferred explanations.
From Section 2-7 your formulation is in logic. It seems to me in Section 8 you give an independent formulation and relate it to the logical formulation with necessary and partially sufficient conditions. Your algorithms in section 9 are justified based on the formulation and results in Section 8.
(xi) Although I can appreciate the usefulness of the logical formulation in Section 2-7, some may pose the following question: Why not just formulate as in Section 8 (with some extensions perhaps) and then have the correctness of the algorithm in Section 9 proven with respect to the formulation in Section 8. Why go through the formulation in Section 2-7? I think it will be a good idea to address this or say a few lines about this to preempt such questions/attacks on logical formulation.
These are some of the questions and/or suggestions I have so far. I am reading the proofs now. If I have additional questions I will take the opportunity provided by this wonderful forum.
Best regards Chitta
Many thanks for your comments and questions.
I think your formulation is equivalent to mine. I just elected to separate the if and the only-if halves of the completion.
(x) Also (Bo3) is a fixpoint expression and you probably need (as needed when defining transitive closure) to minimize `Members' to get the right models.
There is an axiom missing, which says that nothing is a member of Nil. I'll put this in the final draft.
But given that, I don't think there's a problem here. It's easy to
prove, for example, that
I hope that answers all your questions. Many thanks for taking so much trouble over my paper.
In the newsletter of 11.9, in answer to one of Chitta Baral's questions of 19.8, I wrote: "There is an axiom missing, which says that nothing is a member of Nil. I'll put this in the final draft". In fact, this axiom is unnecessary, as it follows from Axioms (Bo3) and (Bo4) of my formalisation.
Q3. Paulo Eduoardo Santos (11.9):
Thank you very much for answering my first questions. I really think it is a very interesting paper.
The second bunch of questions follows:
1. In the last answer set we read:
Then, why do not use negation-as-failure instead, since, for the particular case of circumscription we are interested in, the former is equivalent to the later (as proved in [j-aij-38-75]).
In which sense circumscription is more powerful than negation-as-failure in this framework?
2. I could not understand the last formula of page 14. There a
biimplication is used defining the region
In the beginning of page 15 it is considered, as a solution to the
abduction process, "conjunctions
My question is: what do you do if there is no
Many thanks for this opportunity,
Paulo Eduardo Santos
However, I'm a little sceptical that we do ever want to mix these different kinds of information in this way. In this example, I suspect that another layer of reasoning is called for, which explains observations (such as the fact that it is dark), and this may update the Initiates/Terminates part of the theory, or may update the initial situation description.
On the other hand we can, and often do, write other sorts of formulae that mix
Q4. Paulo Eduoardo Santos (17.9):
Dear Murray Shanahan,
As you suggested, I am sending those questions to ETAI:
1. On page 5 we read the definition of the following circumscription policy:
My question is: Why didn't you circumscribe
2. The second question concerns the same subject.
On page 9 we have the predicate
But anyway, I think you may have uncovered a bug in my formalisation. As
you'll see in other papers and in Chapter 15 of my book, usually when I
present the event calculus I use two
Q5. Anonymous referee 1 (27.3):
Much of the work in the paper has already been published. That's not a criticism, since it is signaled by the author himself, but the paper seems to initiate a third kind of article in the ETAI, between reference papers and crisp new results. I took a real interest reading it, because it collects a bunch of results into a single framework. Showing how those fragments, considered as specifying pieces of a common task, can consistently work together and can help mastering the architecture of a reasoning robot is, according to me, a real contribution worthy of publication in the ETAI (parenthetically, this contribution could be more neatly stated in the abstract).
The discussion with Paolo Eduardo Santos and Chitta Baral has been extensive and several points have been improved. Here under are some more suggestions, which are not conditions to the publication, but that Murray Shanahan can follow if he feels they are improvements.
- In part 4, I suggest: "a region is an open (path)-connected subset of
- while the reader can understand what is meant by a direction, the
definitions could be more precise. In (SP3), since
I suggest to point that a bearing is in fact an equivalence class which may be represented by any of its members, without further developments. (SP3) could then be simplified to :
- The question raised by Chita Baral about touching triangles in (B6) can
be solved if
- (Bo5) could be simplified:
Also in paragraph 3, line 3 of 6., change
- p18, just above (B8): I doubt that the condition for the robot leaping over an obstacle is this one, which does not depend on the size of the robot (if I do not misunderstand the sentence). Could it be clarified which location/circle of uncertainty is relevant ?
- p22 def 7.11 I suggest clarifying that MIN is a parameter of the definition.
Q6. Anonymous referee 2 (27.3):
The paper describes interesting results, which have been originally presented at ECAI-96, that researchers working in the area of reasoning on actions and change ought to know about. It is well-written and clear. At some points, where rather natural solutions to specific problems are proposed, the presentation is too turgid.
The following are my answers to the standard referee questions:
1./2. There is a short (10 lines) abstract, but there is not a summary where the main results are specified. I would ask the author to provide it.
4. Even though the paper is basically well organized, it can be shorthened. Some general discussions as well as some straightforward proofs, e.g., the proof of Proposition 2.8, can be omitted and/or summarized.
5. The major limitation of the paper is that it is not up-to-date (as reported in its cover page, its last revision dates back to April 1996).
I wish to make the following additional comments regarding policy. One of the major advantages of an electronic journal as ETAI is that it guarantees a rapid publication of new results. In particular, it reduces the delay between the presentation of the results of a research work at a conference and their publication in a journal paper.
I believe that one cannot publish old results without putting them in the current state-of-the-art. In the specific case, I do not think that the proposed contribution has been invalidated by later developments in the field, but I would ask the author to discuss such developments in the paper. My suggestion is to provide an additional section relating the work to what has happened elsewhere since then as well as to its subsequent developments (e.g., the simpler description of the robot's environment, mentioned in an answer to Paulo Eduoardo Santos).
More precisely, I would like to ask the author whether nothing has been published on the subject since then that deserves to be taken into account (if this is his opinion, it must be explicitly formulated). I just mention the subsequents developments of the logical approach proposed by Lesperance et al. (cf. the special issue of the Journal of Logic Programming on Reasoning about Action and Change, as well as the Proceedings of KR'98) and Galton's work on representation and reasoning about spatial knowledge. Furthermore, the paper reports the results of preliminary experimentation with the robot. Has experimentation been systematically executed? What are its outcomes?
Another relevant point: complexity issues are completely neglected in the paper and dealt with rather quickly (and superficially) in one of the interactions with Paulo Eduoardo Santos. I ask the author to briefly discuss them in the paper. In particular, he should at least summarize the known existing results about the (worst-case) complexity of logic-based abduction and circumscription, and explain his opinion about the impact of these complexity results on research in logic-based/cognitive robotics.
Minor point: I would remove from the abstract the sentence about the novel solution to the frame problem (inspired by the work of Kartha and Lifschitz). It seems to me a rather specific technical point (as the author explicitly recognizes in his answer to Chitta Baral), mainly concerned with the adopted formalims rather than with the considered problem. Moreover, if the form of the considered theories actually guarantees that the circumscriptions (almost) always reduce to predicate completions, then I believe that this fact should be explicitly stated.
References: please check/integrate [Charniak & McDermott, 1985], [Miller, 1996], and [Shanahan, 1996].
C6-1. Area Editor (30.3):
The second part of the comments by Anonymous Referee 2 raises an interesting policy question for the ETAI, namely to what extent shall commentary material be placed in the article itself, and to what extent is it better placed in the article's discussion session. With 'commentary' material I include comparison to related work that occurred concurrently with or after then work being reported in the article; discussions of alternative ways of realizing subsystems of a largeer system being presented in the article; discussion of intrinsic theoretical limitations of the proposed approach; and so forth.
The A I literature has traditionally required fairly extensive consideration of commentary material. This is clear in comparison with other fields, such as physics, where articles usually seem to be much more focussed on a single mission: define the problem, discuss the state of the art relating to this problem, present the new solution, done.
The emergence through ETAI of a systematically maintained dialogue connected to each article offers an alternative approach: instead of the author trying to answer all questions about the topic that some readers might ask, he or she could focus on the main problem that's being addressed and on its solution, and leave the rest to the question period. A change in this direction would have its pros and cons. The advantages are in the increased flexiblity and the possibility of adding material over time, even after the date the article appeared in the journal. The disadvantage might lie in a possible loss of systematicity, and in the resistance among readers against changing old habits.
As the second half of the statement by Anonymous Referee 2 is a suggestion for including several types of commentary into the article, it would be possible syntactically to rephrase most of these suggestions into questions that the author could answer in the discussion page. Whether it is better to answer the questions this way or by amendments in the article itself may be a matter of debate, and it would be useful to have a decision about a recommended policy in this respect.
Since the same question is likely to come up at other times, I will ask the ETAI policy committee and our area editorial committee to study it and to make a recommendation. Comments by subscribers are invited.
For the time being and for the present article, I will ask the author, Murray Shanahan, to consider the second half of the referee statement as a set of questions that can be answered either by amendments to the article, or through the review dialogue. Based on the referee reports, the article is accepted for the ETAI while giving the author an option of minor modifications in response to the suggestions by both the anonymous referees.
The referees make a recommendation whether the article is to be
accepted or declined, as usual. The article and the discussion
remain on-line regardless of whether the article was accepted or
not. Additional questions and discussion after the acceptance decision
The Review Protocol Page is used as a working structure for the entire
reviewing process. During the first (review) phase it accumulates the
successive debate contributions. If the referees make specific
comments about the article in the refereeing phase, then those comments
are posted on the RPP as well, but without indicating the identity
of the referee. (In many cases the referees may return simply an
" accept" or " decline" recommendation, namely if sufficient feedback
has been obtained already in the review phase).
The referees make a recommendation whether the article is to be accepted or declined, as usual. The article and the discussion remain on-line regardless of whether the article was accepted or not. Additional questions and discussion after the acceptance decision are welcomed.
The Review Protocol Page is used as a working structure for the entire reviewing process. During the first (review) phase it accumulates the successive debate contributions. If the referees make specific comments about the article in the refereeing phase, then those comments are posted on the RPP as well, but without indicating the identity of the referee. (In many cases the referees may return simply an " accept" or " decline" recommendation, namely if sufficient feedback has been obtained already in the review phase).