******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97008 Editor: Erik Sandewall 21.10.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Today the Newsletter begins the on-line continuation of NRAC panel discussions. This year's NRAC workshop (Nonmonotonic Reasoning, Action and Change) at IJCAI had a panel on "Theory Evaluation" that was organized by Leora Morgenstern and which tried to address the question "What should be considered as a good theory in our area of research?" This is a very important question also from the point of view of the ETAI -- it fundamentally defines the questions that ought to be asked in the open discussion and the subsequent refereeing of ETAI submitted articles. The full position statements of the three panelists are reproduced below. We look forward to your questions to the panel and your other comments about this topic. The other contents of this Newsletter issue is a summary by Michael Thielscher of his article "A Theory of Dynamic Diagnosis", which in itself was received and reported earlier this month. The use of such summaries or short extended abstracts (about two pages of text) has been introduced by the ETAI in order to facilitate for its readers to follow all the new results that arrive. Besides being advertised in the Newsletter and News Journal, summaries are also linked in the discussion page for each article. We hope that the summary will make it easier to see what the article is about and facilitate the discussion about it. ********* ETAI PUBLICATIONS ********* --- RECEIVED RESEARCH ARTICLES --- Michael Thielscher http://www.ep.liu.se/ea/cis/1997/011/ A Theory of Dynamic Diagnosis. Summary: http://www.ida.liu.se/ext/etai/received/actions/002/summary.ps Full text: http://www.ep.liu.se/ea/cis/NIL/011/ The following summary contains a number of formulae which are difficult to reproduce in plain text, and where approximate notation has been used. For fully correct formulae, please refer to the web-page version of this Newsletter, and click to the postscript version. Diagnosis in general requires more than just passively observing the behavior of a faulty system. Often it is necessary to actively produce observations by performing actions. Diagnosing then amounts to reasoning about more than a single state of the system to be examined. We propose to capture this dynamic aspect by appealing to Action Theory. A formal system description consists of a static and a dynamic part. The former introduces the system components and their static relations in form of so-called state constraints, like, for instance, active(relay1) == closed(switch1) stating that a particular relay is active if and only if a corresponding switch is closed. The dynamic part of a system description specifies the actions which can be used to manipulate the system's state. These definitions are accompanied by so-called action laws, which focus on the direct effects. State constraints like the above then give rise to additional, indirect effects of actions, which we accommodate according to the theory of causal relationships [Thielscher, 1997b]. E.g., this causal relationship is a consequence of our example state constraint: closed(switch1) causes active(relay1) Informally speaking, it means that whenever closed(switch1) occurs as direct or indirect effect of an action, then this has the additional, indirect effect that active(relay1). Generally, causal relationships are successively applied subsequent to the generation of the direct effects of an action until a satisfactory successor state obtains. In this way, the reactions of a system under healthy condition are modeled as indirect effects, so-called ramifications, of actions. Under abnormal circumstances---i.e., if certain aspects or components of the system are faulty---one or more of these ramifications fail to materialize. We introduce an abnormality fluent ab by which we account for such exceptions to both state constraints and the ramifications they trigger. Thus our example constraint from above, for instance, may read weaker---e.g., to the effect that -ab(resistor1) & -ab(relay1) -> [active(relay1) == closed(switch1)] where ab(resistor1) and ab(relay1) represent an abnormal failure of a corresponding resistor and the relay itself, respectively. This weakening transfers to our expectations regarding indirect effects: The aforementioned causal relationship becomes closed(switch1) causes active(relay1) if -ab(resistor1) & -ab(relay1) An important contribution of this paper, now, is a proof that due to the phenomenon of causality straightforward global minimization of abnormality---which is suitable for static diagnosis---is problematic in case of dynamic diagnosis. This raises a challenge much like the one raised by the famous Yale Shooting counter-example in the context of the Frame Problem. Meeting this challenge is inevitable when searching for `good' diagnoses. As a solution, we adapt from a recent causality-based solution to the Qualification Problem the key principle of initial minimization. All instances of the abnormality fluent are assumed false initially but may be indirectly affected by the execution of actions. In this way, our theory of dynamic diagnosis suitably exploits causal information when generating diagnoses. Our theory moreover respects available knowledge of the a priori likelihood of component failures. Since it is often difficult if not impossible to provide precise numerical knowledge of probabilities, we deal with qualitative rather than quantitative information, and we do not rely on complete knowledge. Such possibly incomplete information as to different degrees of abnormality is formally represented by a partial ordering among the instances of the abnormality fluent. For the entire theory there exists a provably correct axiomatization based on the Fluent Calculus paradigm and which uses Default Logic to accommodate the nonmonotonic aspect of the diagnostic problem. ********* DEBATES ********* --- NRAC PANEL ON THEORY EVALUATION --- The NRAC workshop (Nonmonotonic Reasoning, Action, and Change) at this this year's IJCAI featured three panel discussions. It was agreed at the workshop to continue some of the panels as on-line discussions on the web, and we are now ready to do that in the present Newsletter. Our present issue contains the introductory position statements of the three panelists, almost exactly the way they circulated them to each other before the workshop. The idea is to proceed in a way that is similar to the familiar conference panel format: there can be exchange of opinions by the panelists, questions and comments from the "floor" (that is, all the readers of this Newsletter), and quite possibly a lot of constructive disagreement. As usual, contributions should be sent to the present Newsletter editor; they will be edited and distributed in forthcoming issues of the Newsletter, and accumulated into the News Journal for October and later months. Since there may be a great variation in the size of the contributions, we shall distinguish two orders of magnitude. *Notes* of one or a few pages will be formatted as separate entities which can be individually cited and linked to. *Telegrams* of at most 20 lines or so are used for simple questions, answers, and opinions. If the notes get to be *too* long, then only excerpts of them will be sent in the Newsletter, with a reference to the rest of the text which is found in the web page. The three position statements follow -- questions and comments are welcome. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Leora Morgenstern: Panel on Theory Evaluation: Issues and Questions. Why have a panel on theory evaluation? Nonmonotonic reasoning, action, and change have been studied by the AI community for the past 2 - 3 decades. There has been much churning out of new theories, but limited attempt at analysis of these theories or at introspection. We tend to have little perspective about our work. There's been very little discussion of what makes a theory good, what makes a theory last, how much progress we've really made, and what are good ways to encourage progress in the future. This panel is intended to jump start a discussion on these issues. Questions and issues to be discussed are divided into 2 broad categories: By which criteria do we evaluate theories? Can we understand the history of research on nonmon, action, and change in broader historical terms, as suggested by Kuhn, Lakatos, and Laudan? Criteria for evaluation of theories What makes a theory of nonmonotonic reasoning, action, and/or change a good theory? (These may be the same things that make any AI theory good.) Do we judge a theory by the set of problems it can solve? whether its ontology and axioms "make sense", i.e., are true in some sense? it is easily accessible or "naive" as Pat Hayes would call it? it can be integrated with existing "good theories"? What gives a theory staying power? What are some examples of theories with staying power? Are these always the good ones? Specifically, are there examples of good theories which didn't last very long in the AI community? Examples of bad theories which did last long? (And who will be brave enough to identify these ;-)) Understanding research in a broader, historical perspective Thirty-five years ago, Thomas Kuhn suggested that the history of science is best understood as a cycle of periods of "normal science" followed by "revolutionary science." It works as follows: A theory is developed which solves some problems. The theory is associated with a "paradigm," which is, to quote Kuhn, "the entire constellation of beliefs, values, techniques, and so on shared by the members of a given community." As time goes on, new problems are discovered which the theory doesn't solve; the theory is modified slightly, and the process continues, until all of a sudden, it becomes apparent to some that the old paradigm just doesn't work. Then comes the "revolutionary" phase, in which a new paradigm is suggested and refined, and the "normal" phase starts again. (The classic example of this is the geocentric theory of the universe, which explained certain phenomena; as new phenomena were discovered, this theory had to be modified (epicycles and deferents), until it became clear (to Copernicus, Galileo, Kepler, etc.) that the geocentric theory just wouldn't work. The revolutionary phase supplanted the geocentric paradigm with the heliocentric paradigm, which then became normal science.) Questions: can we understand the history of our field in this way? If so, are we in a "normal" phase or a "revolutionary" phase? Can we identify any such phases? Or are we still in one of the prehistoric phases? Or -- perhaps we are better off viewing our history from another perspective. Lakatos suggests that there's no one "normal" paradigm at any one time, but a number of competing research programmes. What unites these programmes is a core set of assumptions; however, there are different auxiliary assumptions. What research programmes can we identify? Do we subscribe to a core set of beliefs? Which programmes, to use Lakatos's terms, are progressive? Which are degenerative? Have any become degenerative and then popped back to being progressive? Or should we subscribe to Laudan's description of "research traditions" which deny a core set of beliefs, but assert a common set of ontological assumptions and a common methodology for revising old theories and developing new ones? Any other suggestions? Is it worthwhile going through this exercise at all? It could be argued that the major developments of physics, astronomy, biology, occurred without much introspection at all, and this is perhaps valueless. On the other hand, we could argue that given the miserable state of research in nonmonotonic reasoning and action today, we need all the analysis and introspection we can get. Any more ideas? Finally, if you want to get into the swing of theory evaluation, you may want to look at: Erik's book (Features and Fluents) My article "The Problems with Solutions to the Frame Problem" available at http://www-formal.stanford.edu/leora (available also in the collection of papers "The Robot's Dilemma Revisited", Ablex, 1996, but the web is more accessible). +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ David Poole: Modelling Language vs. Repository of Common-Sense Facts. My guess is that we are in a phase of normal science. The revolution is coming. When we have to explicitly consider uncertainty much of what we think we understand now will have to be thrown out. In order to go about evalation, we have to make our goals clear. (If it doesn't matter where you want to get to, it doesn't matter much which way you go, to paraphrase Lewis Carrol). There are two quite different goals people have in building KR system; there is much confusion generated by not making it clear what you are doing (so much so that the researchers who take one view often don't understand what the others are doing and why). These are: 1. A knowledge representation as a modelling language. If you have a domain in your head you can use the KR to represent that domain. The builder of a KR is expected to give a user manual on how to axiomatize the domain. There are right ways of saying something and there may be wrong ways of saying it. Missing knowledge may mean something. Prolog and Bayesian networks are examples of such knowledge representations. 2. A knowledge representation as a repository of facts for commonsense reasoning. Under this scenario, you assume you are given a knowledge base and you are to make as much sense out of it as possible. It isn't OK for the designer of the KR to prescribe how a domain should be axiomatized. The KR should be able to get by with whatever knowledge it has. Much of the nonmon work assumes this (as far as I can see). If you goal is the first, you probably want a very lean language which doesn't provide multiple ways of doing the same thing. You want to provide a recipe book about how to go about modelling a domain. It should be judged by whether someone can go from an informal problem (not a representation of a problem) to a solution efficiently. Does it provide a good way to think about the world? Can it exploit any structure of the domain for efficiency? If your goal is the second, you probably want a rich language that lets you state as much as possible. It should be some free-form language that doesn't constrain you very much. Here we need to go from a representation of a problem into a solution. Does it provide reasonable answers? Can the user debug the knowledge base if an aswer is wrong? I have two ways of judging a representation: Can I teach it to cynical undergraduates without squirming? Can I make a case that this is the obvious answer? How well does it work in practice? What is the range of practical problems for which it provides a solution? +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Erik Sandewall: What Should Count as a Research Result in our Area?. I want to focus on Leora's first issue - criteria for the evaluation of theories, and I think the first thing to discuss is what could or should reasonably count as a *research result* in our area, that is, what things ought to be citable in the literature. "Citable" means that they are crisp, have a lasting value, that later researchers can build on earlier results, etc. Then, presumably, some of the respectable research results are those which tell us something about the qualities of a particular theory/approach/formalization/... Research results presumably come in several colors and shapes; I am thinking of categories such as the following: * a formalism (sitcalc, Allen interval algebra, Yoav's explicit time logic; the A language, GOLOG, and so on) * a semantics for a formalism (maybe formalisms without semantics shouldn't count, but then there may be multiple semantics for the same formalism, so I put this as a separate category) * a nonmonotonic entailment method (using my own term), for example chronological minimization of change, chron min of ignorance, causal minimization * a theorem (with proof) about the validity or range of applicability of an entailment method. This kind of result of course is obtained relative to a validation criterium, and for that we need ontologies (next panel) * a disqualification of a proposed formalism/semantics combination in terms of counterexample(s), e.g. the original Hanks/McDermott paper * equivalence results in various dimensions (reexpressibility of one formalism/semantics in another one, for example) * a metastructure, such as a classification scheme, an impossibility result (do we have any of those?) * a computational property of an algorithm, e.g., a complexity result To the extent that we have this kind of solid results, we can evaluate proposed theories (= formalism + semantics + entailment method ??) with respect to their range of applicability and their computational properties. With respect to David's distinction between knowledge representations that are modelling languages and those that are intended for repositories of common-sense facts, my heart is with the former kind. Among the above categories of results, those that concern or make use of a formal semantics probably only make sense in the context of a modelling language, since the notion of common sense is so vague and inherently difficult to capture. ******************************************************************** 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/ ********************************************************************