spacer
Automated Planning
spacer
Theory and Practice
spacer

Table of Contents

Preface

Table of Notation

Chapter 1: Introduction and Overview

  • 1.1: First Intuitions on Planning
  • 1.2: Forms of planning
  • 1.3: Domain-Independent Planning
  • 1.4: Conceptual Model for Planning
  • 1.5: Restricted Model
  • 1.6: Extended Models
  • 1.7: A Running Example: Dock-Worker Robots

Part I: Classical Planning

Chapter 2: Representations for Classical Planning

  • 2.1: Introduction
  • 2.2: Set-Theoretic Representation
    • 2.2.1: Planning Domains, Problems, and Solutions
    • 2.2.2: State Reachability
    • 2.2.3: Stating a Planning Problem
    • 2.2.4: Properties of the Set-theoretic Representation
  • 2.3: Classical Representation
    • 2.3.1: States
    • 2.3.2: Operators and Actions
    • 2.3.3: Plans, Problems, and Solutions
    • 2.3.4: Semantics of Classical Representations
  • 2.4: Extending the Classical Representation
    • 2.4.1: Simple Syntactical Extensions
    • 2.4.2: Conditional Planning Operators
    • 2.4.3: Quantified Expressions
    • 2.4.4: Disjunctive Preconditions
    • 2.4.5: Axiomatic Inference
    • 2.4.6: Function Symbols
    • 2.4.7: Attached Procedures
    • 2.4.8: Extended Goals
  • 2.5: State-Variable Representation
    • 2.5.1: State Variables
    • 2.5.2: Operators and Actions
    • 2.5.3: Domains and Problems
    • 2.5.4: Properties
  • 2.6: Comparisons
  • 2.7: Discussion and Historical Remarks
  • 2.8: Exercises

Chapter 3: Complexity of Classical Planning

  • 3.1: Introduction
  • 3.2: Preliminaries
  • 3.3: Decidability and Undecidability Results
  • 3.4: Complexity Results
    • 3.4.1: Binary Counters
    • 3.4.2: Unrestricted Classical Planning
    • 3.4.3: Other results
  • 3.5: Limitations
  • 3.6: Discussion and Historical Remarks
  • 3.7: Exercises

Chapter 4: State-Space Planning

  • 4.1: Introduction
  • 4.2: Forward Search
    • 4.2.1: Formal Properties
    • 4.2.2: Deterministic Implementations
  • 4.3: Backward Search
  • 4.4: The STRIPS Algorithm
  • 4.5: Domain-Specific State-Space Planning
    • 4.5.1: The Container-Stacking Domain
    • 4.5.2: Planning Algorithm
  • 4.6: Discussion and Historical Remarks
  • 4.7: Exercises

Chapter 5: Plan-Space Planning

  • 5.1: Introduction
  • 5.2: The Search Space of Partial Plans
  • 5.3: Solution Plans
  • 5.4: Algorithms for Plan Space Planning
    • 5.4.1: The PSP Procedure
    • 5.4.2: The PoP Procedure
  • 5.5: Extensions
  • 5.6: Plan Space Versus State Space Planning
  • 5.7: Discussion and Historical Remarks
  • 5.8: Exercises

Part II: Neoclassical Planning

Chapter 6: Planning-Graph Techniques

  • 6.1: Introduction
  • 6.2: Planning Graphs
    • 6.2.1: Reachability Trees
    • 6.2.2: Reachability with Planning Graphs
    • 6.2.3: Independent Actions and Layered Plans
    • 6.2.4: Mutual Exclusion Relations
  • 6.3: The Graphplan Planner
    • 6.3.1: Expanding the Planning Graph
    • 6.3.2: Searching the Planning Graph
    • 6.3.3: Analysis of Graphplan
  • 6.4: Extensions and Improvements of Graphplan
    • 6.4.1: Extending the Language
    • 6.4.2: Improving the Planner
    • 6.4.3: Extending the Independence Relation
  • 6.5: Discussion and Historical Remarks
  • 6.6: Exercises

