******************************************************************** ETAI NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97002 Editor: Erik Sandewall 22.9.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* The publication of the first issue of the Newsletter led to several rapid responses, and we can proceed at once with the first contribution to the discussion with Wolfgang Bibel, and a list of recently published articles. ********* DEBATE ********* --- QUESTIONS TO WOLFGANG BIBEL --- Here is the first question. It has also been forwarded to Wolfgang; look forward to the answer in a later issue of the Newsletter. Question 1, from Marc Friedman Dr. Bibel, I am intrigued by your passion for posing planning as a deduction problem. Since your lecture at IJCAI 97 in Japan, I have been trying to learn all I can about it. But I have some concerns which I think will have to be addressed for your work to be fully appreciated by those of us who are familiar with planning but not really with deduction. In the process of questioning your work, I will probably do violence to it. I apologize in advance. Please correct me. 0. Linear transition proofs solve the classical planning problem. This is true. Linear backward chainer (LBC), and LIF and LIF+ (Fronhoefer's more recent solutions) are correct. LBC is very clean, too. 1. I think you suggest that deduction has a priveleged place as a basis for classical planning. But planning has other theoretical foundations: the modal truth criterion, and the theory of refinement search. What makes deduction superior to these other bases? 2. You present LBC as an encoding of transition logic (TL) into logic, in particular the languuage of the SETHEO theorem prover. If this were true, AND the implementation compared well with other classical planners, this would be a major step -- giving at once a formal AND operational reduction of the problem to deduction! However, if we look closely at LBC, there is a work-around to make SETHEO into a transition logic engine. TL is not in fact translated to first order logic. Instead, the available propositions are tracked, to prevent two connections from sharing a single proposition. This approach is not truly a reduction. It is an encoding, much like a program that implements a formally sound algorithm, like UCPOP or graphplan, in a formally sound substrate, like PROLOG, or a functional programming language, or as a satisfiable formula. TL loses its priveleged position. Thus it must compete with other approaches on their terms: is it faster or easier to understand, does it do less search, etc. 3. LBC beats UCPOP. But many algorithms have. How does it compare with these? 4. Transition logic solves the frame problem. So does TWEAK. Transiion logic solves the ramification problem. So does UCPOP, via a theorem-proving subroutine. Perhaps TL's ramification solution is a more uniform mechanism, but it is not truly uniform -- the linearity restriction is removed. Why prefer one solution to the other? I think some of the answers are beginning to come to light, and I eagerly await hearing your answers. ********* PUBLICATIONS ********* --- ARTICLES --- The following recent papers and technical reports on actions and causality are available on the UCLA web site, http://bayes.cs.ucla.edu/jp_home.html * David Galles and Judea Pearl An Axiomatic Characterization of Causal Counterfactuals To appear in Foundations of Science, Kluwer Academic Publishers. (1997) Key idea: We study the causal interpretation of counterfactual sentences using modifiable structural equation models and compare this interpretation to Lewis' closest-world semantics. * Galles, D. & Pearl, J., ``Axioms of Causal Relevance,'' To appear in Artificial Intelligence (1997) Abstract This paper develops axioms and formal semantics for statements of the form ``$X$ is causally irrelevant to $Y$ in context $Z$,'' which we interpret to mean ``Changing $X$ will not affect $Y$ if we hold $Z$ constant.'' The axiomization of causal irrelevance is contrasted with the axiomization of informational irrelevance, as in ``Learning $X$ will not alter our belief in $Y$, once we know $Z$.'' Two versions of causal irrelevance are analyzed, probabilistic and deterministic. We show that, unless stability is assumed, the probabilistic definition yields a very loose structure, that is governed by just two trivial axioms. Under the stability assumption, probabilistic causal irrelevance is isomorphic to path interception in cyclic graphs. Under the deterministic definition, causal irrelevance complies with all of the axioms of path interception in cyclic graphs, with the exception of transitivity. We compare our formalism to that of \cite{lewis:74b}, and offer a graphical method of proving theorems about causal relevance. * Pearl, J., "Graphs, Structural Models and Causality" To appear in C. Glymour (Ed.) "Causation, Computation and Discovery", AAAI/MIT Press (1997) Key idea: How graphical models can be used as a mathematical language for integrating statistical data and causal knowledge. * Pearl, J., ``Structural and Probabilistic Causality,'' In D.R. Shanks, K.J. Holyoak, and D.L. Medin (Eds.), The Psychology of Learning and Motivation, Vol. 34 Academic Press, San Diego, CA, 393--435, 1996. Key ideas: How difficulties in probabilistic causality are resolved using graphical models. * Pearl, J., ``On The Foundation Of Structural Equation Models, or, When Can We Give Causal Interpretation To Structural Coefficients?,'' (Part of a commentary prepared for Multivariate Behavioral Research) * Pearl, J., ``Bayesian Networks,'' To appear in MIT Encyclopedia of the Cognitive Sciences (1997) * Pearl, J., ``Causation, Action, and Counterfactuals,'' In Yoav Shoham (Ed.), Theoretical Aspects of Rationality and Knowledge, Proceedings of the Sixth Conference (TARK 1996), The Netherlands, 51--73, March 17-20, 1996. Key words: Action as a Local Surgery, Laws vs. facts, Causal ordering, Imaging vs. conditioning, Causal theories and actions, causal effects and identifiability, A calculus of acting and seeing, Processing Counterfactuals. ******************************************************************** 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/ ********************************************************************