Abstract
Traditional Constraint Satisfaction Problem (CSP) solvers often struggle with variables representing complex, structured components. This paper, originally published in 1987, introduces the concept of "partial choices"—a method that allows solvers to commit to specific attributes of a component without immediately selecting a final model. By leveraging taxonomic classification and multiple hierarchies, this approach prunes search spaces more effectively than atomic assignment or complete flattening of variables.
Introduction
In complex design and configuration tasks, such as building a computer system, variables are rarely simple scalars. A "Printer" variable, for instance, is a package of attributes: speed, technology, and cost. Traditional solvers typically fall into one of two traps: the Atomic Trap, where they try to assign a complete component and backtrack repeatedly upon failure, or the Flattening Trap, where they break components into independent variables, leading to an exponential explosion of the search space.
The Partial Choice Framework
The authors propose a middle ground through "Partial Choices," which allows for incremental commitment to component attributes. This framework operates through two primary mechanisms:
- Partial Commitment: A monotonic inference step. If all remaining valid components for a variable share a specific trait (e.g., all available printers are "High Speed"), the solver commits to that trait. This never requires retraction as it is logically derived from the current domain.
- Partial Guess: When no common trait exists, the solver partitions the domain into subsets (e.g., "Laser" vs. "Thermal") and explores one branch. While this may require backtracking, it allows the system to rule out entire categories of components simultaneously.
Taxonomic Reasoning and Multiple Hierarchies
To implement these choices efficiently, components are organized into taxonomies. Moving down a taxonomic tree represents making increasingly specific partial choices. A key innovation is the use of Multiple Taxonomies, which allows the solver to view the same set of components through different lenses—such as speed, technology, or print quality.
By intersecting these hierarchies, the solver can prioritize the most constrained attribute first. For example, if a budget constraint is tight, the solver might first narrow down choices in the "Cost" taxonomy before considering "Print Quality."
Key Insights
- Components as Compiled Constraints: A component is essentially a pre-solved set of internal constraints. Maintaining their structure prevents the solver from redundantly re-solving these internal relationships.
- Descriptions over Solutions: Solvers should operate on descriptions of sets of solutions (classes) rather than individual solutions.
- Taxonomies as Constraint Language: Hierarchies provide a compact way to express "no-goods." Instead of listing every incompatible printer model, a constraint can simply state that "Thermal Printers" are incompatible with a specific software package.
Results and Applications
The effectiveness of this approach was demonstrated in real-world expert systems like Pride (paper handling design) and Cossack (computer configuration). The primary benefits include:
- Search Reduction: Pruning large branches of the search space without examining every leaf node.
- Efficiency: Avoiding the "blind guesses" common in least-commitment solvers by using partial commitments.
- Knowledge Management: Taxonomies align well with how domain experts organize information, making knowledge acquisition and maintenance more intuitive.
Limitations and Conclusion
While powerful, the method's success depends on the quality of the taxonomies provided. Automatically generating optimal hierarchies remains a difficult problem, often requiring "natural taxonomies" from human experts. Future work suggests integrating these methods more deeply with standard arc-consistency algorithms to further enhance local inconsistency detection. Ultimately, partial choices provide a robust framework for handling the complexity of structured data in constraint reasoning.
Summary updated