Chapter 7: Propositional Satisfiability Techniques

  • 7.1: Introduction
  • 7.2: Planning problems as Satisfiability problems
    • 7.2.1: States as propositional formulas
    • 7.2.2: State transitions as propositional formulas
    • 7.2.3: Planning problems as propositional formulas
  • 7.3: Planning by Satisfiability
    • 7.3.1: Davis-Putnam
    • 7.3.2: Stochastic Procedures
  • 7.4: Different Encodings
    • 7.4.1: Action Representation
    • 7.4.2: Frame axioms
  • 7.5: Discussion and Historical Remarks
  • 7.6: Exercises

Chapter 8: Constraint Satisfaction Techniques

  • 8.1: Introduction
  • 8.2: Constraint Satisfaction Problems
  • 8.3: Planning Problems as CSPs
    • 8.3.1: Encoding a Planning Problem into a CSP
    • 8.3.2: Analysis of the CSP Encoding
  • 8.4: CSP Techniques and Algorithms
    • 8.4.1: Search Algorithms for CSPs
    • 8.4.2: Filtering Techniques
      • Arc Consistency
      • Path Consistency
    • 8.4.3: Local Search Techniques and Hybrid Approaches
  • 8.5: Extended CSP Models
    • 8.5.1: Active CSPs
    • 8.5.2: Valued CSPs
  • 8.6: CSP techniques in Planning
    • 8.6.1: CSPs in Plan-Space Search
    • 8.6.2: CSPs for Planning-Graph Techniques
  • 8.7: Discussion and Historical Remarks
  • 8.8: Exercises

Part III: Heuristics and Control Strategies

Chapter 9: Heuristics in Planning

  • 9.1: Introduction
  • 9.2: Design Principle for Heuristics: Relaxation
  • 9.3: Heuristics for State-Space Planning
    • 9.3.1: State Reachability Relaxation
    • 9.3.2: Heuristically Guided Backward Search
    • 9.3.3: Admissible State-Space Heuristics
    • 9.3.4: Graphplan as a Heuristic-Search Planner
  • 9.4: Heuristics for Plan-Space Planning
    • 9.4.1: Flaw-Selection Heuristics
    • 9.4.2: Resolver-Selection Heuristics
  • 9.5: Discussion and Historical Remarks
  • 9.6: Exercises

Chapter 10: Control Rules in Planning

  • 10.1: Introduction
  • 10.2: Simple Temporal Logic
  • 10.3: Progression
  • 10.4: Planning Procedure
  • 10.5: Extensions
  • 10.6: Extended Goals
  • 10.7: Discussion and Historical Remarks
  • 10.8: Exercises

Chapter 11: Hierarchical Task Network Planning

  • 11.1: Introduction
  • 11.2: STN Planning
    • 11.2.1: Tasks and Methods
    • 11.2.2: Problems and Solutions
  • 11.3: Total-Order STN Planning
  • 11.4: Partial-Order STN Planning
  • 11.5: HTN Planning
    • 11.5.1: Task Networks
    • 11.5.2: HTN Methods
    • 11.5.3: HTN Problems and Solutions
    • 11.5.4: Planning Procedures
  • 11.6: Comparisons
    • 11.6.1: HTN Planning Versus STN Planning
    • 11.6.2: HTN Methods Versus Control Rules
  • 11.7: Extensions
    • 11.7.1: Extensions from Chapter 2
    • 11.7.2: Additional Extensions
  • 11.8: Extended Goals
  • 11.9: Discussion and Historical Remarks
  • 11.10: Exercises

Chapter 12: Control Strategies in Deductive Planning

  • 12.1: Introduction
  • 12.2: Situation Calculus
    • 12.2.1: Situations
    • 12.2.2: Actions
    • 12.2.3: Planning Domains, Problems and Solutions
    • 12.2.4: Plans as Programs in Situation Calculus
  • 12.3: Dynamic Logic
    • 12.3.1: The Language of the Logic
    • 12.3.2: The Semantics
    • 12.3.3: The Deductive Machinery
    • 12.3.4: Planning Domains, Problems, and Solutions
    • 12.3.5: Extensions
    • 12.3.6: User-Defined Control Strategies as Tactics
  • 12.4: Discussion and Historical Remarks
  • 12.5: Exercises

