Dynamic Flexible Constraint Satisfaction and its Application to AI Planning - Brossura

Miguel, Ian

Brossura

ISBN 10: 144711048X ISBN 13: 9781447110484

Casa editrice: Springer, 2012

Riassunto

A detailed systematic review of the constraint satisfaction literature.

Su questo libro

Contenuti

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 Selection.- 5.8.3 Constraint Check Selection.- 5.9 Summary.- 6 GP-rrDCSP: Experimental Results.- 6.1 The Logistics Domain.- 6.1.1 The RocketA Problem.- 6.1.2 The RocketB Problem.- 6.1.3 The LogisticsA Problem.- 6.1.4 The LogisticsB and LogisticsC Problems.- 6.1.5 The LogisticsD Problem.- 6.2 The Blocks-world Domain.- 6.2.1 The 12-step Problem.- 6.2.2 The Blocks-world LargeA Problem.- 6.2.3 The Blocks-world LargeB Problem.- 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.2.1 Representation.- 7.2.2 The Valuable Package Problem (Continued).- 7.3 Flexible Graph Expansion.- 7.3.1 Mutual Exclusivity.- 7.3.2 Basic Flexible Graph Expansion.- 7.3.3 Limited Graph Expansion.- 7.3.4 Satisfaction Propagation During Graph Expansion.- 7.4 Flexible Plan Extraction via rrDFCSP.- 7.4.1 The FCSP Viewpoint.- 7.4.2 The Hierarchical Approach Revisited.- 7.4.3 Memoisation for Flexible Plan Synthesis.- 7.4.4 The Valuable Package Problem - Synthesised Plans.- 7.5 The FGP Algorithm.- 7.5.1 The Top-level Procedure.- 7.5.2 The FExtract() Procedure.- 7.5.3 Complexity Issues.- 7.6 Summary.- 8 FGP: Experimental Results.- 8.1 The Test Suite.- 8.2 The Test Suite: Plan Synthesis Results.- 8.2.1 The Utility of Limited Graph Expansion and Satisfaction Propagation.- 8.3 The Rescue Problem.- 8.3.1 The Shortest Plan.- 8.3.2 A Five Step Plan.- 8.3.3 A Nine Step Plan: The People are Evacuated.- 8.3.4 An Eleven Step Plan: All People and Possessions Evacuated.- 8.3.5 A Plan with No Compromises.- 8.4 Summary.- 9 Conclusion.- 9.1 A Summary.- 9.1.1 Dynamic Flexible Constraint Satisfaction.- 9.1.2 The Application of Dynamic and Dynamic Flexible CSP to AI Planning.- 9.2 Future Work.- 9.2.1 Enrichment of the DFCSP Matrix.- 9.2.2 Improvement of GP-rrDCSP.- 9.2.3 Further Development of Flexible Graphplan.- 9.2.4 Further Applications.- 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.

Dettagli dell?edizione

• Editore: Springer
• Data di pubblicazione: 2012
• Lingua: Inglese
• ISBN 10: 144711048X
• ISBN 13: 9781447110484
• Rilegatura: Copertina flessibile
• Numero di pagine: 344
• Contatto del produttore: non disponibile
• Persona responsabile: Springer Nature Customer Service Center GmbH; ProductSafety@springernature.com; ; Europaplatz 3,69115 Heidelberg, Germany; Heidelberg; 69115; Germania