Electronic Newsletter Actions and Change

Electronic Newsletter on
Reasoning about Actions and Change


Issue 97015 Editor: Erik Sandewall 31.10.1997

The ETAI is organized and published under the auspices of the
European Coordinating Committee for Artificial Intelligence (ECCAI).

Today

Pat Hayes's note on situation calculus in this Newsletter on the 22.10 provoked a number of responses. In today's issue he gives his answers to all of them. I have divided Pat's answer into two parts, one for the discussion about theory evaluation and the other for the discussion about ontologies. These debates are not over yet.

Besides the panels, the present issue contains our first occurrence of a research note, that is, a short (this one: 4 pages) note containing a concise research result. The background is interesting as an illustration of publication patterns in the ETAI system. The author of the note, Paolo Liberatore, submitted an article to the ETAI in July; it had its discussion period of three months, after which the paper goes to the referees. Before refereeing, the author gets a chance to revise his paper in order to take the feedback into account. In this case, the discussion had not given Paolo any reason to change the paper, but he had an additional result. In our system, it would not have been reasonable to add that result to the original paper, since then the amendment would go to the referees without previous discussion. At the same time, it would also not be reasonable to delay the publication of the original paper by another three months.

This is the kind of situation where ETAI research notes may be appropriate. In size, they are supposed to be a few pages; in appearance, they are presented with journal look-and-feel using latex and postscript. Wrt availability, they are put on-line immediately when received, with a link from the concurrent Newsletter to the research note, and for the formalities, they are included in the monthly News Journal which is published in a stable fashion.

We have already seen the emergence of discussion notes within panel debates: the dialogue is represented as a sequence of messages; more strongly technical contributions go into notes. What we see today is another variant of notes, research notes rather than discussion notes. Their graphical appearance is similar, but research notes go to reviewing and refereeing just like full articles.

Access to the research note is obtained using the URL stated below, by clicking the link in the HTML version of the present Newsletter. It will also be included as one part of the News Journal for October, which will appear a few days into the next month and contain the accumulated contents of October's Newsletters.

Questions and comments about this research note are invited. Refereeing can be done three months from now.


ETAI Publications

Research notes

Paolo Liberatore

Compilability of Domain Descriptions in the Language A.

[interactions]

In this note we analyze the possibility of reducing the complexity of entailment in A by a compilation of the domain description. Since a single domain description D must in general be queried many times with respect to many different queries V, it makes sense to reduce it in a form that allows the solving problem of entailment in polynomial time. Using results from the field of language compilation, we prove that such a compilation is impossible, if we impose the result of compilation to be a polynomial data structure.


Debates

NRAC Panel on Theory Evaluation

Pat Hayes:

Answers re Theory Evaluation

I wrote and Murray answered as follows:

  We need some characterisation of what ... proper reasoning is, or at least some examples of where it can be found. ... we don't have any hard data about 'common sense' at all, and the intuitions we appeal to often confuse linguistic, psychological and pragmatic issues.

  This is where building robots based on logic-based KR formalisms comes into its own. When we construct a logical representation of the effects of a robot's actions and use that theory to decide the actions the robot then actually performs, we have one clear criterion for judging the formalisation. Does the robot do what it's supposed to? There are other criteria for judging the formalisation too, of course, such as its mathematical elegance. But when our formalisations are used to build something that actually does something, we're given an acid test. Furthermore, when the "something that actually does something" is a robot, we're forced to tackle issues to do with action, space, shape, and so on, which I think are crucial to common sense.

I'm sympathetic to the fact that robot-testing forces one into the gritty realities of the actual world, and admire Murray's work in this direction. However, I think that to use this as a paradigm for testing formalizations gets us even deeper into the other problem I worry about, which is how to separate the formalism itself from all the rest of the machine it is embedded in. With robots there are even more things that stand between the formalization and the test: all the architectural details of the robot itself, the ways it sensors work, etc., are likely to influence the success or otherwise of the robot's performance; and perhaps a better performance can be achieved by altering these aspects rather than doing anything to the logic it uses or the ontology expressed in that logic.

