Because the authors believe that “progress in developing plan reasoning systems in realistic worlds depends not so much on issues of search (although search is obviously important) but on progress in representing more complex world situations,” their formalization of plan reasoning systems emphasizes representational issues. The explicit temporal representation makes it possible to represent more complex worlds more naturally and to formalize all previous work in the field.
The book contains four chapters. In the first, James F. Allen presents the temporally based explicit representation and a uniform general planning framework on which the rest of the book is based. The formalization of plan recognition is presented in the second chapter. The third chapter formalizes planning with simultaneous actions and external events. Chapter 4 deals with the formalization of the abstraction used in plan construction.
Chapter 1 begins by motivating Allen’s alternative temporally explicit world representation. He reviews many current state-based planning systems in regard to their assumptions about world representation. The emphasis is on how those assumptions limit the range of problems the systems can handle. His conclusion is that many common planning situations of interest in realistic domains cannot be handled without a temporal representation. In the second section, a temporal logic and the underlying time representation are described and defined in an axiomatic form. The third section deals with the representation of knowledge about action.
The fourth section explains how to specify a planning system using temporal logic. In the fifth section, Allen develops a nonlinear deductive planner. After some examples of the basic techniques for plan generation, a nondeterministic version of the planning algorithm is given. Some examples reveal the limitations of traditional backward chaining planners in contrast with the author’s approach. In the last part of the chapter, a hierarchical planner is specified by extending the explicit temporal representation.
Chapter 2, “A Formal Theory of Plan Recognition and Its Implementation,” by Henry A. Kautz, presents a general logical formalism for the recognition of plans of stereotypical behavior. The observer (recognizer) must infer the agent’s intentions from some of its actions; the agent’s activities are not deliberately structured in order to make its intentions clear; the observer has complete knowledge of the domain; only correct plans are recognized; and plans are recognized deductively based on observations, the recognizer’s knowledge, and some assumptions. The observer’s knowledge is represented by a set of axioms that define various types of relationships among events.
A formal logical definition of the event hierarchy is given and supported by an example from cooking. Then the formal theory of recognition is presented. The set of closed-world assumptions on which the recognition is based is formally presented, and a model theory for plan recognition is developed on the basis of the model theory of circumscription. Some algorithms for plan recognition that implement the formal theory are given. The chapter ends with some conclusions about the limitations of the theory.
In the third chapter, “Planning with Simultaneous Actions and External Events,” by Richard N. Pelavin, the formalism from chapter 1 is extended to provide a formal basis for planning with concurrent actions, external events, and an incomplete world description. Pelavin views an action as an “action instance,” that is, an action at a specified time, and he views a state as a “world-history,” which captures exactly what the planning agent does and what is happening in the external world at all times. The world-history can be interpreted as the context in which the execution of an action instance is specified.
Pelavin reviews some logics in regard to their limitations in handling simultaneous events and partial or imprecise world description. The third part of the chapter presents a semantic model based on the interval logic structure from chapter 1. Next, Pelavin deals with the definition of correctness criteria for a planner and the specification of a planning problem within the formalism. He adapts the planning algorithm from chapter 1 in order to deal with partial or imprecise world descriptions and to handle concurrent interaction. Some efficiency issues are discussed. The chapter ends with two appendices. The first presents a clear formal description of the semantic model and its logic, and the second gives axioms and inference rules of a proof theory.
Josh D. Tenenberg’s chapter on “Abstraction in Planning” mainly formalizes two forms of abstraction used in plan construction: inheritance abstraction and relaxed model abstraction. The formalism is based on the state-based representation and on a search strategy that observes the map, plan, inverse-map (MPI) paradigm, that is, abstract the initial state and operators (map), solve the problem at the abstract level (plan), and guide the search at a concrete level by using the abstract solution (inverse-map). A detailed description of a rigorous formalism adapted from Lifschitz’s formalization of the well-known STRIPS planning system is given.
The next part of the chapter presents a formal method for inheritance abstraction. The author proposes to extend the inheritance abstraction from objects to actions to conform to the MPI paradigm and to abstract a STRIPS system. An example of a simplified kitchen domain illustrates the method. The third part of the chapter deals with another abstraction method, the relaxed model, characterized by the removal of precondition constraints during the ascent of the abstraction hierarchy. By extending STRIPS systems, the author formalizes Sacerdoti’s ABSTRIPS system. Because abstraction mapping can unintentionally introduce inconsistency, a set of domain-independent constraints are introduced to preserve consistency. Tenenberg discusses search strategy, and the chapter ends with proofs of the results.
Throughout the book, ideas are presented gradually and the reasons for their introduction are given. The presentation is sustained by graphics and examples. The volume is well written. It includes a subject index and many up-to-date references collected at the end of the book.
The book is a significant step toward addressing the representational problems of plan reasoning systems in realistic worlds. It is a useful reference for researchers in plan reasoning systems. I also gladly recommend it to anyone interested in the state of the art in this field. Finally, because some of the formal methods are stated as algorithms, the book would also be useful to those who want to implement practical planning systems.
