1. Introduction.- 1.1 The Problem.- 1.2 Key Issues.- 1.3 Planning Versus Scheduling.

- 1.4 Contributions and Organization.- 1.5 Background.- I. Representation, Basic Algorithms, and Analytical Techniques.- 2. Representation and Basic Algorithms.

- 2.1 Basic Representation.- 2.1.1 Domain Description.- 2.1.2 Partial-Order and Partial-Instantiation Plans.

- 2.2 Basic Planning Algorithms.- 2.3 Partial-Order, Backward-Chaining Algorithms.- 2.3.1 Correctness.- 2.

3.2 Threat Detection and Resolution.- 2.3.3 Establishing Preconditions.- 2.3.4 A House-Painting Example.

- 2.4 Total-Order, Forward-Chaining Algorithms.- 2.5 More Advanced Operator Representations.- 2.6 Search Control.- 2.7 Satisfaction Based Methods.

- 2.7.1 Overview.- 2.7.2 Model Definition.- 2.7.

3 Model Satisfaction and Plan Construction.- 2.8 Background.- 3. Analytical Techniques.- 3.1 Basic Analytical Techniques.- 3.

2 Analyzing Forward-Chaining, Total-Order Planners.- 3.3 Analyzing Partial-Order Planners.- 3.4 Case Study: An Analysis of Tweak.- 3.4.1 An Implementation of Tweak.

- 3.4.2 Analyzing Tweak.- 3.5 Critics of Basic Planners.- 3.6 Background.- 4.

Useful Supporting Algorithms.- 4.1 Propositional Unification Algorithm.- 4.2 Graph Algorithms.- 4.3 Dynamic Programming.- 4.

4 Branch and Bound.- 4.5 Constraint Satisfaction.- 4.5.1 Local-Consistency Based Methods.- 4.5.

2 Backtrack-Free Algorithm.- 4.5.3 Backtrack-Based Algorithms.- 4.6 The Gsat Algorithm.- 4.7 Background.

- 5. Case Study: Collective Resource Reasoning.- 5.1 Eager Variable-Binding Commitments.- 5.2 Extending the Representation.- 5.3 Plan Generation.

- 5.3.1 Correctness Check.- 5.3.2 Threat Detection.- 5.3.

3 Precondition Establishment.- 5.4 A House-Painting Example.- 5.5 A Variable-Sized Blocks World Domain.- 5.6 Summary.- 5.

7 Background.- II. Problem Decomposition and Solution Combination.- 6. Planning by Decomposition.- 6.1 Decomposition Planning.- 6.

1.1 Two Examples.- 6.1.2 Global Planning-Domain Decomposition.- 6.2 Efficiency Benefits of Decomposition.- 6.

2.1 Forward-Chaining, Total-Order Planners.- 6.2.2 Backward-Chaining, Partial-Order Planners.- 6.2.3 Criteria for Good Decomposition.

- 6.3 Goal-Directed Decomposition: The Gdecomp Algorithm.- 6.4 Other Benefits of Decomposition.- 6.5 Alternative Approaches to Decomposition Planning.- 6.6 Summary.

- 6.7 Background.- 7. Global Conflict Resolution.- 7.1 Global Conflict Resolution -- An Overview.- 7.2 Conflict Resolution Constraints.

- 7.2.1 Conflicts and Conflict Resolution Methods.- 7.2.2 Relations Among Conflict Resolution Methods.- 7.3 Conflict Resolution as Constraint Satisfaction.

- 7.3.1 Representation.- 7.3.2 Propagating Constraints Among Conflicts.- 7.3.

3 Redundancy Removal via Subsumption Relations.- 7.4 The Painting Example.- 7.5 When Is the Constraint-Based Method Useful?.- 7.6 The Combine Algorithm.- 7.

7 Related Work.- 7.7.1 Overview of Previous Work.- 7.7.2 Related Work by Smith and Peot.- 7.

7.3 Related Work by Etzioni.- 7.8 Open Problems.- 7.9 Summary.- 7.10 Background.

- 8. Plan Merging.- 8.1 The Value of Plan Merging.- 8.2 Formal Description.- 8.2.

