NRAC Panel on Ontologies for Actions and Change |
This on-line session is a continuation of a panel discussion at the NRAC, chaired by Erik Sandewall. We begin with the written notes of the panelists, and continue with the comments by the participants which can have the same style as in conference panel discussion: comments between the panelists, questions to the panelists from the "floor" (that is, all of you who see this page). Then we'll see where the discussion takes us.
The present page will contain the full text of the contributions, as often as possible, and will be updated as the discussion proceeds. Exception: if a discussion contribution is quite heavy with formulas, then possibly it will only be posted in postscript format, and a link to it will be given here.
The headlines fields contain the date of the Newsletter issue where the contribution was sent out, the name of the author, and the title (if any) that was used for the contribution. Headlines with reddish background color is used for position statements.
The previous ECSTER discussion on "Approaches to Actions and Change" addressed similar topics but a while ago. The four position statements in that discussion may also be of interest here.
The monthly News Journals postscript version contains the debate contributions that were received during the month in question.
| Erik Sandewall | Panel on Ontologies for Actions and Change: Issues and Questions. |
The following is my idea of the topic for the panel:
By an "ontology" for actions and change, I mean a set of assumptions about the character of the world that one is reasoning about. For example, the choice of discrete vs continuous time, the choice to allow or not to allow for causation relations between events, and the choice to allow or not to allow for nondeterminism, are examples of such assumptions which together form an ontology.
It may be useful to distinguish between ontological and epistemological assumptions, where the latter are assumptions about what we know about the world. "All the actions/events are explicitly known" is an example of such an epistemological assumption.
Ontologies may be expressed formally or informally. I propose that the panel should focus on formally expressed ontologies.
One consequence of the definition is that the "frame assumption" or assumption of persistence must be built into the ontology. The situation calculus then does not represent an ontology, since commonsense scenario descriptions in sitcalc need to be complemented with additional axioms, minimization of models, or other similar devices.
The main workshop invitation mentions two families of ontologies, namely those represented by action languages (cal-A and successors) and by the features and fluents framework (that is, trajectory semantics and the approach of using underlying semantics). Ray has pointed out to me that GOLOG also represents an ontology that differs from the first two in important respects.
If you agree with me about this background, at least in its main parts, I propose that you might address the following topics (but not exhaustively!) in your introductory statements at the panel:
1) What ontologies = sets of ontological assumptions are in use at present?
2) How are they expressed formally?
3) What results have been obtained within and between those ontologies? What types of results are likely to be obtained in the near future?
| Ray Reiter | The Situation Calculus Ontology. |
I like Erik's proposal for lots of reasons, but mostly because he wants to keep the discussion technical. No vague claims, and amen to that.
Here's what I want to say:
1. Erik's notion of an ontology seems odd to me, mainly because it requires "that the "frame assumption" or assumption of persistence must be built into the ontology". I would have thought that the frame assumption is epistemological or, as the philosophers like to say, "metaphysical". My own understanding of "ontology" is that it is determined by the {\em language} one uses in formulating one's theories. In any case, I think that Erik {\em is} making an important foundational point, namely, that there are two rather different ways to address the frame problem, one more fundamental than the other:
a. Solve it axiomatically by including in one's domain axioms suitable sentences capturing the frame assumption. Whether or not these axioms are parsimonious, or how one arrives at them, is largely irrelevant. The problem is seen simply as writing down an intuitively correct collection of axioms. This is the "classical" approach in AI. It seems to be what McCarthy and Hayes had in mind in their original formulation of the problem. In other words, this is the axiom-hacking approach. I admit to being guilty of this sin in almost all my past work on actions.
b. The second approach -- which I believe Erik is advocating -- is much more principled and fundamental. It requires that one's ontological assumptions (in Erik's use of the term) be formalized {\em semantically}, i.e. as a class of structures in the logician's sense of that word. Of course, this must be a class of structures for some logical {\em language}. So one's ontological assumptions (in my sense of the term) have first to be expressed in a choice of language, but that having been done, one can then define the class of structures that capture one's intuitions about persistence. Alas, a lot more remains to be done after this. Next, you have to figure out what {\em sentences} of the language characterize the above class of structures, and finally, prove a representation theorem stating that the models of these sentences are all and only the structures in the class. I take it that much of Erik's work is of this kind, as is also the work on the A-families of languages of Gelfond and Lifschitz. Circumscriptive approaches seem to lie somewhat between the axiom-hacking and semantic methodologies.
I have no quarrel with the second approach. I think that methodologically, it's the right way to go. However, most of my work, and that of my colleagues at Toronto, is motivated by quite different considerations, namely, given a (perhaps not completely general, perhaps not methodologically solid) solution to the frame problem, what can we do with it? We have been very busy answering this question during the past few years, and this has led to the GOLOG family of programming languages, as well as various extensions of the sitcalc ontology and of our solution to the frame problem to accommodate this extended ontology.
Which brings me to:
2. The extended ontology of the sitcalc for which the basic solution to the FP is sufficient.
I think that Erik is right in focusing on ontologies in this panel, so let me say a little bit about the sitcalc ontology, how it differs from other approaches to actions, and why these differences matter.
3. The central ontological ingredient of the sitcalc is the situation. Even at this late stage in AI, many people still don't understand what a situation is, so here's the secret: A situation is a finite sequence of actions. Period. It's not a state, it's not a snapshot, it's a history. Moreover, situations are first class objects in the sitcalc -- you can quantify over them.
These features have lots of consequences:
(a) Planning is done deductively, not abductively as in linear time logics like the event calculus or the features and fluents approach.
(b) Because they are just action sequences, plans are situations; they are terms in the language and can therefore be inspected by suitable predicates and reasoned about. Our experience has been that this is an essential feature of the sitcalc. See Fangzhen Lin's paper at this IJCAI for an elaboration and application of this idea.
(c) The GOLOG family of languages depends crucially on the fact that histories are first class objects in the sitcalc. The result of executing a GOLOG program is a situation representing its execution trace.
(d) The space of situations is the set of all finite sequences and therefore it is a tree rooted at [], the empty sequence. This means that the sitcalc provides branching futures. In addition, the sitcalc ontology includes a predicate for subsequence. This, together with the ability to quantify over situations means that one can express almost all the modalities that temporal logics provide like in (some, all) futures, past, next, etc.
(e) Since it supports branching futures, the sitcalc is well suited to hypothetical and counterfactual reasoning.
(f) Because situations are terms, they can function as surrogates for the possible worlds much beloved of modal logicians. This means, as Bob Moore showed years ago, and as Hector Levesque has elaborated, we can axiomatize accessibility relations on situations, and embed logics of knowledge directly into the sitcalc. As John Mccarthy likes to put it: Modalities si, modal logic no! Using this, Levesque has formulated an elegant treatment of sensing actions, knowledge and a solution to the frame problem for knowledge within the sitcalc.
4. Relationship of the sitcalc to other ontologies. (I'm flying a bit by the seat of my pants here. Corrections welcome.)
Sitcal A-languages Linear temporal approaches
(e.g. event calculus, F&F)
---------------------------------------------------------------------
actions are terms same? same
histories are
first class state-based no histories
citizens no histories
branching futures branching linear
first order propositional first order
logic
supports sensing
actions and knowledge possible, but
without explicit not yet done. not likely
modalities
5. Finally, I'd like to say a few words about relationships to another
approach to dynamical systems, namely classical discrete event control theory.
The central component of DECT is an automaton, whose transitions are defined
by actions, and whose states are what we normally think of as world states,
i.e. tuples of fluent truth values. The work on A-languages comes very
close to this view semantically and one can view this work as the logicization
of DECT. There are lots of advantages to this logicization, not least, that
sentences in a language provide a compact representation for the exponentially
large state spaces that control theorists have to deal with. Also, sentences
allow for incomplete information about the initial state, a serious and
difficult problem for control theory. While this connection to DECT is pretty
direct for the sitcalc and A-languages, it's not so straightforward for the
linear temporal logics. I think the sitcalc has lots of advantages for
establishing these connections:
(a) It's first order and therefore generalizes the essentially propositional
automata of DECT. (DECT can be interpreted as a version of the monadic
sitcalc.)
(b) The family of GOLOG languages can be used to write controllers.
(c) Because it's all in logic, one can prove properties of these controllers
(safety, fairness, etc).
(d) With its expanded ontology for continuous actions and time, the sitcalc
is suitable for modeling and controlling so-called "hybrid" systems, a hot
topic these days in the control theory world.
| Vladimir Lifschitz | Action Languages from A to C: A Statement for the Panel on Ontologies. |
The contribution by Lifschitz is fairly dense with formulae. For your own convenience, please switch to the postscript page which is obtained by clicking the title above.
| 23.10 | Murray Shanahan |
I'm sympathetic with most of Pat Hayes's criticisms of the situation calculus, but not when he writes ...
| 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? |
The frame problem seems to arise in any logic-based formalism in which the effects of actions are described. It certainly arises in the event calculus, which has a very different ontology to the situation calculus. It also arises in the ontologies of Yoav Shoham's and Erik Sandewall's books, which is why those book took the shape they have. The YSP, in some guise, arises in all these formalisms too. And (at the risk of reviving an old debate Pat had with Drew McDermott), the frame problem seems to arise in Pat Hayes's histories formalism too.
| 23.10 | Ray Reiter |
When Pat Hayes speaks, one is well advised to listen, because he usually gets it right. But when the godfather of the sitcalc, and a parent of the frame problem says such surprising things about his own creations, I can't restrain myself.
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.
False. Situations are simply finite sequences of actions. These need not be just the actions under the robot's control; they can, and in interesting cases do, involve exogenous actions (Fido ate the sandwich that the robot is asked to fetch.) Writing controllers to deal correctly with such exogenous event occurrences has long been the meat-and-potatoes of control theory, and this is certainly possible also in the sitcalc. Indeed, the sitcalc can easily be seen to be a generalization of discrete event control theory.
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.
I can't figure out what Pat means by this, even with the help of his grow(s) example. I suspect that he wants to distinguish between processes, that evolve in time, and actions, but I'm not sure. So I'll simply say here that there is a sitcalc story for continuous processes, and leave it at that.
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.
So what's the point here? With a suitable solution to the frame problem, one can, in the sitcalc, reason in all directions.
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 ...
Absolutely false! I can't speak to how the natural language community treats actions, but qualitative physics and planning have no difficulty with the FP because, without exception, they adopt the STRIPS sleeping dogs strategy. Which is to say, THEY ASSUME THEY HAVE COMPLETE INFORMATION ABOUT WORLD STATES. If you don't believe that, here's a challenge. Give a theory of planning for incompletely specified worlds, in any formalism you like, that does not require a solution to the FP.
Now sleeping dogs are great, when applicable. But robots must necessarily function in incompletely specified worlds; otherwise, why do they need sensors? In the absence of a good story of how to reason about the effects of actions in open worlds without solving the FP, I'll put my money on the Lifschitzs, Sandewalls, Shanahans and Thielschers of our community.
| 27.10 | Mikhail Soutchanski |
"Bad theory" [the sit. calc.] 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.
There are reasons why the situation calculus (SC) has been successful for so long time. Here are some of them.
1. The SC is simple and easy to understand. It is formulated in the classical many-sorted first-order (or second-order, if necessary) logic with the standard semantics. I want to stress here the difference between the classical logic approach and other logics (with non-standard syntax and semantics) proposed for formalization of reasoning about actions. If at a later time, somebody will propose a new (non-standard) logic for reasoning, say, about shapes, and somebody else will propose yet another (non-standard) logic, e.g., for reasoning about materials (or substances), it would be a difficult task to combine all those proposals in a one logical framework.
2. The situation calculus is a foundation for general purpose high-level programming languages. Reminder: This idea is proposed in the 1969 paper "Some philosophical problems from the standpoint of artificial intelligence" (J.McCarthy & P.Hayes). Note that it is an easy exercise to formalize the Turing machine in the SC.
Moreover, thanks to the explicit situational argument, as long as the SC-based program proceeds, the information about the sequence of actions performed so far, can be used to direct the further execution of a program. For example, if (in the real world) during the execution of a primitive action robot `fails', analyzing the list of primitive actions performed so far, the robot can (sometimes) infer conclusions regarding what caused the failure. As we know from the control theory and the game theory, the history of the interaction of an agent with an environment (that may include other agents with possibly contradictory goals) may provide useful guidelines when the agent decides how to recover from a `failure'. From the other hand, the event calculus and other "narrative time-line languages" do not have any term that would keep record of what part of the narrative had been done before the moment when a failure happened.
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.
A. We should distinguish between situations (which are uniquely associated with sequences of actions) and snapshots (which are equivalence classes over situations). B. The SC of 1997 can handle very sophisticated views of the way things happen in the everyday world.
Most intuitive reasoning done by humans lies entirely outside the purview of the situation calculus.
Note that your objection can be easily rephrased as: "Most intuitive reasoning done by humans lies entirely outside the purview of the formal logic".
I'm not sure whether we must have the same concerns that the cognitive science has. Most of the people do not think in terms of C, LISP, PROLOG, but all these languages are still useful for writing programs that will exhibit an intended behavior. Similarly, the SC is useful as the basis for the high-level programming language.
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,
Please, formulate those examples in technical terms.
FROM: Murray Shanahan
> here are a few of the things that are wrong with sitcalc.
I'm sympathetic with most of Pat Hayes's criticisms of the situation
calculus
FROM: Erik Sandewall
With respect to your second point,
concerning the situation calculus as an example of a theory with
staying power but considerable weaknesses, exactly those observations
have led to the work on reasoning about actions using first-order logic
with explicit metric time [...]
We can certainly discuss whether the shortcomings in the basic sitcalc
can be fixed by add-ons, or whether a metric-time approach is more fruitful,
and this discussion is likely to go on for a while (see also Ray Reiter's
comments, next contribution). However, since we agree about the shortcomings
of sitcalc, it might also be interesting to discuss why *it* has such
remarkable inertia.
Please provide formal arguments why the SC of 1997 cannot be used for high-level programming of robots and for providing operational semantics of programming languages and explain what frameworks will work better.
-------------------
Reply to Rob Miller's message "Comparing Action Formalisms: A Preliminary Position Statement". It is available at http://vir.liu.se/brs/news/96deb/03/debit.html
A good example of a (nevertheless interesting) problem which is the product of a particular ontology (rather than being fundamental) is the difficulty of distinguishing between observations and causal rules in the Situation Calculus [...] Neither the problem nor the solution translate to other (ontologically different) approaches. We need to be careful to distinguish between this type of issue and more fundamental problems such as dealing with ramifications or continuous change.
In the 1997 version of the SC, there are _no_ causal rules. Toronto's version of the SC has instead of them successor state axioms specifying the evolution of a dynamical system (for example, composed from robot, other agents and the nature) and precondition axioms which specify when primitive actions are possible. Let's understand "observation" as a SitCalc formula that contains occurrences of only one (current) situational term. There are no problems with any observation as long as observations and robot's beliefs about the world (deduced from an initial description by successor-state axioms) coincide with each other. If they do not, it means only that an exogenous (with respect to robot's mind) action changed value of one or several fluents. However, there is a straightforward and technically sound approach to incorporate "unexpected" observations using successor state axioms. Note that event calculus will have exactly the same problem if the robot believes regarding a fluent _f_ that it was _InitialisedTrue(f)_ and was not _Clipped(0,f,t)_ at the moment _t_, but nevertheless, a sensor reports that this fluent does not hold at _t_ (due to some external reasons).
-------------------------------------------------
Reply to Vladimir Lifschitz message "Approaches to Reasoning About Actions: A Position Statement".
1. Explicit time vs. the situation calculus. The following situation calculus
formula seems to have no counterpart in languages with explicit time:
But there is a little problem here. What is the meaning of (1) if the effects
of a1 and a2 on f are nondeterministic? I have a few coins in my pockets;
let a1 stand for getting a coin from my left pocket, let a2 stand for getting
a coin from my right pocket, and let f stand for the value of the coin that
I have in my hand. We can interpret (1) as a counterfactual, but this seems
less interesting than assertions involving some kind of quantification over
the outcomes of a1 and a2, for instance:
(i) there exist an outcome of a1 and an outcome of a2 such that (1) holds,
(ii) for any outcome of a1 and any outcome of a2, (1) holds,
(iii) for any outcome of a1 there exists an outcome of a2 such that (1) holds.
The situation calculus has no mechanism for expressing these distinctions.
value(f,result(a1,s)) = value(f,result(a2,s)). (1)
It says that the value of f at the next instant of time does not depend on
which of the actions a1, a2 is going to be executed. For instance, if I now
send an e-mail message to Erik Sandewall, the total number of messages
sent by me since this morning will be the same as if I send a message to
Ray Reiter instead. This is an argument in favor of the situation calculus.
1). Consider nondeterministic actions as concurrent executions of two actions: one action is performed by an agent (like a1 and a2 in the example above), another action is performed by the nature. These concurrent executions seem nondeterministic for the agent (or any other external observer) only because there is no information what particular action is selected by the nature. Thus, we distinguish two separate activities: Vladimir extracts an object from a pocket and nature makes this object into the coin of the particular value. Let n1 be nature's action of turning a coin from the left pocket into the coin of the particular value, n2 - the corresponding action for the right pocket. Consider now new sort "c" for sets of actions performed concurrently. Let constants C1 and C2 represent activities in corresponding pockets, then the formula
IN(a1,C1) & IN(n1,C1)
says that a1 - a physical action performed by Vladimir is included in "C1" and
n1 - action chosen by nature is also included in "C1".
Similarly,
IN(a2,C2) & IN(n2,C2)
represents a concurrent activity (a2 and n2) in the right pocket.
Assuming some additional axioms like unique name axioms and like
\forall a. IN(a,C1) <=> a=a1 or a=n1 , \forall a'. IN(a',C2) <=> a'=a2 or a'=n2
the formula (1) can be rewritten as:
IN(a1,C1) & IN(n1,C1) & IN(a2,C2) & IN(n2,C2) & [value(f,res(C1,s))= value(f,res(C2,s))]
I will denote the resulting formula by "Formula(a1,n1,a2,n2,s)". The assertions involving some kind of quantification over the outcomes are represented in the following way:
(i) \exists n1, n2. Formula(a1,n1,a2,n2,s) (ii) \forall n1, n2. Formula(a1,n1,a2,n2,s) (iii) \forall n1, exists n2. Formula(a1,n1,a2,n2,s)
2. (by R.Reiter)
Instead of the function _result(a,s)_ consider the relation _do(a,s,s')_: do(a,s,s') means that s' is one of the situations you can reach from s by performing action a. It's just like Golog's do(\delta,s,s'). Then we can represent Vladimir's three distinctions by:
(i) (\exists s',s''). do(a1,s,s') & do(a2,s,s'') & value(f,s')=value(f,s''). (ii) (\forall s',s''). do(a1,s,s') & do(a2,s,s'') -> value(f,s')=value(f,s''). (iii) (\forall s'). do(a1,s,s') -> (\exists s''). do(a2,s,s'') & value(f,s')=value(f,s'').
| 28.10 | Murray Shanahan |
Stop! Enough! This discussion has quickly degenerated into childish bickering. There is little value in a debate of the form:
A: You can't do X in B's formalism.
B: Yes you can. But you can't do Y in A's formalism.
A: Yes you can. But you can't do Z in B's formalism.
and so on. . . No doubt, suitably modified, you can do whatever you need to in any of the formalisms. (Why does Ray write "sensing actions in the event calculus: not likely"? Rob Miller has work in progress on this theme. History should tell us that such claims are dangerous. A few years ago we were saying "continuous change in the situation calculus: not likely".)
Why this possessivenss about formalisms? I'm proud to say I've written papers using both situation calculus and event calculus, and my book covers both extensively. It would be so much more valuable if we sought relations between different formalisms and tried to understand the space of possible action formalisms.
The most pertinent comment I've read in this debate so far was Pat Hayes's when he wrote: 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., . . . 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. It's as if we were violinists in an orchestra who, instead of making music, spent all their time arguing over who has the nicest violin. Let's make some music. Let's use our formalisms to build theories, and then let's see how those theories fare when used in anger. Then perhaps we'll actually make some progress in common sense reasoning.
| 28.10 | Erik Sandewall |
Murray,
I agree with you that possessiveness about formalisms is a bad thing, but let's not give up this discussion so hastily. After all, it is important to understand what is the range of expressiveness of our current major formalisms. What we need, I think, is
Wrt structure of the topic, why don't we build on Ray's table - contributions addressing specific combinations of "representation aspect" and "ontology" (possibly correlated with a formalism) are invited. I'll try to set up a web-page structure where every such combination obtains its own thread of messages.
One reason why this discussion will be useful is to clear up some misunderstandings. For example, Michail, when you write From the other hand, the event calculus and other "narrative time-line languages" do not have any term that would keep record of what part of the narrative had been done before the moment when a failure happened... you express a misunderstanding bordering on an mistake. Since each interpretation in a narrative time-line approach contains one history of the world along the time-line, it can also contain the actions that are (were) performed in that history, or up to a point in time in that history. Then the history of past events is not expressed as a term, of course, but why would that matter?
In the work on range of applicability for entailment methods, as reported in the "Features and Fluents" book, I started out with a narrative timeline approach simply because it seemed more natural for dealing with events with extended duration and overlapping intervals, and with continuous change. However, it became clear during the work that a simple generalization of the time-domain definition made it possible to include situation calculus as a special case, and that virtually all the formal results about the properties of various nonmonotonic methods carried over without any difficulty. In that sense there is no contradiction between sitcalc and narrative timeline approaches, although I still like to think of the former as a special case of the latter.
On the other hand, I have also noticed that it is apparently much easier to get articles published if they use situation calculus. This may possibly be due to notational chauvinism (a natural consequence of possessiveness) on the side of some reviewers: If one really believes that (e.g.) the situation calculus is the best answer to all problems, then why accept a paper from someone that hasn't seen the truth?
If our research area is going to conserve an older approach to such an extent that essential new results can't make it through the publication channels, then the whole area will suffer. There, in fact, is an additional reason why we may have to sweat out this discussion about the capabilities of different ontologies and formalisms: not in order to bicker, but to increase the acceptance of each other's approaches.
| 30.10 | Pat Hayes |
Before responding to the responses to my comments about the situation calculus, a note on terminology.
The 'situation calculus', 'event calculus', etc., are all just styles of writing axioms in a first-order logic (with suitable modifications to allow circumscription, etc..) The word 'calculus' doesnt point to anything more substantial than a choice of vocabulary and an axiomatic style. (Contrast the useage in 'lambda calculus', for example.) This isn't anything to regret in itself, but it does mean that to talk about something being an 'extension' to a calculus becomes rather fuzzy. There is no end to the relations and axioms one might add to a first-order theory; and if we also allow the axioms of the theory to be altered and the intuitions which motivated them to be replaced by different intuitions, then we can make any set of axioms into any other set of axioms, so all talk of this or that 'calculus' becomes meaningless. Ray Reiter seems to have done this for the situation calculus. Whatever it is, this 'extended ontology' that Ray describes [see ENAI 27.10] bears almost no similarity to the ontology and axiomatic style expounded by McCarthy about 30 years ago (and still used by Ray, along with everyone else, as late as 1991 in his paper in the McCarthy festschrift). It has a different vocabulary, different axioms and is based on different intuitions (which are directly opposed to those motivating the original situation calculus) and has different formal properties. Contrast, for example, Reiter and McCarthy on what a 'situation' is meant to be:
McCarthy (1969): "A situation is the complete state of the universe at an instant of time."
Reiter (1997): "Even at this late stage in AI, many people still don't understand what a situation is, so here's the secret: A situation is a finite sequence of actions. Period. It's not a state, it's not a snapshot, it's a *history*."
Evidently Ray is talking about something different from McCarthy. Nothing wrong with this, of course: I've done it myself from time to time. (Consider my old naive physics 'histories' ontology. World-states are a special case of histories, and there's a systematic translation of situation-vocabulary into history-vocabulary; does that mean that the 'liquids' axiomatisation is written in an "extended" situation calculus?)
Now, it may be said that the field has advanced, and its up to old fogies like me to adapt ourselves to the new terminological consensus. Just as 'frame problem' now means almost everything from Hume's problem of induction to the cost of memory, the meaning of 'situation calculus' has moved with the times. (As Mikhail Soutchanski says, "the SC of 1997" is different from the SC of, say, 1991.) I've made a similar point to Erik, who carelessly used 'ontology' to mean what it meant for about a thousand years, thus risking confusion with the new West-coast sense of 'ontology' (ie. a sorted first-order theory presented in an object-oriented notation, with comments in Managerese.) But, as Erik said, we still need a name for the old sense; and we still need a name for the situation calculus as it was everywhere from 1965 until around 1994 and still is in most of the world outside Toronto. How about 'gofsitcalc'? Whatever we call it, in any case, that's what I was talking about.
More substantive comments to follow.
| 31.10 | Pat Hayes |
As I expected, criticising the sitcalc on this newsletter is rather like farting in church. Much of the spluttering seems to be motivated more by the event than by the content of what I said, however.
Murray wrote:
| I'm sympathetic with most of Pat Hayes's criticisms of the situation calculus, but not when he writes ... |
| 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? |
| The frame problem seems to arise in any logic-based formalism in which the effects of actions are described. It certainly arises in the event calculus, which has a very different ontology to the situation calculus. It also arises in the ontologies of Yoav Shoham's and Erik Sandewall's books, which is why those book took the shape they have. The YSP, in some guise, arises in all these formalisms too. And (at the risk of reviving an old debate Pat had with Drew McDermott), the frame problem seems to arise in Pat Hayes's histories formalism too. |
Well, I'm afraid I disagree. Id be interested to have this explained to me in a little more detail, if anyone can. The histories ontology has its problems, some of them very serious; but the FP isnt among them. Its hard to see how it could be, since the ontology doesnt even refer to states, situations or actions.
One criticism of histories was that some kind of frame-problem-tackling 'continuation principle' was needed to make sure, for example, that the history of a ball's trajectory didnt just stop in the middle of the table somewhere. This was just a misunderstanding. The description of a history includes its boundary conditions, and in the case of a trajectory history the temporal boundaries (assuming no friction) must involve an impact, which in turn requires an impacting surface. So one can infer directly that a trajectory will continue until the ball hits something; no nonmonotonic principles are involved.
Ray wrote:
| When Pat Hayes speaks, one is well advised to listen, because he usually gets it right. But when the godfather of the sitcalc, and a parent of the frame problem says such surprising things about his own creations, I can't restrain myself. |
| 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. |
| False. Situations are simply finite sequences of actions. These need not be just the actions under the robot's control; they can, and in interesting cases do, involve exogenous actions (Fido ate the sandwich that the robot is asked to fetch.) Writing controllers to deal correctly with such exogenous event occurrences has long been the meat-and-potatoes of control theory, and this is certainly possible also in the sitcalc. Indeed, the sitcalc can easily be seen to be a generalization of discrete event control theory. |
Part of why we arent communicating here may be that the term 'sitcalc' has become ambiguous, and Ray helped it get that way. The Reiter-sitcalc is a very different beast than the original sitcalc, both in the way it is supposed to describe the world and in how it sets about doing it: so different, in fact, that it is misleading to call it by the same name. (Alright, I concede that maybe the world has come to use 'sitcalc' to refer to Reiter's calculus, and so I ought to change my own vocabulary to avoid misunderstandings. But now what do we call the old situation calculus? Let me distinguish gof-sitcalc, for the situation calculus before Reiter, from R-sitcalc, just to avoid confusion. )
| 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. |
| I can't figure out what Pat means by this, even with the help of his grow(s) example. I suspect that he wants to distinguish between processes, that evolve in time, and actions, but I'm not sure. So I'll simply say here that there is a sitcalc story for continuous processes, and leave it at that. |
No, that wasnt my point. It was more to do with what Ray calls 'exogenous' actions. Part of what made the gof-sitcalc so attractive was the way it could be used to plan: a proof that a goal situation exists automatically gives you a plan of how to achieve it, encoded in the very name of the situation. You can read it off from the actions named in the term whcih refers to the goal state. This basic idea was used, with variations and elaborations, for many years and felt to be a wonderful positive feature, as Mikhail Soutchanski kindly reminds us. It is the basis of the analogy with program synthesis (the situation becomes the state of the computer) and with finite-state control theory (the state of the controlled system.) Fine. But this works provided that the only state-to-state functions used in the formalism are those which correspond to state-transitions. But other interpretations of the sitcalc - notably that which claims that it can do the work of temporal modalities - lead naturally to the use of functions to simply assert a temporal relation between situations, with no corresponding implication of there being any kind of action or state-transition which can be used to achieve that new state. Suppose, to use a different example, we want to assert that whenever the stock market is high, it will be lower at some time in the future (the Greenspan axiom?). In tense logic this wouild be something like
highdow implies F(lowdow)
demodalised into the sitcalc it becomes (simplifying)
highdow(s) implies (exists t) later(s, t) lowdow(t) )
Now however if we skolemise this we get
highdow(s) implies later(s, greenspan(s)) lowdow(greenspan(s))
where greenspan is the skolem function. The ontology of the situation
calculus provides no principled way to distinguish functions like this,
which simply express an existential temporal relationship, from functions
which are supposed to describe achievable state-transitions corresponding
to actions.
Now of course we can always make this distinction by adding something. For example, we can add "do-able" as a relation between situations, or, better, as a predicate on functions whcih have been reified into objects by using a 'do' function. Yes, and we can also add Godel-Bernays set theory, Peano arithmetic and Tarski's axiomatisation of spatial orderings. So what? We can ADD any other axioms you like. But my point was only that there was (and I think still is) a clash of intuitions which the sitcalc didnt resolve; and the ontology of the sitcalc not only doesnt resolve it, but in fact encourages a confusion between these very different ideas, by assimilating them to a single formal structure. And to repeat, I think that much of the work directed towards solutions to the frame problem - notably, almost everything connected with chronological minimisation - is entirely wrongheaded, and seemed plausible only because of this confusion between action and temporal ordering.
| So what's the point here? With a suitable solution to the frame problem, one can, in the sitcalc, reason in all [temporal] directions. |
Well, maybe Im not fully following this, but I dont see how its done. Heres an example, from my old liquids axioms. Theres a table top which is dry in state s but on which theres a pool of liquid in state t, where t is later than s. Now, how did the liquid get there? In fact there are about five ways it can have done so (depending on what one counts as a 'different' way), and some of them involve intermediate stuff which has to have been removed (such as a leaky container). How does one describe this in the situation calculus? Or another example: Drew McDermott is healthy in state s but dead from a gunshot in state t. How do we infer, in the sitcalc, that somebody shot him?
| ..... 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 ... |
| Absolutely false! I can't speak to how the natural language community treats actions, but qualitative physics and planning have no difficulty with the FP because, without exception, they adopt the STRIPS sleeping dogs strategy. Which is to say, they assume theyhave complete information about world states. |
Sorry, just not true. Most qualitatative physics reasoning doesn't assume complete information, and certainly doesnt use a STRIPS strategy. For example, Feng Zhao's work on qualitative phase-space reasoning works with incomplete data and approximate descriptions. In contrast, I might point out that such assumptions as the unique-names axiom that many circumscriptive reasoners rely on so centrally amount to a completeness assumption in disguise, since they essentially insist that all models are isomorphic to Herbrand models, which reduces reasoning to a kind of symbolic state-simulation.
Mikhail wrote:
| There are reasons why the situation calculus (SC) has been successful for so long time. Here are some of them. |
| 1. The SC is simple and easy to understand. ... |
| 2. The situation calculus is a foundation for general purpose high-level programming languages. Reminder: This idea is proposed in the 1969 paper "Some philosophical problems from the standpoint of artificial intelligence" (J.McCarthy & P.Hayes). Note that it is an easy exercise to formalize the Turing machine in the SC. |
Thanks for the reminder. It is pretty easy to formalize a Turing machine in almost anything, so this doesnt mean much. But in any case, what has this got to do with the topic we are all concerned with? How did Turing machines come to be relevant here?
| Moreover, thanks to the explicit situational argument, as long as the SC-based program proceeds, the information about the sequence of actions performed so far, can be used to direct the further execution of a program. For example, if (in the real world) during the execution of a primitive action robot `fails', analyzing the list of primitive actions performed so far, the robot can (sometimes) infer conclusions regarding what caused the failure. As we know from the control theory and the game theory, the history of the interaction of an agent with an environment (that may include other agents with possibly contradictory goals) may provide useful guidelines when the agent decides how to recover from a `failure'. From the other hand, the event calculus and other "narrative time-line languages" do not have any term that would keep record of what part of the narrative had been done before the moment when a failure happened. |
I think theres a good point lurking here, but its not quite right as stated. Its not the situational argument as such that makes this possible, but the fact that the terms that get bound to it contain explicit sytactic information about the actions performed. But that's also a problem, as Ive already explained. I think the real advantage of the situational argument is that by having explicit terms which denote the outcomes of actions (not the actions themselves), it allows alternatives to be represented as conjunctions rather than as disjunctions. To say that one might do P (with result A) or one might do Q (with result B) in sitcalc style, one asserts a conjunction: A(do P) & B(do Q) . If we have to talk about one single temporal world (be it 'linear' or not), this has to be a disjunction: either (P, then A) happens, or (Q, then B) does. These alternatives get out of hand very fast.
I wrote and Mikhail answered as follows:
| Most intuitive reasoning done by humans lies entirely outside the purview of the situation calculus. |
| Note that your objection can be easily rephrased as: "Most intuitive reasoning done by humans lies entirely outside the purview of the formal logic". |
I have no idea what this response is supposed to mean. Do you identify formal logic with the situation calculus? Or do you mean only that much of intuitive reasoning is outside the scope of our subject? Or what??
Mikhail continued:
| I'm not sure whether we must have the same concerns that the cognitive science has. Most of the people do not think in terms of C, LISP, PROLOG, but all these languages are still useful for writing programs that will exhibit an intended behavior. Similarly, the SC is useful as the basis for the high-level programming language. |
And again, I'm at a loss to understand your point. What is 'the high-level programming language' you refer to here? For the record, I think that unless our subject is part of cognitive science, then it's just empty formula-hacking. See earlier comments in reply to Erik.
| 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, |
| Please, formulate those examples in technical terms. |
I can't formulate them in technical terms. If I could, they would already be formalised. But for a good start, try looking at
http://www.dcs.qmw.ac.uk/~rsm/CS98/CS98Problems.html
Pat Hayes
| 3.11 | Michael Gelfond |
I agree with Ray that it may be a good idea to separate ``ontology'' from ``epistemology''.
For me to specify ``ontology'' means to give a collection of individual objects, functions and relations which comprise our domain. The type of logical connectives used to construct sentences in this language is part of ``logical system'' and does not belong to the ontology. Closed World Assumptions of different sorts,etc belong to ``epistemology''.
We seem to differ slightly on the meaning of the frame problem. To me the frame problem is a special case of a more general problem of finding logical system suitable for representing defaults and their exceptions in a way which will insure a high degree of elaboration tolerance. (Frame axiom is a particularly difficult default since it is related to causality, representation of time, etc)
This is of course only one of several possible views but I think an important one.
I believe that the ontology of situation calculus and action languages are basically the same. Situation IS a sequence of actions, etc. Our causal models (or automata) are graphs representing trees of situations. (One superficial difference is that our actions are undefined in situation where the corresponding preconditions are not satisfied, while in Ray's case they seem to ``return'' the same situation).
The more important difference is that action languages stress the distinction between description languages and query languages and define entailment relation directly without appealing to first-order logic.
To turn these languages into calculi one need to decide what logical system to use to formalize reasoning about causal models defined by the corresponding action theory. My favorite choice here is declarative logic programming with answer set semantics which can be viewed as a variant of default logic.
We have now several logic programming versions of situation calculus proven to be sound and complete w.r.t. entailment in action description languages.
The disadvantage of this approach is that we need to develop more mathematics for dealing with declarative logic programs (default theories) which is a slow process. Even though there has been an important progress in this in the last few years, classical logic is still a better choice in this respect. I believe however that in a long run default logics will allow for more elaboration tolerant and computationally better representations of various types of commonsense knowledge.
This is related also to the comment by Mikhail Soutchanski when he stresses the differences between classical and non-classical logics for knowledge representation. If formalizations of different domains are all done in default logic then we will have no problem to combine all of them together. For instance, if our initial situation is defined in Datalog then it combines very nicely with logic programming version of situation calculus. Even if the languages used for encoding knowledge in different domains are special purpose (like action languages) we will not have any problem combining them together if their entailment relations are formalized in the same language. (e.g. Instead of A we can use its sound and complete formalization in default theories).
I am not claiming BTW that nonmonotonic logics are better than classical one. I do not take it as a truth (revealed or otherwise). Pat (and Ray?) can be right and commonsense reasoning can be compatible with monotonic logic. But I think that it is an open and difficult research question which can be answered but trying various approaches.
One more comment on how action languages are used. Suppose you have some collection of actions and their effects and would like to write a planner which examines, in some reasonable order, possible sequences of actions and checks if your domain description entails that the goal G holds after the sequence of actions is executed. In this case domain description in A-like language together with its entailment relation can be used to precisely specify the problem.
The corresponding logic programming formalization of this entailment together with the domain description forms the main part of the planner. If you decide to use Prolog inference engine you may need to slightly transform the program to avoid floundering, etc. If you do it using results from the theory of logic programming the resulting program will be provenly correct. It seems to be very similar to what people in Toronto do, except we probably concentrate more on correctness of actual program.
There are of course many other uses.
Finally, some corrections to Ray's comment on A-languages. They have histories (actually, it is their basic feature). Language L from this family combines branching and linear time. This is published in
C. Baral, M. Gelfond, A. Provetti, ``Representing Actions: Laws, Observations and Hypotheses'', Journal of Logic Programming, vol. 31, Num. 1,2 and 3, pp. 201-245, 1997
This is a special issue on Logic Programming and Reasoning about actions and I think it contains good papers.
As Vladimir already mentioned there are (fully) first order languages.
| 3.11 | Mickail Soutchanski |
I will follow the distinction between the gof-sitcalc (sitcalc of 1969) and the R-sitcalc (sitcalc of 1997+); this distinction is proposed by Pat Hayes in ENAI 31.10.97
The situation calculus is a foundation for general purpose high-level programming languages. Note that it is an easy exercise to formalize the Turing machine in the SC.
It is pretty easy to formalize a Turing machine in almost anything, so this doesnt mean much. But in any case, what has this got to do with the topic we are all concerned with? How did Turing machines come to be relevant here?
My intention was to turn the attention to computational aspects: the R-sitcalc is a general theory of action that is a foundation for the high-level logic-programming language GOLOG and its descendants (mentioned by Ray Reiter, ENAI 27.10.97). Because a version of GOLOG is used to control a robot in the real world, the R-sitcalc (as a formalism for reasoning about actions) can be judged according to the test suggested by Murray Shanahan (ENAI 23.10.97).
Most intuitive reasoning done by humans lies entirely outside the purview
of the situation calculus.
Note that your objection can be easily rephrased as: "Most intuitive reasoning
done by humans lies entirely outside the purview of the formal logic".
I have no idea what this response is supposed to mean. Do you identify formal logic with the situation calculus? Or do you mean only that much of intuitive reasoning is outside the scope of our subject? Or what??
I do not identify formal logic with the situation calculus. But it is true that I am not sure whether formal logic corresponds precisely to much of our intuitive reasoning. My point was that it is not fair to judge the R-sitcalc only according to the criterion whether it exactly captures *our* intuitions about actions, changes and situations (by the way, nobody ever claimed that the gof-sitcalc or the R-sitcalc expresses the final truth). As long as robots can successfully execute high-level programs based on the R-sitcalc, it is not completely worthless.
I'm not sure whether we must have the same concerns that the cognitive science has. Most of the people do not think in terms of C, LISP, PROLOG, but all these languages are still useful for writing programs that will exhibit an intended behavior. Similarly, the SC is useful as the basis for the high-level programming language.
And again, I'm at a loss to understand your point. What is 'the high-level programming language' you refer to here? For the record, I think that unless our subject is part of cognitive science, then it's just empty formula-hacking. See earlier comments in reply to Erik.
'the high-level programming language'= GOLOG. There are several experiments performed by anthropologists and psychologists with different people in different parts of the world. As far as I understand their results, in some cases, ability to solve naive physics problems or derive conclusions from syllogistic premises depends on cultural background, education and other personal factors. For this reason, psychology (and cognitive science) cannot be the only foundation of our research.
| 6.11 | Rob Miller |
Hector,
I'd like to express agreement with your first point, that KR is about modelling. But I'd like to take issue with a couple of your other points, (3) and (5). In point (3) you said:
|
3. The remaning problem, that we can call the semantic problem,
involves things like the frame problem, causality, etc.
To a large extent, I think the most basic of these problems have also been solved: Basically, thanks to Michael and Vladimir, Erik, Ray, and others we know that a rule like: if A, then B where A is a formula that refers to time i or situation, and B is a literal that refers to the next time point of situation, is just a constraint on the possible transitions from the the states at i or s, and the following states. Or put in another way, temporal rules are nothing else but a convenient way for specifying a dynamic system (or transition function) ...... |
Your point (5) was:
| 5. It's not difficult to change the basic solutions to accommodate additional features (e.g., non-deterministic transition functions, unlikely initial conditions, concurrent actions, etc.) in a principled way. |
Well again, it seems to me that if this is true, it's simply because researchers tend to pick "additional features" to work on which will conveniently fit into the state transition view of the world, as opposed to picking from the rather large collection of issues that won't.
| 6.11 | Ernie Davis |
Ray Reiter writes, in newsletter ENAI 23.10
| qualitative physics and planning have no difficulty with the FP because, without exception, they adopt the STRIPS sleeping dogs strategy. Which is to say, they assume they have complete information about world states. |
I don't think that this is quite right in the case of qualitative physics. My KR '92 article "Axiomatizing Qualitative Physics" presents a theory which, being in first-order logic, is perfectly able to characterize inferences from partial information, but does not require any special frame axioms for the continuous parameters. The reason is that the behavior of a continuous parameter is governed by governed by a qualitative differential equation of the form, ``The derivative of P is the sum of the influences on P''. P remains absolutely constant if the sum of the influences is zero. P retains the same qualitative value to some next modes of the system if it is consistent that some other parameter should change its value before P does. In any case, the behavior of P in staying the same is governed by the same law that governs its behavior in changing. No special law is needed to cover the cases where P stays the same. (For discrete parameters, I did need a frame axiom.)
More generally, for those, like Pat and me, whose primary interest is physical reasoning, a temporal ontology whose central category is "a finite sequence of actions'' seems awkward at best. Physical reasoning is chiefly concerned with continuous, asynchronous, external change, and it is much easier to deal with this by making the continuous time-line primary and adding actions on top of that, rather than vice versa.
-- Ernie Davis
| 10.11 | Hector Geffner |
Rob Miller says:
| My problem with this is that, in general, dynamical systems in the everyday world can't be realistically modelled as state transition systems, because they involve things like continuous change, actions or events with duration, partially overlapping events, interuptable events, etc. ... |
if loaded and shoot then not alive
is that the only state trajectories s0, s1, s2, ..., that are possible are the
ones in which `alive' is false at si+1 when loaded and shoot are true at si.
You can formulate the idea in many ways (suitable circumscriptive policy, Erik's version of chronological minimization, predicate completion, ...), but it is the same idea: rules specify possible state transitions, observations prune possible state trajectories.
Now, Rob is right; dynamic systems come in different varieties; e.g.,
Rules like the one above (with first order extensions, etc) are good for specifying systems of Type 1 only. Yet it's not difficult to see how systems of Type 2 could be specified as well.
Actually there are other type of mathematical models for the type of problems that Rob has in mind as the "Semi-Markov Decision Processes" (probabilistic continuous processes - like queuing systems - that are controlled at discrete time intervals).
My point is that we are not inventing new mathematical models of dynamic systems. What we are inventing are suitable structured languages for specifying and in certain cases controlling those systems. That's what STRIPS is about.
In my view, the KR/control enterprise is about developing richer versions of STRIPS suitable for specifying and controlling not only systems of Type 1, but also Markov Decision Processes, Partially Observable MDPs, Semi-MDP's, etc etc.
How we will measure success?
When we can model and control some dynamic systems that cannot even be modeled using non KR methods.
- Hector Geffner
| 11.11 | Rob Miller |
Hector Geffner (ENAI 10.11) wrote:
Now, Rob is right; dynamic systems come in different
varieties; e.g.,
Actually there are other type of mathematical models for the type of problems that Rob has in mind as the "Semi-Markov Decision Processes" (probabilistic continuous processes - like queuing systems - that are controlled at discrete time intervals). |
Rob
| 13.11 | Erik Sandewall |
Rob,
You wrote:
| ... But I think that an important wider problem that we have to tackle within "reasoning about action and change" is how to synthesise or combine very different approaches to modelling dynamic systems within a single "commonsense" framework. For example, I'd like to see more research along the lines of Erik Sandewall's 1989 work on combining reasoning about actions with modelling using the differential calculus. It's true that there has been a small amount of subsequent work on this theme since then ... But not much compared with, say, work on extending state-transition based approaches to deal with ramifications in evermore sophisticated ways. Why is this so? Why don't we put much effort into addressing challenges such as Kuipers' - on combining the Situation Calculus with Q.R. (see Kuipers' book, p. 201)? ... |
Unfortunately, the answer to this question is a brutal one: publication problems. At least, that's the conclusion I have drawn from the experience of our group. The following is what happened after our start on hybrid systems in 1988-89. A key new result in the 1989 papers (KR and IJCAI) was that minimization or restriction of change generalized nicely to minimization or restriction of discontinuities. (The particular use of chronological minimization as a restrictor on the set of models was of secondary importance, I think; one can do it in other ways). The weak spot that we identified at the same time, and which was clearly spelled out in the papers, was that some additional model selection criterion was necessary, since we still got some unintended models. There were two options: modifying the logic itself, or introducing concepts from other disciplines.
The first approach was pursued by two of our graduate students at the time, Tommy Persson and Lennart Staflin. Their first paper in this direction was accepted at ECAI 1990, but then they ran into the wall. One more of their papers is still available as a departmental report; it was called "Cause as an Operation on a Logic with Real-valued Fluents and Continuous Time". The article is available at
http://www.ida.liu.se/publications/cgi-bin/tr-fetch.pl?r-90-45+abstrand the abstract goes as follows:
| We propose a new method for characterizing the discontinuities in processes that are mostly continuous. We introduce a causal operator that is used to specify when the value of a fluent has a cause. A discontinuity in a fluent is allowed if the fluent's value immediately after the discontinuity has a cause. The causal operator is incorporated in a temporal logic with continuous time and real-valued fluents. The resulting logic is a nonmonotonic logic suitable for representing physical models of real world situations. We define a selection function which given a set of models returns a subset of the models. This selection function defines a nonmonotonic entailment operator. The intuitive idea behind the selection function is that is should select all models where all discontinuities are ``specified'' as allowed. |
The other approach, which we also investigated, was to bring in aspects of real physics. We started cooperation with people who had that competence, and in particular with our colleagues in control theory. This led to work on the use of bond graphs, which is a classical energy-based method for modelling physical systems, and uniformly applicable to systems from different domains (mechanical, electrical, hydraulic, etc.). Members of our group (Stroemberg, Soederman) developed a generalization of bond graphs to take account of abrupt changes (that is, combining continuous and discontinuous) by introducing a "switch" concept in a clean way.
Yet another approach was the use of hybrid transition systems, which are a generalization of the transition systems that come from the theory of real-time systems. Additional members of our group (Nadjm-Tehrani and Stroemberg) used hybrid transition systems for modelling actions, analyzing safety conditions ("is it possible that if I drive this way, I may crash into the car in front of me?"), etc.
For both bond graphs and transition systems, the idea was to import methods from other areas into AI and KR. In both cases, our people were able to publish successfully in the neighboring discipline, but not in AI, or at least most of the AI submissions were rejected. Reviewers tended to say either that this was not relevant for AI, or that although possibly relevant, more would have to be done in order to reach the presumed high quality standards that we require in our field.
It goes without saying that after a few experiences of this kind, these (then) Ph.D. students turned away from AI and continued their work in the areas where they were better received. They were also put off by what they considered as idiotic comments by reviewers, for example, to the effect that the proposed modelling system was not capable of accounting for the sudden occurrence of asteroids on the scene.
When these things happen, it is our discipline that stands to lose. There were great opportunities at that time for bringing in fresh concepts into KR, and for integrating them with what we are otherwise doing. On the other hand, time does not stand still while we fumble, and if our area does not deal in a timely fashion with new problems, then there are others who will.
It is also important to note that this resistance to new ideas is not reciprocal. This year's HART conference (Hybrid And Real Time systems) had no trouble accepting my paper on relating high-level and low-level descriptions of actions, which was an extension of my invited paper at last year's ECAI.
This panel discussion has already touched on the remarkable persistence of situation calculus in our field. The field's unwillingness to accept and use outside knowledge for dealing with continuous change is equally remarkable.
Erik
| 17.11 | Patrick Doherty |
After following the discussion between Rob Miller and Tom Costello, I'd like to point out another approach that my group has been using in our research in the area of action and change. It is based on a distinction between surface and base languages made by Sandewall in Features and Fluents. The family of logics we use is called TAL (Temporal Action Logics) and the newer versions are generalizations of an entailment policy called PMON, first described in F&F.
Clearly, high-level narrative description languages are not only useful, but will obviously be necessary when dealing with scenarios more complex than those we see in the literature today. On the other hand, general purpose logics such as classical logic have great advantage when doing comparative analyses, debugging and incremental extension of formalisms.
In our approach, we combine the advantages of each. Our narrative descriptions are represented in terms of a high-level language which allows for straightforward description of observations, action instances and types, casual rules, and explicit temporal constraints. The high-level language may simply be viewed as a set of macros where each has a modular translation into formulas in the base language, 1st-order classical logic. The language is always extensible in an incremental manner. So far, we've extended the language for causal rules and concurrency simply by adding new macros and translation functions.
The logic TAL 1.0, and the approach using surface and base languages is implemented and accessible as an applet or a Marimba Castanet Channel. The visualization tool allows for the construction of narratives in the high-level language, their automatic translation into a 2nd-order theory, and that theories automatic translation into a first-order theory. One also has the possibility of viewing models as time-lines and a query mechanism is provided. The system and related references are accessible via the following URL:
http://anton.ida.liu.se/vital/vital.html
The majority of scenarios discussed in the literature are
represented in the tool and can be queried. The purpose of the
tool is not only for our individual research, but also to open up the
logics for public evaluation and comparative analyses. The use
of both a high-level macro language and a translation into
classical logic should meet the needs of groups taking the A language
approach or those more comfortable with good old classical logic.
The danger we find with the trend in using A language approaches is that it often appears to be the case that one is taking a relatively simple surface language and translating into what turns out to be something along the lines of classical logic, but in a rather indirect and complex manner. It is difficult to see how the guarantee of semantic continuity in the base language or incrementality in the surface language will be met as scenarios or narratives become increasingly more complex. On the other hand, if provided with well-understood and modular translations into classical logic, it is much easier to evaluate progress and simplify comparisons. One sign that there is a problem is that the A-type languages are generally only compared relative to other A-type languages. Of course, translations of formalisms to classical logic and ensuing comparisons are not all that simple when comparing widely differing ontologies, but we have a rich infrastructure of well-established technical tools to help us along.
I'm certainly all for the flourishing of alternative approaches to modeling action and change, but I really think it is time to clean up our methodology, do more comparative analyses across paradigms regarding strengths, weaknesses, assessments of use, and to apply the formalisms to some "real" problems in the area of DES, process control, etc. I'd like to see a library of tools and implementations which allow each of the different groups to actually test the representational capabilities of the perspective approaches and a number of realistic modeling challenges similar to those one finds in the "Hybrid Systems" area. This appears to be a common and useful aspect of methodology in other areas. Why is this lacking in our area and what can we do about it?
I hope the tool we have developed and placed on-line might serve as a starting point for discussion or for developing healthier methodological tools and coherence in the area. Perhaps Murray Shannahan's and Ray Reiter's interests in controlling robots with logics could also lead to another set of testbed's for comparative analysis of formalisms.
| 19.11 | Vladimir Lifschitz |
I would like to respond to some of the comments on action languages published in ENAI 13.11 and 17.11.
Tom Costello writes to Tony Kakas and Rob Miller regarding their new action language:
|
The reason I ask for truth
conditions for your propositions is that I cannot understand what the
intuitive consequences of a set of propositions should be, unless I
understand what the propositions say.
As you say, action languages are supposed to be "understandable and intuitive". Languages cannot be understood without semantics. |
Patrick Doherty writes:
|
The danger we find with the trend in using A language approaches is
that it often appears to be the case that one is taking a relatively
simple surface language and translating into what turns out to be
something along the lines of classical logic, but in a rather
indirect and complex manner.
On the other hand, if provided with well-understood and modular translations into classical logic, it is much easier to evaluate progress and simplify comparisons. |
Vladimir Lifschitz
| 21.11 | Erik Sandewall |
Vladimir,
In ENAI 19.11, in the context of the discussion with Tom Costello and Patrick Doherty, you wrote:
| It is impossible, unfortunately, to translate an action language into classical logic in a modular way, because classical logic is monotonic, and action languages are not. The best we can achieve is a modular translation from an action language into a nonmonotonic formalism, such as circumscription, whose semantics can be characterized by a nonmodular translation into classical logic. This is indeed indirect and complex. But we have to pay this price for the convenience of reasoning about actions in classical logic. |
Through the Features and Fluents approach, we have demonstrated a much more direct and less complex way of doing these things. However, "convenience of reasoning" is not the only issue, and it's not what Patrick addressed; what he actually wrote and what you quoted in the preceding lines was:
| On the other hand, if provided with well-understood and modular translations into classical logic, it is much easier to evaluate progress and simplify comparisons. |
In particular, translating scenario descriptions into first-order logic helps evaluation and comparisons in two ways. First, for transparency, i.e. for allowing us to understand in a precise manner what the scenario descriptions say, which is also what Tom Costello's persistent questions are concerned about. After it, there is the issue of actually carrying out the reasoning about actions, which quite possibly can be done (or implemented) more conveniently if one uses first-order theorem provers as inference engines. Anyway, let's stick to the question of how we can evaluate progress and simplify comparisons for the work that gets done and published.
With respect to transparency, it seems to me that action languages such as cal-A and cal-E add to the obscurity rather than dissolving it. In the Features and Fluents approach, we achieve the same results in a much less elaborate fashion: we have one single language, namely a straightforward multi-sorted first-order theory; we have a set of syntactic abbreviations or "macros" in order to sugar the notation for legibility; and we have two different semantics. There is the classical semantics of the Tarskian type which is almost straight from the textbook, with routine modifications to take care of the multitude of types and for assuring a closed-world assumption with respect to objects. There is also the underlying semantics which specifies what one really means - corresponding to Tom Costello's question to Tony Kakas and Rob Miller, where he wrote:
|
The reason I ask for truth conditions for your propositions is that I
cannot understand what the intuitive consequences of a set of propositions
should be, unless I understand what the propositions say.
As you say, action languages are supposed to be "understandable and intuitive". Languages cannot be understood without semantics. |
The underlying semantics does exactly this. To put it another way, here is a recipe for converting an action-language approach to our approach. You take the action-language setup with its two languages, each with its own syntax and semantics. First, you remove the separate syntax of the action language. You retain the use of two distinct semantics, so one and the same scenario description can be mapped into a set of models by two different methods: the set of classical models, and the set of intended models. Also, you make sure that the two semantics use the same space of possible interpretations; it's just that the set of intended models is (usually) a subset of the set of classical models. The you have captured the essentials of our approach.
The definition of the underlying semantics is indeed not truth-functional in a conventional way; it can rather be described as a kind of simulation of the world in question. However, truth conditions are still used within that 'simulation', namely for defining the truth conditions for each individual observation statement. The resulting semantics is concise, intuitively convincing, and formally precise at the same time.
This approach has several important advantages:
Consider ramification, for example. In the cal-A tradition, new language variants were introduced for ramification. In our approach, all you have to do is to remove the syntactic restriction that is imposed in the footnote on page 176 in the "Features and Fluents" book, select PMON among the twelve entailment methods that are defined and analysed there, and you have a method for ramification that in fact is as powerful or more powerful than most of what has been published in the last couple of years. (To be precise, the two formulations of PMON that are stated on page 243 are no longer equivalent after the generalization, and you have to use the second one. That's all).
A possible objection against defining a quite expressive language from the start is that you may not be able to prove your results for such a broad language. That is one reason why we focus on "range of applicability" results rather than "validation" results. Instead of defining a narrow language and proving that a property holds throughout the language, we identify what is the part of our broad language where the property holds. This helps avoiding the proliferation of languages, but it also helps obtaining results that are as general as possible, since the result is not artificially constrained by the choice of language. This is a real difference between the approaches, since the published general results about cal-A type languages are consistently validation results (unless I have missed something).
Then there is the other reason for reducing an action language to a first-order theory, namely for implementation purposes. There, again, Doherty et al have developed efficient computational mechanisms as a part of our approach; their implementation has been available for on-line use over the net since May of this year. In their case it's only an implementation issue; the purpose of their work is not to assign a meaning to the language since that has already been taken care of. (Patrick writes more about this in his contribution to the discussion, below).
The bottom line is that it is perfectly possible to achieve legibility (initial motivation of action languages), transparency (Tom Costello's request), and effective implementation by the approach used in Features and Fluents, and with much less administrative overhead than in the work based on action languages. My question is, therefore: what are the real benefits of all the definitional work in the action-language papers; what are the results that the rest of us can use?
| 21.11 | Tom Costello |
Vladimir writes,
| It seems to me that the semantics of an action language cannot be described by specifying truth conditions for its propositions. The problem is the same as with nonmonotonic languages in general. Take, for instance, the closed-world database {P(1),P(2)}. The negation of P(3) is a consequence of this database, but this fact cannot be justified on the basis of truth conditions for P(1) and P(2). |
I do not ask that Action language designer's define their semantics in terms of truth conditions. I ask that the designers give truth conditions to each of their assertions. The difference can be seen in your example if you take P to mean there is a flight and 1 to means Glasgow,London and 2 to mean London,Moscow. The P(1) is true, if there is a flight from Glasgow to London. What is puzzling me about Kakas and Miller's language is what their propositions mean, in exactly this sense.
In particular, what does
A causes F if Gor
A initiates F if Gmean. That is, given a model M of a domain description, when is this proposition satisfied in M. I have pointed out that problems arise under certain definitions of model.
The most difficult issue that I am aware of, is that it is unclear whether
A causes F if Gmeans that
in every actual state S where G is true, then F is true in R(A,s),or the similar, but different
in every possible state S where G is true, then F is true in R(A,s).Similarly, does
Always F,Gor Kakas and Miller's
F Whenever -Gmean that every actual state satisfies F,G, or every possible state.
Tom Costello
| 21.11 | Patrick Doherty |
Vladimir's reply to my paragraph about A Languages introduces two interesting and subtle issues:
To clarify my "current" working view of the role action languages should play, I simply quote the original intuition Vladimir himself at one time had about their role in his paper, "Two Components of an Action Language":
| Originally, action languages were meant to play an auxiliary role. The primary goal was to represent properties of actions in less specialized formalisms, such as first-order logic and its nonmonotonic extensions, and the idea was to present methods for doing that as translations from action languages. |
My group currently uses this approach and it is also one of the cornerstones of the Features and Fluents methodology. Formally and conceptually, we translate from an action scenario description language into a first-order theory with a circumscription axiom. I consider 2nd-order theories to be part of classical logic. From an analysis of the circumscriptive theory, we can identify different means of deriving efficient computational mechanisms for reasoning or "querying" a class of action scenarios.
The advantages we have derived from this approach are the following:
As regards modularity:
In our current family of logics (TAL), we find that the circumscription policies used are really quite simple, basically nothing more than predicate completion. This given, we can either reduce the 2nd-order theory associated with an action scenario using a reduction algorithm in a "nonmodular" manner, or generate a "modular" translation directly from the action scenario description which includes one additional formula for each predicate completion. So, I'd disagree with Vladimir's view on the coupling between modular/nonmodular -- monotonic/nonmonotonic in his reply. Although one can interpret the use of a reduction algorithm as nonmodular, one can also interpret the use of local syntactic translation as modular. Again, it all comes down to what is meant by "modular" and we may have slight disagreements on pinning down a definition.
As regards the monotonicity/nonmonotonicity issue:
One fascinating insight which the translation into a circumscribed theory provides us with, is that the automated reduction of the circumscription axiom to a logically equivalent 1st-order formula, essentially generates what could be interpreted as "explanation closure axioms". This has been noted and used by other researchers in other contexts such as Vladimir, Ray Reiter, and Fangzen Lin, although in these cases, one works directly with syntactic translations on an existing 1st-order theory rather than direct translation from a circumscription formula.
So this could turn out to be a non-issue in the sense that meta-assumptions of a nonmonotonic character are sometimes left outside a formalism, but guide the way we write axioms or use syntactic translations, or the assumptions are part of the actual formal theory as in the case of using circumscription axioms or default inference rules. There should be a straightforward means of providing formal translation between the two "stances". The discusion would than revolve around what criteria, such as elaboration tolerence or efficient theorem-proving methods, contribute to a particular choice of "stance".
One other related point worth discussion is that if one takes a good look at the diverse approaches being proposed and actually applied in some sense of the word "applied", analysis at the classical logic level shows that
This is why I like approaches which relate in a direct manner to classical logic. We can say useful things like:
These techniques have informal correlates in the original work by McCarthy and have been refined into formal techniques used by a number of researchers in this area. The problem is that this type of analysis is rare. A contributing factor to the lack of generic analyses could very well be the diversity of specialized action languages and the often complex and direct translations to procedural or computationally oriented frameworks.
| 25.11 | Pat Hayes |
Vladimir Lifschitz writes:
| It seems to me that the semantics of an action language cannot be described by specifying truth conditions for its propositions. The problem is the same as with nonmonotonic languages in general. Take, for instance, the closed-world database {P(1),P(2)}. The negation of P(3) is a consequence of this database, but this fact cannot be justified on the basis of truth conditions for P(1) and P(2). |
But it can be justified on the basis of the truth conditions for P(3), which is just as much a proposition of the language as the first two. Nonmonotonic logics are not classically truthfunctional, but they do have truth conditions. The simple language sketched here has the truth condition: P(n) is true iff P(n) occurs in the database.
Pat Hayes
| 27.11 | Vladimir Lifschitz |
Erik, In ENAI 21.11 you discuss advantages of the F&F approach, in comparison with action languages, and you write:
| No need to define new languages all the time, and of comparing newly published languages with previously published ones. We stay with the same language, which is sufficiently expressive right from the start to last for a while ... |
1. Ramification constraints vs. qualification constraints. A fact about fluents sometimes allows us to conclude that an action has an indirect effect, and sometimes that it has an implicit precondition. (It functions sometimes as a "ramification constraint" and sometimes as a "qualification constraint.") Example: the objects that I have in my pocket are in the same place where I am. After I come home with a comb in my pocket, the comb will be in my home also; this is an indirect effect. Since knives are not allowed in airplanes, I can't board an airplane with a knife in my pocket; this is an implicit precondition.
2. Asymmetry of ternary constraints. Consider a spring-loaded suitcase with two locks. Its state can be described by three fluents: lock 1 is open; lock2 is open; the suitcase is closed. The constraint is that these fluents cannot hold simultaneously. Consider a state in which one of the locks is open and the suitcase is closed. When I open the other lock, this causes the suitcase to open. (This action does not cause the first lock to close, which, logically speaking, is another possibility.)
3. Interaction between concurrently executed acions. Consider lifting the opposite ends of a table upon which various objects have been placed. If one end of the table has been raised, the objects on the table will fall off. But if both ends are lifted simultaneously, the objects on the table will remain fixed.
These phenomena could not be described in the original action language A and in some of its successors. New, more expressive languages had to be designed. I am wondering what the status of examples 1-3 in the F&F framework is. Would you be able to formalize them in your original language, which you described as sufficiently expressive right from the start? My understanding of the possibilities of F&F is not sufficient to answer this without your help. But about the situation calculus I know that new syntactic features had to be added to it to address these problems, such as the predicate Caused (similar to Holds, but not quite the same), and an addition operation on actions (to represent concurrent execution).
Patrick, in ENAI 21.11 you write:
|
To clarify my "current" working view of the role action languages
should play, I simply quote the original intuition Vladimir himself
at one time had about their role in his paper, "Two Components of an
Action Language":
"Originally, action languages were meant to play an auxiliary role. The primary goal was to represent properties of actions in less specialized formalisms, such as first-order logic and its nonmonotonic extensions, and the idea was to present methods for doing that as translations from action languages." My group currently uses this approach and it is also one of the cornerstones of the Features and Fluents methodology. |
Indeed, your TAL is essentially an action language. There are minor differences in style between TAL and the languages that I've been working on. What you write as
[t1,t2] move(p,l) ~> [t1] !(place_of(p) == l) -> [t1,t2] place_of(p) := lI would maybe represent this as
move(p,l) CAUSES place_of(p)=l, IMPOSSIBLE move(p,l) IF place_of(p)=l.This is slightly more concise because t1, t2 are suppressed. I am wondering whether you would lose any important expressivity if you changed your macros in a similar way.
Tom, In ENAI 21.11 you write:
The most difficult issue that I am aware of, is that it is unclear whether
A causes F if Gmeans that in every actual state S where G is true, then F is true in R(A,s),or the similar, but different
|
Pat, In ENAI 25.11 you write:
| Vladimir Lifschitz writes: |
| It seems to me that the semantics of an action language cannot be described by specifying truth conditions for its propositions. The problem is the same as with nonmonotonic languages in general. Take, for instance, the closed-world database {P(1),P(2)}. The negation of P(3) is a consequence of this database, but this fact cannot be justified on the basis of truth conditions for P(1) and P(2). |
| But it can be justified on the basis of the truth conditions for P(3), which is just as much a proposition of the language as the first two. |
Similarly, a domain description in the language A determines the transition diagram in which a value proposition is to be evaluated when we want to determine whether it is a consequence of the description.
Further you write:
| Nonmonotonic logics are not classically truthfunctional, but they do have truth conditions. |
Vladimir
| 9.12 | Erik Sandewall |
Vladimir,
You wrote (ENAI 27.11)
|
I'd like to understand this better. The need to define new action
languages arises when we want to describe aspects of reasoning about
action that have not been understood in the past. Here are some
examples.
... These phenomena could not be described in the original action language A and in some of its successors. New, more expressive languages had to be designed. I am wondering what the status of examples 1-3 in the F&F framework is. Would you be able to formalize them in your original language, which you described as sufficiently expressive right from the start? |
Yes. By the original language I then mean a first-order language having three predicates:
Holds(t,f,v) feature f has value v at time t
Occurs(s,t,e) event e takes place over the interval [s,t]
Occlude(t,f) the fluent f is occluded at time t
The fuller picture is as follows. Recall that we use
plus, for analysing the properties of those,
The interesting thing is that quite a number of phenomena, including the ones that occur in your examples, can be accomodated within the same base language FL. Sometimes it is useful to extend the surface language SD with more macros, in order to obtain convenient expressivity, but the proof methods survive the extension since they are defined for FL.
To see how it works in more detail, a recent reference for your first two examples (involving concurrency and ramification, respectively) is an article by Lars Karlsson and Joakim Gustafsson, available at
http://www.ep.liu.se/ea/cis/1997/014/As for qualification and the qualification/ramification tradeoff, this is the topic of a paper by Patrick Doherty that is just about ready. In fact, within our lab it is mostly Patrick and his colleagues and students that work on these issues and extend the limits with respect to expressivity as well as proof methods. In the course of their work, the approach is now being renamed from PMON to TAL (for Temporal Action Logics). There will be more details about this in Patrick's forthcoming answer to your questions to him.
The three relations in FL have been with us all the time since 1988-89, although their usage has been extended along the way. Also, in some of the publications the Occurs relation has been viewed as a 'macro'. That simplifies things and is sufficient for some purposes, but not always.
Whereas FL has been remarkably able to accomodate additional phenomena (including not only the ones in your questions, but also things having to do with mixed continuous/ discrete behaviors, imperfect sensors, etc), it has certainly been necessary to revise items 6 through 9. In fact, it is part of the basic idea that the formal ontology and underlying semantics should represent those phenomena as clearly as possible. This is the topic that I focus on in my own work. Sometimes the entailment method is developed and assessed first, and "implemented" afterwards as a proof method; sometimes it is the other way around. The approach to concurrency in the recent PMON-TAL work, for example, has not yet been analyzed wrt range of applicability and on the basis of an underlying semantics. There is some earlier work (by Choong-ho Yi) which does provide a reasonable candidate for an underlying semantics for concurrent actions, but so far it has only been used for analysing the case of independent concurrency.
With respect to ramification, my KR-96 paper describes a formal ontology for causal-chain ramification, where one microevent (= elementary change) causes another one, which causes another one, all within one and the same main event or action. A number of entailment methods are assessed on the basis of that ontology. However, there are also other kinds of ramification that do not fit into that framework, for example, those based on physical connections between objects. It seems to me that the notion of ramification is too crude to allow a single ontological analysis.
With respect to qualification, no underlying semantics has been proposed. My belief is that even more than for ramification, a serious ontological analysis of qualification needs to identify a number of different cases which have entirely different character, and which deserve different logical treatment. However, this does not of course prevent one from proceeding with the work on representation and proof methods for qualification.
Erik
| 23.1 | Hector Geffner |
Some brief comments about Pat's last comments.
|
In any AI the same (causality) principle makes perfect sense
when actions are exogenous; such actions, I think,
we can agree, should never affect your beliefs about the past ..
But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that somone else has been present there recently. |
It's important to distinguish observations from actions. In dynamic systems the first are usually expressed as "initial conditions" e.g., x(0) = 5 , loaded(0) = false , etc; while the latter are the inputs to the system.
An observation at time
On the other hand, what I'm saying (and of course, many other people)
is that exogenous actions at time
You may say that if you drop the cup to the floor and it breaks, then you should change your beliefs about the past, infering things like that the cup was made of glass, etc.
Yet, it's not the action that is having an influence on your beliefs about the past; it is the observation that it breaks (you may say that "breaks" is not an observation but an action; yet in that case, it's definitely not an exogenous action as it depends on variables in the model)
If you remove that observation, and simply drop the cup, you will learn nothing about the past.
BTW, the causality principle is not about physics; I believe it's about models of physics. Whether such (dynamic) models are specified by means of mathematical equations or rules in a logical language, I don't think it's relevant (for compliance with the principle).
A final point before this gets to long. Pat says
| .... such simulations are often unreliable precisely because we don't have sufficiently complete knowledge; and when this is so, we cannot cleave to the strict causality principle, but are obliged to use techniques such as nonmonotonic reasoning which allow us to recover gracefully from observed facts which contradict our predictions, which would otherwise enmesh us in contradictory beliefs. Nonmonotonicity is a good example of the need to revise ones beliefs about the past in the light of unexpected outcomes in the present, in fact, which gets us back to the YSP: |
Actually, I think none of the received models of actions in AI (say A, Toronto Sit Calc, Basic Features and Fluents, etc) does that.
I believe they are all monotonic in the set of observations.
In other words, if they predict
They are non-monotonic however in the set of actions.
That is, you can affect the prediction "
It's basically like in the standard dynamic models either deterministic or probabilistic.
So I think our models are not so different from more standard models of action. Of course, they are very different in the description languages; but that's the type of difference that you have between Strips, and transition-functions. The first is much more convenient, but it's basically a "front-end". It's not a new model of action; it's a new language for describing the most basic one (deterministic models). Of course, I'm completely convinced that this is very important, and I think it's precisely there where KR/action fits in.
- Hector Geffner
| 23.1 | Judea Pearl |
Correcting a statement by Pat Hayes.
Hector Geffner said (about the principle of causality) :
| In any AI the same principle makes perfect sense when actions are *exogenous*; such actions, I think, we can agree, should never affect your beliefs about the past (indeed, as long as you cannot predict exogenous actions from your past beliefs, you shouldn't change your past beliefs when such actions occur). |
To which Pat Hayes replied:
| But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that someone else has been present there recently. We constantly make inferences about the past on the basis of present knowledge, even in such technical areas as military planning. |
Correction
The principle of causality is in fact stronger than Pat's interpretation of it. Not only the past, but also our beliefs about the past, do not change as a result of actions, unless the acting agent is part of our model. Moreover, if the agent is part of our model, then actions cease to be interesting and problematic as they are today (at least in some AI approaches to actions).
To explain: The action of putting a cup of coffee on the table does not change the state of the coffee or the table before the action, and does not change our beliefs about the state of the coffee before the action. But, Pat will argue: seeing the coffee on the table allows us to infer that "someone else has been present there recently." True, but only if we are concerned about the actor's whereabout and if the limitations or motivations of the action-producing agents are IN the model (e.g., that someone must be in a house to do it, and will probably do it if he/she is thirsty, etc.) Once this action are perceived as produced by a modeled agent, it is no different than any other events, say the agent tripping or being hit by a car, because then it is liscensed to trigger the usual inferences of predictions and abduction that observations trigger.
Hector said all this by using the term "exogenous". Indeed, the problematic aspects of actions surface when we try to treat actions as exogenous, namely produced by external agents NOT modeled in our system. Only by considering an action exogenous can we talk about the world "changing" (anyone ever saw a world truly changing?.)
Put another way, the peculiarities of actions vis a vis observations stem from the boundaries we put around our models and our audacity to call our models "worlds".
B. Russel (1910) noted (my words, not his) that if we model the entire universe, there is no meaning to causality or to actions, because the manipulator and the manipulated loose their distinction.
One problematic aspect of dealing with external actions is that ordinary abduction, from the immediate consequences of those actions, must be suppressed. For example, we do not want to abduce that it rained when we decide to pour water on the driveway and get it wet. This suppression is easily enforced in systems such as logic programming (Lifschitz et al) in which inference has preferred directionality, and where abduction is not a built-in feature (e.g., contraposition is not sanctioned) but must be crafted as a special feature. However, the suppression is problematic in standard logic and probability where inference is symmetric, and no differentiation is made between abduction and prediction. Such differentiation is one role played by causally ordered relations.
Well, enough said for one tiny correction.
| 23.1 | David Poole |
Pat Hayes wrote:
| But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that someone else has been present there recently. We constantly make inferences about the past on the basis of present knowledge, even in such technical areas as military planning. |
No. No. No. Observations can change one's beliefs about the past. Doing an action doesn't change beliefs about the past. Observing the hot coffee made you update your beliefs about the past. The action of coming into the room didn't change your beliefs about the past (unless you include the observation that the action succeeded).
To make everything clearer it is crucial to distinguish sensing (making observations) from motor control (doing/attempting actions). The only role of sensing is to update your beliefs. Sensing in this sense doesn't change the world (of course, acting in order that you can sense can, and often does, change the world). Acting (i.e., sending a command to your motor controllers) doesn't change your beliefs about your present or your past, but only about the future. Acting can change the world.
If we fail to distinguish these, confusion will reign supreme. Surely in order to make some progress we could agree on such a distinction, then get back to the argument with at least one confusion cleared up!
David Poole
P.S. I am wondering why such confusion between observing and acting may have arisen in the first place.
I conjecture is that it has to do with the preconditions of actions. For example, the action has the precondition that there is nothing on x. Then by carrying out the action, can you infer that there was nothing on x? But this doesn't make sense. What happens if I had attempted to pickup x when there was something on it? What if I didn't know whether there was something on x when I tried to pick it up? It seems that the only sensible interpretation of the precondition is that if there was nothing on x and I carried out pickup(x), then the expected thing would happen. If something was on x and I carried out pickup(x) then who knows what may happen. The role of the precondition is that it is only sensible to attempt to carry out the action when the preconditions hold.
An alternative explanation if the confusion may be that the action is an observation of the effect of my motor control on a particular state of the world. If I carry out a particular motor control when there is nothing on x, then a action arises. When I do the same motor control when there is something on x then some other action arises. Then I do not choose the action, but I only choose the motor control (consider the case when I don't know whether there is something on x or not, and I try to pick it up). Is this what people mean by an action? Surely then it is imperative to distinguish that motor control (for a better description) that I get to choose, from the observation of the effect of that motor control.
| 23.1 | Erik Sandewall |
Do all current approaches behave monotonically with respect to observations? On 23.1, Hector Geffner wrote:
|
Actually, I think none of the received models of actions in AI
(say A, Toronto Sit Calc, Basic Features and Fluents, etc) does that.
I believe they are all monotonic in the set of observations. In other words, if they predict F at time i, nothing that they observe is going to affect that prediction. At most they can make the theories inconsistent. |
With respect to features and fluents, this is true for those cases where proven assessments exist at present, but not in general. The full catalogue of ontological characteristics includes such phenomena as "surprises" and "normality", both of which are nonmonotonic with respect to observations. A simple example is for the stolen car scenario: the car is left in the parking lot, three nights pass, it is for sure that the car is not removed during the day, the default is for it to stay where it is at night as well. The default conclusion is that it's still there after the three nights. Then add the observation that it's gone at the end of the period. Without admitting surprises, this scenario is inconsistent, as Hector writes. If surprises are allowed for, then you may conclude that it was removed during one of those three nights.
If you add in addition the fact that the parking lot was supervised the first and the third night, making removal impossible, then one is entitled to infer that it was stolen during the second night. Thus, the initial default conclusion regarding the presence of the car in the parking lot during the day after the second night goes from "yes" via "don't know" to "no" as these successive observations are added.
From the point of view of diagnostic reasoning these are familiar problems, but I can't think of any work in mainstream actions and change that has addressed nonmonotonicity with respect to observations in a serious way. Except, without knowing the details, I would imagine that the people who do probabilistic or possibilistic approaches might have something to say about this. Judea, or the folks in Toulouse, any input?
Do all current approaches comply with the causality principle? On 21.1, Hector Geffner wrote:
| Most recent models of action comply with the causality principle. In some it comes for free (e.g., language A ) due to the semantic structures used (transition functions); in others (Reiter, Sandewall, etc), I'm sure it can be proved. |
Yes, with respect to the features and fluents approach, it also "comes for free". The underlying semantics that's used there is essentially a simulation of the world, using non-deterministic transition from state to state or from state to state sequence (the latter in order to account for actions with extended duration). In either case the simulation proceeds forward in time, so it complies with the causality principle. The same applies for the extensions of the approach to deal with concurrency, ramification, and continuous change.
Erik Sandewall
| 23.1 | Hector Geffner |
Some brief comments about Pat's last comments.
|
In any AI the same (causality) principle makes perfect sense
when actions are exogenous; such actions, I think,
we can agree, should never affect your beliefs about the past ..
But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that somone else has been present there recently. |
It's important to distinguish observations from actions. In dynamic systems the first are usually expressed as "initial conditions" e.g., x(0) = 5 , loaded(0) = false , etc; while the latter are the inputs to the system.
An observation at time
On the other hand, what I'm saying (and of course, many other people)
is that exogenous actions at time
You may say that if you drop the cup to the floor and it breaks, then you should change your beliefs about the past, infering things like that the cup was made of glass, etc.
Yet, it's not the action that is having an influence on your beliefs about the past; it is the observation that it breaks (you may say that "breaks" is not an observation but an action; yet in that case, it's definitely not an exogenous action as it depends on variables in the model)
If you remove that observation, and simply drop the cup, you will learn nothing about the past.
BTW, the causality principle is not about physics; I believe it's about models of physics. Whether such (dynamic) models are specified by means of mathematical equations or rules in a logical language, I don't think it's relevant (for compliance with the principle).
A final point before this gets to long. Pat says
| .... such simulations are often unreliable precisely because we don't have sufficiently complete knowledge; and when this is so, we cannot cleave to the strict causality principle, but are obliged to use techniques such as nonmonotonic reasoning which allow us to recover gracefully from observed facts which contradict our predictions, which would otherwise enmesh us in contradictory beliefs. Nonmonotonicity is a good example of the need to revise ones beliefs about the past in the light of unexpected outcomes in the present, in fact, which gets us back to the YSP: |
Actually, I think none of the received models of actions in AI (say A, Toronto Sit Calc, Basic Features and Fluents, etc) does that.
I believe they are all monotonic in the set of observations.
In other words, if they predict
They are non-monotonic however in the set of actions.
That is, you can affect the prediction "
It's basically like in the standard dynamic models either deterministic or probabilistic.
So I think our models are not so different from more standard models of action. Of course, they are very different in the description languages; but that's the type of difference that you have between Strips, and transition-functions. The first is much more convenient, but it's basically a "front-end". It's not a new model of action; it's a new language for describing the most basic one (deterministic models). Of course, I'm completely convinced that this is very important, and I think it's precisely there where KR/action fits in.
- Hector Geffner
| 23.1 | Judea Pearl |
Correcting a statement by Pat Hayes.
Hector Geffner said (about the principle of causality) :
| In any AI the same principle makes perfect sense when actions are *exogenous*; such actions, I think, we can agree, should never affect your beliefs about the past (indeed, as long as you cannot predict exogenous actions from your past beliefs, you shouldn't change your past beliefs when such actions occur). |
To which Pat Hayes replied:
| But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that someone else has been present there recently. We constantly make inferences about the past on the basis of present knowledge, even in such technical areas as military planning. |
Correction
The principle of causality is in fact stronger than Pat's interpretation of it. Not only the past, but also our beliefs about the past, do not change as a result of actions, unless the acting agent is part of our model. Moreover, if the agent is part of our model, then actions cease to be interesting and problematic as they are today (at least in some AI approaches to actions).
To explain: The action of putting a cup of coffee on the table does not change the state of the coffee or the table before the action, and does not change our beliefs about the state of the coffee before the action. But, Pat will argue: seeing the coffee on the table allows us to infer that "someone else has been present there recently." True, but only if we are concerned about the actor's whereabout and if the limitations or motivations of the action-producing agents are IN the model (e.g., that someone must be in a house to do it, and will probably do it if he/she is thirsty, etc.) Once this action are perceived as produced by a modeled agent, it is no different than any other events, say the agent tripping or being hit by a car, because then it is liscensed to trigger the usual inferences of predictions and abduction that observations trigger.
Hector said all this by using the term "exogenous". Indeed, the problematic aspects of actions surface when we try to treat actions as exogenous, namely produced by external agents NOT modeled in our system. Only by considering an action exogenous can we talk about the world "changing" (anyone ever saw a world truly changing?.)
Put another way, the peculiarities of actions vis a vis observations stem from the boundaries we put around our models and our audacity to call our models "worlds".
B. Russel (1910) noted (my words, not his) that if we model the entire universe, there is no meaning to causality or to actions, because the manipulator and the manipulated loose their distinction.
One problematic aspect of dealing with external actions is that ordinary abduction, from the immediate consequences of those actions, must be suppressed. For example, we do not want to abduce that it rained when we decide to pour water on the driveway and get it wet. This suppression is easily enforced in systems such as logic programming (Lifschitz et al) in which inference has preferred directionality, and where abduction is not a built-in feature (e.g., contraposition is not sanctioned) but must be crafted as a special feature. However, the suppression is problematic in standard logic and probability where inference is symmetric, and no differentiation is made between abduction and prediction. Such differentiation is one role played by causally ordered relations.
Well, enough said for one tiny correction.
| 23.1 | David Poole |
Pat Hayes wrote:
| But actions - or external events - do change ones beliefs about the past. They do not change the past itself, of course: that is the causality principle. But consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that someone else has been present there recently. We constantly make inferences about the past on the basis of present knowledge, even in such technical areas as military planning. |
No. No. No. Observations can change one's beliefs about the past. Doing an action doesn't change beliefs about the past. Observing the hot coffee made you update your beliefs about the past. The action of coming into the room didn't change your beliefs about the past (unless you include the observation that the action succeeded).
To make everything clearer it is crucial to distinguish sensing (making observations) from motor control (doing/attempting actions). The only role of sensing is to update your beliefs. Sensing in this sense doesn't change the world (of course, acting in order that you can sense can, and often does, change the world). Acting (i.e., sending a command to your motor controllers) doesn't change your beliefs about your present or your past, but only about the future. Acting can change the world.
If we fail to distinguish these, confusion will reign supreme. Surely in order to make some progress we could agree on such a distinction, then get back to the argument with at least one confusion cleared up!
David Poole
P.S. I am wondering why such confusion between observing and acting may have arisen in the first place.
I conjecture is that it has to do with the preconditions of actions. For example, the action has the precondition that there is nothing on x. Then by carrying out the action, can you infer that there was nothing on x? But this doesn't make sense. What happens if I had attempted to pickup x when there was something on it? What if I didn't know whether there was something on x when I tried to pick it up? It seems that the only sensible interpretation of the precondition is that if there was nothing on x and I carried out pickup(x), then the expected thing would happen. If something was on x and I carried out pickup(x) then who knows what may happen. The role of the precondition is that it is only sensible to attempt to carry out the action when the preconditions hold.
An alternative explanation if the confusion may be that the action is an observation of the effect of my motor control on a particular state of the world. If I carry out a particular motor control when there is nothing on x, then a action arises. When I do the same motor control when there is something on x then some other action arises. Then I do not choose the action, but I only choose the motor control (consider the case when I don't know whether there is something on x or not, and I try to pick it up). Is this what people mean by an action? Surely then it is imperative to distinguish that motor control (for a better description) that I get to choose, from the observation of the effect of that motor control.
| 23.1 | Erik Sandewall |
Do all current approaches behave monotonically with respect to observations? On 23.1, Hector Geffner wrote:
|
Actually, I think none of the received models of actions in AI
(say A, Toronto Sit Calc, Basic Features and Fluents, etc) does that.
I believe they are all monotonic in the set of observations. In other words, if they predict F at time i, nothing that they observe is going to affect that prediction. At most they can make the theories inconsistent. |
With respect to features and fluents, this is true for those cases where proven assessments exist at present, but not in general. The full catalogue of ontological characteristics includes such phenomena as "surprises" and "normality", both of which are nonmonotonic with respect to observations. A simple example is for the stolen car scenario: the car is left in the parking lot, three nights pass, it is for sure that the car is not removed during the day, the default is for it to stay where it is at night as well. The default conclusion is that it's still there after the three nights. Then add the observation that it's gone at the end of the period. Without admitting surprises, this scenario is inconsistent, as Hector writes. If surprises are allowed for, then you may conclude that it was removed during one of those three nights.
If you add in addition the fact that the parking lot was supervised the first and the third night, making removal impossible, then one is entitled to infer that it was stolen during the second night. Thus, the initial default conclusion regarding the presence of the car in the parking lot during the day after the second night goes from "yes" via "don't know" to "no" as these successive observations are added.
From the point of view of diagnostic reasoning these are familiar problems, but I can't think of any work in mainstream actions and change that has addressed nonmonotonicity with respect to observations in a serious way. Except, without knowing the details, I would imagine that the people who do probabilistic or possibilistic approaches might have something to say about this. Judea, or the folks in Toulouse, any input?
Do all current approaches comply with the causality principle? On 21.1, Hector Geffner wrote:
| Most recent models of action comply with the causality principle. In some it comes for free (e.g., language A ) due to the semantic structures used (transition functions); in others (Reiter, Sandewall, etc), I'm sure it can be proved. |
Yes, with respect to the features and fluents approach, it also "comes for free". The underlying semantics that's used there is essentially a simulation of the world, using non-deterministic transition from state to state or from state to state sequence (the latter in order to account for actions with extended duration). In either case the simulation proceeds forward in time, so it complies with the causality principle. The same applies for the extensions of the approach to deal with concurrency, ramification, and continuous change.
Erik Sandewall
| 25.1 | Pat Hayes |
I said:
|
... actions - or external events - do change ones beliefs about the past.... consider for example coming into a room in an empty house and finding a hot cup of coffee resting on a table. One immediately infers that somone else has been present there recently. |
This seems quite obvious and uncontroversial to me. One can be surprised by things that happen in one's world. Observations can, in fact, violate one's model of the world and show that it is faulty and needs to be updated; and these updates can involve changing one's beliefs about the past. However, many seem to disagree:
Hector Geffner:
| It's important to distinguish observations from actions. |
David Poole:
| No. No. No. Observations can change one's beliefs about the past. Doing an action doesn't change beliefs about the past. Observing the hot coffee made you update your beliefs about the past. |
Well, OK. I said 'actions or external events'.
I dont think this sharp distinction between sensing and acting is either necessary or even ultimately coherent, in fact. We are constantly monitoring our own actions in this kind of way, at various levels, so almost every action has observation involved in it. And similarly, it is hard to observe without somehow acting, and a good deal of our planning and acting is motivated by a perceived need to find out more about the world. So observation is intimately bound up with action. Our peripheral systems often blend motor action and lowlevel perception in tight feedback control loops, so that our bodies seem to 'move by themselves', but these lowlevel controls are the result of more cognitive decision-making (deciding to hit a tennis ball, say.)
But even if I agree, for the sake of argument; David's point about observation applies to beliefs about anything, past, present or future. You might predict what is going to happen when you act, but the only way to be sure it will happen is to do it and then take a look. So again, I see no reason why this distinction supports the original claim that we cannot draw new conclusions about the past from observations in the present.
Hector Geffner continues:
| In dynamic systems the first are usually expressed as "initial conditions" e.g., x(0) = 5 , loaded(0) = false , etc; while the latter are the inputs to the system. An observation at time ("cup in the table") of course should have an effect on your beliefs at times j<=i (the past) |
This seems so peculiar that I wonder if we are talking about the same thing. The whole point of making an observation, surely, is to gain information about the present state, not the initial conditions (which, once one has taken an action, are in the past.) Similarly, I wasnt saying that an observation could change one's past beliefs - nothing can change the past - but rather that it could change one's (present) beliefs about the past.
[Regarding Hector's later remarks on nonmonotonicity, I agree with Erik Sandewall's reply in 23.1(98007).]
Judea Pearl:
|
Correction
The principle of causality is in fact stronger than Pat's interpretation of it. Not only the past, but also our beliefs about the past, do not change as a result of actions, unless the acting agent is part of our model. Moreover, if the agent is part of our model, then actions cease to be interesting and problematic as they are today (at least in some AI approaches to actions). To explain: The action of putting a cup of coffee on the table does not change the state of the coffee or the table before the action, and does not change our beliefs about the state of the coffee before the action. |
Well, I was talking about a later observation of the coffee put there by someone else, not the act of putting it there oneself. But in any case, this second statement again seems to me to be simply false. Suppose that one is walking along in NYC minding ones own business, when suddenly a mugger grabs one from behind and holds a knife to one's throat. Isnt this an example of an "exogenous" act (by an agent not in one's model) causing one to change one's beliefs about a whole lot of things, some of them involving the past, such as that you were alone in the street? (Examples like this are so blindingly obvious that I wonder if we are talking about the same thing??)
I fail to see why having beliefs about other agents (?I presume this is what is meant by an agent being part of a model) means that "actions cease to be interesting". Most of our daily lives are taken up with worrying about what other agents are doing, especially the ones we know a lot about. (Ever had kids to look after, or even a dog?)
| BUT, Pat will argue: seeing the coffee on the table allows us to infer that "someone else has been present there recently." True, but only if we are concerned about the actor's whereabout and if the limitations or motivations of the action-producing agents are in the model (e.g., that someone must be in a house to do it, and will probably do it if he/she is thirsty, etc.) |
Well of course. If one knew nothing of people and coffee, one wouldnt come to the conclusion I mentioned. It follows from one's knowledge of such things. That is simply a nonsequiteur. Notice however that the inference is that an agent exists, whose existence one had not previously considered. I'm not sure what your doctrine allows, but this doesn't seem quite the same as having that agent in one's model before seeing the cup. Not to mention the mugger.
| Once this action are perceived as produced by a modeled agent, it is no different than any other events, say the agent tripping or being hit by a car, because then it is liscensed to trigger the usual inferences of predictions and abduction that observations trigger. |
Well, all this talk of 'licence' seems like the reiteration of a doctrine of some kind (one I am not familiar with, being an atheist); but leaving that aside, if I can make sense of this at all, then Judea seems to simply be agreeing with me. The point is that (within one's "licence") it is possible to come to new conclusions about the past on the basis of new information about the present. The direction of inference can be opposed to time's arrow. Is that not what we were talking about?
| Hector said all this by using the term "exogenous". Indeed, the problematic aspects of actions surface when we try to treat actions as exogenous, namely produced by external agents not modeled in our system. Only by considering an action exogenous can we talk about the world "changing" (anyone ever saw a world truly changing?.) |
Of course I have seen a world changing, in the relevant sense. It happens even if the actions are entirely within my own conceptual scope, eg as when I flick the light switch, confident that the light will in fact come on, and it does indeed come on. That's an observation of a changing world. (Sometimes the light doesnt come on, and I am forced to update my beliefs, often about the past history of the light bulb or the electrical system.) ....
| One problematic aspect of dealing with external actions is that ordinary abduction, from the immediate consequences of those actions, must be suppressed. For example, we do not want to abduce that it rained when we decide to pour water on the driveway and get it wet. |
I confess to failing completely to follow this point. Why is my putting water on my driveway considered an external action? External to what?
Pat Hayes
P.S. back to David Poole:
|
P.S. I am wondering why such confusion between observing and acting
may have arisen in the first place.
I conjecture is that it has to do with the preconditions of actions. For example, the pickup(x) action has the precondition that there is nothing on x. Then by carrying out the action, can you infer that there was nothing on x? |
No, of course not. the implication runs from precondition to result, not in reverse. (You might also have a reverse implication if the precondition was necessary as well as sufficient; but then this would be a valid inference to make. Consider for example that the only way to stay alive is to not hit the oncoming truck; you make a wild swerve, survive, and say with a sigh of relief, Thank God I didnt hit the truck.)
| But this doesn't make sense. What happens if I had attempted to pickup x when there was something on it? |
You would have failed, and maybe (if the axiom had been an iff ) concluded that there must have been something on the block after all, or at any rate that something had prevented it being picked up. It would have been an abnormal state, in McCarthy's middle-period sitcalc using ab-minimisation.
| What if I didn't know whether there was something on x when I tried to pick it up? It seems that the only sensible interpretation of the precondition is that if there was nothing on x and I carried out pickup(x), then the expected thing would happen. If something was on x and I carried out pickup(x) then who knows what may happen. The role of the precondition is that it is only sensible to attempt to carry out the action when the preconditions hold. |
No no. This is all a description of an action. What actually happens when you do the actual action may be much more complicated than your description (your beliefs about the action) are able to predict. Maybe something was there that you didnt know about; maybe your idea of lifting is defective in some way. We can never guarantee that our beliefs are accurate, and still less that they are complete. But whatever actually happens, if you are able to deduce from your beliefs that X should happen at time t, and then when you actually do it, (you observe that) X doesnt happen at time t, you want to be able to recover from this situation without dissolving into inconsistency. Hence the (original) need for nonmonotonic logics.
| An alternative explanation if the confusion may be that the action pickup(x) is an observation of the effect of my motor control on a particular state of the world. If I carry out a particular motor control when there is nothing on x, then a pickup(x) action arises. When I do the same motor control when there is something on x then some other action arises. Then I do not choose the action, but I only choose the motor control (consider the case when I don't know whether there is something on x or not, and I try to pick it up). Is this what people mean by an action? Surely then it is imperative to distinguish that motor control (for a better description) that I get to choose, from the observation of the effect of that motor control. |
In the sitcalc (any variety), actions are changes in the world, not motor commands. One plans by thinking about the changes, not by thinking about the muscles one is going to use. Putting such a system into a robot requires one to somehow connect these actions with motor controls, no doubt, but they shouldnt be identified. (Murray and Ray, do y'all agree??)
| 26.1 | Michael Thielscher |
On 23.1., Erik wrote
| ... but I can't think of any work in mainstream actions and change that has addressed nonmonotonicity with respect to observations in a serious way. |
Well, I at least intended to be serious in my KR'96 paper on "Qualification and Causality," where I address the Qualification Problem. The latter is inherently concerned with nonmonotonicity wrt. observations--if we view it the way John introduced it, and not oversimplify it to the marginal issue of deriving implicit preconditions from state constraints. The classical example goes as follows. By default, we conclude that the car's engine is running after turning the ignition key. Adding the observation that initially the tail pipe houses a potato, the previous conclusion gets withdrawn. Part of my paper was concerned with a Fluent Calculus axiomatization capable of dealing with (a well-defined aspect of) the Qualification Problem. A nice feature about the Fluent Calculus is that it provides monotonic solutions to both the Frame and the Ramification Problem. But when it comes to the Qualification Problem, nonmonotonicity is inevitable per definitionem, which is why my Fluent Calculus axiomatization in the KR paper comes with a nonmonotonic feature.
| 26.1 | Erik Sandewall |
Michael,
Sorry about that, I expressed myself imprecisely. What I had in mind was in the context of Pat Hayes's contribution:
| Nonmonotonicity is a good example of the need to revise ones beliefs about the past in the light of unexpected outcomes in the present,... |
What happens in the approach of your KR-96 paper for the case of "backwards in time", such as the stolen car scenario?
Re the potato in tailpipe scenario, see also my question number 2 to Wolfgang Bibel in yesterday's newsletter.
Erik
| 26.1 | Judea Pearl |
On Actions vs Observations, or on Pat Hayes' reply to Geffner, Poole and me.
Well, well, and I thought my tiny correction would end with Pat just replying "Of course, I did not mean it ..." Instead, it now seems that the cleavage between the culture that Hector, David and I represent and the one represented by Pat has gotten so deep that we are not even sure we are talking about the same thing.
Pat does not think the "distinction between sensing and acting is either necessary or even ultimately coherent", For him, observing a surprising fact evokes the same chain of reasoning as establishing that fact by external act. In both cases, so claims Pat, the world is changing, because a world is none other but one's beliefs about the world, and these do change indeed in both cases.
I tend to suspect that Pat's position is singular, and that most readers of this newsletter share the understanding that it is useful to think about observations as changing beliefs about a static world, and about actions as changing the world itself. I am under the impression that this distinction has become generally accepted among AI researchers (as it has among philosophers and database people, e.g., counterfactual vs indicative conditionals, imaging vs. conditioning, belief updating vs. belief revision, etc. etc.) Otherwise, one would find it hard to understand why so much energy has been devoted in AI to actions vis a vis observations, why the title of this Newsletter is what it is. Why the Frame Problem does not exist relative to observations (e.g., need frame axions for "I saw only x"?), why there is no ramification problem relative to observations (surely every observation has some ramifications) and why people write so many papers on concurrent actions and not on concurrent observations. Or are these observational problems just waiting around the corner to hit us once we solve the corresponding problems with actions?
If Pat's position is singular, I would not wish to bore the rest of the readers with this issue, and I I will pursue it with Pat in the privacy of our screens. I am curious, though, if my suspicion is correct, and I will be waiting readers' feedback.
---------* * * ---------------
Those who read my paper in TARK 1996 need not read further. Others may wish to ask when a change is considered a "world-change" and when it is merely a "belief change".
Let us use Pat's example:
| Of course I have seen a world changing, in the relevant sense. It happens even if the actions are entirely within my own conceptual scope, eg as when I flick the light switch, confident that the light will in fact come on, and it does indeed come on. That's an observation of a changing world. (Sometimes the light doesnt come on, and I am forced to update my beliefs, often about the past history of the light bulb or the electrical system.) |
But we are not dealing here with physics or psychology. We are dealing with various formal systems for modeling the world and our beliefs about the world. For every such system, if we are to accomplish anything more useful than trying to solve Schrödinger's equation for all the particles in the universe, we must define some limits, or boundaries, thus distinguishing the things our system will explain from those that it wont. Once the boundaries are defined, they also define a set of relationships as invariant namely holding true permanently for all practical purposes unless they are violated by exceptions that come from outside those boundaries. We say that the world "changed" if any of these invariant relationships is violated.
These concepts were developed for systems with static boundaries. Humans on the other hand, show remarkable flexibility in expanding and shrinking these boundaries as the needs arise, and most of Pat's examples draw on this flexibility. This may account for his statement:
| I dont think this sharp distinction .... is either necessary or even ultimately coherent, in fact. We are constantly.... |
Flicking the switch would be a case of a changing world if our formal system is ignorant of the causal connection between the switch and the light. But for a formal system that includes causal rules saying
"switch flicked causes light on"and (this is important)
"switch unflicked causes light off"
seeing "light on" (even without flicking the switch) need not be considered a change of world, because "light on" can be explained within the system (in terms of the switch being flicked by some agent) and there is no need to invoke such dramatic phrases as "changing worlds" for things that we know how to handle by standard inference methods. (e.g., adding a proposition "light on" to the system and let a classical theorem prover draw the consequences. [and if our current beliefs contain "light off" then the contradiction can be handled by either temporal precedence or minimal-change belief-revision]).
What cannot be explained within such a system is the flicking of the switch (unless we model the agents' motivations too). Thus, we ask: Should the flicking of the switch be considered a "change of world" in such system? Yes, it CAN be considered such. But if our model is confined to the objects and the lighting in the room, and does not contain knowledge about switch-flicking agents, then it wont make any difference if we consider it on equal footing with the observation: "the switch is reported to be flicked". All inferences triggered by a changing world semantics will also be triggered by an observational semantic, according to which the world was static and we just opened our eyes and learned a new fact: "switched is flicked".
So when MUST we resort to the changing-world semantics? Pat answered this question:
| Sometimes the light doesnt come on, and I am forced to update my beliefs, often about the past history of the light bulb or the electrical system.) |
Here we have it! a violation of one of the system's invariant -- the causal rules (stated above), which specify the influence of the switch on the light. Why it is special? Consider now the action "take the bulb out" with its immediate consequence "light out". Had the causal rule (above ) been qualified with "flick causes light unless someone takes the bulb out" there would be no violation, and again we can absorb the new information as before, without invoking world-change semantics. But without such qualification, a violation occurs in a rule that was meant to be permanent (Vladimir even uses the predicate always to distinguish causal rules from less permanent relationships) Well, now we have no choice BUT to invoke changing world semantics. The new semantics is similar to the one for changing-observations, with one important difference: the suppression of certain explanations. Before the action "take the bulb out" was enacted we had the license (excuse the religious overtones, Pat) to use our causal rule and infer and explanation: "light out, therefore switch must be unflicked" But after that action, the license is revoked, and this explanation should not be infered. (even though the causal rule still resides somewhere in the database, ready to be used again in a new situation.)
And this is where the difference between actions and observations come in. An action must be equipped with a pointer to mark some causal rule "violated", to suppress its use in abduction (or explanation). Such marking is needed only when some of the predicates in the action's add-list are consequences by some causal rule. Predicates that are not consequences of any causal rules are called "exogenous", and it does not matter if we treat them as actions or observations -- we will never attempt to explain them anyway.
Looking back, it appears that I did manage to bore you after all, despite my determination to do it to Pat only.
Time to stop.
Judea
| 26.1 | Erik Sandewall |
The topic of "what's in an action?" is important and quite worth some attention. In the previous Newsletter issues, David Poole wrote and Pat Hayes answered as follows:
| If I carry out a particular motor control when there is nothing on x, then a pickup(x) action arises. When I do the same motor control when there is something on x then some other action arises. Then I do not choose the action, but I only choose the motor control (consider the case when I don't know whether there is something on x or not, and I try to pick it up). Is this what people mean by an action? Surely then it is imperative to distinguish that motor control (for a better description) that I get to choose, from the observation of the effect of that motor control. |
| In the sitcalc (any variety), actions are changes in the world, not motor commands. One plans by thinking about the changes, not by thinking about the muscles one is going to use. Putting such a system into a robot requires one to somehow connect these actions with motor controls, no doubt, but they shouldnt be identified. (Murray and Ray, do y'all agree??) |
However, earlier in the same contribution Pat had written:
| ... Our peripheral systems often blend motor action and lowlevel perception in tight feedback control loops, so that our bodies seem to 'move by themselves', but these lowlevel controls are the result of more cognitive decision-making (deciding to hit a tennis ball, say.) |
Pat, I can't make sense out of your position: at one point you seem to argue that low-level and high-level descriptions of actions can't ever be separated; at another point you seem to say that they are best treated in complete separation.
My own preference is to take both into account, but to be precise about having two distinct levels of descriptions with distinct roles. In particular, this allows for dealing both with an action as a prescription for motor controls and as the expectation for what state changes will be obtained as a result. It also allows one to relate those two levels to each other.
Regardless of level, I understand an action as an instantaneous invocation that starts a process, just like in the ontology of Reiter-sitcalc. The invocation is treated similarly across levels. The two levels of description apply for the process; I've called them the material level and the deliberative level (previously in [1], but the deliberative levelwas called "image level"). An illustrative example of an action description on the material level is as follows for the action of going from the current location A to a new location B: turn around until you're looking towards B, then accelerate by 0.3 m/s/s until you reach the velocity of 1 m/s, from then on keep a constant velocity until you are at B. A lot of details aside, such as defining what it means to be "at B", the point I want to illustrate is that we use a continuous level description of the action, or more precisely, at least piecewise continuous for all the relevant state variables, but with a possibility to change the control mode due to interventions by some higher control level.
From a software engineering point of view, this is more like a specification than like a program. It is also "above" the level of control engineering in the sense that it provides no details about the feedback control loop between velocity sensor and motor controls. At the same time, it is much closer to the control level than a conventional description in some of our favorite logics in KR.
The deliberative level is the one that Pat alludes to, where actions are characterized by discrete properties at a small number of timepoints: possibly only the beginning and the end of the action, possibly a few more, possibly a sequence of partial world states at integer timepoints (as in basic Features and fluents). From the point of view of the deliberative level, it may be convenient to think of the material level as a "program" for performing the action, but then in a very general sense of program.
Here are some of the benefits from the explicit treatment of the action's process on both the material level and the deliberative level:
The precondition in an deliberative-level action description should at least guarantee that the action is applicable. It is desirable that it also excludes those cases where the action can be predicted to fail.
A recent article [2] showed how the goal-directed process of pursuing a goal even though some of the planned actions fail, can be characterized in logic. In this way, the same concepts of failure and applicability are at work across several system levels.
Furthermore, David Poole wrote and Pat Hayes answered:
| What if I didn't know whether there was something on x when I tried to pick it up? It seems that the only sensible interpretation of the precondition is that if there was nothing on x and I carried out pickup(x), then the expected thing would happen. If something was on x and I carried out pickup(x) then who knows what may happen. The role of the precondition is that it is only sensible to attempt to carry out the action when the preconditions hold. |
| No no. This is all a description of an action. What actually happens when you do the actual action may be much more complicated than your description (your beliefs about the action) are able to predict. Maybe something was there that you didn't know about; maybe your idea of lifting is defective in some way. We can never guarantee that our beliefs are accurate, and still less that they are complete. But whatever actually happens, if you are able to deduce from your beliefs that X should happen at time t, and then when you actually do it, (you observe that) X doesn't happen at time t, you want to be able to recover from this situation without dissolving into inconsistency. Hence the (original) need for nonmonotonic logics. |
I'll agree with David if the last sentence is changed to go "...it is only sensible to attempt to carry out the action when the preconditions are believed to hold". This belief may be based on correct observations, on defaults, or even on incorrect observations, but if one does have bona fide belief that the preconditions hold, with a high degree of assurance (and one has no particular reason to believe that a great disaster is to ensue if one happens to be mistaken, etc. etc), then of course it is sensible to attempt the action.
Therefore, Pat, I don't understand what you are objecting against in this respect. (And what does it have to do with the original need for nonmonotonic logic?)
Erik
References:
[1] Erik Sandewall: Features and Fluents, p. 3 ff.
Oxford University Press, 1994.
[2] Erik Sandewall
Logic Based Modelling of Goal-Directed Behavior.
Linkoping University Electronic Press, Vol 2 (1997): nr 19,
http://www.ep.liu.se/ea/cis/1997/019/
[3] Erik Sandewall
Towards the validation of high-level action descriptions from their
low-level definitions.
Artificial Intelligence Communications, December 1996.
Also Linkoping University Electronic Press, Vol 1 (1996): nr 4,
http://www.ep.liu.se/ea/cis/1996/004/
| 28.1 | Michael Thielscher |
Dear Erik,
On 26.1., you wrote:
|
What happens in the approach of your KR-96 paper for the case of
"backwards in time", such as the stolen car scenario?
Re the potato in tailpipe scenario, see also my question number 2 to Wolfgang Bibel in yesterday's newsletter. |
The approach is not restricted to projection, so observations may very well give cause to revising one's belief about the qualifications of an action in the past. As for the stolen car scenario: The only abnormality I consider in the paper is that of being unable to perform an action, in which case none of its effects materializes. Your Stolen Car scenario requires to consider abnormalities as to the surprising production of a single effect (or the failure of producing an expected effect). However, I can give you a straightforward formalization of your example in the Fluent Calculus, including default rules, along the lines of my KR-paper. The resulting axiomatization supports precisely the intended conclusions which you mentioned. My approach also works with non-deterministic action, so if an action has the (nondeterministic) effect that the tail pipe of either of two cars A and B gets clogged, then two preferred models result, one of which denies that we can start car B--as intended.
Michael
| 29.1 | Michael Gelfond |
I would like to better understand the following comment by Hector Geffner:
|
I believe they (models of actions in AI) are all monotonic in the
set of observations. In other words, if they predict |
If I understood Hector correctly, the following may be a counter
example. Consider the following domain description D0 in the language
The language of D0 contains names for two actions,
|
A | ||
|
B | ||
| true_at(P, S0). | ||
| true_at(neg(F), S0). |
(Domain descriptions in
Here we are interested in queries of the type
| holds(F, [A1, ...An] ) |
The entailment relation on
As expected, we have that
|
D0 |
| occurs(B, S0). |
The second example shows how observations can change beliefs about the past. Consider a domain description D3
|
A | ||
|
F |
| S0 < S1 | ||
|
neg(F) |
Hector, is this really a counter example or you meant something else?
Reference.
C. Baral, M. Gelfond, A. Provetti, ``Representing Actions: Laws, Observations and Hypotheses'', Journal of Logic Programming, vol. 31, Num. 1,2 and 3, pp. 201-245, 1997.
| 29.1 | Luís Moniz Pereira |
Dear Erik,
I noticed in the discussion that you said:
| From the point of view of diagnostic reasoning these are familiar problems, but I can't think of any work in mainstream actions and change that has addressed nonmonotonicity with respect to observations in a serious way. |
I have tackled the issue of nonmonotonicty with respect to observations. Cf my home page, the AAAI-96, ECAI-96, AIMSA-96, LPKR97, JANCL97,AI&MATH98 papers. Using a LP approach I perform abuction to explain observations. The abductive explanations may be: non-inertiality of some fluent with respect to some action; occurrence of some erstwhile unsuspected foreign concurrent action along with some action of mine; or opting for a definite initial state of the world up till then given only by a disjunction of possibilities.
You're right, the techniques I and my co-author, Renwei Li, use were first developed by me and others in the context of diagnosis using LP! In fact we haven't yet used them all up yet in actions. For a view of LP and diagnosis, as well as representing actions in LP, see our book:
José J. Alferes, Luis M. Pereira Reasoning with Logic Programming LNAI vol.1111, Springer 1996
Best, Luís
| 30.1 | Hector Geffner |
This is in reply to Michael's message.
As I see it, in the "basic" approaches to the frame problem (Reiter's completion, Sandewall form of chrnological minimization, language L , etc), in one way or another, action rules are compiled into transition functions of the form f(a, s) - where is a state and is an action - that describe the set of possible state trajectories. Observations in such models just prune some of the trajectories and hence have a "monotonic" effect (i.e., predictions are not retracted, at most they are made inconsistent).
In other models, Michael's and Luís's included, actions are represented in the state (in one way or the other) and hence abdution to both fluents and actions are supported. Such models are non-monotonic in the set of observations. Actually the only apparent difference in such models between actions and fluents is that the former are assumed to be "false by default" while the latter are assumed "to persist by default".
Interestingly, there seems to be another difference between actions and fluents in those models, and that is, that actions, unlike fluents, are not allowed to appear in the head of rules. Actually I'm not sure whether this is the case in all such models, but it is true at least in my AAAI-96 paper. The reason I excluded actions from rule heads was precisely "to prevent actions from having an effect on beliefs about the past" (just think of a rule like hungry then eat). Again "the causality principle".
I wonder now what's the reason the same constraint is in force in most other models of such type (if that's so).
Any ideas?
Hector Geffner
| 2.2 | Michael Gelfond |
Dear Hector,
You write
|
As I see it, in the "basic" approaches to the frame problem (Reiter's
completion, Sandewall form of chronological minimization, language
|
If you replace
A model of
Observations not only prune "the set of possible trajectories"
but also change the actual path in each model.
This gives the nonmonotonicity of entailment in
Is this nonmonotonicity "in the set of observations"?
You continue:
| In other models, Michael's and Luís' included, actions are represented in the state (in one way or the other) and hence abduction to both fluents and actions are supported. Such models are non-monotonic in the set of observations. Actually the only apparent difference in such models between actions and fluents is that the former are assumed to be "false by default" while the latter... |
You are right when you say that
in
Michael
| 2.2 | Hector Geffner |
Dear Michael,
I meant the language
I've read your paper with Chitta and Provetti, but don't have it with me. As far as I recall, and following what you say, yes, definitely that account is non-monotonic wrt to the observations.
Hector
| 12.2 | Pat Hayes |
Responses to Judea Pearl and Erik Sandewall in ENRAC 26.1 (issue 98009):
Responses to Judea (all quotations from his message 26.1):
On Actions vs Observations, or on Pat Hayes' reply to Geffner, Poole and me:
| ... the cleavage between the culture that Hector, David and I
represent and the one represented by Pat has gotten so DEEP that we
are not even sure we are talking about the same thing.
|
| Pat does not think the "distinction between sensing and acting is
either necessary or even ultimately coherent". For him, observing a
surprising fact evokes the same chain of reasoning as establishing
that fact by external act. In both cases, so claims Pat, the world
is changing, because a world is none other but one's beliefs about
the world, and these do change indeed in both cases.
|
| ... there
is no need to invoke such dramatic phrases as "changing worlds" forthings
that we know how to handle by standard inference methods. (e.g., adding
a proposition "light on" to the system and let a classical theorem
prover draw the consequences. [and if our current beliefs contain
"light off" then the contradiction can be handled by either temporal
precedence or minimal-change belief-revision]).
|
| [we need to decide]... when a change is considered a "world-change" and
when it is merely a "belief change".
|
| Question:
Is flicking the switch and seeing the light come on an example of
a changing world ?
|
| From a physical viewpoint, the world has obeyed Schrodinger's
equation before and after the action, so it has not changed at all.
|
One last comment:
| ... we are not dealing here with physics or psychology. We are dealing
with various formal systems for modeling the world and our beliefs
about the world.
|
Responses to Erik
In his message 26.1, referring to an earlier message by myself, he wrote:
| In the sitcalc (any variety), actions are changes in the world, not motor
commands. One plans by thinking about the changes, not by thinking about
the muscles one is going to use. Putting such a system into a robot
requires one to somehow connect these actions with motor controls, no
doubt, but they shouldnt be identified. (Murray and Ray, do y'all agree??)
|
| However, earlier in the same contribution Pat had written:
|
| ... Our peripheral systems often blend motor action and lowlevel perception
in tight feedback control loops, so that our bodies seem to 'move by
themselves', but these lowlevel controls are the result of more cognitive
decision-making (deciding to hit a tennis ball, say.)
|
| Pat, I can't make sense out of your position: at one point you seem to
argue that low-level and high-level descriptions of actions can't ever
be separated; at another point you seem to say that they are best
treated in complete separation.
|
| My own preference is to take both into account, but to be precise about
having two distinct levels of descriptions with distinct roles. In
particular, this allows for dealing both with an action as a
prescription for motor controls and as the expectation for what
state changes will be obtained as a result. It also allows one to relate
those two levels to each other.
|
| ... The deliberative level is the one that Pat alludes to, where actions
are characterized by discrete properties at a small number of timepoints:
possibly only the beginning and the end of the action, possibly a few
more, possibly a sequence of partial world states at integer timepoints
(as in basic Features and fluents).
|
The fact that someone with Erik's insight seems to be unable to think of 'high-level' as meaning anything other than instantaneous situations is a vivid illustration of the problem Ive been complaining about: almost all our thinking in this field is dominated by the archaic and awkward oversimplifications embodied in the situation calculus.
David Poole wrote:
| What if I didn't know whether there was something on
|
| No no. This is all a description of an action. .....
|
| I'll agree with David if the last sentence is changed to go "...it is
only sensible to attempt to carry out the action when the preconditions
are believed to hold". .....
Therefore, Pat, I don't understand what you are objecting against in
this respect.
|
| (And what does it have to do with the original need for nonmonotonic
logic?)
|
|
|
Im puzzled that you need to ask this question. Isnt this textbook-level stuff?
Pat Hayes