Hugendubel.de - Das Lesen ist schön

Warenkorb

€ 0,00 0 Buch dabei,
portofrei
Bücher immer versandkostenfrei
Dynamic Flexible Constraint Satisfaction and its Application to AI Planning als Buch
PORTO-
FREI

Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

'Distinguished Dissertations'. 2004. Auflage. Book. Sprache: Englisch.
Buch (gebunden)
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 ot... weiterlesen
Dieses Buch ist auch verfügbar als:
Buch

165,49*

inkl. MwSt.
Portofrei
Lieferbar innerhalb von zwei bis drei Werktagen
Dynamic Flexible Constraint Satisfaction and its Application to AI Planning als Buch
Produktdetails
Titel: Dynamic Flexible Constraint Satisfaction and its Application to AI Planning
Autor/en: Ian Miguel

ISBN: 1852337648
EAN: 9781852337643
'Distinguished Dissertations'.
2004. Auflage.
Book.
Sprache: Englisch.
Springer London

14. November 2003 - gebunden - 344 Seiten

Beschreibung

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

Inhaltsverzeichnis

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.

Kunden, die diesen Artikel gekauft haben, kauften auch

Tragen Sie Ihre E-Mail- Adresse ein, und bleiben Sie kostenlos informiert:
Endstation Donau
- 49% **
eBook
von Edith Kneifl
Print-Ausgabe € 19,90
Harry Potter 1 und der Stein der Weisen
Buch (gebunden)
von Joanne K. Row…
Inseltage
eBook
von Jette Hansen
Splitter
eBook
von Sebastian Fit…

Diese Artikel könnten Sie auch interessieren

Harry Potter 1 und der Stein der Weisen. Schmuckausgabe
Buch (gebunden)
von Joanne K. Row…
Küstenmorde
- 55% **
eBook
von Nina Ohlandt
Statt € 8,99
Mörderischer Mistral
- 20% **
eBook
von Cay Rademache…
Print-Ausgabe € 9,99
Kaiserschmarrndrama
- 12% **
eBook
von Rita Falk
Print-Ausgabe € 15,90
Ostfriesenfluch
- 9% **
eBook
von Klaus-Peter W…
Print-Ausgabe € 10,99
Servicehotline
089 - 70 80 99 47

Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 20.00 Uhr
Filialhotline
089 - 30 75 75 75

Mo. - Sa. 9.00 - 20.00 Uhr
Bleiben Sie in Kontakt:
Sicher & bequem bezahlen:
akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal
Zustellung durch:
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
** im Vergleich zum dargestellten Vergleichspreis.