******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98022 Editor: Erik Sandewall 27.2.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* The discussion on causal approaches to ramification got a bit heated in our issue two days ago, but today more messages have been exchanged, and everyone is friends again. What's more, there is the beginning of a consensus as to the similarities and the differences between those approaches that have participated in the discussion. This is the kind of clarification that may be difficult to extract by only reading the papers, and we hope that the Newsletter discussion can be a useful complement. Perhaps this is something that your graduate students ought to see? The present Newsletter contains contributions from four actors in the debate. Is there more to come? A practical note: many of these messages contain references to published papers. The on-line, HTML version of the debate contributions have often been augmented with full bibliographic references and hot links to the actual papers. Therefore, if you wish to check the full paper, our on-line version is often a convenient means of access. Please note also that it sometimes takes a few days before these hot links get to be installed. ********* DISCUSSIONS ********* --- DISCUSSIONS ABOUT ARTICLES AT COMMONSENSE WORKSHOP --- ======================================================== | AUTHOR: Peter Grunwald | TITLE: Ramifications and sufficient causes ======================================================== -------------------------------------------------------- | FROM: Peter Grunwald | TO: Vladimir Lifschitz -------------------------------------------------------- Vladimir, I agree with you that the concept of `causality in terms of intervention only' is too narrow (and Searle expresses it quite well!); I just think that most of the examples in common sense reasoning we are currently dealing with are simple enough to be formalized in `interventionistic' terms. On the technical side, I do think there are some advantages in using the formalization one would obtain by translating the `reverse switches domain' (example 5 in my paper) to the suitcase domain, i.e. using $(holds ^ caused) V (caused ^ holds) -> caused$ instead of $holds ^ holds -> caused$. These advantages are the same as those outlined for the switches domain in my common sense paper (see example 5). -------------------------------------------------------- | FROM: Peter Grunwald | TO: Fangzhen Lin -------------------------------------------------------- Fangzhen, First of all, let me apologize. I am very sorry to have insulted you with my remarks. This was never my intention. Too eager to write a reply quickly, I wrote it without thinking and I didn't realize that it would be taken literally. In fact, I find your approach one of the most intuitive I have come across; I think we both have quite similar intuitions about we are modelling which makes it all the more silly to write `you don't know what you're modelling'. Here is what I really wanted to say; I hope I'll be able to formulate it in a better way now: `I think it is clearer what kind of situation can and what kind of situation cannot be modeled with the help of the `Do' predicate (which is intended to stand for interventions) than with the help of the `Caused' predicate (which, if I understand you correctly, is intended to be used in those situations in which we would use the _word_ Caused in natural language).' Now that I'm at it, let me elaborate on this a little bit: Though their roots are different (`Do' coming from Pearl's structural equation theory and `Caused' coming from your work), it turns out that _formally_ speaking, `Do' is almost the same as your `Caused' : they are defined in very similar ways which may even be equivalent (though this hasn't been proven). One of the aims of (the long version of) my paper is to point this out. That it may make sense to point it out can be seen from example 5 in the paper (the `reversed switches domain', originally due to Sandewall and/or Doherty, I believe). The Do-predicate occurs there in the following axiom: Do(Light(t),TRUE) -> Do(Switch(t),TRUE) (*) (from the fact that the light has been put on we conclude that the switch has been put in the on position) If we describe to one another, in natural language, what is modelled by this axiom, then we would probably not use any causal terms (does putting on the light cause the switch to be on?) (see the paper for details). However, (*) can be modelled equally well by your `caused'-predicate as with the `do'-predicate used here. It follows that your `caused'-predicate has broader applicability than it might seem, which I think is worth noting. -------------------------------------------------------- | FROM: Peter Grunwald | TO: Erik Sandewall -------------------------------------------------------- Erik, You wrote: > Peter, you seem to argue that (3) is the right approach, and quote > Fangzhen as using (1); Vladimir defends this with the reference to > Searle. However, I observe that in his 1995 article, Fangzhen allows > both (1) and (3). The general form of causal rules in his formula > (16) allows one or more uses of the exception operator in the > antecedent. However, example (22) does not use it, apparently in order > to assure that the minimization will be computable by Clark completion. > Isn't that a problem in your (Peter's) case as well? Indeed, Fangzhen allows both approaches (1) [holds -> caused] and (3) [caused -> caused]. My point is only (see my answer to Lin's question C1-4)) that my approach can help you in deciding what domains should be modelled by (1) and what domains should be modelled by (3). I may indeed have trouble with efficiently computing the minimization - that wasn't my primary concern in the paper. -------------------------------------------------------- | FROM: Vladimir Lifschitz | TO: Erik Sandewall -------------------------------------------------------- Erik, I am puzzled by your comments about Lin's predicate Caused in ENRAC 25.2. In your view, it is an "exception operator," like occlusion. My understanding is very different. Exception operators are as old as formal default reasoning; McCarthy called his exception operator Ab, and its predecessor End can be found in your paper written back in the 1970s. Lin's predicate Caused, on the other hand, is a new and original idea. You quote from Lin's abstract: > Technically, we introduce a new ternary predicate... > $Caused(p,v,s)$ if the proposition $p$ is caused... to have the > truth-value $v$ in the situation $s$. Then you write: > Compare e.g. my article in Journal of Logic and Computation, vol. 4, > no. 5, 1994, section 7.2 (misprint corrected): > > > Here $[s,t]p := F$ is an often-useful abbreviation for > > $(s,t]Xp and [t]p=F$. Informally, it is read as saying that the > > feature $p$ changes its value to become $F$ some time during the > > interval $[s,t]$. > > This reduces to $Caused(p,F,s)$ if $s = t$. Two points: First, if s=t then your informal reading turns into "$p$ changes its value to become $F$ some time during the interval $[t,t]$." How can p change its value during an interval consisting of one time instant? Second, Lin's paper and yours use different temporal formalisms. To compare the two approaches, let's translate your formulas into the situation calculus. The counterpart of the formula (s,t]Xp and [t]p=F in the situation calculus is Ab(p,a,s) and Value(p,Result(a,s))=F, (1) where $Ab$ is the abnormality predicate from the commonsense law of inertia not Ab(p,a,s) -> Value(p,Result(a,s))=Value(p,s). The fundamental difference between (1) and $Caused(p,F,s)$ is that the former contains an action variable, and the latter doesn't. Lin's IJCAI-95 paper was a major development that has not been fully appreciated so far by the nonmonotonic community. --Vladimir -------------------------------------------------------- | FROM: Erik Sandewall | TO: Vladimir Lifschitz -------------------------------------------------------- Vladimir, I thought I had found a previously unused term when I used "exception operator" as a generic for "occlude", "release", "Caused", etc. I don't think you would claim that all of those are trivially reducible to abnormality? Re > First, if $s=t$ then your informal reading turns into "$p$ changes its > value to become $F$ some time during the interval $[t,t]$." How can > $p$ change its value during an interval consisting of one time instant? a feature is said to change its value at time $t$ iff its value at $t$ differs from its value at $t-1$. This is for the case of discrete time; for continuous time you have to use the left limit value at time $t$. Then, a feature is said to change its value in the interval $[s,t]$ iff it changes its value in some point in $(s,t]$ (omitting the left endpoint of the interval), that is, either between $s$ and $s+1$, or..., or between $t-1$ and $t$. When I referred to the special case of $s=t$ in $[s,t] p := F$, I chose naturalness over formal precision, since it should have said $s=t-1$. I thought introducing this technicality would have been an unnecessary distraction. Re > The fundamental difference between (1) and $Caused(p,F,s)$ is that > the former contains an action variable, and the latter doesn't. evidently this action variable is an artifact of your translation, since it is not present in the original formulation. Also, since Lin's paper does not use any $Ab$ predicate (he minimizes $Caused$ directly), translating my formulation to one using $Ab$ doesn't particularly help the comparison. In fact, if you translate Lin's notation in the same way as you did for mine, you will have to introduce an action variable there as well since your $Ab$ predicate is *defined* with that as its second argument. However, this has nothing to do with either Lin's formalism or mine. The translation task is actually very simple, since my formalism allows for both linear time and branching time (F&F page 138 ff). For branching time, the notation $[s,t]$ is defined only if $t$ is a direct or indirect successor of $s$, and it then refers to the path from $s$ to $t$. Defining $t^$ as $t-1$ in the case of integer time, and through the axiom $do(a,s)^ = s$ for the case of gof-sitcalc situations, the obvious translation of (t^,t]Xp & [t]p = F (1) into Lin's notation is Caused(p,F,t) (2) (Remember that $[t]p=v$ is the same as $H(p,v,t)$, and that this is a modified kind of equality, the correct character for which isn't defined in ASCII). Both the informal explanation and the formal treatment of (1) and (2) are identical in the two approaches, for mainstream examples. Formula (2) is more compact, which is why I introduced the abbreviation [t^,t] p:=F Then it's clear that the difference is purely notational. If one doesn't want to represent the duration of actions, then one can of course modify the abbreviation so that only one timepoint is mentioned. -------------------------------------------------------- | FROM: Fangzhen Lin | TO: Erik Sandewall -------------------------------------------------------- Erik, Some thoughts about your note in ENRAC 25.2 (98021). 1. Caused \== Occlude. For example, $Caused(p,true,s) => H(p,s)$. But there are no such axioms for Occlude. Notice that these axioms go a long way: in deriving a generic successor state axiom, new causal rules from old ones, making causal rules strictly stronger than corresponding state constraints... 2. Caused(p,true,s) \== Occlude(p,s,s) & H(p,s) Caused(p,true,s) \== Occlude(p,s) & H(p,s) See (Gustafsson and Doherty, KR'96). 3. Regarding the previous results of occlude that you mentioned: > > ... we argue that normal state constraints that refer only to the > > truth values of fluents are not strong enough for [specifying the > > effects of actions using domain constraints], and that a notion of > > causation needs to be employed explicitly. > > See e.g. the Persson-Staflin paper at ECAI 1990. Several papers in > our group during 1988-1993 used a unique concept, "occlusion" or > "explanation" of change for several purposes: for imprecise timing > of changes within an action with extended duration, for nondeterminism, > and also for "our intuition that a discontinuity should have a cause" > (Persson/ Staflin). The abstract continues: Observe that none of them were about domain (state) constraints and the ramification problem. As you can see from the paragraph that you cited from (Lin 95), the main contribution of my paper has to do with constraints and in particular causal constraints. If I'm not mistaken, the main impacts of the set of quite related papers on actions in IJCAI'95 have to do with the ramification problem. They shed some new lights on the nature of this problem that had never before been thought of, and have just begun to bear fruits: for example, the work by Michael Thielsher on diagnoses that was discussed in this newsletter before, and the work on planning from causal theories using GSAT by Norm McCain and Hudson Turner (in KR'98). 4. Regarding the connection between your PMON and the minimization strategy that I used, yes, I'd be the first to admit that they are very similar. I apologize for not knowing it earlier. Thinking back, it's not surprising how they come together. As you know, I have been a devotee of what you call "filtered preferential entailment" approach for as long as I can remember, going back when Yoav and I were working on our provably correct theories of actions. The idea of minimizing Caused with Holds fixed was also straightforward as it was the obvious one that would yield the Clark completion of causal rules. 5. I enjoyed reading Gustafsson and Doherty's KR'96 paper. I learned a lot from that paper. Patrick and I had some correspondences on the related topics. I believe we found some common grounds, but none in terms of "one can be reformulated in terms of another." (Patrick, correct me if I'm wrong.) If anything, I wouldn't call PMON(RCs) a "trivial extension of PMON to causal rules," especially when Occlude is applied to a time point in PMON(RCs) while the same predicate is applied to a time interval in PMON. Many things are trivial in retrospect. (The idea of GSAT is so simple that Russell and Norvig even include it as an assignment in their AI textbook.) But in any event, this paper is more or less irrelevant as far as the history is concerned. Last but not the least, Erik, I have all the respects and regards in the world for you and your work! And Peter, there is no hard feeling whatsoever. - Fangzhen -------------------------------------------------------------------- This sentiment is reciprocal! - Erik ******************************************************************** 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/ ********************************************************************