The same kind of problem comes up in cognitive psychology. It is very hard to design experiments to test any theories of cognitive functioning in humans. Noun meanings in psycholinguistics is about as far into the mind as any empirical tests have been able to penetrate; other, non-cognitive, factors interfere so much with anything measurable that hard data is virtually unobtainable.

(On the other hand, maybe this is something to be celebrated rather than to worry about! On this view, influenced by 'situatedness', one shouldnt expect to be able to divorce an abstract level of logical representation completely separated from the computational architecture it is supposed to be implemented on. I expect this view is not acceptable to most subscribers to this newsletter, however, on general methodological grounds. :-)

Erik wrote:
  Pat,

I am puzzled by your remarks, because while I agree with most of your points, I think they have already been answered by research especially during the last five years.....

Even if I were to agree, just cast my remarks entirely in the past tense and only point to the fact that sitcalc exercised a remarkably strong hold on everyone's imaginations for a very long time in spite of its shortcomings. It still provides an example for Leora's query. As you say:

  ... since we agree about the shortcomings of sitcalc, it might also be interesting to discuss why it has such remarkable inertia. Does the frame assumption apply to theories, and what actions affect the research community's choice of theoretical framework?

Yes, I think that there was (and still is) a tendency for the field to go through the following loop. We start with a genuine research problem; make some initial progress by inventing a formalism; the formalism fails to fit the original goals, but itself becomes the subject of investigation, and its failings themselves the subject of research; and then this research effort detaches itself completely from the original goal and becomes an end in itself. You provide a very elegant example of this with the methodology you suggest for evaluating formalisations:

  .... the remedy exists and has been published: it is the systematic methodology which I introduced in (the book) "Features and Fluents". In brief, the systematic methodology program proposes to work in the following steps:

  • Define an underlying semantics for a suitable range of problems. The definition must be strictly formal, and should as far as possible capture our intuitions wrt inertia, ramification, etc. ...

  • Define a taxonomy of scenario descriptions using the underlying semantics. ...

  • Analyse the range of applicability of proposed entailment methods (for example involving chronological minimization, or occlusion, and/or filtering). ...

In this way, we don't have to validate the logics against the ill-defined notion of common sense; validation is performed and range of applicability is defined from perfectly precise concepts.

Yes, but to what end? The things you characterise as 'ill-defined' are the very subject-matter which defines our field. There is no objective account of 'action', 'state', etc. to be found in physics, or indeed any other science; our inttuitions about hese things is the only unltimate test we have for the correctness or appropriateness of our formalisms. Theres no way for us to escape from philosophical logic into the clean, pure halls of JSL. For example, your first step requires a formal semantics which captures our intuitions regarding "inertia, ramification, etc.". But these are technical terms arising within the theory whose validity we are trying to test. People don't have intuitions about such things: they have intuitions about space and time, tables and chairs, liquids and solids, truth and lies; about the stuff their worlds are made of. Even if people did have intuitions about inertia and ramification, those intuitions wouldnt be worth a damn, because they would be intuitions about their own reasoning, and one thing that psychology can demonstrate very clearly is that that our intuitions about ourselves are often wildly mistaken.

  And how do these formal structures relate to real common sense? Well, an additional step may also be appropriate, namely, that of comparing the intended conclusions (as specified by the underlying semantics) with the conclusions that people would actually tend to make by common sense. However, that would be a task for psychologists, and not for computer scientists.

Surely this must be done first (if we are to pretend to be still pursuing the original research goals which gave rise to this field.) Until the 'psychologists', or somebody, has told us what it is that our formalisms are supposed to be doing, speculation about their properties is just an exercise in pure mathematics.

NRAC Panel on Ontologies for Actions and Change

Pat Hayes:

Answers to Defenders of Situation Calculus

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. ...
True.

  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