1 A Formal Definition for Plan Merging.- 8.2.2 An Example.- 8.2.3 Impact on Correctness.- 8.

3 Complexity of Plan Merging.- 8.3.1 Deciding What to Merge.- 8.3.2 Deciding How to Merge.- 8.

4 Optimal Plan Merging.- 8.5 Approximate Plan Merging.- 8.5.1 Algorithm ApproxMerge.- 8.5.

2 Example.- 8.5.3 Complexity.- 8.6 Related Work.- 8.6.

1 Critics in Noah, Sipe, and Nonlin.- 8.6.2 Machinist.- 8.6.3 Operator Overloading.- 8.

7 Open Problems.- 8.7.1 Order-Dependent Cost Functions.- 8.7.2 Hierarchical Plan Merging.- 8.

7.3 Enhancing Conflict Resolution.- 8.8 Summary.- 8.9 Background.- 9. Multiple-Goal Plan Selection.

- 9.1 Consistency-Based Plan Selection.- 9.1.1 The Multiple-Goal Plan-Selection Problem.- 9.1.2 A CSP Representation.

- 9.1.3 A Constraint-Based Solution.- 9.1.4 Evaluation--a Blocks-World Example.- 9.2 Optimization-Based Plan Selection.

- 9.2.1 Examples.- 9.2.2 Complexity.- 9.2.

3 A Heuristic Algorithm for Plan Selection.- 9.2.4 Examples.- 9.2.5 Empirical Results in a Manufacturing Planning Domain.- 9.

3 Open Problems.- 9.4 Summary.- 9.5 Background.- III. Hierarchical Abstraction.- 10.

Hierarchical Planning.- 10.1 A Hierarchical Planner.- 10.1.1 Algorithm.- 10.1.

2 Precondition-Elimination Abstraction.- 10.2 Specifying Refinement.- 10.2.1 Forward-Chaining, Total-Order Refinement.- 10.2.

2 Backward-Chaining, Partial-Order Refinement.- 10.3 Properties of an Abstraction Hierarchy.- 10.3.1 Existence-Based Properties.- 10.3.

2 Refinement-Based Properties.- 10.4 An Analytical Model.- 10.4.1 Assumptions.- 10.4.

2 The Probability of Refinement.- 10.4.3 Analytical Result.- 10.5 Open Problems.- 10.6 Summary.

- 10.7 Background.- 11. Generating Abstraction Hierarchies.- 11.1 Syntactic Connectivity Conditions.- 11.2 Hipoint.

- 11.2.1 Alpine.- 11.2.2 Probability Estimates.- 11.2.

3 Collapsing Nodes with Low Refinement Probabilities.- 11.2.4 Augmented Topological Sort of Abstraction Graph.- 11.3 Empirical Results in the Box Domain.- 11.4 Related Work on Abstraction Generation.

- 11.5 Open Problems.- 11.6 Summary.- 11.7 Background.- 12. Properties of Task Reduction Hierarchies.

- 12.1 Defining Operator Reduction.- 12.2 Upward Solution Property.- 12.2.1 Losing the Property.- 12.

2.2 A Variable-Assignment Example.- 12.2.3 The Chinese Bear Example.- 12.3 Imposing Restrictions.- 12.

3.1 Motivation.- 12.3.2 Unresolvable Conflicts.- 12.3.3 The Unique-Main-Subaction Restriction.

- 12.4 Preprocessing.- 12.5 Modifying Operator-Reduction Schemata.- 12.6 Open Problems.- 12.7 Summary.

- 12.8 Background.- 13. Effect Abstraction.- 13.1 A Motivating Example.- 13.2 Primary-Effect Restricted Planning.

- 13.3 Incompleteness and Sub-optimal Solutions.- 13.4 An Inductive Learning Algorithm.- 13.5 How Many Training Examples.- 13.5.

1 Informal Description.- 13.5.2 A Brief Introduction to PAC Learning.- 13.5.3 Application of the PAC Model.- 13.

6 Open Problems.- 13.7 Summary.- 13.8 Background.- References.