Dynamic Flexible Constraint Satisfaction and its Application to AI Planning (Distinguished Dissertations) - Hardcover

Miguel, Ian

Hardcover

ISBN 10: 1852337648 ISBN 13: 9781852337643

Publisher: Springer, 2003

Synopsis

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

About this title

Synopsis

"The Distinguished Dissertation Series" is published on behalf of the Conference of Professors and Heads of Computing and the British Computer Society, who annually select the best British PhD dissertations in computer science for publication. The dissertations are selected on behalf of the CPHC by a panel of eight academics. Each dissertation chosen makes a noteworthy contribution to the subject and reaches a high standard of exposition, placing all results clearly in the context of computer science as a whole. In this way, computer scientists with significantly different interests are able to grasp the essentials - or even find a means of entry - to an unfamiliar research topic. Constraint satisfaction is a fundamental technique for knowledge representation and inference in Artificial Intelligence. This success is founded on simplicity and generality: a constraint simply expresses a set of admissible value combinations among a number of variables. However, the classical formulation of a static constraint satisfaction problem (CSP) with inflexible constraints, all of which a solution must satisfy, is insufficient to model many real problems.

Recent work has addressed these shortcomings via two separate extensions, known as dynamic CSP and flexible CSP. Representing three years of PhD work by Dr. Ian Miguel, this book demonstrates how a range of instances of these two powerful extensions can be combined in order to solve more complex problems. As an application of this work, Artificial Intelligence Planning is extended to support compromise. Preferences are attached to plan goals and to the set of actions available to achieve these goals, allowing a systematic comparison of candidate plans. Although a plan may not completely satisfy all goals, nor perform the actions it uses in the most preferred situations, it may be significantly shorter than a compromise-free plan. Dr. Miguel has implemented Flexible Graphplan, a planning system based on dynamic flexible CSP, which generates a range of plans from an input problem, trading plan length against the number and severity of compromises made.

Edition details

• Publisher: Springer
• Publication date: 2003
• Language: English
• ISBN 10: 1852337648
• ISBN 13: 9781852337643
• Binding: Hardcover
• Number of pages: 338