******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97034 Editor: Erik Sandewall 23.12.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Recommended reading for Christmas: Michael Thielscher's article "A Theory of Dynamic Diagnosis" which was received by this ETAI area on October 7, and Marie-Odile Cordier's discussion contribution on this article which follows in the present Newsletter issue, where she also relates Michael's approach to her own. Additional contributions to this discussion are welcome, particularly before January 7 since the period for open discussion is set to be three months. ********* 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: Marie-Odile Cordier -------------------------------------------------------- I have three main comments on this paper : 1) The example on page 4-6 is quite interesting and highlights very clearly what happens when dealing with interactive faults (ab(r1) causes ab(re1) when s1 is closed). But, I did not really agree with the conclusion the author is drawing from it. What it clearly highlighted, in my opinion, is that "minimizing abnormality" cannot be used when dealing with interactive faults. Most research papers on diagnostics suppose implicitly that faults are independent and equiprobable, and in these cases, "minimizing abnormalities" is a good way of selecting the most probable diagnoses. However, as soon as you are dealing with interactive faults the preferred diagnoses have no good reason (no probabilistic foundation) to be the minimal ones. In the example, the probability of ab(re2), knowing ab(r2) and closed(s2) is equal to 1 whatever the probability of re2 is of being faulty from its own. Then, d1 has to preferred rather than d2 and d3. The key point is that "minimization" (minimizing abnormalities) is not a good preference strategy in case of interactive faults. This seems to me to be the very reason why one doesn't get the expected results in this example. Another point concerns when this "preferring" step has to be done. The author argues that it has to be done at the starting point and uses the example as a justification. I don't contest this fact (see below), but I contest that it follows from the example. From the following example, it can be seen that "minimizing abnormalities" is not a correct solution even if it is done at the starting state. Let us suppose that it is known that closed(s1), closed(s2), closed(s3) and off(light) are true in the initial state. Whatever the action might be, for example "open s1" or the empty action, you are going to prefer a state where ab(re1) is true rather than the one where ab(r1) and ab(re1) are true, which is not at all justified from a probabilistic point of view. It is even problematic from a diagnostic point of view, for replacing re1 by an unfaulty relay (instead of replacing r1) will lead to breaking re1 again as soon as you will close s1. In fact, example 1 (page 20) exhibits similar results which are not satisfying by forgetting ab(r1) and ab(r2) as possible faults. 2) The term "dynamic diagnosis" is used throughout the paper to denote diagnosis on systems on which you are performing actions (tests). As far as I understand, the systems are supposed to be static ones; they are not supposed to evolve by their own; they don't have any proper dynamic behaviour. The only way to make them change is to perform actions. This is the reason why you can predict the resulting state by looking only to the effects of the action. Unpredictable events are not taken into account, for exemple faults (or more simply evolutions of the system) that occur during the sequence of actions. The term "dynamic diagnosis" is then misleading, at least for the diagnostic community for which dynamic diagnosis usually means diagnosing systems evolving in time by themselves, without explicit exogeneous events making them change. In this context, the problem which is proposed is very similar to that of postdiction : knowing some observed facts resulting from an action (or a sequence of actions), you want to infer the actual state of the system. Faults cannot happen during the sequence of actions, and then dealing with an action or a sequence of actions makes no difference. Consequently, it is quite justified to apply the "preference step" on the initial point. You have to determine the most probable sequences of steps (or histories, scenarii, trajectories?) starting from initial states, leading to some final states in which observations are true, and corresponding to a given sequence of actions. There are no unknown events; there is no uncertainty in the actions; no uncertainty wrt their effects; the only uncertainties concern the initial states. The preference between sequences depends directly on preferences on initial states, which explains why the "preference step" concerns the initial states. This scheme is a restricted case of a most general scheme in which you take into account the possible occurences of events (as faults) interleaved with the actions, the probability of such events, and the probability of an action to produce some effects. Selecting some of these scenarii according to preference criteria corresponds to what we called "event-based diagnosis" in [Cordier-Thiebaux94]. It is also close to McIlraith's approach; see the references below. The main difference between these approaches is that we tried to define diagnostics independently of the mechanism used for modeling actions and changes, whereas Sheila's proposal is clearly dependent on the formalism used to model actions (situation calculus). 3) The last point concerns the ramification problem and the use of a causal model to predict the effects of an action. I realize that this point is not the main subject of this paper, since it is devoted to diagnostics. However, an important point related to this paper is to examine whether it can be applied when dealing with dynamic systems. This theory of action based on causal relationships is very attractive as long as you are looking for the effects of an action or a sequence of actions, and as long as the concerned system has no proper evolution. Fluents which are not affected by an action are then supposed not to change, by virtue of a minimal change principle. But as soon as you are concerned with dynamical systems, (which is not really the case in the paper), such a causal model would probably not be sufficient and you will need a "transition model", describing the way things evolve along time. This happens for example if you want to model the dynamics of a system, or the possible events as faults that occur as you are monitoring a system, or the natural ageing of components. An answer could be that there cannot be changes without causes, but most of the time you don't want to model these causal chains or you are not even able to model the primary causes of such evolutions (for example, the ageing of components or the sudden occurence of a fault), but you want nevertheless to take them into account as far as possible. The basic idea of the proposal we made in [Cordier-Siegel95] was that a transition model (that is, a set of possible (partially ordered) transitions) is needed in order to decide what is the most plausible state after an update, or equivalently, an action. A causal model is certainly quite adequate when considering static systems reacting to actions. More than that, in my opinion, a causal model is a very nice formalism allowing to acquire the partial orderings that exist between transitions, in a natural way. There is probably a strong correspondence between your "influences" and our "partially ordered transitions" which would be worth studying more deeply. However, transitions seem to have a broader scope in that they allow to represent any changes from one world to a next one, whereas causal relations or influences are restricted to represent "causative changes" (changes for which one can exhibit the causes). This is a problem when dealing with dynamical systems. References : ----------- 1. M.-O. Cordier, S. Thiébaux Event-based diagnosis for evolutive systems Proceedings of DX'94, 1994 or the internal report IRISA #819 http://www.irisa.fr/EXTERNE/bibli/pi/pi819.html 2. M.-O. Cordier, P. Siegel Prioritized transitions for updates, Proceedings of ESCQARU95, LNAI 946, 142-151, 1995 or the internal report IRISA #884 : http://www.irisa.fr/EXTERNE/bibli/pi/pi884.html 3. S. Mc Ilraith Towards a theory of diagnosis, testing and repair Proceedings of DX'94, 185-192, 1994 4. S. Mc Ilraith Explanatory diagnosis: conjecturing actions to explain observations Proceedings of DX'97, Mont-Saint-Michel, 69-77, 1997 ******************************************************************** 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/ ********************************************************************