| Vol. 1, Nr. 3 | Editor: Erik Sandewall | 31.10.1997 |
New initiatives |
ETAI Newsletter develops | ||
ETAI Publications |
Received research articles | ||
| Received research notes | |||
Debates |
NRAC Panel on Theory Evaluation | ||
| NRAC Panel on Ontologies for Actions and Change | |||
New initiatives |
Dated: 21.10.1997
Today the Newsletter begins the on-line continuation of NRAC panel discussions. This year's NRAC workshop (Nonmonotonic Reasoning, Action and Change) at IJCAI had a panel on "Theory Evaluation" that was organized by Leora Morgenstern and which tried to address the question "What should be considered as a good theory in our area of research?" This is a very important question also from the point of view of the ETAI -- it fundamentally defines the questions that ought to be asked in the open discussion and the subsequent refereeing of ETAI submitted articles. The full position statements of the three panelists are reproduced below. We look forward to your questions to the panel and your other comments about this topic.
The other contents of this Newsletter issue is a summary by Michael Thielscher of his article "A Theory of Dynamic Diagnosis", which in itself was received and reported earlier this month. The use of such summaries or short extended abstracts (about two pages of text) has been introduced by the ETAI in order to facilitate for its readers to follow all the new results that arrive. Besides being advertised in the Newsletter and News Journal, summaries are also linked in the discussion page for each article. We hope that the summary will make it easier to see what the article is about and facilitate the discussion about it.
Dated: 22.10.1997
The panel discussion on Theory Evaluation which started yesterday has received a contribution from Pat Hayes, which is included in today's Newsletter. We also have a summary of the article by Kakas and Miller which was received a few days ago.
Dated: 23.10.1997
The discussion about Theory Evaluation continues with three responses to Pat Hayes's contribution:
Dated: 24.10.1997
Today's newsletter contains a question to the authors of the article by Kakas and Miller that was received a week ago. It is an example of how the Newsletter serves one of the key ideas in ETAI: that of exposing submitted articles to discussion in our research community before it is sent to the referees.
Dated: 27.10.1997
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.
Dated: 30.10.1997
It is very fascinating to see this Newsletter develop! Gradually, a new form of scientific communication is taking shape. Today's issue contains the answers of authors Kakas and Miller to three questions about their paper, namely two questions which were stated in issues a few days ago, and one question which is also in today's Newsletter. This is really in the spirit of a global, on-line scientific colloquium, where physical distance doesn't count.
The other interesting thing is that we see the emergence of "midi" size contributions - significantly shorter than the conventional article, but significantly bigger and more thought out than the plain, newsgroup style message. Both in the answer by Kakas and Miller to the question by Thielscher, and in today's question by Costello, the authors decided to package the core of their arguments as separate research notes. These notes are attached to the immediate contributions, but will be published in a more journal-like style so that they can be cited in their own right.
This development is a natural consequence of the rapid pace of our medium: when the turnaround is counted in days or even hours, instead of months, then there is no occasion to write full articles in each cycle. Conversely, although traditional journals often maintain a section for "research notes", their use is much more restricted in the journals because of the publication delays.
Besides the continued discussion about the Kakas/Miller article, we also feature a contribution by Pat Hayes on the topic of ontologies.
Dated: 31.10.1997
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 |
Dated: 7.10.1997
The following article has been received by the present ETAI
area,
which means that it will be open for a three-month discussion period,
followed by the closed peer-review decision on whether it will be
accepted by the ETAI. All readers of this Newsletter are invited
to participate in the discussion.
Please don't be shy to ask questions; it is actually in the author's
interest to receive tough questions. Just like at an internal seminar,
they give him or her a chance to show that he/she is able to answer
well, and they give valuable feedback. Also, since the article has
already been published (but not yet refereed), it is citable from
now on, so tough questions do not deprive the author of being
"on record" with the article.
Clicking the title of the article leads to the official cover page
where it was published, with links e.g. to its full text.
Clicking "[interactions]" leads to the on-going question-answer
debate about the article, with options for submitting a question
or comment to the present Newsletter editor.
Abstract: Diagnosis is, in general, more than a mere passive reasoning task. It often requires to actively produce observations by performing a test series on a faulty system. We present a theory of diagnosis which captures this dynamic aspect by appealing to Action Theory. The reactions of a system under healthy condition are modeled as indirect effects, so-called ramifications, of actions performed by the diagnostician. Under abnormal circumstances - i.e., if certain aspects or components of the system are faulty-one or more of these ramifications fail to materialize. Ramifications admitting exceptions is shown to giving rise to a hitherto unnoticed challenge - a challenge much like the one raised by the famous Yale Shooting counter-example in the context of the Frame Problem. Meeting this challenge is inevitable when searching for "good" diagnoses. As a solution, we adapt from a recent causality-based solution to the Qualification Problem the key principle of initial minimization. In this way, when suggesting a diagnosis our theory of dynamic diagnosis exploits causal information, in addition to possibly available, qualitative knowledge of the a priori likelihood of components to fail.
Some of the results in this paper have been preliminarily reported in (Thielscher, 1997a).
Dated: 21.10.1997
The following summary contains a number of formulae which are difficult to reproduce in plain text, and where approximate notation has been used. For fully correct formulae, please click to the postscript version.
Dated: 21.10.1997
Summary: Diagnosis in general requires more than just passively observing the behavior of a faulty system. Often it is necessary to actively produce observations by performing actions. Diagnosing then amounts to reasoning about more than a single state of the system to be examined. We propose to capture this dynamic aspect by appealing to Action Theory. A formal system description consists of a static and a dynamic part. The former introduces the system components and their static relations in form of so-called state constraints, like, for instance,
active(relay1) == closed(switch1)
stating that a particular relay is active if and only if a
corresponding switch is closed. The dynamic part of a system
description specifies the actions which can be used to manipulate the
system's state. These definitions are accompanied by so-called action
laws, which focus on the direct effects. State constraints like the
above then give rise to additional, indirect effects of actions, which
we accommodate according to the theory of causal relationships
[Thielscher, 1997b]. E.g., this causal relationship is a consequence
of our example state constraint:
closed(switch1) causes active(relay1)
Informally speaking, it means that whenever
closed(switch1) occurs as direct or indirect
effect of an action, then this has the additional, indirect effect that
active(relay1). Generally, causal relationships
are successively applied subsequent to the generation of the direct
effects of an action until a satisfactory successor state obtains.
In this way, the reactions of a system under healthy condition are modeled as indirect effects, so-called ramifications, of actions. Under abnormal circumstances---i.e., if certain aspects or components of the system are faulty---one or more of these ramifications fail to materialize. We introduce an abnormality fluent ab by which we account for such exceptions to both state constraints and the ramifications they trigger. Thus our example constraint from above, for instance, may read weaker---e.g., to the effect that
-ab(resistor1) & -ab(relay1) -> [active(relay1) == closed(switch1)]
where ab(resistor1) and ab(relay1) represent an abnormal failure
of a corresponding resistor and the relay itself, respectively. This
weakening transfers to our expectations regarding indirect effects:
The aforementioned causal relationship becomes
closed(switch1) causes active(relay1) if -ab(resistor1) & -ab(relay1)
An important contribution of this paper, now, is a proof that due to
the phenomenon of causality straightforward global minimization of
abnormality---which is suitable for static diagnosis---is problematic
in case of dynamic diagnosis. This raises a challenge much like the
one raised by the famous Yale Shooting counter-example in the context
of the Frame Problem. Meeting this challenge is inevitable when
searching for `good' diagnoses.
As a solution, we adapt from a recent causality-based solution to the Qualification Problem the key principle of initial minimization. All instances of the abnormality fluent are assumed false initially but may be indirectly affected by the execution of actions. In this way, our theory of dynamic diagnosis suitably exploits causal information when generating diagnoses. Our theory moreover respects available knowledge of the a priori likelihood of component failures. Since it is often difficult if not impossible to provide precise numerical knowledge of probabilities, we deal with qualitative rather than quantitative information, and we do not rely on complete knowledge. Such possibly incomplete information as to different degrees of abnormality is formally represented by a partial ordering among the instances of the abnormality fluent.
For the entire theory there exists a provably correct axiomatization based on the Fluent Calculus paradigm and which uses Default Logic to accommodate the nonmonotonic aspect of the diagnostic problem.
Abstract: The Language E is a simple declarative language for describing the effects of action occurrences within a given narrative, using an ontology of actions, time points and fluents (i.e. properties which can change their truth values over time). This paper shows how E may be extended to deal with ramifications. More precisely, we show how Language E domain descriptions can include statements describing permanent relationships or constraints between fluents, and how the model theoretic semantics of E can be extended in an intuitive way to ensure that the effects of actions are appropriately propagated via such statements, whilst retaining E's simple approach to the frame problem. We also show how Event Calculus style logic programs may be used to compute consequences of such domain descriptions using standard SLDNF, even when only incomplete information is given about some initial state of affairs. Because of E's generality, these techniques are easily adaptable to other formalisms for reasoning about actions, such as the Language A and the Situation Calculus.
Various Prolog program listings associated with this paper are also available from http://www.dcs.qmw.ac.uk/~rsm/abstract15.html
Dated: 22.10.1997
Address of Antonis Kakas:
Department of Computer Science, University of Cyprus,
75 Kallipoleos Street, P.O. Box 537, CY-1678 Nicosia, CYPRUS
Email: antonis@turing.cs.ucy.ac.cy
WWW:
http://www.ucy.ac.cy/ucy/cs/webPages/PEOPLE/faculty/kakas.htm
Address of Rob Miller:
Department of Computer Science, Queen Mary and Westfield College,
University of London, Mile End Road, London E1 4NS, U.K.
Email: rsm@dcs.qmw.ac.uk
WWW: http://www.dcs.qmw.ac.uk/~rsm/
This paper shows how the Language E [Kakas and Miller, 1997] may be extended to deal with ramifications, and how domain descriptions written in this extended language may be translated into Event Calculus style logic programs. These programs are shown to be sound even when only incomplete information is given about some initial state of affairs.
The Language E was developed partly in response to the Language A [Gelfond and Lifschitz, 1993], which was introduced as the first in a family of "action description languages". Action description languages (such as A) inherit an ontology from the Situation Calculus, whereas the Language E inherits its ontology (which includes an independent flow of time) from Kowalski and Sergot's Event Calculus [Kowalski and Sergot, 1986]. E can therefore be regarded as a basic or kernel "event description language". It was developed in the belief that the use of, and comparison between, different ontologies is important in the study of formal reasoning about actions. The semantics of E, like that of A, is model-theoretic, and divorced from computational considerations.
The paper begins by reviewing the basic Language E. E's vocabulary includes a set of fluent constants, a set of action constants, and a partially ordered set of time-points. Basic Language E domain descriptions can include three types of propositions: t-propositions ("t" for "time point"), h-propositions ("h" for "happens"), and c-propositions ("c" for "causes"). For example, the following domain description (about taking a photograph) contains 1 t-proposition, 3 h-propositions and 2 c-propositions:
The model theoretic semantics of E ensures that (for example) this domain description entails the t-proposition
The notions of an "initiation point" and a "termination point" are central to E's semantics. For example, in all models of the above domain, 2 is an initiation point for "Load" and 8 is an initiation point for "Picture". Time can be discrete or continuous, and need not be linear. Indeed, as a special case time may be modelled as a branching structure of sequences of action constants. This allows the "simulation" in E of the Language A, by writing and reasoning about t-propositions such as
The remainder of the paper discusses an extension of E to include a forth type of statement called an r-proposition ("r" for "ramification"). R-propositions express permanent constraints or relationships between fluents. In formalisms which allow for such statements, the effects of actions may sometimes be propagated via groups of these constraints. This gives rise to the "ramification problem", i.e. the problem of adequately and succinctly describing these propagations of effects whilst retaining a solution to the frame problem.
R-propositions are statements of the form
The intended meaning of this statement is "at every time-point that {L1, ..., Ln}, L holds, and hence every action occurrence that brings about {L1, ..., Ln} also brings about L". Hence the semantics of E is extended so that from a static point of view r-propositions behave like classical constraints, but they are unidirectional in terms of the way they propagate temporal change initiated by action occurrences. This is achieved in the main by appropriately extending the definitions of an initiation and a termination point. These definitions are now recursive, or in terms of least fixed points. R-propositions thus provide a simple, succinct method of expressing domain constraints, and the corresponding semantics behaves in a satisfactory way for a range of examples found in the literature.
The use of r-propositions is illustrated in the paper with two examples. The second of these is Thielscher's electric circuit example [Thielscher, 1997]. This example is of interest because it presents difficulties for what Thielscher describes as "categorisation-based" approaches to ramification. In the (Language E version of the) example, the permanent configuration and dynamic behaviour of an electric circuit is described by r- and c-propositions such as
If "Switch2" already holds (i.e. switch number 2 is connected) and a "CloseSwitch1" action occurs, say at time-point T1, the extended semantics of E ensures that (in all models) the effect of this event is propagated through the first of the r-propositions above, so that "Light" becomes true. This is because the least fixed point definition of an initiation point ensures that T1 is an initiation-point for "Switch1", and hence (by the recursive definition) an initiation point for "Light" by the first r-proposition above.
The paper gives a translation method from E domain descriptions into logic programs, and gives a proof of the correctness of the translation (as regards derivation of t-propositions) for a wide class of domains. As in [Kakas and Miller, 1997], over-zealous application of logic programming's closed world assumption is avoided by representing negated fluents inside a meta-level "HoldsAt" predicate. For example, "Relay holds-at 2" is translated as "HoldsAt(Pos(Relay),2)" and "¬Relay holds-at 2" is translated as "HoldsAt(Neg(Relay),2)". C-propositions such as "CloseSwitch2 initiates Switch2 when {¬Relay}" are translated into two clauses:
Initiates(CloseSwitch2,Switch2,t) <-
HoldsAt(Neg(Relay),t).
PossiblyInitiates(CloseSwitch2,Switch2,t) <-
not HoldsAt(Pos(Relay),t).
The first of these clauses gets used to compute changes in the truth value of "Switch2" and other fluents via occurrences of "CloseSwitch2". The second gets used in the computation of persistence of truth values. (Similar techniques are used in a number of other logic program translations of action formalisms.)
A soundness property is proved for the logic program translations of a general class of domain descriptions, which may include r-propositions. It is stated in terms of SLDNF-derivability: if there is a finite SLDNF derivation of "HoldsAt(Pos(F),T)" (respectively "HoldsAt(Neg(F),T)") from the program, then "F holds-at T" (respectively "¬F holds-at T") is entailed from the original domain description.
For the examples given in the paper, these logic programs are more-or-less directly executable in Prolog. The relevant Prolog listings are available at http://www.dcs.qmw.ac.uk/~rsm/abstract15.html
Dated: 7.10.1997
Please click for a list of all received articles in a plain web page, or for a page using frames.
Paolo Liberatore
Compilability of Domain Descriptions in the Language A.
[Interactions]
Dated: 31.10.1997
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 |
Dated: 21.10.1997
The NRAC workshop (Nonmonotonic Reasoning, Action, and Change) at this this year's IJCAI featured three panel discussions. It was agreed at the workshop to continue some of the panels as on-line discussions on the web, and we are now ready to do that in the present Newsletter. Our present issue contains the introductory position statements of the three panelists, almost exactly the way they circulated them to each other before the workshop.
The idea is to proceed in a way that is similar to the familiar conference panel format: there can be exchange of opinions by the panelists, questions and comments from the "floor" (that is, all the readers of this Newsletter), and quite possibly a lot of constructive disagreement. As usual, contributions should be sent to the present Newsletter editor; they will be edited and distributed in forthcoming issues of the Newsletter, and accumulated into the News Journal for October and later months.
Since there may be a great variation in the size of the contributions, we shall distinguish two orders of magnitude. Notes of one or a few pages will be formatted as separate entities which can be individually cited and linked to. Telegrams of at most 20 lines or so are used for simple questions, answers, and opinions. If the notes get to be too long, then only excerpts of them will be sent in the Newsletter, with a reference to the rest of the text which is found in the web page.
The three position statements follow -- questions and comments are welcome.
Questions and issues to be discussed are divided into 2 broad categories:
What makes a theory of nonmonotonic reasoning, action, and/or change a good theory? (These may be the same things that make any AI theory good.) Do we judge a theory by
What gives a theory staying power? What are some examples of theories with staying power? Are these always the good ones? Specifically, are there examples of good theories which didn't last very long in the AI community? Examples of bad theories which did last long? (And who will be brave enough to identify these ;-))
Thirty-five years ago, Thomas Kuhn suggested that the history of science is best understood as a cycle of periods of "normal science" followed by "revolutionary science." It works as follows: A theory is developed which solves some problems. The theory is associated with a "paradigm," which is, to quote Kuhn, "the entire constellation of beliefs, values, techniques, and so on shared by the members of a given community." As time goes on, new problems are discovered which the theory doesn't solve; the theory is modified slightly, and the process continues, until all of a sudden, it becomes apparent to some that the old paradigm just doesn't work. Then comes the "revolutionary" phase, in which a new paradigm is suggested and refined, and the "normal" phase starts again. (The classic example of this is the geocentric theory of the universe, which explained certain phenomena; as new phenomena were discovered, this theory had to be modified (epicycles and deferents), until it became clear (to Copernicus, Galileo, Kepler, etc.) that the geocentric theory just wouldn't work. The revolutionary phase supplanted the geocentric paradigm with the heliocentric paradigm, which then became normal science.)
Questions: can we understand the history of our field in this way? If so, are we in a "normal" phase or a "revolutionary" phase? Can we identify any such phases? Or are we still in one of the prehistoric phases?
Or -- perhaps we are better off viewing our history from another perspective. Lakatos suggests that there's no one "normal" paradigm at any one time, but a number of competing research programmes. What unites these programmes is a core set of assumptions; however, there are different auxiliary assumptions. What research programmes can we identify? Do we subscribe to a core set of beliefs? Which programmes, to use Lakatos's terms, are progressive? Which are degenerative? Have any become degenerative and then popped back to being progressive?
Or should we subscribe to Laudan's description of "research traditions" which deny a core set of beliefs, but assert a common set of ontological assumptions and a common methodology for revising old theories and developing new ones?
Any other suggestions?
Is it worthwhile going through this exercise at all? It could be argued that the major developments of physics, astronomy, biology, occurred without much introspection at all, and this is perhaps valueless. On the other hand, we could argue that given the miserable state of research in nonmonotonic reasoning and action today, we need all the analysis and introspection we can get.
Any more ideas?
Finally, if you want to get into the swing of theory evaluation, you may want to look at: Erik's book (Features and Fluents) My article "The Problems with Solutions to the Frame Problem" available at http://www-formal.stanford.edu/leora (available also in the collection of papers "The Robot's Dilemma Revisited", Ablex, 1996, but the web is more accessible).
In order to go about evalation, we have to make our goals clear. (If it doesn't matter where you want to get to, it doesn't matter much which way you go, to paraphrase Lewis Carrol). There are two quite different goals people have in building KR system; there is much confusion generated by not making it clear what you are doing (so much so that the researchers who take one view often don't understand what the others are doing and why). These are:
1. A knowledge representation as a modelling language. If you have a domain in your head you can use the KR to represent that domain. The builder of a KR is expected to give a user manual on how to axiomatize the domain. There are right ways of saying something and there may be wrong ways of saying it. Missing knowledge may mean something. Prolog and Bayesian networks are examples of such knowledge representations.
2. A knowledge representation as a repository of facts for commonsense reasoning. Under this scenario, you assume you are given a knowledge base and you are to make as much sense out of it as possible. It isn't OK for the designer of the KR to prescribe how a domain should be axiomatized. The KR should be able to get by with whatever knowledge it has. Much of the nonmon work assumes this (as far as I can see).
If you goal is the first, you probably want a very lean language which doesn't provide multiple ways of doing the same thing. You want to provide a recipe book about how to go about modelling a domain. It should be judged by whether someone can go from an informal problem (not a representation of a problem) to a solution efficiently. Does it provide a good way to think about the world? Can it exploit any structure of the domain for efficiency?
If your goal is the second, you probably want a rich language that lets you state as much as possible. It should be some free-form language that doesn't constrain you very much. Here we need to go from a representation of a problem into a solution. Does it provide reasonable answers? Can the user debug the knowledge base if an aswer is wrong?
I have two ways of judging a representation:
Research results presumably come in several colors and shapes; I am thinking of categories such as the following:
To the extent that we have this kind of solid results, we can evaluate proposed theories (= formalism + semantics + entailment method ??) with respect to their range of applicability and their computational properties.
With respect to David's distinction between knowledge representations that are modelling languages and those that are intended for repositories of common-sense facts, my heart is with the former kind. Among the above categories of results, those that concern or make use of a formal semantics probably only make sense in the context of a modelling language, since the notion of common sense is so vague and inherently difficult to capture.
So, to turn to more practical matters:
Leora writes:
What makes a theory of nonmonotonic reasoning, action, and/or change
a good theory? (These may be the same things that make any
AI theory good.) Do we judge a theory by
Well surely we need to first focus on what problems we are expecting it to solve. Suppose someone in this field were to announce that they had the whole thing finished, all the problems solved, etc. What tests would we ask them to pass before we believed them? What do we expect these nonmonotonic logics to be able to DO, exactly?
Its not enough to just say, 'to reason properly'. We need some characterisation of what that proper reasoning is, or at least some examples of where it can be found. For 25 years we have been appealing to a vague sense of intuitive reasonableness, but this is a very weak basis to test theories on. Even linguists, whose empirical methods are treated with ridicule by experimental psychologists, have some statistical data to back up their 'seems-grammatical-to-native-speaker' criteria, but 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.
One worry I have is that it seems to be impossible to test a logic or formalism as such, since the intuitiveness or otherwise of any example depends as much on the way the intuition is encoded in that logic as on the logic itself. Logics seem to require a kind of two-stage evaluation. 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. But the intuitive test is always of the axioms/ontologies, not of the logics themselves: there is always the possibility that a more ingenious hacker could have gotten things right with logic A, if she had only thought of the right ontological framework. For example, it has become almost accepted as revealed truth in this field that common sense reasoning isnt compatible with monotonic logic, because of examples such as if you are told that an automobile exists then you infer that its in working order, but if you later hear its out of gas you change your mind. (Or if you hear its only a toy bear, or a penguin, etc.) All of these examples assume that the new knowledge is simply conjoined onto the previous knowledge: you know some stuff, new stuff arrives, and you just chuck it into the set of mental clauses and go on running the mental inference engine. But maybe the updating process is more complicated than that. Maybe when you hear that the car tank is empty, you don't just add some new information, but also remove some previous assumptions; and maybe this is not part of the reasoning process but of the linguistic comprehension process. If so, then the representation may, perhaps, be able to use monotonic logic perfectly happily. Maybe not; but my point is only that the argument that it must be nonmonotonic makes assumptions about other mental processes - specifically, those involving the integration of new information - which have not been examined critically.
What gives a theory staying power? What are some examples of theories with staying power? Are these always the good ones? Specifically, are there examples of good theories which didn't last very long in the AI community? Examples of bad theories which did last long? (And who will be brave enough to identify these ;-))
I'll take on that onerous task. At the risk of treading on almost everyone's toes, let me propose the situation calculus; or more properly the idea behind it, of describing change in terms of functions on world-states. "Bad theory" 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. And even its critics - for example, Wolfgang Bibel's recent IJCAI survey gives an alternative approach based on limited-resource logics - seem to me to miss the essential things that are wrong with it.
This deserves a much longer treatment, but 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. Sitcalc belongs with SHAKEY, in a world where only the robot can move and nothing else is happening.
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. (Consider how to describe the growth of a plant in sitcalc. It seems easy enough: something like this might be a beginning:
(Alive(p, s) & Height(p,s)=h & Watered(p,s)) =>
(Alive(p, grow(s)) & Height(p, grow(s)) = h)
But in the sitcalc this would mean that there was an action called
'grow'. (All gardeners would find this action very useful, no doubt.)
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. (This conception of intuitive thought as being a progressive inferential progress in a past-to-future direction has been responsible for many other blind alleys, such as much of the work on principles for 'maintaining' truth as long as possible.)
Most intuitive reasoning done by humans lies entirely outside the purview of the situation calculus. 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, while entire libraries are devoted to overcoming artificial problems, such as the frame problem and the YSP, which only arise in the sitcalc framework. 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; they are all concerned with how to keep track of what is true in what 'state' .
Then, Erik writes:
What Should Count as a Research Result in our Area?.
I want to focus on Leora's first issue - criteria for the evaluation of
theories, and I think the first thing to discuss is what could or should
reasonably count as a research result in our area, that is, what things
ought to be citable in the literature. "Citable" means that they are
crisp, have a lasting value, that later researchers can build on earlier
results, etc. Then, presumably, some of the respectable research results
are those which tell us something about the qualities of a particular
theory/approach/formalization/...
Yes, but 'theory' is crucially ambiguous here. 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. Examples of actual formalizing are usually given as counterexamples to some conjectured technique rather than as things to be studied and compared in their own right.
There's nothing wrong with metatheory, provided there is something there for it to be the metatheory of. Right now, the chief problem with this field is that we've run out of subjectmatter. McCarthy set out in a pioneering direction, but instead of continuing his movement, we've set camp and are arguing interminably about what kind of compass to use. Let's get some actual knowledge represented, and only then study how it works and fit our theories to the things we find.
For example, here's an issue which might have some meat on it. Erik mentions Allen's time-interval algebra. Now, timepoints and intervals are a pretty simple structure, mathematically speaking, but nevertheless Allen's algebra has its problems. In particular, its not really compatible with the usual view of intervals as sets of points on a line -- for details, see
http://www.coginst.uwf.edu/~phayes/TimeCatalog1.ps
http://www.coginst.uwf.edu/~phayes/TimeCatalog2.ps
I used to be convinced, all the same, that having intervals as a basic
ontological category was fundamentally important, and spent a lot of time
finding ways to show that certain interval theories were reducible to
others and that points were definable in terms of intervals, etc.. But when
I try to actually use these concepts to write axioms about clocks,
timedurations, calendars and dates, I find that in fact the concept of
interval is almost useless. One can think of an interval as just a fancy
way to talk about a pair of points; and when one does so, the entire Allen
apparatus just dissolves away into a simple theory of total linear order,
all the axioms become simpler (for example, instead of writing 'duration
(between(p,q))' one simply writes 'duration(p,q)'; there is no need to
refer to the interval defined by the endpoints) and everything becomes
clearer and more intuitive (for example, many quite natural relations on
intervals become awkward disjunctions in the Allen framework, such as
{before, meet, overlap, start, equal}, which is p1 => p2 ). So maybe there
isnt much use to the concept of 'interval' at all: or, more exactly, since
Allen intervals can't be thought of as sets of points but are uniquely
specified by their endpoints, maybe thats really all they are, and the
elaborate Allen theory is like the Wizard of Oz.
So, two points. First, in response again to Erik, 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'.
Second, more substantially: this is all because time is one-dimen\-sional. I bet the story for spatial reasoning will be quite different, as there is no way there to encode the topology into an ordering. Now, what kinds of action and change make essential reference to two- or -three-dimensional things, and how can we formalise these? For example, consider the verbs 'spread', 'cover', 'surround', 'embed', 'emerge','penetrate' and similar actions that refer to a change in some spatially extended relation. Any ideas on this? Has anyone in this area even considered such actions/changes?
Answer from: Murray Shanahan on 23.10.1997
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.)
Answer from: Erik Sandewall on 23.10.1997
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:
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?
Answer from: Ray Reiter on 23.10.1997
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.
Answer from: Pat Hayes on 31.10.1997
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:
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.
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.
From: Mikhail Soutchanski on 27.10.1997
"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'').
From: Murray Shanahan on 28.10.1997
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.
From: Erik Sandewall on 28.10.1997
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.
From: Pat Hayes on 30.10.1997
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.
Answer from: Pat Hayes on 31.10.1997
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