Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

1 Introduction.- 1.1 Solving Classical CSPs.- 1.2 Applications of Classical CSP.- 1.3 Limitations of Classical CSP.- 1.3.1 Flexible CSP.- 1.3.2 Dynamic CSP.- 1.4 Dynamic Flexible CSP.- 1.5 Flexible Planning: a DFCSP Application.- 1.6 Structure.- 1.7 Contributions and their Significance.- 2 The Constraint Satisfaction Problem.- 2.1 Constraints and Constraint Graphs.- 2.2 Tree Search Solution Techniques for Classical CSP.- 2.2.1 Backtrack.- 2.2.2 Backjumping.- 2.2.3 Conflict-Directed Backjumping.- 2.2.4 Backmarking.- 2.2.5 The Backmark Hybrids.- 2.2.6 Dynamic Backtracking.- 2.2.7 Relative Evaluation.- 2.3 Pre-Processing Techniques.- 2.3.1 Arc Consistency.- 2.3.2 Improving Efficiency in Enforcing Arc Consistency.- 2.3.3 Path Consistency.- 2.3.4 K-Consistency.- 2.3.5 Practical Consistency Enforcing.- 2.3.6 Directional Pre-Processing.- 2.4 Hybrid Tree-search Consistency-enforcing Algorithms.- 2.4.1 Partial Arc Consistency.- 2.4.2 Relative Evaluation.- 2.5 Heuristics.- 2.6 Conflict Recording.- 2.7 The Phase Transition in CSPs.- 2.8 Graph-Based Methods.- 2.8.1 The Invasion Procedure.- 2.8.2 The Cycle-Cutset Method.- 2.8.3 Non-separable Components.- 2.8.4 Tree-Clustering.- 2.9 Extending the CSP Framework.- 2.9.1 Extending Tree Search.- 2.9.2 Solution via Graph Decomposition.- 2.9.3 Additive Flexible CSP.- 2.9.4 Priority Maximisation Flexible CSP.- 2.10 Dynamic Constraint Satisfaction.- 2.10.1 Restriction/Relaxation-based Dynamic Constraint Satisfaction Problems.- 2.10.2 Recurrent Dynamic Constraint Satisfaction Problems.- 2.10.3 Activity-based Dynamic Constraint Satisfaction Problems.- 2.11 Summary.- 3 Dynamic Flexible Constraint Satisfaction.- 3.1 Towards Dynamic Flexible Constraint Satisfaction.- 3.1.1 Concepts of DFCSP.- 3.2 Examples from the Dynamic Perspective.- 3.2.1 Restriction/Relaxation-based DFCSP.- 3.2.2 Recurrent DFCSP.- 3.2.3 Activity-based DFCSP.- 3.3 A Specific Instance of DFCSP.- 3.3.1 The Flexible Component - a Recap.- 3.4 Fuzzy rrDFCSP Solution via Branch and Bound.- 3.5 Fuzzy rrDFCSP Solution via Local Repair.- 3.5.1 Local Changes.- 3.5.2 Flexible Local Changes: A Fuzzy rrDFCSP Algorithm.- 3.5.3 FLC Complexity Issues.- 3.6 Fuzzy Arc Consistency.- 3.6.1 The Complexity of Fuzzy Arc Consistency.- 3.6.2 Pre-processing with Fuzzy Arc Consistency.- 3.6.3 Hybrids.- 3.6.4 The Deletion Threshold.- 3.7 Solution Techniques for other DFCSP Instances.- 3.8 An Example.- 3.8.1 Solution of Initial Problem via Branch and Bound.- 3.8.2 Solution of Initial Problem via FLC.- 3.8.3 The Problem Changes.- 3.8.4 Solution of Updated Problem via Branch and Bound.- 3.8.5 Solution of Updated Problem via FLC.- 3.9 Summary.- 4 An Empirical Study of Fuzzy rrDFCSPs.- 4.1 The Problems.- 4.2 The Algorithms Studied.- 4.3 Evaluation Criteria.- 4.4 Heuristics Investigated.- 4.4.1 Variable Selection.- 4.4.2 Domain Element Selection.- 4.4.3 Constraint Check Selection.- 4.5 Results: 3-point Satisfaction Scale.- 4.6 Results: 4-point Satisfaction Scale.- 4.7 Results: 5-point Satisfaction Scale.- 4.8 The Utility of Dynamic Information.- 4.9 The Utility of the Deletion Threshold.- 4.10 The Utility of the Constraint Check Ordering Heuristic.- 4.11 The Utility of FLC Variable Selection Heuristics.- 4.12 The Utility of FLC Domain Element Selection Heuristics.- 4.13 Summary.- 5 Dynamic CSP in Domain-independent AI Planning.- 5.1 AI Planning.- 5.1.1 Constraint Satisfaction in Planning.- 5.2 An Overview of Graphplan.- 5.2.1 The Planning Graph.- 5.2.2 Basic Plan Extraction.- 5.2.3 Memoisation.- 5.3 Viewing the Planning Graph as a CSP.- 5.4 Plan Extraction via Dynamic Constraint Satisfaction.- 5.4.1 A Hierarchical Approach.- 5.4.2 Memoisation in the Hierarchical Context.- 5.5 The GP-rrDCSP Algorithm.- 5.5.1 The Top-level Procedure.- 5.5.2 The extract() Procedure.- 5.5.3 The propagateMS() Procedure.- 5.6 Complexity Issues.- 5.7 Avoiding Irrelevant Variables in Memosets Created by Propagation.- 5.8 Focusing the Search.- 5.8.1 Variable Selection.- 5.8.2 Value Select