ETAI Newsletter Actions and Change

ETAI Newsletter on
Reasoning about Actions and Change


Issue 97010 Editor: Erik Sandewall 23.10.1997

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

Today

The discussion about Theory Evaluation continues with three responses to Pat Hayes's contribution:


Debates

NRAC Panel on Theory Evaluation

From: Murray Shanahan

Suppose someone in this field were to announce that they had the whole thing finished, all the problems solved, etc.. What tests would be ask them to pass before we believed them?

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.

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

One of the biggest failures of the KR community generally is that it is virtually impossible to actually publish a knowledge representation itself! One can talk about formalisms and semantics and equivalences etc. etc. (the stuff in Erik's list), but this is all part of the *metatheory* of knowledge representation. But when it comes to actually getting any representing done, we hardly hear about that at all.

Absolutely! More papers in the Naive Physics Manifesto vein, please. However, I did manage to "actually publish a knowledge representation itself" in ECAI-96, and won the best paper prize for it. The paper supplies axioms describing the relationship between a mobile robot and the world, specifically the effect of the robot's actions on the world and the impact of the world on the robot's sensors. Two papers on the same theme appear in AAAI-96 and AAAI-97. (See


    http://www.dcs.qmw.ac.uk/~mps/pubs.html
under the Robotics heading.)

From: Erik Sandewall

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. 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 (integers and reals, in particular). This approach was introduced in systematic fashion by Yoav Shoham. It has been continued under the banners of "features and fluents" (in my own group) and "event calculus" (Shanahan, Miller, and others). To check off your points, we do model the world with successive and (if applicable) continuous change, we are able to reason about exogenous events, and of course we can combine prediction, postdiction, planning, and so on in the same formal system. Also, we do use pairs of numbers to characterize intervals. It is true that the classical Kowalski-Sergot paper from 1986 about the event calculus is formulated in terms of intervals and does not mention metric properties, but the more recent event-calculus literature uses timepoints and defines intervals as pairs of timepoints.

With respect to worlds where there is change that's not being caused by actions, see my KR 1989 paper which proposes how to embed differential calculus into a nonmonotonic logic, and to generalize minimization of change to minimization of discontinuities for dealing with mode changes in a hybrid world. See also the IJCAI 1989 paper which shows how to reason about actions in the presence of such external events, under uncertainty about their exact timing. The same general approach has been pursued by Dean, Shanahan, Miller, and others, and Murray Shanahan's award paper last year shows that this is now a very productive line of research.

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, if we agree about the shortcomings of sitcalc, it might also be interesting to discuss why it has been able to maintain its dominance for so long. What kind of inertia is at work here?

Also, with respect to your first observation:

Knowledge-hackers try to formalise an intuition using logic A and find it hard to match formal inference against intuition no matter how ingenious they are with their ontologies and axioms; so they turn to logic B, which enables them to hack the examples to fit intuition rather better...

this is true, of course, but 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:

In this way, we don't have to validate the logics against the ill-defined notion of common sense. As an additional step may also be appropriate, namely, to compare 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.

With respect to your final point:

... when do we decide that something warrants the title of "theory/ approach/ formalisation.."? The sit. calc. is just a style of writing axioms, and the Allen algebra is just a complicated way to arrange order relationships. These seem to be little more than what Apple tried to sue IBM for, ie something like a 'look-and-feel'.

it seems to me that what really counts in the long run is things like proven range of applicability results, proven methods for transforming logic formalizations to effectively computable forms, etc. However, we can't avoid the fact that whoever writes a paper using formalization F is well advised to include the standard references to where the formalization F was first introduced and defended. Again, Leora's question about staying power becomes significant: if introducing a new formalism can give you a high Citation Index rating for very little work, what are the factors that dictate success and failure for formalizations? Does a formalization win because it solves problems that previously proposed formalizations didn't - or is it more like in the world of commercial software, where people tend to go for the de facto standard?

From: 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.