Hierarchical constraint satisfaction
Encyclopedia
In artificial intelligence
and operations research
, hierarchical constraint satisfaction (HCS) is a method of handling constraint satisfaction
problems where the variables
have large domains by exploiting their internal structure.
For many real-world problems the domain elements cluster together into sets with common properties and relations. This structure can be represented as a hierarchy and is partially ordered
on the subset of a relation. The expectation is that the domains are structured so that the elements of a set frequently share consistency properties permitting them to be retained or eliminated as a unit. Thus, if some elements of a set satisfy a constraint
, but not all, the subsets of the set are considered. In this way, if no elements of a set can satisfy the constraint the whole set can be discarded. Thus, structuring the domain helps in considering sets of elements all at a time and hence helps in pruning the search space more quickly.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, hierarchical constraint satisfaction (HCS) is a method of handling constraint satisfaction
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints.The techniques used in...
problems where the variables
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
have large domains by exploiting their internal structure.
For many real-world problems the domain elements cluster together into sets with common properties and relations. This structure can be represented as a hierarchy and is partially ordered
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
on the subset of a relation. The expectation is that the domains are structured so that the elements of a set frequently share consistency properties permitting them to be retained or eliminated as a unit. Thus, if some elements of a set satisfy a constraint
Constraint (mathematics)
In mathematics, a constraint is a condition that a solution to an optimization problem must satisfy. There are two types of constraints: equality constraints and inequality constraints...
, but not all, the subsets of the set are considered. In this way, if no elements of a set can satisfy the constraint the whole set can be discarded. Thus, structuring the domain helps in considering sets of elements all at a time and hence helps in pruning the search space more quickly.