******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 97009 Editor: Erik Sandewall 22.10.1997 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* The panel discussion on Theory Evaluation which started yesterday has received a contribution from Pat Hayes, which is included in today's Newsletter. We also have a summary of the article by Kakas and Miller which was received a few days ago. ********* ETAI PUBLICATIONS ********* --- RECEIVED RESEARCH ARTICLES --- Antonis Kakas and Rob Miller: Reasoning about Actions, Narratives and Ramification. Summary: http://www.ida.liu.se/ext/etai/received/actions/003/summary.html Full text: http://www.ep.liu.se/ea/cis/1997/012/ Note: This paper was advertised in the Newsletter 16.10; now the summary is also available. The complete summary contains a number of hot links which have been omitted here. To see them, please refer to the on-line HTML version of the present Newsletter via the URL stated in the newsletter heading. Summary: This paper shows how the Language E [Kakas and Miller, 1997] may be extended to deal with ramifications, and how domain descriptions written in this extended language may be translated into Event Calculus style logic programs. These programs are shown to be sound even when only incomplete information is given about some initial state of affairs. The Language E was developed partly in response to the Language A [Gelfond and Lifschitz, 1993], which was introduced as the first in a family of "action description languages". Action description languages (such as A) inherit an ontology from the Situation Calculus, whereas the Language E inherits its ontology (which includes an independent flow of time) from Kowalski and Sergot's Event Calculus [Kowalski and Sergot, 1986]. E can therefore be regarded as a basic or kernel "event description language". It was developed in the belief that the use of, and comparison between, different ontologies is important in the study of formal reasoning about actions. The semantics of E, like that of A, is model-theoretic, and divorced from computational considerations. The Basic Language E -------------------- The paper begins by reviewing the basic Language E. E's vocabulary includes a set of fluent constants, a set of action constants, and a partially ordered set of time-points. Basic Language E domain descriptions can include three types of propositions: t-propositions ("t" for "time point"), h-propositions ("h" for "happens"), and c-propositions ("c" for "causes"). For example, the following domain description (about taking a photograph) contains 1 t-proposition, 3 h-propositions and 2 c-propositions: NOT Picture #holds-at# 1 Load #happens-at# 2 Look #happens-at# 5 Take #happens-at# 8 Load #initiates# Loaded Take #initiates# Picture #when# {Loaded} The model theoretic semantics of E ensures that (for example) this domain description entails the t-proposition Picture #holds-at# 10 The notions of an "initiation point" and a "termination point" are central to E's semantics. For example, in all models of the above domain, 2 is an initiation point for "Load" and 8 is an initiation point for "Picture". Time can be discrete or continuous, and need not be linear. Indeed, as a special case time may be modelled as a branching structure of sequences of action constants. This allows the "simulation" in E of the Language A, by writing and reasoning about t-propositions such as Picture #holds-at# [Load, Look, Take] Describing Indirect Effects in E -------------------------------- The remainder of the paper discusses an extension of E to include a forth type of statement called an r-proposition ("r" for "ramification"). R-propositions express permanent constraints or relationships between fluents. In formalisms which allow for such statements, the effects of actions may sometimes be propagated via groups of these constraints. This gives rise to the "ramification problem", i.e. the problem of adequately and succinctly describing these propagations of effects whilst retaining a solution to the frame problem. R-propositions are statements of the form L #whenever# {L1, ..., Ln} The intended meaning of this statement is "at every time-point that {L1, ..., Ln}, L holds, and hence every action occurrence that brings about {L1, ..., Ln} also brings about L". Hence the semantics of E is extended so that from a static point of view r-propositions behave like classical constraints, but they are unidirectional in terms of the way they propagate temporal change initiated by action occurrences. This is achieved in the main by appropriately extending the definitions of an initiation and a termination point. These definitions are now recursive, or in terms of least fixed points. R-propositions thus provide a simple, succinct method of expressing domain constraints, and the corresponding semantics behaves in a satisfactory way for a range of examples found in the literature. The use of r-propositions is illustrated in the paper with two examples. The second of these is Thielscher's electric circuit example [Thielscher, 1997]. This example is of interest because it presents difficulties for what Thielscher describes as "categorisation-based" approaches to ramification. In the (Language E version of the) example, the permanent configuration and dynamic behaviour of an electric circuit is described by r- and c-propositions such as Light #whenever# {Switch1, Switch2} Relay #whenever# {Switch1, Switch2} -Switch2 #whenever# {Relay} CloseSwitch1 #initiates# Switch1 OpenSwitch1 #terminates# Switch1 CloseSwitch2 #initiates# Switch2 #when# {-Relay} If "Switch2" already holds (i.e. switch number 2 is connected) and a "CloseSwitch1" action occurs, say at time-point T1, the extended semantics of E ensures that (in all models) the effect of this event is propagated through the first of the r-propositions above, so that "Light" becomes true. This is because the least fixed point definition of an initiation point ensures that T1 is an initiation-point for "Switch1", and hence (by the recursive definition) an initiation point for "Light" by the first r-proposition above. Logic Program Translations -------------------------- The paper gives a translation method from E domain descriptions into logic programs, and gives a proof of the correctness of the translation (as regards derivation of t-propositions) for a wide class of domains. As in [Kakas and Miller, 1997], over-zealous application of logic programming's closed world assumption is avoided by representing negated fluents inside a meta-level "HoldsAt" predicate. For example, "Relay #holds-at# 2" is translated as "HoldsAt(Pos(Relay),2)" and "-Relay #holds-at# 2" is translated as "HoldsAt(Neg(Relay),2)". C-propositions such as CloseSwitch2 #initiates# Switch2 #when# {¬Relay} are translated into two clauses: Initiates(CloseSwitch2,Switch2,t) <- HoldsAt(Neg(Relay),t). PossiblyInitiates(CloseSwitch2,Switch2,t) <- not HoldsAt(Pos(Relay),t). The first of these clauses gets used to compute changes in the truth value of "Switch2" and other fluents via occurrences of "CloseSwitch2". The second gets used in the computation of persistence of truth values. (Similar techniques are used in a number of other logic program translations of action formalisms.) A soundness property is proved for the logic program translations of a general class of domain descriptions, which may include r-propositions. It is stated in terms of SLDNF-derivability: if there is a finite SLDNF derivation of "HoldsAt(Pos(F),T)" (respectively "HoldsAt(Neg(F),T)") from the program, then "F #holds-at# T" (respectively "-F #holds-at# T") is entailed from the original domain description. For the examples given in the paper, these logic programs are more-or-less directly executable in Prolog. The relevant Prolog listings are available at http://www.dcs.qmw.ac.uk/~rsm/abstract15.html ********* DEBATES ********* --- NRAC PANEL ON THEORY EVALUATION --- +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Pat Hayes: Contribution to the Panel Debate on Theory Evaluation. First, let me urge caution about getting too tied up in the Kuhnian vocabulary which Leora has introduced us to, for several reasons. First, Kuhn was talking about rather larger changes in scientific view than our entire field can realistically aspire to: things like the Newtonian revolution in physics. Second, Kuhn's story is easily distorted by being too quickly summarised, as Kuhn himself complained on several occasions; and third, because Kuhn himself later rejected it as overly simple and potentially misleading. The last thing we need is broad, historical discussion by amateur historians using an over-simplified theoretical vocabulary which is already out of date. So, to turn to more practical matters: Leora writes: > >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"? Well surely we need to first focus on what problems we are *expecting* it to solve. Suppose someone in this field were to announce that they had the whole thing finished, all the problems solved, etc.. What tests would be ask them to pass before we believed them? What do we expect these nonmonotonic logics to be able to DO, exactly? Its not enough to just say, 'to reason properly'. We need some characterisation of what that proper reasoning is, or at least some examples of where it can be found. For 25 years we have been appealing to a vague sense of intuitive reasonableness, but this is a very weak basis to test theories on. Even linguists, whose empirical methods are treated with ridicule by experimental psychologists, have some statistical data to back up their 'seems-grammatical-to-native-speaker' criteria, but we don't have any hard data about 'common sense' at all, and the intuitions we appeal to often confuse linguistic, psychological and pragmatic issues. One worry I have is that it seems to be impossible to test a logic or formalism as such, since the intuitiveness or otherwise of any example depends as much on the way the intuition is encoded in that logic as on the logic itself. Logics seem to require a kind of two-stage evaluation. Knowledge-hackers try to formalise an intuition using logic A and find it hard to match formal inference against intuition no matter how ingenious they are with their ontologies and axioms; so they turn to logic B, which enables them to hack the examples to fit intuition rather better. But the intuitive test is always of the axioms/ontologies, not of the logics themselves: there is always the possibility that a more ingenious hacker could have gotten things right with logic A, if she had only thought of the right ontological framework. For example, it has become almost accepted as revealed truth in this field that common sense reasoning isnt compatible with monotonic logic, because of examples such as if you are told that an automobile exists then you infer that its in working order, but if you later hear its out of gas you change your mind. (Or if you hear its only a toy bear, or a penguin, etc.) All of these examples assume that the new knowledge is simply conjoined onto the previous knowledge: you know some stuff, new stuff arrives, and you just chuck it into the set of mental clauses and go on running the mental inference engine. But maybe the updating process is more complicated than that. Maybe when you hear that the car tank is empty, you don't just add some new information, but also *remove* some previous assumptions; and maybe this is not part of the reasoning process but of the linguistic comprehension process. If so, then the representation may, perhaps, be able to use monotonic logic perfectly happily. Maybe not; but my point is only that the argument that it must be nonmonotonic makes assumptions about other mental processes - specifically, those involving the integration of new information - which have not been examined critically. >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 ;-)) I'll take on that onerous task. At the risk of treading on almnost everyone's toes, let me propose the situation calculus; or more properly the idea behind it, of describing change in terms of functions on world-states."Bad theory" isnt really right: it was a really neat theory for a while, and better than anything going, and its still useful. But it has some pretty dreadful properties; and yet not only has it lasted a long time, but its almost considered to be inviolable by many people in the field. And even its critics - for example, Wolfgang Bibel's recent IJCAI survey gives an alternative approach based on limited-resource logics - seem to me to miss the essential things that are wrong with it. This deserves a much longer treatment, but here are a few of the things that are wrong with sitcalc. First, its based on an overly simplistic view of the way things happen in the everyday world, one obviously inspired by reasoning about what happens inside computers. The everyday world just doesnt consist of static states and functions between them: its not organised like a series of snapshots. Sitcalc belongs with SHAKEY, in a world where only the robot can move and nothing else is happening. Second, sitcalc only works properly if we are careful only to mention processes which can be acted upon; that is, it confuses change with action. (Consider how to describe the growth of a plant in sitcalc. It seems easy enough: something like this might be a beginning: (Alive(p, s) & Height(p,s)=h & Watered(p,s)) => (Alive(p, grow(s)) & Height(p, grow(s))>h ) . But in the sitcalc this would mean that there was a *action* called 'grow'. All gardeners would find this action very useful, no doubt.) Third, it confuses action with inference. The way that actions are described in the sitcalc involves asserting conditions on the past and inferring conclusions about the future: axioms have the general form ...(s) => ...(action(s)). But common-sense reasoning often involves reasoning from the present to the past (as when we infer an explanation of something we see) or more generally, can move around in time quite freely, or may have nothing particularly to do with time or action. We are able not just to say that if the trigger is pulled then the target will be dead, but also, given the corpse, that someone must have pulled the trigger. In the sitcalc this would require giving necessary and sufficient conditions for every action description, and Reiter's recent attempt to rejuvenate it does. (This conception of intuitive thought as being a progressive inferential progress in a past-to-future direction has been responsible for many other blind alleys, such as much of the work on principles for 'maintaining' truth as long as possible.) Most intuitive reasoning done by humans lies entirely outside the purview of the situation calculus. Yet so firm has been the grip of the sitcalc ontology on people's thinking that examples which do not immediately fit into it are routinely ignored, while entire libraries are devoted to overcoming artificial problems, such as the frame problem and the YSP, which only arise in the sitcalc framework. Which brings us to the fourth thing wrong with sitcalc: it has many fatal, or at any rate very intractable, technical problems. Why is it that the only people who feel at all bothered by the frame/ramification/qualification problems are philosophers (who mostly dont even understand what they are) and people working in this rather isolated part of KR? Why hasnt the FP become a central difficulty in, say, natural language work, or qualitative physics, or planning (as used in industrial applications)? Because those fields typically dont use this clumsy ontology, that's why. These problems are all artifacts of the sitcalc; they are all concerned with how to keep track of what is true in what 'state' . .... > > 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/... Yes, but 'theory' is crucially ambiguous here. One of the biggest failures of the KR community generally is that it is virtually impossible to actually publish a knowledge representation itself! One can talk about formalisms and semantics and equivalences etc. etc. (the stuff in Erik's list), but this is all part of the *metatheory* of knowledge representation. But when it comes to actually getting any representing done, we hardly hear about that at all. Examples of actual formalizing are usually given as counterexamples to some conjectured technique rather than as things to be studied and compared in their own right. There's nothing wrong with metatheory, provided there is something there for it to be the metatheory of. Right now, the chief problem with this field is that we've run out of subjectmatter. McCarthy set out in a pioneering direction, but instead of continuing his movement, we've set camp and are arguing interminably about what kind of compass to use. Let's get some actual knowledge represented, and only then study how it works and fit our theories to the things we find. For example, here's an issue which might have some meat on it. Erik mentions Allen's time-interval algebra. Now, timepoints and intervals are a pretty simple structure, mathematically speaking, but nevertheless Allen's algebra has its problems. In particular, its not really compatible with the usual view of intervals as sets of points on a line (for details see http://www.coginst.uwf.edu/~phayes/TimeCatalog1.ps http://www.coginst.uwf.edu/~phayes/TimeCatalog2.ps ) . I used to be convinced, all the same, that having intervals as a basic ontological category was fundamentally important, and spent a lot of time finding ways to show that certain interval theories were reducible to others and that points were definable in terms of intervals, etc.. But when I try to actually *use* these concepts to write axioms about clocks, timedurations, calendars and dates, I find that in fact the concept of interval is almost useless. One can think of an interval as just a fancy way to talk about a pair of points; and when one does so, the entire Allen apparatus just dissolves away into a simple theory of total linear order, all the axioms become simpler (for example, instead of writing 'duration (between(p,q))' one simply writes 'duration(p,q)'; there is no need to refer to the interval defined by the endpoints) and everything becomes clearer and more intuitive (for example, many quite natural relations on intervals become awkward disjunctions in the Allen framework, such as {before, meet, overlap, start, equal}, which is p1=