Intelligent Planning

This monograph on planning based on Artificial Intelligence methods may serve both as an advanced textbook and as a general reference book. AI planning is an active research and applications field concerned with action and plan representation, plan synthesis and reasoning, analysis of planning algorithms, plan execution and monitoring, and plan reuse and learning.
The book provides a clear, thorough coverage of key areas of classical AI planning. Its main theme is to build more intelligence on a set of basic algorithms and representations for planning. It presents advanced techniques for plan generation using decomposition and plan merging and for analyzing and comparing planning algorithms. The book contains illustrations, examples, algorithms, analyses, tables, and extensive references.

Texte du rabat

"The central fact is that we are planning agents." (M. Bratman, Intentions, Plans, and Practical Reasoning, 1987, p. 2) Recent arguments to the contrary notwithstanding, it seems to be the case that people-the best exemplars of general intelligence that we have to date­ do a lot of planning. It is therefore not surprising that modeling the planning process has always been a central part of the Artificial Intelligence enterprise. Reasonable behavior in complex environments requires the ability to consider what actions one should take, in order to achieve (some of) what one wants­ and that, in a nutshell, is what AI planning systems attempt to do. Indeed, the basic description of a plan generation algorithm has remained constant for nearly three decades: given a desciption of an initial state I, a goal state G, and a set of action types, find a sequence S of instantiated actions such that when S is executed instate I, G is guaranteed as a result. Working out the details of this class of algorithms, and making the elabora­ tions necessary for them to be effective in real environments, have proven to be bigger tasks than one might have imagined.

Contenu

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.