Front Cover -- About the Authors -- Automated Planning Theory and Practice -- Copyright Page -- Contents -- Foreword -- 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.3 Classical Representation -- 2.4 Extending the Classical Representation -- 2.5 State-Variable Representation -- 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.5 Limitations -- 3.6 Discussion and Historical Remarks -- 3.7 Exercises -- Chapter 4. State-Space Planning -- 4.1 Introduction -- 4.2 Forward Search -- 4.3 Backward Search -- 4.4 The STRIPS Algorithm -- 4.5 Domain-Specific State-Space Planning -- 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.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.3 The Graphplan Planner -- 6.4 Extensions and Improvements of Graphplan -- 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.3 Planning by Satisfiability -- 7.4 Different Encodings -- 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.4 CSP Techniques and Algorithms -- 8.5 Extended CSP Models -- 8.6 CSP Techniques in Planning -- 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.4 Heuristics for Plan-Space Planning -- 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.3 Total-Order STN Planning -- 11.4 Partial-Order STN Planning -- 11.5 HTN Planning -- 11.6 Comparisons -- 11.7 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.3 Dynamic Logic -- 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.4 Quantitative Temporal Constraints -- 13.5 Discussion and Historical Remarks -- 13.6 Exercises -- Chapter 14. Temporal Planning -- 14.1 Introduction -- 14.2 Planning with Temporal Operators -- 14.3 Planning with Chronicles.

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.3 Machine Scheduling Problems -- 15.4 Integrating Planning and Scheduling -- 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.3 Planning under Partial Observability -- 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.3 Planning for Extended Goals -- 17.4 Planning under Partial Observability -- 17.5 Planning as Model Checking versus MDPs -- 17.6 Discussion and Historical Remarks -- 17.7 Exercises -- Chapter 18. Uncertainty with Neoclassical Techniques -- 18.1 Introduction -- 18.2 Planning as Satisfiability -- 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.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.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.4 Hierarchical Task Editor -- 22.5 SiN -- 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. Other Approaches to Planning -- 24.1 Case-Based Planning -- 24.2 Linear and Integer Programming -- 24.3 Multiagent Planning -- 24.4 Plan Merging and Plan Rewriting -- 24.5 Abstraction Hierarchies -- 24.6 Domain Analysis -- 24.7 Planning and Learning -- 24.8 Planning and Acting, Situated Planning, and Dynamic Planning -- 24.9 Plan Recognition -- 24.10 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 -- Index.