| Issue 97012 | Editor: Erik Sandewall | 27.10.1997 |
Today |
The panel on Theory Evalution addresses the question of what are good theories in our area: what properties should a theory have; what properties do acutally give a theory a staying power. Pat Hayes has mentioned the situation calculus as an example of a theory with staying power in spite of its shortcomings, which of course has caused others to come to its defense or to agree with the critique.
In this way, the discussion has drifted over to the topic of another NRAC panel, namely the panel on Ontologies. I will therefore now start the ontologies panel with the position statements by the three panelists, and define a bifurcation from the Theory evaluation panel to the Ontologies panel: contributions will be listed under the panel that the most closely matches the contents. In particular, today's debate contribution by Michail Soutchanski which continues the discussion about the merits and limitations of situation calculus will be listed in the ontologies panel.
I hope that the readership will not forget the Theory Evaluation panel for this feud about formalisms and ontologies... And the opportunity to ask questions to Wolfgang Bibel about his IJCAI paper is still open.
Debates |
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?
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.
"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'').