Reasoning About Plans - 1st Edition - ISBN: 9781558601376, 9781483295961

Reasoning About Plans

1st Edition

Authors: James Allen Henry Kautz Richard Pelavin Josh Tenenberg
eBook ISBN: 9781483295961
Imprint: Morgan Kaufmann
Published Date: 1st July 1991
Page Count: 300
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


This book presents four contributions to planning research within an integrated framework. James Allen offers a survey of his research in the field of temporal reasoning, and then describes a planning system formalized and implemented directly as an inference process in the temporal logic. Starting from the same logic, Henry Kautz develops the first formal specification of the plan recognition process and develops a powerful family of algorithms for plan recognition in complex situations. Richard Pelavin then extends the temporal logic with model operators that allow the representation to support reasoning about complex planning situations involving simultaneous interacting actions, and interaction with external events. Finally, Josh Tenenberg introduces two different formalisms of abstraction in planning systems and explores the properties of these abstraction techniques in depth.

Table of Contents

Reasoning About Plans

James F. Allen, Henry A. Kautz, Richard N. Pelavin, John D. Tenenberg

Temporal Reasoning and Planning

1.1 Introduction

1.1.1 Background: Actions as State Change

1.1.2 Temporally Explicit Representations

1.2 Representing Time

1.2.1 Temporal Logic

1.3 The Logic of Action

1.4 The Logic for Planning

1.4.1 Predicting the Future

1.4.2 Planning With a Temporal World Model

1.5 The Planning System

1.5.1 A Nonlinear Planning Algorithm

1.5.2 Assumptions About Temporal Extension

1.5.3 Discussion of the Algorithm

1.6 The Door-Latch Problem

1.7 Hierarchical Planning

1.8 Conclusions

A Formal Theory of Plan Recognition and its Implementation Henry A. Kautz

2.1 Introduction

2.1.1 Background

2.1.2 Overview

2.1.3 Plan Recognition and the Frame Problem

2.2 Representing Event Hierarchies

2.2.1 The Language

2.2.2 Representation of Time, Properties, and Events

2.2.3 The Event Hierarchy

2.2.4 Example: The Cooking World

2.3 The Formal Theory of Recognition

2.3.1 Exhaustiveness Assumptions (EXA)

2.3.2 Disjointness Assumptions (DJA)

2.3.3 Component/Use Assumptions (CUA)

2.3.4 Minimum Cardinality Assumptions (MCA)

2.3.5 Example: the Cooking World

2.3.6 Circumscription and Plan Recognition

2.4 Examples

2.4.1 An Operating System

2.4.2 Medical Diagnosis

2.5 Algorithms for Plan Recognition

2.5.1 Directing Inference

2.5.2 Explanation Graphs

2.5.3 Implementing Component/Use Assumptions

2.5.4 Constraint Checking

2.5.5 Algorithms

Planning With Simultaneous Actions and External Events Richard N. Pelavin

3.1 Introduction

3.1.1 Key Considerations

3.1.2 Overview

3.2 Representations That Treat Simultaneous Events

3.2.1 Interval Logic

3.2.2 A Model Based on Events

3.2.3 Branching time Models

3.2.4 Adapting the State-Change Model to Handle Simultaneous Events

3.3 The Semantic Model

3.3.1 The Interval Logic Structure

3.3.2 The Branching Time Structure

3.3.3 Plan Instances and Basic Actions

3.3.4 The Closeness Function

3.3.5 Composition and Interaction of Basic Action Instances

3.4 The Language

3.4.1 The Syntax: Additions to Interval Logic

3.4.2 Interpretations

3.5 Planning

3.5.1 Planner Correctness

3.5.2 The World Description

3.5.3 The Action Specifications

3.5.4 Plan Instance Composition

3.5.5 Persistence and Maintenance Plan Instances

3.6 A Planning Algorithm

3.6.1 The Input to the Planning Algorithm

3.6.2 The Algorithm

3.6.3 Planning Examples

3.6.4 Limitations of the Planning Algorithm

3.7 Discussion

3.7.1 Issues Outside the Scope of the Deductive Logic

3.7.2 Incomplete Descriptions and Obtaining Additional Information

3.7.3 Planning With an Incorrect World Description

3.7.4 Addressing the Frame Problem

3.8 Appendix A. the Semantic Model and Logical Language

3.8.1 The Semantic Model

3.8.2 The Syntax

3.8.3 The Interpretation of the Language

3.9 Appendix B. Proof Theory

Abstraction in Planning Josh D. Tenenberg

4.1 Introduction

4.1.1 Inheritance Abstraction

4.1.2 Relaxed Model Abstraction

4.1.3 Macro Expansion

4.1.4 Outline

4.1.5 STRIPS

4.2 Inheritance Abstraction

4.2.1 Generalizing Inheritance

4.2.2 Predicate Mappings

4.2.3 Model Abstraction

4.2.4 Theory Abstraction

4.2.5 Theory Mappings

4.2.6 Proof-Theoretic Relationship Between Levels

4.2.7 Abstract STRIPS Systems

4.2.8 Downward Solution Property

4.2.9 Example

4.2.10 The Frame Problem

4.2.11 Comparison With Kautz

4.2.12 Related Research in Plan Generation

4.2.13 Summary

4.3 Abstraction Using Relaxed Models


4.3.2 Planning With Inconsistent Systems

4.3.3 Restricted ABSTRIPS

4.3.4 Simple Restrictions

4.3.5 Relaxing the Simple Restrictions

4.3.6 Example

4.3.7 Upward Solution Property

4.3.8 The Monotonicity Property

4.3.9 Search

4.3.10 Related Research

4.3.11 Summary

4.4 Conclusion

4.4.1 Discrete Levels

4.4.2 Solution Properties

4.5 Proofs

4.5.1 Proofs for Inheritance Abstraction

4.5.2 Proofs for Relaxed Model Abstraction




No. of pages:
© Morgan Kaufmann 1991
Morgan Kaufmann
eBook ISBN:

About the Author

James Allen

Henry Kautz

Richard Pelavin

Josh Tenenberg

Ratings and Reviews