Murray ShanahanA Logical Account of the Common Sense Informatic Situation for a Mobile Robot. |
[full text] [abstract] |
[msg to moderator] [debate procedure] [copyright] |
N:o | Question | Answer(s) | Continued discussion |
---|---|---|---|
1 |
1.8 Paulo Eduoardo Santos |
25.8 Murray Shanahan |
|
2 |
19.8 Chitta Baral |
11.9 Murray Shanahan |
31.1 Murray Shanahan |
3 |
11.9 Paulo Eduoardo Santos |
9.10 Murray Shanahan |
|
4 |
17.9 Paulo Eduoardo Santos |
9.10 Murray Shanahan |
|
5 |
27.3 Anonymous referee 1 |
||
6 |
27.3 Anonymous referee 2 |
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:
An alternative approach is to tailor make algorithms for specific tasks, such as sensor data assimilation, whose correctness with respect to the logical account can be demonstrated. This is the methodology I will adopt here, and the logic programming approach is left for further research. |
In another paper by Shanahan "What Sort of Computation Mediates Best between Perception and Action" [Shanahan-96] we read:
It is important to note that the logicist prescription does not demand a one to one correspondence between the data structures in the machine and the sentences of the chosen formal language. (...). In other words, the machine does not have to implement a theorem prover directly. Between the abstract description of a logic-based AI program and the actual implementation can come many steps of transformation, compilation, and optimisation. |
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 ?
Yours,
Paulo Eduardo Santos
Unpublished reference
[Shanahan-96] Murray Shanahan, What Sort of Computation Mediates Between Perception and Action?, Working notes of the AAAI Fall Symposium on Embodied Cognition, 1996.
References:
c-stacs-93-au/Eiter | T. Eiter and G. Gottlob. The Complexity of Logic Based Abduction. Proc. Symposium of Theoretical Aspects of Computer Science, 1993, pp. . |
j-jlp-17-127 | Marco Cadoli and Marco Schaerf. A Survey of Complexity Results for Non-monotonic Logics. Journal of Logic Programming, vol. 17 (1993), pp. 127-160. |
A1. Murray Shanahan (25.8):
Many thanks for the questions.
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" cite{Shan: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 ?
|
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.
4- At the beginning of section 9 we read: |
An alternative approach is to tailor made algorithms for specific tasks, such as sensor data assimilation, whose correctness with respect to the logical account can be demonstrated. This is the methodology I will adopt here, and the logic programming approach is left for further research. |
In another paper by Shanahan ("What Sort of Computation Mediates Best between Perception and Action" cite{Shan:96} we read: |
It is important to note that the logiscist prescription does not demand a one to one correspondence between the data structures in the machine and the sentences of the chosen formal language. (...). In other words, the machine does not have to implement a theorem prover directly. Between the abstract description of a logic-based AI program and the actual implementation can come many steps of transformation, compilation, and optimisation. |
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?
|
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.
In the framework presented in the paper under discussion two important
points are 'explanation by adbuction' and 'circumscribing theories'. As
presented in cite{EG:92} 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 cite{CS:93}).
My question is, taking into account these complexity results, can we
still apply this framework in robotics ?
|
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.
Murray Shanahan
Q2. Chitta Baral (19.8):
Dear Murray:
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
Happens(Switch1, t) ·-> t = T {bump} |
Happens(Switch2, t) ·-> t = T {bump} |
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
anc(X, Y) <- par(X, Y) | ||
anc(X, Y) <- par(X, Z), anc(Z, Y) |
anc(X, Y) <-> par(X, Y) v (par(X, Z) ^ anc(Z, Y)) |
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
A2. Murray Shanahan (11.9):
Chitta,
Many thanks for your comments and questions.
(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 Line(p1, p2) denotes the
straight line whose ...''. Perhaps it is more appropriate to say
``straight line segment'' instead of ``straight line''.
(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 Blocked(w1,w2,r) by
`if object w1 cannot move any distance at all in direction r without
overlapping with another object'. Perhaps you should say: ``if object w1
cannot move any distance at all because of w2 in direction r without
overlapping with another object'.
|
(vii) When defining HoldsAt(Touching(w1,w2,p),t) are you making some
assumptions about the shape of w1 and w2. Imagine two triangles which
touch at a point, you can align them such that they touch but yet do not
satisfy the conditions you have in B6.
|
(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
|
I think your formulation is equivalent to mine. I just elected to separate the if and the only-if halves of the completion.
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. |
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
(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.
|
I hope that answers all your questions. Many thanks for taking so much trouble over my paper.
Murray
C2-1. Murray Shanahan (31.1):
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.
Murray
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:
By splitting the circumscription into parts, we get a more managable
theory, one whose consequences are easier to work out. In fact, the role
of circumscription here is mainly to complete certain predicates,
specifically Initiates, Terminates and Happens. If we circumscribe
everything together, we have to do a lot more work to avoid difficulties
like the
|
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
3-
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
References:
j-aij-38-75 | Michael Gelfond, Halina Przymusinska, and Teodor Przymusinski. On the Relationship between Circumscription and Negation as Failure. Artificial Intelligence Journal, vol. 38 (1989), pp. 75-94. |
A3. Murray Shanahan (9.10):
I agree that Separation avoids the Hanks-McDermott problem , but doing
so you get a restriction in the theory, since you are not able to write
formulae using Initiates (or Terminates) and Happens together (on the
contrary it won't be clear where to place such formulae in the
circumscriptions). Thus, we are not able to
express (and infer) some facts.
|
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
Happens(a, t) |
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
In which sense circumscription is more powerful than negation-as-failure
in this framework?
|
I could not understand the last formula of page 14. There a
biimplication is used defining the region
|
My question is: what do you do if there is no M2 that explains Psi ?
|
Murray Shanahan
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:
Given a conjunction of
|
My question is: Why didn't you circumscribe
2. The second question concerns the same subject.
On page 9 we have the predicate
AbSpace(w) <- Initially(Occupies(w, g)) |
The predicate |
CIRC [O ^ M;AbSpace;Initially] ^ ... |
Cheers,
Paulo
A4. Murray Shanahan (9.10):
Why didn't you circumscribe
|
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
Murray Shanahan
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 :
Bearing(P1, P)-Bearing(P2, P) = 180 [mod 360] |
- 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.
3. No.
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].
13-Jun-98 20:28