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