Ebook: Dynamic Flexible Constraint Satisfaction and its Application to AI Planning
Author: Ian Miguel BSC MSc PhD (auth.)
- Tags: Computer Applications, Artificial Intelligence (incl. Robotics)
- Series: Distinguished Dissertations
- Year: 2004
- Publisher: Springer-Verlag London
- Edition: 1
- Language: English
- pdf
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Content:
Front Matter....Pages I-XX
Introduction....Pages 1-11
The Constraint Satisfaction Problem....Pages 13-64
Dynamic Flexible Constraint Satisfaction....Pages 65-90
An Empirical Study of Fuzzy rrDFCSPs....Pages 91-158
Dynamic CSP in Domain-independent AI Planning....Pages 159-183
GP-rrDCSP: Experimental Results....Pages 185-201
Flexible Planning Problems & Flexible Graphplan....Pages 203-223
FGP: Experimental Results....Pages 225-237
Conclusion....Pages 239-250
Back Matter....Pages 251-318
Content:
Front Matter....Pages I-XX
Introduction....Pages 1-11
The Constraint Satisfaction Problem....Pages 13-64
Dynamic Flexible Constraint Satisfaction....Pages 65-90
An Empirical Study of Fuzzy rrDFCSPs....Pages 91-158
Dynamic CSP in Domain-independent AI Planning....Pages 159-183
GP-rrDCSP: Experimental Results....Pages 185-201
Flexible Planning Problems & Flexible Graphplan....Pages 203-223
FGP: Experimental Results....Pages 225-237
Conclusion....Pages 239-250
Back Matter....Pages 251-318
....