Dynamic Flexible Constraint Satisfaction and its Application to AI Planning
Published on 14. November 2003
Book
Hardback
XX, 318 pages
978-1-85233-764-3 (ISBN)
Description
First, I would like to thank my principal supervisor Dr Qiang Shen for all his help, advice and friendship throughout. Many thanks also to my second supervisor Dr Peter Jarvis for his enthusiasm, help and friendship. I would also like to thank the other members of the Approximate and Qualitative Reasoning group at Edinburgh who have also helped and inspired me. This project has been funded by an EPSRC studentship, award num ber 97305803. I would like, therefore, to extend my gratitude to EPSRC for supporting this work. Many thanks to the staff at Edinburgh University for all their help and support and for promptly fixing any technical problems that I have had . My whole family have been both encouraging and supportive throughout the completion of this book, for which I am forever indebted. York, April 2003 Ian Miguel Contents List of Figures XV 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 Solving Classical CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 Applicat ions of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. 3 Limitations of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 3. 1 Flexible CSP 6 1. 3. 2 Dynamic CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 4 Dynamic Flexible CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. 5 Flexible Planning: a DFCSP Application . . . . . . . . . . . . . . . . . . 8 1. 6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. 7 Contributions and their Significance 11 2 The Constraint Satisfaction Problem 13 2. 1 Constraints and Constraint Graphs . . . . . . . . .. . . . . . . . . . . . . . 13 2. 2 Tree Search Solution Techniques for Classical CSP . . . . . . . . . . 16 2. 2. 1 Backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. 3 Conflict-Directed Backjumping . . . . . . . . . . . . . . . . . . . . . 19 2. 2. 4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
More details
Series
Edition
2004 ed.
Language
English
Place of publication
London
United Kingdom
Target group
Professional and scholarly
Research
Illustrations
XX, 318 p.
Dimensions
Height: 241 mm
Width: 160 mm
Thickness: 24 mm
Weight
682 gr
ISBN-13
978-1-85233-764-3 (9781852337643)
DOI
10.1007/978-0-85729-378-7
Schweitzer Classification
Other editions
Additional editions
Book
09/2012
Springer
€106.99
Shipment within 15-20 days
Content
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.