******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97017 Editor: Erik Sandewall 5.11.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Today we have the answer of Rob Miller and Tony Kakas to Michael Gelfond's question the other day. We also have a late appearance of a position statement by Hector Geffner for the panel on theory evaluation. When you visit our web page, you will notice that it has become more colorful, and reorganized a bit. Also, if you wish to go directly to the webpage for actions and change, without going via the general ETAI entry page, please try for first visits: (recommend this one to your friends) http://www.ida.liu.se/ext/etai/actions/ for repeated use: http://www.ida.liu.se/ext/etai/actions/indexframe.html ********* ETAI PUBLICATIONS ********* --- DISCUSSION ABOUT RECEIVED ARTICLES --- The following debate contributions (questions, answers, or comments) have been received for articles that have been received by 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: Antonis Kakas and Rob Miller | TITLE: Reasoning about Actions, Narratives and Ramification ======================================================== -------------------------------------------------------- | FROM: The authors | TO: Michael Thielscher -------------------------------------------------------- Hello Michael, thanks for your question (several questions in fact!). Here are replies to each of your points in turn. You wrote: > I am trying to understand the relationship between your language E > and language L by Baral, Provetti and myself. This is indeed an interesting question, and one that we tried to address to some extent in our first (JLP) paper on E (see Section 3, last three paragraphs). You wrote: > My feeling is that the meaning [of E domains] really depends on > what you call ``the structure of time''. If time is linear then > your ``happens_at'' corresponds exactly to our ``occurs_at'' and > your ``f holds at T'' to our ``f at T''. Yes, that seems correct. You wrote: > If time is branching as in your second example in the paper where > T corresponds to the sequence of actions then I do not fully > understand the meaning of, say, ``A occurs at S0''. If it is > still a statement of actual occurrence then I think that > ``A1 occurs_at S0'' and ``A2 occurs at S0'' should cause > inconsistency. Yes, the meaning of statements such as "A happens-at S0" would indeed be hard to dissect if put in this type of domain description, hence we've avoided doing so in our examples. Our intuition about Situation Calculus terms such as "S0" and "Result(A,S0)" is that they refer to (hypothetical) periods of time _between_ (hypothetical) action occurrences. In other words, for all actions A, "S0" is the period of time immediately before the (hypothetical) occurrence of A, and "Result(A,S0)" is the period of time immediately afterwards. Now, in order to simulate Situation-Calculus-like hypothetical reasoning in E, we need to refer to the exact points at which actions (hypothetically) occur. Hence we include extra points in our structure of hypothetical time, such as "Start(Result(A,S0))" (written "Start([A])" in our syntax), and require that S0 < Start([A]) < [A] We then write "A happens-at Start([A])", to assert that there is indeed a hypothetical occurrence of A just before the hypothetical time-point [A] (i.e. Result(A,S0)). Once we've included the complete set of assertions such as this in the domain description, we can use the same general principles of initiation, termination and persistence (encapsulated in our Definitions 9 and 13 of a model) to reason about what holds in this branching structure of (hypothetical) time. Like the Situation Calculus and the Language A, with time structures such as this everything is intended to be in hypothetical mode, so that, as you suggest, "F holds-at [A1,A2]" should be read as "F is true in the hypothetical situation [A1,A2]". It is straightforward to extend this approach to partially deal with hypothetical reasoning about concurrent actions, by adapting Chitta Baral's and your ideas. Our structure of time would include sequences of sets of action symbols, e.g. [C1,C2], and, for example, h-propositions of the form "A happens-at Start([C1,C2])" for each A in C2. You wrote: > The goal of L (as well as of the work by Pinto and Reiter) was to > combine situation calculus ontology with actual history of the > dynamical system. Yes. A plug for Miller and Shanahan (JLC 1994) is irresistible here! That work had the same aim (as you point out in your papers), and there is perhaps more similarity between L and [Miller and Shanahan] than with [Pinto and Reiter]. [Miller and Shanahan] also has the advantage that it deals with concurrent, divisible and overlapping actions. You wrote: > Since we have both [situation calculus ontology and an actual > history] we can combine reasoning about actual occurrences of > actions and observations about values of fluents at particular > moments of time with hypothetical reasoning of situation calculus > useful for planning, counterfactual reasoning, etc. > > Can you (and do you want to) use E for the same purpose? We haven't thought about this a great deal, although it seems possible that hypothetical and "actual" reasoning (for want of a better term) could be combined in E by an appropriately rich structure of time. (A simple solution might be to index hypothetical time-points such as [A1,A2] with the actual time-point - typically a natural or real number - from which they were being hypothetically projected, and extend the ordering between all time-points appropriately.) But (at the risk of re-opening an old and seemingly unstoppable debate), at least for planning our first choice would be to use abduction with a linear time structure rather than deduction with a hypothetical branching time structure. Again, there are some remarks about this in the original (JLP) paper on the Language E. You wrote: > My other questions are about your logic program. I do not fully > understand your definition of initiation point. Do I understand > correctly that it should be changed? If so, what happens with > the correctness of logic program? The definition doesn't need to be changed. The reply to Michael Thielscher simply fills in the details that we did not include in the paper. So the proof of correctness of the logic programs is unchanged. Also note that the notions of initiation and termination points are implemented in the logic programs using Proposition 2. You wrote: > It may be useful to use some semantics of logic program instead > of using SLDNF directly. SLDNF can give some results which are > correct w.r.t. your specification even though the program is > semantically meaningless (Say, its Clark's completion is too weak > or inconsistent, or it does not have stable model, etc.) If you > prove that the program is semantically correct one will be able > to use this result directly even if your program is run on, say, > XDB or SLG (which checks for some loops) and not under Prolog. We agree, and we are in fact working on these lines, as we say in the paper towards the end of Section 5. The point is that the present approach gives us a baseline translation that would be accepted by any semantics of logic programs, at least for those cases (as you say) where the corresponding logic program has a meaning under any semantics. Of course, there is also the debate as to whether every logic program should have a meaning, but this is probably not the place to discuss this issue. You wrote: > Finally, more comments on LP4 will help. I find comments like > Resolve(A,B,C,D) is true iff some English description extremely > useful. Similarly for disjunctive_form, partition, etc. Yes, sorry. "Resolve" is just a simple implementation of a propositional resolution based prover for positive or negative literals. "Resolve(l1,c,l,t)" means that we can show that "l" holds by resolution starting from the clause corresponding to "Whenever(l1,c)" applied at the time instant "t". (The details are really not that important, and in fact "Resolve" can be replaced by any sound propositional theorem prover). It first tranforms the "implication" of the r-proposition into normal disjunctive form, using the predicate "DisjunctiveForm", then the "Partition" predicate picks out the literal "l" that we are interested in proving, and finally we try to show through the predicate "NothingHoldsIn" that the rest of the disjunction is false, by showing that for each of its literals its negation holds. So, as we say above, it is just a simple and naive implementation of resolution. Rob and Tony. ********* DEBATES ********* --- NRAC PANEL DISCUSSION ON THEORY EVALUATION --- The following is a position statement by Hector Geffner, who was also a member of the panel at NRAC. By accident it was not included in the initial set of position statements in this Newsletter debate. -------------------------------------------------------- | FROM: Hector Geffner | RE: KR/Non-mon is about Modeling -------------------------------------------------------- 1. I think the goal in KR/Non-Mon is *modeling*, not logic. A formalism may be interesting from a logical point of view, and yet useless as a modeling language. A "solution" is thus a good modeling language: declarative, general, *meaningful*, concise, that non-experts can understand and *use*, etc. (I agree with David's remark on teaching the stuff to "cynical" undergrads) The analogy to Bayesian Networks and Logic Programs that David makes is very good. We want to develop modeling languages that are like Bayesian networks, but that, on the one hand, are more *qualitative* (assumptions in place of probabilities), and on the other, more expressive (domain constraints, time, first-order extensions, etc). 2. For many years, it was believed that the problem was mathematical (which device to add to FOL to make it non-monotonic). That, however, turned out to be only part of the problem; a part that has actually been *solved*: we have a number of formal devices that yield non-mon behavior (model preference, kappa functions, fixed points, etc.); the question is how to use them to define good modeling languages 3. The remaning problem, that we can call the *semantic* problem, involves things like the frame problem, causality, etc. To a large extent, I think the most basic of these problems have also been *solved*: Basically, thanks to Michael and Vladimir, Erik, Ray, and others we know that a rule like: if A, then B where A is a formula that refers to time i or situation, and B is a literal that refers to the next time point of situation, is just a constraint on the possible transitions from the the states at i or s, and the following states. Or put in another way, **temporal rules are nothing else but a convenient way for specifying a dynamic system (or transition function)** Actually, for causal rules, the solution (due to Moises, Judea, and others) is very similar: *causal default rules are just a convenient way for specifying (qualitative) Bayesian Networks* 4. These solutions (that appear in different dresses) are limited (e.g., in neither case B can be an aribtrary formula) but are *meaningful*: not only the work, we can also understand why. We also understand now a number of things we didn't understand before. e.g., 1. a formula can have different "meanings" according to whether it represents a causal rule, an observation or a domain constraint. (this is not surprising from a Bayesian Net or Dynamic systems point of view, but is somewhat surprising from a logical point of view) 2. reasoning forward (causally or in time) is often but not always sound and/or complete; i.e., in many cases, forward chaining and sleeping dog strategies will be ok, in other cases, they won't. 5. It's not difficult to change the basic solutions to accommodate additional features (e.g., non-deterministic transition functions, unlikely initial conditions, concurrent actions, etc.) in a principled way. So, i think, quite a few problems have been solved and default languages, in many cases, are ripe for use by *non* non-mon people. 6. We have to make a better job in packaging the available theory for the outside world, and in delineating the solved problems, the unsolved problems and the non-problems, for the inner community and students. Actually i have been doing some of this myself, giving a number of tutorials in the last couple of years at a number of places (i invite you to look at the slides in http://wwww.ldc.usb.ve/~hector) -------------------------------------------------------- | FROM: Pat Hayes -------------------------------------------------------- I think this meta discussion, though at times confused (mea culpa, of course), has been useful in revealing a clear divergence between two methodologies, giving different answers to the original question about how we should evaluate work in the field. ('NRAC PANEL ON THEORY EVALUATION' ETAI 21.10) One view appeals to our human intuitions, one way or another. In this it is reminiscent of linguistics, where the basic data against which a theory is tested are human judgements of grammaticality. We might call this a 'cognitive' approach to theory testing. Talk of 'common sense' is rife in this methodology. Based on the views expressed in these messages, I would place myself, Erik Sandewall, Michael Gelfond in this category. The other, exemplified by the responses of Ray Reiter, Mickail Soutchanski and Murray Shanahan, emphasises instead the ability of the formalism to produce successful behavior in a robot; let me call this the 'behavioral' approach. This distinction lies orthogonal to the extent to which people find formality more or less congenial. Both Ray and Erik dislike 'vague claims', and Erik's suggested methodology (Newsletter 23.10) meticulously avoids all contact with psychology, as he emphasises; yet he ultimately appeals to capturing our intuition, rather than any successful application in a robot, to tell us which kinds of model-theoretic structures are more acceptable than others. It also lies orthogonal to the extent to which people see their ultimate goal as that of creating a full-blown artificial intelligence (as both Wolfgang Bibel and Mickail Soutchanski seem to, for example, along with our founder, John McCarthy), or might be satisfied with something less ambitious. This distinction in approaches - start with insects and work 'up', or start with human common sense and work 'down' - is also a methodological split within AI in general, and seems to be largely independent of whether one feels oneself to be really working towards a kind of ultimate HAL. Do people find this distinction seriously incomplete or oversimplifying? (Why?) Or on the other hand if they find it useful, which side of the division they would place themselves? In a nutshell, is the immediate goal of the field to understand and accurately model human intuitions about actions, or is it to help produce artifacts which behave in useful or plausible ways? I think this is worth getting clear not to see which 'side' wins, but to acknowledge that this difference is real, and likely to produce divergent pressures on research. ******************************************************************** 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/ ********************************************************************