Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

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.