Dynamic Flexible Constraint Satisfaction and its Application by Ian Miguel BSC, MSc, PhD (auth.)

By Ian Miguel BSC, MSc, PhD (auth.)

First, i need to thank my primary manager Dr Qiang Shen for all his support, suggestion and friendship all through. Many thank you additionally to my moment manager Dr Peter Jarvis for his enthusiasm, aid and friendship. i might additionally prefer to thank the opposite participants of the Approximate and Qualitative Reasoning staff at Edinburgh who've additionally helped and encouraged me. This undertaking has been funded via an EPSRC studentship, award num­ ber 97305803. i need, for that reason, to increase my gratitude to EPSRC for assisting this paintings. Many due to the employees at Edinburgh collage for all their support and aid and for in a timely fashion solving any technical difficulties that i've got had . My entire family members were either encouraging and supportive through the finishing touch of this publication, for which i'm perpetually indebted. York, April 2003 Ian Miguel Contents checklist of Figures XV 1 advent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. 1 fixing Classical CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 2 Applicat ions of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . three 1. three boundaries of Classical CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. three. 1 versatile CSP 6 1. three. 2 Dynamic CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. four Dynamic versatile CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. five versatile making plans: a DFCSP software . . . . . . . . . . . . . . . . . . eight 1. 6 constitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nine 1. 7 Contributions and their importance eleven 2 The Constraint pride challenge thirteen 2. 1 Constraints and Constraint Graphs . . . . . . . . . . . . . . . . . . . . . . . thirteen 2. 2 Tree seek resolution innovations for Classical CSP . . . . . . . . . . sixteen 2. 2. 1 back off . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. 2. 2 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2. 2. three Conflict-Directed Backjumping . . . . . . . . . . . . . . . . . . . . . 19 2. 2. four Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Show description

Read Online or Download Dynamic Flexible Constraint Satisfaction and its Application to AI Planning PDF

Similar nonfiction_8 books

Superlattices and Other Heterostructures: Symmetry and Optical Phenomena

Superlattices and different Heterostructures offers with the optical houses of superlattices and quantum good buildings with emphasis on phenomena ruled through crystal symmetries. After a short advent to team concept and symmetries, equipment for calculating spectra of electrons, excitons, and phonons in heterostructures are mentioned.

Masses of Fundamental Particles: Cargèse 1996

Boson lots within the general version; D. Treille. Non-Commutative Geometry and the interior area of Gauge Theories; T. Krajewski. best Quark Mass; J. L. Rosner. Unified Theories of Flavour with U(2) as Horizontal crew; A. Romanino. Heavy-Quark plenty; M. Neubert. Light-Quark lots; H. Leutwyler. vulnerable Matrix parts at the Lattice: fresh advancements in K-Physics; M.

Additional info for Dynamic Flexible Constraint Satisfaction and its Application to AI Planning

Sample text

All domain elements that consequently lack support (the counter reached 0 for a particular arc) are added to L for removal. AC-5 [38] is a generic arc consistency algorithm which depends on two procedures, ArcCons and LocalArcCons which are specified but whose actual implementation is left open. AC-3 and AC-4 can be represented by a specific implementation of these two procedures. AC-5 can also be implemented to produce an algorithm with a worst-case bound O(em) for restricted constraint types.

X D j , indicating variable assignments that are compatible with each other. These constraints are imperative(each one must be satisfied) and inflexible (they are fully satisfied or fully violated) . 2 presents the constraints that exist in the example problem. They specify a lexicographic ordering such that, for example, Xl < X2 requires that the assignment to Xl is strictly lexicographically less than that to X2. A solution to a classical CSP is a complete assignment to the problem variables satisfying all constraints simultaneously.

The Thrashing Problem A major factor contributing to the poor behaviour of Backtrack is that it suffers from thrashing: repeated failure of the search process due to the same reason [63]. Here is a general example: x g and Xi are related via a constraint such that when x g is assigned a particular value, the constraint disallows all potential values for Xi. Backtrack fails at level i for each element of Di, Further, this failure will be repeated for every combination of variable assignments to the variables in the intermediate levels, h, where g < h < i.

Download PDF sample

Rated 4.37 of 5 – based on 9 votes