******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98003 Editor: Erik Sandewall 9.1.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* ETAI PUBLICATIONS ********* --- DISCUSSION ABOUT RECEIVED ARTICLES --- This issue contains Michael Thielscher's answers to the questions by Marie-Odile Cordier and Wolfgang Nejdl with respect to his ETAI submitted article. ======================================================== | AUTHOR: Michael Thielscher | TITLE: A Theory of Dynamic Diagnosis ======================================================== -------------------------------------------------------- | FROM: Michael Thielscher | TO: Marie-Odile Cordier -------------------------------------------------------- I want to thank Marie-Odile for the very detailed comments, the pointers to related literature, and for the interesting questions. Let me answer the latter in turn. The main matter of concern in my paper is to point out a crucial aspect of generalizing theories of diagnosis to what I call the dynamic case: Component failures, which usually are considered abnormal, may naturally arise in the course of time as direct or indirect effects of actions (or events, for that matter). As a consequence, it is inappropriate to simply apply minimization strategies that are suitable in the static case equally to all states that arise during the diagnosis process. Rather it is necessary to employ the `static' strategy only once, namely, initially. This allows to count as perfectly normal any component failure that is effected later on. Now, in the paper I have pursued one particular `static' minimization strategy, namely, where it is required that if there is a difference in the a priori likelihood of component failures, then it needs to be explicitly stated so. This is not the case in the scenario and reasoning process you described: The a priori likelihood of ab(re1) is higher than that of ab(r1). Hence, what you suggest is a more sophisticated *static* strategy, where differences in the a priori likelihood of abnormalities are derived from state constraints. This does not affect my argument: If diagnosis concerns a sequence of states, then again this more elaborated minimization strategy should be applied only once, thus allowing for component failures to be effected in the course of time. Concerning the second remark, I admit that for the diagnosis community the term "dynamic" might be misleading, at least at first glance. To begin with, in the area of formalizing reasoning about actions and change it has become common to call "dynamic" any system that may exhibit different states in the course of time, no matter whether state changes are brought about by exogenous action or by natural events that happen inside the system. The striving motivation for me adopting this term was to contrast the contents of the paper to Reiter's work on diagnosis [1]. But apart from that, many results have been established that show how approaches to reasoning about actions can be generalized to the case where actions are performed in self-evolving systems. (See, e.g., [2], [3], [4], just to mention a few.) The gap between dynamic systems which idle unless actions are performed, and those that are self-evolving turned out less deep than one might have expected. In particular, the theory of causal relationships (and the axiomatization on the basis of the Fluent Calculus) has very recently been extended to allow for natural events aside from exogenous, volitional actions [5]. Combining this extension with the diagnosis approach pursued in the paper has yet to be achieved, but there seems to be no fundamental obstacle for so doing. This leads to my answer to your third remark. An example taken from [5] is the following specification of the behavior of a simple timer by means of a causal relationship: (clock IS x+1) causes (timer IS t-1) if (timer=t and t>0) which says that whenever the global clock ticks, then the timer counts down until it reaches zero. This shows that causal relationships do not depend on the performance of actions but just on the occurrence of effects, which might just as well be the consequence of natural events inside the system. Now, the motivation for using a causal description rather than an explicit transition model is that only the former corresponds directly to a natural and "elaboration-tolerant" (see [6]) description of actions and events, effects and change. (Notice that via the theory of causal relationships, any causal description implicitly determines a transition model.) Generally, research in the area of commonsense reasoning about actions is largely motivated by the conceptual gap between a natural description of causes and effects, and the corresponding transition model. The Ramification Problem, for instance, has to be understood in this way, and so is of course an issue in case of self-evolving dynamic systems just as well (see again [5]). [1] R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence Journal, 32:57-95, 1987. [2] M. Thielscher. The logic of dynamic systems. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), p. 1956-1962, Morgan Kaufmann 1995. [3] R. Reiter. Natural Actions, concurrency and continuous time in the situation calculus. In: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), p. 2-13, Morgan Kaufmann, 1996. [4] M. Shanahan. Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia. MIT Press 1997. [5] M. Thielscher How (not) to minimize events, 1997. (Submitted to KR'98.) [6] J. McCarthy. Elaboration tolerance. In: Working Notes of "Common Sense '98", 1998. URL: http://www.dcs.qmw.ac.uk/conferences/CS98/CS98Papers.html. [7] M. Thielscher. Ramification and causality. Artificial Intelligence Journal, 89(1-2):317-364, 1997. -------------------------------------------------------- | FROM: Michael Thielscher | TO: Wolfgang Nejdl -------------------------------------------------------- Let me now give answers to the questions by Wolfgang Nejdl. One of them also concerns the use of the term "dynamic systems" and so has already been considered in the answer to the previous question. The references before refer to the bibliography of that answer. As for the motivation for using causal relationships, this is entirely due to the dynamic aspect. The past decade or so of research in reasoning about actions has revealed that state constraints, being static in nature, may however also give rise to indirect effects of actions (or events)-- yet it is usually challenging to determine exactly to which effects. In fact, state constraints often lack information needed to tell `real' indirect effects from `phantom' effects, which would never occur in reality. Causal relationships do provide this necessary additional information. (See the first three sections of [7] for a detailed introduction to this problem and for the motivation behind causal relationships.) As for the problem of determining suitable test actions, this is indeed a side issue in the present paper. I merely want to show that the theory does in principle support the search for such actions. A detailed account would mean to develop a sophisticated search strategy and to make precise how the relative usefulness of possible actions is to be judged. This would clearly go beyond the scope of the present paper, but is definitely of interest and could very well be the topic of a follow-up paper. Finally, to the relation to Sheila's approach. First of all, there is a difference from a very general point of view. Her approach starts with a particular axiomatization strategy, namely, the Situation Calculus. My intention was to focus on a high-level theory of dynamic diagnosis, prior to considering the problem of a suitable first-order axiomatization. The latter I have briefly tackled in the section on a (provably correct) Fluent Calculus-based axiomatization. At least for a large part of the high-level theory, Sheila's axiomatization may very well prove correct, too. Some more specific remarks as to differences in the expressiveness have been made in the discussion part of the paper. In addition to this it is worth mentioning that much work has been done on the pros and cons of Situation Calculus in general compared to alternative axiomatization strategies (among which are the Event- and the aforementioned Fluent Calculi; see, e.g., [4,7]). ******************************************************************** 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/ ********************************************************************