******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98065 Editor: Erik Sandewall 25.8.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Today, Murray Shanahan's answer to the questions by Paolo Eduardo Santos about his submitted article, and Jixin Ma's answer to Erik Sandewall's latest message about the ontologies of time. ********* ETAI PUBLICATIONS ********* --- DISCUSSION ABOUT RECEIVED ARTICLES --- The following debate contributions (questions, answers, or comments) have been received for articles that have been submitted to the ETAI and which are presently subject of discussion. To see the full context, for example, to see the question that a given answer refers to, or to see the article itself or its summary, please use the web-page version of this Newsletter. ======================================================== | AUTHOR: Murray Shanahan | TITLE: A Logical Account of the Common Sense Informatic | Situation for a Mobile Robot | PAPER: http://www.dcs.qmw.ac.uk/~mps/robotics_long.ps.Z | REVIEW: http://www.ida.liu.se/ext/etai/received/actions/010/aip.html ======================================================== -------------------------------------------------------- | FROM: Murray Shanahan -------------------------------------------------------- Many thanks for the questions. > PART A: > > 1- In appendix A: Proof of proposition 5.9 should be 5.8; > 2- In appendix A: I could not find proof of proposition 7.9; > 3- In appendix A: I could not find proposition 7.12 in the text; > 4- In appendix B: Proof of theorem 7.12 shoud be 7.13. These are all typos. There is no Proposition 7.12, and the proof of Proposition 7.12 in Appendix A is the missing proof of Proposition 7.9. PART B is harder. Here goes. > 1- In section 1, when defining the assimilation of sensor data, it is > proposed a background theory $\Sigma_B$ comprising axioms for change, > actions, space and shape. However along the paper I did not see anyother > mention of such a theory, my question is whether is $\Sigma_B$ > represented by the last formula of section 4? The description in Section 1 is supposed to give just an impression of the way the abduction works. It's just a caricature of the real formalisation, intended to help the reader. The actual formalisation we see later is very complex, and I thought it would be hard to understand without a gentle introduction. The axioms for change, actions, space and shape in $\Sigma_B$ are actually the event calculus axioms CEC plus the spatial axioms (Sp1) to (Sp8). > 2- If so, why include in the theory $\Sigma_E$ (section 5) again the > axioms for actions and change, space and shape already included in > $\Sigma_B$, since it is considered the conjunction of $\Sigma_B$ and > $\Sigma_E$ for the abduction process? I guess this question is irrelevant in the light of the last answer. > 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 ? 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 Hanks-McDermott problem. 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? I don't think there's a contradiction here. As both these quotes emphasise, the role of logic in the implementation can be more or less direct. The implementation described in the paper under discussion doesn't use a theorem proving approach, so the role of the logic with respect to that implementation is solely as a specification. (I regard the logic, not the implementation, as the main contribution of the paper, by the way.) 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 ? This is a difficult issue. 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 ********* DEBATES ********* --- ONTOLOGIES FOR TIME --- -------------------------------------------------------- | FROM: Jixin Ma -------------------------------------------------------- In ENRAC 20.8 (98064), Erik wrote: > One of the cases you mention is where two intervals Meet in direct > succession; one is where the first interval Meets a point which in > turn Meets a second interval; in the two remaining cases one or the > other interval includes that point. - I am afraid there's a > misunderstanding here, since I was referring to the domain used *in > each of the interpretations*. For each particular interpretation, it > must certainly be determined whether or not there is a point between > the two intervals. Therefore, different scenarios will sometimes > differ with respect to their domains for the type of "point" (and > maybe also for the type "interval"?) if one insists on dealing with > dividing instant situations by using domains where for certain > clocktimes there is no corresponding (time)point. Sometimes, > different models for the same scenario will also differ in that > respect. > > Now to the examples. I will take for granted that we talk about > timepoints and intervals that are related along the lines of Pat's > core theory, only with the adjustment that intervals are not > entirely determined by their endpoints: there can be up to four > intervals for each pair of endpoints, because you allow these > intervals to be either open or closed at each end. (The interval > will then be defined as closed if there exists a point beginning > resp. ending it, otherwise it's open). Yeah, there's a misunderstanding about the time domain, and actually it was my fault since I didn't make it clear in my former message. In fact, the time domain (actually the time theory as a whole) which I was referring is that which takes both intervals and points as primitive on the same footing (neither intervals are constructed out of points, nor points are defined as the "meeting places" or other limiting structures of intervals), rather than the time lines of Pat's core theory. An interval can meet other intervals and/or points, but a point can only meet intervals (including moments) (see Ma and Knight, Comuter Journnal 94). Therefore, such a theory allows all the following cases: (1) interval I1 Meets interval J1 (without any information as whether there is a point, say P1, which Finishes I1, or Starts J1); (2) interval I2 Meets interval J2; and point P2 Meets J2 (or equivalently, point P2 Finishes I2); (3) interval I3 Meets interval J3; and interval I3 Meets point P3 (or equivalently, P3 Starts J3); (4) interval I4 Meets point P4, and point P4 Meets interval J4. In it important to note that, in case (1), (2) and (3), there is not any time element, neither interval/moment nor point, that stands between the two successive intervals, while in case (4) there IS a time point which connects two intervals. As I argued in my former message, all the above cases can be accommodated by the single time theory (model) -- all these scenarios may (but not necessarily) appear somewhere over the time lines (even if the time itself is further characterised as linear) without the need of any futher specifications. They are not conflict with each other. > You refer to an example by Galton where a Green light and a Red > light both switch On at the same time. This is somewhat > counterintuitive - I would have thought that one goes Off when the > other one goes On - but that doesn't matter. Yeah, this doesn't really matter. Actually, the facts that one light, e.g., Green light, is On before P and then switched Off at P, and the other, the Red light, is Off before P and then switch On at P can be just expressed as: Holds(GreenOn, I) and Holds(RedOff, P), leaving the real question still as how to express the state of the two lights at the switching point P. If both lights are asserted as "On" at P, the corresponding axioms will be: Holds(GreenOn, I) Holds(GreenOn, P) Holds(GreenOff, J) Holds(RedOff, I) Holds(RedOn, P) Holds(RedOn, J) Meets(I, P) Meets(P, J) Similar treatments apply to the case where both the lights are asserted as "Off" at P. As for the case where no information about the Switching point is given at all, i.e., none of the two lights is asserted as On or Off at the switching point P, the axioms wil be as simple as: Holds(GreenOn, I) Holds(GreenOff, J) Holds(RedOff, I) Holds(RedOn, J) Meets(I, J) Therefore, the only remaining case is that at the switching point P, one light is known as On (or similarly, Off), while there is no assersion as to the state of the other light at P. This is actually similar to Galton's example, and can be treated by the same approach (see below). > You propose the following scenario description for the case where we > have decided to consider the Green light to be On at the dividing > instant, and we have decided to keep that open for the Red light: > > Holds(GreenOff, I2) > Holds(GreenOn, P) > Holds(GreenOn, J2) > Holds(RedOff, I1) > Holds(RedOn, J1) > Meets(I2,P) > Meets(P,J2) > Meets(I1,J1) > I1 + J1 = I2 + P + J2 > > Actually, these axioms do not indicate that the two lights switch at > the same time. Let's assume that such a statement has been added, > otherwise the point with the example is lost. Now, in every model > for these axioms it must be determined whether P is included in I1 > or in J1. (Or, if you disagree, what would a model be like where P > is neither included in I1 nor in J1?) Suppose P is included in I1. > Then, as long as timepoints and intervals are related along the > lines of Pat's core theory, you can't avoid the conclusion that the > interval I1 ends with P, and hence that the Red light is Off at the > dividing point. Similarly, if P is included in I2, it must be that > I2 begins with P, and that the Red light is On at the dividing > point. Therefore, *in each of the models* there is the kind of > choice that you called "arbitrary" with respect to whether the Red > light is to be considered On or Off. After I had sent my former message containing the above solutions, I found I should include an additional "axiom", that is: Duration(I1) = Duration(I2) which implies that Duration(J1) = Duration(J2). Remember that Duration(P + J2) = Duration(J2) therefore the following axioms: Holds(GreenOff, I2) Holds(GreenOn, P) Holds(GreenOn, J2) Holds(RedOff, I1) Holds(RedOn, J1) Meets(I2,P) Meets(P,J2) Meets(I1,J1) I1 + J1 = I2 + P + J2 Duration(I1) = Duration(I2) together express the specified example, showing that: (a) "GreenOff" Meets "GreenOn", i.e., Meets(I2, P+J2), "RedOff" Meets "Red"On, i.e., Meets(I1, J1), (b) Since, together with the rest axioms, axiom I1 + J1 = I2 + P + J2 and axiom Duration(I1) = Duration(I2) indicate that the Green light and the Red light are both Off before the switching point P, and are both On after P. Therefore, both the Green light and the Red light are switched at the same time point P (c) The switching point P satisfies the "GreenOn" property which is specified as P Starts the GreenOn interval (i.e., P+J2), where there is nothing specified as whether the switching point P Finishes the RedOff interval (i.e., I1) or Starts the RedOn interval (i.e., J1). > My two examples come out in similar ways. For example A, you write: > > > Yeah, for the modelling of the throwing of a ball, it requires > > that there exists a point referring to the apex. However, the fact > > that Jim turned the switch does not necessarily imply that there > > must not be any such point, especially if one insists that "at a > > moment (point?) when it (the ball) reaches the top of its > > trajectory, he (Jim) turns the switch". > > But if (in a particular model) such a point exists for the clocktime > where Jim turned the switch, then it must be determined (in that > same model) whether the switch is on or off at that point, and you > have your Dividing Instant Problem back again. > > For example B, you write: > > > I don't agree with the claim that "a point both exists and does > > not exist at the clocktime whent he winner finishes his last cone > > and the bell rings". Again, I think this claim was reached by > > means of confusing two cases, that is, the case that an interval > > "Meets" a point, and the case that an interval was "Finished-by" a > > point. > > Not really. If you wish to avoid a dividing instant situation by > using a punctuated time domain (for each of the models, so that > there is no dividing instant problem in any of the models), then you > *must exclude* models where that timepoint is present. It can't be > present explicitly, and it can't be present implicitly by being the > ending or beginning of an interval, because in all of those cases > you end up assigning the truthvalue that you considered arbitrary. > The only way of complying is to have two successive open intervals > without any point between them. (That is, an interval not ending in > a point, and a subsequent Meeting interval not beginning in a > point). However, this in turn contradicts the assumption that the > Bell rings, since it was assumed the Bell rings at (time)points. > Therefore, the only possible models are those where the Bell rings > without the cones having been finished, and you obtain the > conclusion I indicated. > > The bottom line is, therefore, that it is futile to try to impose > noncommitment for dividing instants on the level of the models and > by using nonstandard time domains such as "punctuated time". In > those cases where we wish to express that we don't know or don't > care whether a certain proposition is true or false at a point of > change, it's sufficient to use the multiple models approach while > admitting "standard" time (integers or reals, by preference). Then > we don't need any theory of time at all besides high-school or (at > most) college math. > > All of this presumes of course standard two-valued logic, where > models can only assign the truth-value true or false. You may obtain > another perspective by going to e.g. three-valued logic, where > *everything* can be undetermined besides true or false. But, as H.C. > Andersen once said, that is another story. I feel my explanations/arguments about the time theroy (model) in the first part of this message and the above revised demostration of the two-lights exmple also apply to Erik's questions/arguments and his examples A and B, since as Erik observed, they come out in similar ways. Jixin ******************************************************************** This Newsletter is issued whenever there is new news, and is sent by automatic E-mail and without charge to a list of subscribers. To obtain or change a subscription, please send mail to the editor, erisa@ida.liu.se. Contributions are welcomed to the same address. Instructions for contributors and other additional information is found at: http://www.ida.liu.se/ext/etai/actions/njl/ ********************************************************************