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. 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. 3 Pre-Processing Techniques. - 2. 4 Hybrid Tree-search Consistency-enforcing Algorithms. - 2. 5 Heuristics. - 2. 6 Conflict Recording. - 2. 7 The Phase Transition in CSPs. - 2. 8 Graph-Based Methods. - 2. 9 Extending the CSP Framework. - 2. 10 Dynamic Constraint Satisfaction. - 2. 11 Summary. - 3 Dynamic Flexible Constraint Satisfaction. - 3. 1 Towards Dynamic Flexible Constraint Satisfaction. - 3. 2 Examples from the Dynamic Perspective. - 3. 3 A Specific Instance of DFCSP. - 3. 4 Fuzzy rrDFCSP Solution via Branch and Bound. - 3. 5 Fuzzy rrDFCSP Solution via Local Repair. - 3. 6 Fuzzy Arc Consistency. - 3. 7 Solution Techniques for other DFCSP Instances. - 3. 8 An Example. - 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. 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. 2 An Overview of Graphplan. - 5. 3 Viewing the Planning Graph as a CSP. - 5. 4 Plan Extraction via Dynamic Constraint Satisfaction. -5. 5 The GP-rrDCSP Algorithm. - 5. 6 Complexity Issues. - 5. 7 Avoiding Irrelevant Variables in Memosets Created by Propagation. - 5. 8 Focusing the Search. - 5. 9 Summary. - 6 GP-rrDCSP: Experimental Results. - 6. 1 The Logistics Domain. - 6. 2 The Blocks-world Domain. - 6. 3 The Gripper Domain. - 6. 4 The Movie Domain. - 6. 5 The Grid Domain. - 6. 6 Summary. - 7 Flexible Planning Problems & Flexible Graphplan. - 7. 1 Background. - 7. 2 Flexible Planning Problems. - 7. 3 Flexible Graph Expansion. - 7. 4 Flexible Plan Extraction via rrDFCSP. - 7. 5 The FGP Algorithm. - 7. 6 Summary. - 8 FGP: Experimental Results. - 8. 1 The Test Suite. - 8. 2 The Test Suite: Plan Synthesis Results. - 8. 3 The Rescue Problem. - 8. 4 Summary. - 9 Conclusion. - 9. 1 A Summary. - 9. 2 Future Work. - 9. 3 And Finally. - References. - A Pseudo-code. - A. 1 Backtrack. - A. 2 Backjump. - A. 3 Conflict-directed Backjump. - A. 4 Backmark. - A. 5 Revise(). - A. 6 AC-1(). - A. 7 AC-3(). - A. 8 AC-1/4(). - A. 9 Branch and Bound. - B Proofs. - B. 1 Soundness and Completeness of FLC. - B. 3 Soundness and Completeness of Flexible Graphplan. - D Planning Problems. - D. 1 The Test Suite. - D. 1. 1 Domain Operators. - D. 1. 2 Problem 1. - D. 1. 3 Problem 2. - D. 1. 4 Problem 3. - D. 1. 5 Problem 4. - D. 1. 6 Problem 5. - D. 1. 7 Problem 6. - D. 1. 8 Problem 7. - D. 1. 9 Problem 8. - D. 1. 10 Problem 9. - D. 1. 11 Problem 10. - D. 1. 12 Problem 11. - D. 1. 13 Problem 12. - D. 2 The Rescue Problem. - D. 2. 1 Domain Operators. - D. 2. 2 Problem Specification. Language: English