Part IV: Planning with Time and Resources

Chapter 13: Time for Planning

  • 13.1: Introduction
  • 13.2: Temporal References and Relations
  • 13.3: Qualitative Temporal Relations
    • 13.3.1: Point Algebra
    • 13.3.2: Interval Algebra
    • 13.3.3: A Geometric Interpretation of the Interval Algebra
    • 13.3.4: Interval Algebra vs. Point Algebra
  • 13.4: Quantitative Temporal Constraints
    • 13.4.1: Simple Temporal Constraints
    • 13.4.2: Temporal Constraint Networks
  • 13.5: Discussion and Historical Remarks
  • 13.6: Exercises

Chapter 14: Temporal Planning

  • 14.1: Introduction
  • 14.2: Planning with Temporal Operators
    • 14.2.1: Temporal Expressions and Temporal Databases
    • 14.2.2: Temporal Planning Operators
    • 14.2.3: Domain axioms
    • 14.2.4: Temporal Planning Domains, Problems and Plans
    • 14.2.5: Concurrent Actions with Interfering Effects
    • 14.2.6: A Temporal Planning Procedure
  • 14.3: Planning with Chronicles
    • 14.3.1: State Variables, Timelines and Chronicles
    • 14.3.2: Chronicles as Planning Operators
    • 14.3.3: Chronicle Planning Procedures
    • 14.3.4: Constraint Management in CP
    • 14.3.5: Search Control in CP
  • 14.4: Discussion and Historical Remarks
  • 14.5: Exercises

Chapter 15: Planning and Resource Scheduling

  • 15.1: Introduction
  • 15.2: Elements of Scheduling Problems
    • 15.2.1: Actions
    • 15.2.2: Resources
    • 15.2.3: Constraints and Cost Functions
  • 15.3: Machine Scheduling Problems
    • 15.3.1: Classes of Machine Scheduling Problems
    • 15.3.2: Complexity of Machine Scheduling
    • 15.3.3: Solving Machine Scheduling Problems
    • 15.3.4: Planning and Machine Scheduling
  • 15.4: Integrating Planning and Scheduling
    • 15.4.1: Representation
    • 15.4.2: Detecting Resource Conflicts
    • 15.4.3: Managing Resource-Conflict Flaws
  • 15.5: Discussion and Historical Remarks
  • 15.6: Exercises

Part V: Planning under Uncertainty

Chapter 16: Planning based on Markov Decision Processes

  • 16.1: Introduction
  • 16.2: Planning in Fully Observable Domains
    • 16.2.1: Domains, Plans, and Planning Problems
    • 16.2.2: Planning Algorithms
  • 16.3: Planning under Partial Observability
    • 16.3.1: Domains, Plans, and Planning Problems
    • 16.3.2: Planning Algorithms
  • 16.4: Reachability and Extended Goals
  • 16.5: Discussion and Historical Remarks
  • 16.6: Exercises

Chapter 17: Planning based on Model Checking

  • 17.1: Introduction
  • 17.2: Planning for Reachability Goals
    • 17.2.1: Domains, Plans, and Planning Problems
    • 17.2.2: Planning Algorithms
  • 17.3: Planning for Extended Goals
    • 17.3.1: Domains, Plans, and Planning Problems
    • 17.3.2: Planning Algorithms
    • 17.3.3: Beyond Temporal Logics
  • 17.4: Planning under Partial Observability
    • 17.4.1: Domains, Plans, and Planning Problems
    • 17.4.2: Planning Algorithms
  • 17.5: Planning as Model Checking vs. MDPs
  • 17.6: Historical Remarks
  • 17.7: Exercises

