Issue 97002 | Editor: Erik Sandewall | 22.9.1997 |
Today |
Debate |
Question 1, from Marc Friedman [friedman@cs.washington.edu]
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 |
* 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.