A Review of Murray Shanahan's Bookby Erik SandewallMurray Shanahan's book "Solving the Frame Problem" (MIT Press, 1997) describes the historical development of the situation calculus and the event calculus approaches to reasoning about actions and change. The book is well organized: it proceeds stepwise through different aspects of the frame problem and presents several approaches to its solution. Along the way, Shanahan also gives clear, concise introductions to predicate logic, to circumscription, and to logic programming. The technicalities of these prerequisites are kept to a minimum and are presented in the context where needed, which contributes to the ease of reading the book's 400 pages. Shanahan's book addresses the major recognized difficulties in reasoning about actions and change: incomplete narratives, nondeterministic effects, ramification, concurrent events, explanation of observations, and so on. It also describes many of the techniques that have been proposed for dealing with these difficulties, such as chronological minimization, explanation closure, occlusion (= releasing), and filtering. As Shanahan correctly points out, these techniques are largely independent of the choice of calculus (situation calculus, event calculus, and so forth) that is being used. The specialist in the area will find that the book is a well written exposition of familiar material, and it certainly fills a need in that respect. For researchers in other parts of AI, and in other parts of applied logic, it offers a comprehensive presentation of the state of the art in reasoning about actions. The book therefore represents an important step forward for research in this field. Shanahan adopts, and argues for the example-based methodology, where approaches to formalizing actions are explained and motivated through a small number of scenario examples, and where an existing approach can also be refuted by showing an example where it does not provide the intended conclusions. Some of the research in this area uses another, systematic approach, where one attempts to characterize the properties of various known approaches: for which types of worlds does a proposed logic give correct results (range of applicability results); what transformations on the logic are correct (for example, transformations to a circumscriptive formulation), and so on. The example-based and systematic methodologies need not be mutually exclusive. It is perfectly possible, and in fact advisable, to use them together. The advantage of the systematic methodology is that it begins, at least, to answer the question that any user of these logics is likely to ask: "which one of all those approaches is the best one for my needs?" Without such an analysis, this research merely provides a menue of alternatives, with little guidance for the user. It is a pity that Shanahan has not taken the opportunity to include any assessment results in his book, not even on an informal level. After all, we do know that chronological minimization is correct if all actions are nondeterministic; we also know that occlusion (or an equivalent device) is necessary for the general case of nondeterministic actions, and so on. It would have been easy, in a book with this structure, to show how difficulties are systematically related to techniques. Shanahan's omission in this respect is even more surprising in view of the book's subtitle: "A Mathematical Investigation of the Common Sense Law of Inertia". Assessment results, of the kinds just mentioned, have a reasonable generality and require a certain degree of mathematical investigation. The plentiful formal propositions in this book, by contrast, are only statements about one particular toy example at a time (except for theorems about nonmonotonic logics in general). The subtitle does seem a bit out of place, therefore. The author explains his methodological stance in the preface, as follows:
It is not clear how the deployment of a proposed design in a working
system will help us understand reliably how the same design will work
in another working system, for another application, which is what we
will need to know for engineering purposes. With respect to the choice
of framework - there is one single "abstract framework" that has been
used extensively for this purpose, namely state transition systems
and various generalizations of them (for example, systems that map
state Therefore, it is not a circular exercise to asses logics for actions and change relative to a transition-system framework. On the contrary, doing so provides a better understanding of when the logic works correctly and when it doesn't, and it helps relate research in this area to neighboring disciplines. Shanahan's strict adherence to only one of the two methodologies is therefore unfortunate. The book centers on the situation calculus and the event calculus, as the author also points out in the preface. This may partly explain the author's methodological stance, since exactly those two traditions have not (to my knowledge) defined their semantics in terms of transition systems or some other abstract world model. The development of those two traditions is described historically, even including "dead end" approaches that are no longer in use. This makes for easy reading, but in the event calculus part it is unfortunately misleading. The history of the event calculus is described as follows. The `original' event calculus was introduced by Kowalski and Sergot in 1986. Because of its various weaknesses, it was succeeded by the `simplified' event calculus (Eshgi 1988, Shanahan 1989, Kowalski 1992, using the same references as in the book). Much of the notation was changed in the new calculus, and the logic programming basis was replaced by a standard nonmonotonic first-order logic using circumscription or preferential entailment.
What Shanahan misses, or fails to acknowledge, is that many of the
designs of the `simplified' event calculus had already been proposed
or were developed concurrently under other names. The use of linear,
metric time had been advocated by Shoham since 1986. The combination
of the Any author has to restrict his topic in order to finish his work in finite time, and Shanahan is not to be blamed for imposing restrictions on his. It is unfortunate, however, that he has chosen restrictions that are based on label and not on content, for by doing so he misses and leaves out an important part of the total picture in this field of research. These critical comments illustrate that, not surprisingly, the field of actions and change is characterized by a multiplicity of approaches and less than total agreement about methodology; the present reviewer does differ from the book's author on several accounts. However, it must be said again, like in the opening paragraphs, that Shanahan's book is an excellent piece of work, and it is cordially recommended as a textbook for advanced graduate courses as well as for any researcher interested in logics of actions and change.
Editor:
Erik Sandewall, Linköping University, Sweden. |