Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

A detailed systematic review of the constraint satisfaction literature.

Methods are developed which, for the first time, are able to solve problems which both contain a dynamic component and are open to compromise if a 'perfect' solution does not exist Classical artificial intelligence planning is extended to incorporate preferences so that it too can support compromise A trade-off between the length of a plan versus the number and severity of the compromises it contains is now possible An extensive empirical analysis of the new dynamic-flexible problem solving methods and the development of a new flexible planning Includes supplementary material: sn.pub/extras

Zusammenfassung
A detailed systematic review of the constraint satisfaction literature.

Inhalt
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.