******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98023 Editor: Erik Sandewall 2.3.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* The question-and-answer session about Peter Grunwald's article at the Commonsense workshop continues, and has gradually extended into a discussion about causality and ramification in general. With one more contribution today - by Eugenia Ternovskaia - it seems it's time to start up the topic-oriented (``panel'') discussion about **Ramification and Causality** that has been advertised since a while. Authors of additional contributions are asked to specify whether they wish their note to go into the new, topic-oriented debate or to the specific discussion with Peter. Today's issue contains two contributions: Eugenia's contribution to the new ``ramification and causality'' debate, and also an answer by Eyal Amir to Erik Sandewall's question re his Commonsense workshop paper. ********* DISCUSSIONS ********* --- CAUSALITY AND RAMIFICATION --- -------------------------------------------------------- | FROM: Eugenia Ternovskaia -------------------------------------------------------- Erik Sandewall wrote: > maybe the section on "related work" in research papers ought not to be > our only mechanism for assembling topic-specific surveys and > bibliographies, and possibly the present debate forum could serve as > a complement. Additional contributions are invited to this account of > recent history, therefore. A few notes about earlier work on the solution to the frame and ramification problems based on the notion of causation. In connection with the frame problem, an important step forward was the idea 1. to characterize the conditions making fluent F true and the conditions making it false separately, and, at the same time, 2. to say that actions produce no other effects using a minimization policy. I think it was proposed in Lifschitz's 1987 paper. Unfortunately, I don't have it anymore and cannot check. Vladimir, could you remind us? [Full reference in on-line version of this Newsletter. - Editor] Reiter, basing his solution on the previous work by Pednault, Haas and Schubert, appeals to the same two principles. He specifies the conditions making a fluent to hold and not to hold by FO formulas $\gamma^+$ and $\gamma^-$. Instead of explicit minimization, he uses the Causal Completion Assumption. The main lesson we can derive from this work is that no special non-logical symbol (predicate) is necessary to capture causal information in classical logic. With respect to the ramification problem, Elkan considers a ``stuffed room'' domain, a variant of the ``suitcase example''. He argues that the ambiguity problem can be resolved using an explicit notion of causation. He uses two predicates, $causes(a,s,f)$ to be read ``executing action $a$ in state $s$ causes fluent $f$ to become true'', and $cancels(a,s,f)$ saying ``executing action $a$ in state $s$ causes fluent $f$ to become false''. In order to specify that actions produce no other effects, he uses ``bidirectional implication as a minimization operator'', i.e., he completely characterises predicates ``causes'' and ``cancels''. V. Lifschitz, 1987. Formal theories of action. In Proc. of the Workshop on the Frame Problem in AI. R. Reiter, 1991. The Frame Problem in the Situation Calculus: a simple solution (sometimes) and a completeness result for goal regression. In: Lifschitz, ed. AI and Math. Theory of Computations: Papers in Honor of J. McCarthy. C. Elkan, 1992. Reasoning about actions in first order logic. In Proc. of the Conference of the Canadian Society for Computational Studies of Intelligence. --- DISCUSSIONS ABOUT ARTICLES AT COMMONSENSE WORKSHOP --- ======================================================== | AUTHOR: Eyal Amir | TITLE: Point-Sensitive Circumscription ======================================================== -------------------------------------------------------- | FROM: Eyal Amir -------------------------------------------------------- Dear Erik. Thank you much for your insightful comments. You write > ... The K-IA ontological class allows for > scenarios with nondeterministic actions, actions with extended duration > in time and internal structure, and all combinations of prediction and > postdiction. It does not model causality or other forms of ramification, > nor concurrency, etc. > ... > For this K-IA class, we have studied a number of , > each of which can then be reexpressed in e.g. pointwise circumscription. > PCM is one of those entailment methods. > .... > In this framework it is perfectly reasonable, as you do, to evaluate > a variant of circumscription with respect to whether or not it is > capable of expressing a particular entailment method, or even a > collection of them. > ... > > Though I agree with your methodology up to that point, I do not > understand the concrete case where it is applied. You only discuss > how PCM is rendered in variants of circumscription, but Doherty has > already shown how to express PCM in pointwise circumscription. > If your variant of circumscription is able to handle more examples > correctly within the range of K-IA, it could therefore only be > because it were an inaccurate rendering of PCM. [For the reader: PCM is defined roughly as follows (see [SandSho94] for more details): Interpretations $I <<_pcm I'$ iff $M=M'$ (the objects are the same) and there is $t_0$ s.t. 1. for all t < t_0, R(t) = R'(t) (the fluents are identical in $I$ and $I'$ before t_0) and 2. $breakset(I,t_0) subset breakset(I',t_0)$ (the fluent value changes from $t_0 - 1$ to $ t_0 $ in $I$ are a subset of the appropriate changes in $I'$). Then the set of models for PCM is S_pcm(T) = Min( <<_pcm, models(T)) .] Pointwise Circumscription (I shall abbreviate it here Pt-Circ) is a special case of Point-Sensitive Circumscription (abbreviated here Pt-Sens), and so PCM can be expressed in Pt-Sens the same way [DohLuk94] shows with Pt-Circ. However, Doherty and Lukaszewicz showed that Pt-Circ expresses PCM only for the ontological class Kp-IAex, in which no observations later than time $t=0$ are allowed. The example I give in the paper shows that Pt-Sens may be able to express PCM outside Kp-IA (notice that the example I give falls within K-IA, as the "ramification" is accounted for by domain constraints (observations for time later than 0)). I did not prove a higher lower-bound, though. I just showed cases outside Kp-IA where Pt-Circ fails and Pt-Sens succeeds. You then write > Also, although the range of applicability of PCM is only a limited > part of K-IA, there are other entailment methods such as PMON > which are correct for K-IA, and which can also be expressed in > pointwise circumscription following Doherty. This makes it even > more strange how point-sensitive circumscription can do something > that pointwise circumscription can not, with respect to the K-IA > class. My claim was that we may be able to avoid filtering (the way does) in grasping K-IA. I did not prove that either. Future work?... > You also discuss a simple case of ramification using the duality > between the and properties. This of course is > not within K-IA, as you also observe. However, there are certainly > known methods that handle such simple ramifications (as well somewhat > less trivial ones) correctly and that have been expressed or > re-expressed using pointwise circumscription. Although the simple example I gave is within K-IA, I support the claim that Pt-Sens can treat some forms of ramification (a first hint at that was made in a paper of mine in NRAC'97). I am not aware of previous expressions of ramifications using Pt-Circ and will be happy to get some pointers. Eyal [DohLuk94] @inproceedings{DohLuk94, author = {Patrick Doherty and Witold Lukaszewicz}, title = {Circumscribing Features and Fluents}, booktitle = {Proceedings of the 1st int'l conf. on Temporal Logic}, editor = {D. Gabbay and H.J. Ohlback}, pages = {82--100}, year = 1994 } [SandSho94] @incollection{SandSho94, author = "Erik Sandewall and Yoav Shoham", title = {\htmladdnormallinkfoot{Nonmonotonic Temporal Reasoning} {Reference requested from Yoav 1/2/97}}, booktitle = {Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 4: Epistemic and Temporal Reasoning}, editor = {D.M.~Gabbay and C.J.Hogger and J.A.Robinson}, publisher = {Oxford University Press}, year = 1994 } ******************************************************************** 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/ ********************************************************************