Chapter 18: Uncertainty with Neo-Classical Techniques

  • 18.1: Introduction
  • 18.2: Planning as Satisfiability
    • 18.2.1: Planning problem
    • 18.2.2: Planning problems as propositional formulas
    • 18.2.3: Planning by Satisfiability
    • 18.2.4: QBF planning
  • 18.3: Planning Graphs
  • 18.4: Discussion and Historical Remarks
  • 18.5: Exercises

Part VI: Case Studies and Applications

Chapter 19: Space Applications

  • 19.1: Introduction
  • 19.2: Deep Space 1
  • 19.3: The Autonomous Remote Agent
  • 19.4: The Remote Agent Architecture
  • 19.5: The Planner Architecture
  • 19.6: The Deep Space 1 Experiment
    • 19.6.1: Validation Objectives
    • 19.6.2: Scenarios
    • 19.6.3: Experiment Results
    • 19.6.4: Lesson Learned
  • 19.7: Discussion and Historical Remarks

Chapter 20: Planning in Robotics

  • 20.1: Introduction
  • 20.2: Path and Motion Planning
  • 20.3: Planning for the Design of a Robust Controller
    • 20.3.1: Sensory-Motor Functions
    • 20.3.2: Modalities
    • 20.3.3: The Controller
    • 20.3.4: Analysis of the Approach
  • 20.4: Dock-Worker Robots
  • 20.5: Discussion and Historical Remarks

Chapter 21: Planning for Manufacturability Analysis

  • 21.1: Introduction
  • 21.2: Machined Parts
  • 21.3: Feature Extraction
  • 21.4: Generating Abstract Plans
  • 21.5: Resolving Goal Interactions
  • 21.6: Additional Steps
  • 21.7: Operation Plan Evaluation
  • 21.8: Efficiency Considerations
  • 21.9: Concluding Remarks

Chapter 22: Emergency Evacuation Planning

  • 22.1: Introduction
  • 22.2: Evacuation Operations
  • 22.3: Knowledge Representation
    • 22.3.1: HTNs
    • 22.3.2: Cases
  • 22.4: Hierarchical Task Editor
  • 22.5: SiN
    • 22.5.1: How SiN Works
    • 22.5.2: Correctness of SiN
    • 22.5.3: Imperfect World Information
  • 22.6: Example
  • 22.7: Summary
  • 22.8: Discussion and Historical Remarks

Chapter 23: Planning in the Game of Bridge

  • 23.1: Introduction
  • 23.2: Overview of Bridge
  • 23.3: Game-Tree Search in Bridge
  • 23.4: Adapting HTN Planning for Bridge
  • 23.5: Implementation and Results

Part VII: Conclusion

Chapter 24: Conclusion and Other Topics

  • 24.1: Overview
  • 24.2: Case-Based Planning
  • 24.3: Linear and Integer Programming
  • 24.4: Multi-Agent Planning
  • 24.5: Plan Merging and Plan Rewriting
  • 24.6: Abstraction Hierarchies
  • 24.7: Domain Analysis
  • 24.8: Planning and Learning
  • 24.9: Planning and Acting, Situated Planning, Dynamic Planning
  • 24.10: Plan Recognition
  • 24.11: Suggestions for Future Work

Part VIII: Appendices

Appendix A: Search Procedures and Computational Complexity

  • A.1: Nondeterministic Problem-Solving
  • A.2: State-Space Search
  • A.3: Problem-Reduction Search
  • A.4: Computational Complexity of Procedures
  • A.5: Computational Complexity of Problems
  • A.6: Planning Domains as Language-Recognition Problems
  • A.7: Discussion and Historical Remarks

Appendix B: First Order Logic

  • B.1: Introduction
  • B.2: Propositional Logic
  • B.3: First Order Logic

Appendix C: Model Checking

  • C.1: Introduction
  • C.2: Intuitions
  • C.3: The Model Checking Problem
  • C.4: Model Checking Algorithms
  • C.5: Symbolic Model Checking
  • C.6: BDD-based Symbolic Model Checking

Bibliography


Copyright © 2004 by Elsevier Inc. All rights reserved. Used with permission.