******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97016 Editor: Erik Sandewall 3.11.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* The discussion about submitted articles and in the two panels continues at a regular pace in this Newsletter issue... and for those who still wonder whether it's worthwhile to submit articles or research notes to the ETAI, there is now a simple answer: just take a look at how it works. Wouldn't you also want your article to be actually discussed by peers, right after you have completed writing it, instead of being delayed in a conventional review process? And this, particularly, if it already has the status of "published" so that the your date of first publication is uncontestable? Besides reading today's discussion, please also take a look at the News Journal issue for October in postscript format. As you may recall, the accumulated contents of the newsletters during a month are to be assembled into the monthly News Journal, in a format that you can conveniently print out and read in paper mode, and which has the look-and-feel of a journal. In fact, we will try to arrange that it is printed in a regular fashion as well, but of course it will always remain on-line free of charge. The News Journal issue for October is *almost* perfect; a few Latex bugs remain to be ironed out, but maybe you want to take a look already. Access is via the "past issues" structure in our web page. PS. But please don't mix up the Electronic News Journal with the ETAI itself. The ETAI has not had any issue yet, and it will only contain refereed articles. You have to pass both review discussion and refereeing in order to get into the ETAI. ********* 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: Michael Thielscher | TITLE: A Theory of Dynamic Diagnosis ======================================================== -------------------------------------------------------- | FROM: Rob Miller -------------------------------------------------------- Michael, a question regarding the relative likelihoods of different components failing: It seems to me that, in the absence of specific domain knowledge to the contrary, it's right to prefer explanations of system failure which are minimal in terms of the number of failures of individual components, other things being equal (this is one aspect of how your main example works, if I've understood correctly). But you also mention that good diagnosis is able to "take into account a priori knowledge of differences in the likelihood of components to break" (an example might be the knowledge that relays are more likely to fail than resistors). Could you say a little more about this in relation to your approach? Would you perhaps use more than one "ab" predicate, with some sort of prioritised minimisation between the predicates? -------------------------------------------------------- | FROM: Michael Thielscher -------------------------------------------------------- Rob, My theory does indeed respect domain knowledge of the kind you mention. This knowledge is formally represented by a partial ordering among the instances of the (unique) "ab" predicate--which is equivalent to your suggestion of allowing a priority hierarchy of different "ab" predicates. The notion of preferred models (Definition 10) reflects a given partial ordering in that more unlikely instances of "ab" are preferably minimized. As a consequence, the axiomatization of the theory by means of the Fluent Calculus (Section 5) employs Brewka's prioritized extension to classical Default Logic. Best regards, Michael ======================================================== | AUTHOR: Antonis Kakas and Rob Miller | TITLE: Reasoning about Actions, Narratives and Ramification ======================================================== -------------------------------------------------------- | FROM: Michael Gelfond -------------------------------------------------------- Dear Tony and Rob. I am trying to understand the relationship between your language E and language L by Baral, Provetti and myself. To do that I need some good intuitive understanding of the meaning of statements of E and I am having some difficulties here. My feeling is that the meaning 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''. In both cases we have actual occurrences at moments of time (or actual situations as we call them). 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. (In the case of linear time we just have concurrent actions). The meaning of ``holds_at'' also seems to change. Instead of actual observations it becomes hypothetical. If I am right then I think this property of the language should be somewhat stressed. If not then some explanation will help. 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. Since we have both 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? 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? 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. 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. ********* DEBATES ********* --- NRAC PANEL DISCUSSION ON THEORY EVALUATION --- -------------------------------------------------------- | FROM: Michael Gelfond -------------------------------------------------------- I found parts of it difficult to follow since I am not sure what the participants mean by the word ``theory''. Are you referring to theory as organized body of knowledge about some subject matter, to theory in mathematical sense (like theory of probability), or to logical theory - collection of formulae in some language with precisely defined entailment relation? (This is of course a very incomplete list of possibilities). It is important to be somewhat more precise here because in the AI community ``theory'' is sometimes identified with an ``idea'' and I am not sure that it is very useful to publicly judge ideas until they develop into theories. Sometimes this process takes much more than 25 years especially if the idea is prevented from its natural development by premature judgments or if development of a theory requires more than one basic idea. --- NRAC PANEL DISCUSSION ON ONTOLOGIES FOR ACTIONS AND CHANGE --- -------------------------------------------------------- | FROM: Michael Gelfond -------------------------------------------------------- I agree with Ray that it may be a good idea to separate ``ontology'' from ``epistemology''. For me to specify ``ontology'' means to give a collection of individual objects, functions and relations which comprise our domain. The type of logical connectives used to construct sentences in this language is part of ``logical system'' and does not belong to the ontology. Closed World Assumptions of different sorts,etc belong to ``epistemology''. We seem to differ slightly on the meaning of the frame problem. To me the frame problem is a special case of a more general problem of finding logical system suitable for representing defaults and their exceptions in a way which will insure a high degree of elaboration tolerance. (Frame axiom is a particularly difficult default since it is related to causality, representation of time, etc) This is of course only one of several possible views but I think an important one. I believe that the ontology of situation calculus and action languages are basically the same. Situation IS a sequence of actions, etc. Our causal models (or automata) are graphs representing trees of situations. (One superficial difference is that our actions are undefined in situation where the corresponding preconditions are not satisfied, while in Ray's case they seem to ``return'' the same situation). The more important difference is that action languages stress the distinction between description languages and query languages and define entailment relation directly without appealing to first-order logic. To turn these languages into calculi one need to decide what logical system to use to formalize reasoning about causal models defined by the corresponding action theory. My favorite choice here is declarative logic programming with answer set semantics which can be viewed as a variant of default logic. We have now several logic programming versions of situation calculus proven to be sound and complete w.r.t. entailment in action description languages. The disadvantage of this approach is that we need to develop more mathematics for dealing with declarative logic programs (default theories) which is a slow process. Even though there has been an important progress in this in the last few years, classical logic is still a better choice in this respect. I believe however that in a long run default logics will allow for more elaboration tolerant and computationally better representations of various types of commonsense knowledge. This is related also to the comment by Mikhail Soutchanski when he stresses the differences between classical and non-classical logics for knowledge representation. If formalizations of different domains are all done in default logic then we will have no problem to combine all of them together. For instance, if our initial situation is defined in Datalog then it combines very nicely with logic programming version of situation calculus. Even if the languages used for encoding knowledge in different domains are special purpose (like action languages) we will not have any problem combining them together if their entailment relations are formalized in the same language. (e.g. Instead of A we can use its sound and complete formalization in default theories). I am not claiming BTW that nonmonotonic logics are better than classical one. I do not take it as a truth (revealed or otherwise). Pat (and Ray?) can be right and commonsense reasoning can be compatible with monotonic logic. But I think that it is an open and difficult research question which can be answered but trying various approaches. One more comment on how action languages are used. Suppose you have some collection of actions and their effects and would like to write a planner which examines, in some reasonable order, possible sequences of actions and checks if your domain description entails that the goal G holds after the sequence of actions is executed. In this case domain description in A-like language together with its entailment relation can be used to precisely specify the problem. The corresponding logic programming formalization of this entailment together with the domain description forms the main part of the planner. If you decide to use Prolog inference engine you may need to slightly transform the program to avoid floundering, etc. If you do it using results from the theory of logic programming the resulting program will be provenly correct. It seems to be very similar to what people in Toronto do, except we probably concentrate more on correctness of actual program. There are of course many other uses. Finally, some corrections to Ray's comment on A-languages. They have histories (actually, it is their basic feature). Language L from this family combines branching and linear time. This is published in C. Baral, M. Gelfond, A. Provetti, ``Representing Actions: Laws, Observations and Hypotheses'', Journal of Logic Programming, vol. 31, Num. 1,2 and 3, pp. 201-245, 1997 This is a special issue on Logic Programming and Reasoning about actions and I think it contains good papers. As Vladimir already mentioned there are (fully) first order languages. -------------------------------------------------------- | FROM: Mickail Soutchanski -------------------------------------------------------- I will follow the distinction between the gof-sitcalc (sitcalc of 1969) and the R-sitcalc (sitcalc of 1997+); this distinction is proposed by Pat Hayes in ENAI 31.10.97 > > The situation calculus is a foundation for general purpose high-level > >programming languages. Note that it is an easy exercise to formalize > >the Turing machine in the SC. > > It is pretty easy to formalize a Turing machine in > almost anything, so this doesnt mean much. But in any case, what has this > got to do with the topic we are all concerned with? How did Turing machines > come to be relevant here? My intention was to turn the attention to computational aspects: the R-sitcalc is a general theory of action that is a foundation for the high-level logic-programming language GOLOG and its descendants (mentioned by Ray Reiter, ENAI 27.10.97). Because a version of GOLOG is used to control a robot in the real world, the R-sitcalc (as a formalism for reasoning about actions) can be judged according to the test suggested by Murray Shanahan (ENAI 23.10.97). > >> Most intuitive reasoning done by humans lies entirely outside the purview > >> of the situation calculus. > > > >Note that your objection can be easily rephrased as: "Most intuitive reasoning > >done by humans lies entirely outside the purview of the formal logic". > > I have no idea what this response is supposed to mean. Do you identify > formal logic with the situation calculus? Or do you mean only that much of > intuitive reasoning is outside the scope of our subject? Or what?? I do not identify formal logic with the situation calculus. But it is true that I am not sure whether formal logic corresponds precisely to much of our intuitive reasoning. My point was that it is not fair to judge the R-sitcalc only according to the criterion whether it exactly captures *our* intuitions about actions, changes and situations (by the way, nobody ever claimed that the gof-sitcalc or the R-sitcalc expresses the final truth). As long as robots can successfully execute high-level programs based on the R-sitcalc, it is not completely worthless. > >I'm not sure whether we must have the same concerns that the cognitive > >science has. Most of the people do not think in terms of C, LISP, PROLOG, > >but all these languages are still useful for writing programs that will > >exhibit an intended behavior. Similarly, the SC is useful as the basis > >for the high-level programming language. > > And again, I'm at a loss to understand your point. What is 'the high-level > programming language' you refer to here? For the record, I think that > unless our subject is part of cognitive science, then it's just empty > formula-hacking. See earlier comments in reply to Erik. 'the high-level programming language'= GOLOG. There are several experiments performed by anthropologists and psychologists with different people in different parts of the world. As far as I understand their results, in some cases, ability to solve naive physics problems or derive conclusions from syllogistic premises depends on cultural background, education and other personal factors. For this reason, psychology (and cognitive science) cannot be *the only* foundation of our 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/ ********************************************************************