Making Partial Choices in Constraint Reasoning Problems

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Engineering Problem Solving

Constraint problems derived from design and configurations tasks often use components (structured values) as domains of constrained variables. Most existing methods are forced into unnecessary search because they assign complete components to variables. A notion of partial choice is introduced as a way to assign a part of a component. The basic idea is to work with descriptions of classes of solutions as opposed to the actual solutions. It is shown how this idea can reduce search and in the best case eliminate search. A distinction is made between a partial commitment (a partial choice that would not be retracted) and a partial guess. A particular way to implement partial choice problem solvers is discussed. This method organizes choices in a taxonomic classification. Use of taxonomies not only helps in pruning the search space but also provides a compact language for describing solutions, no-goods, and representing constraints. It is also shown how multiple hierarchies can be used to avoid some of the problems associated with using a single hierarchy.