Information Technology Reference
In-Depth Information
(Freeman-Benson 1992). Borning presented the concept of constraint hierarchy
in order to solve the “overly constrained” problem of graph design. The idea is
that system can not only satisfy “Hard constraint”, but also allow users to present
as much “soft constraint” as possible. These soft constraints are divided into
several priority grades, which is also called constraint hierarchy.
Constraint hierarchy is a definite set of marked constraints. Given a constraint
level H, H
0
is a set of constraint that must be satisfied in H. H
1
is the strongest
constraint of non-essential constraints and Hn is the weakest in which n denotes
the grade of non-essential constraints.
The evaluation of constraint set is a function, which maps a free variable into
an element of
domain. A solution of constraint hierarchy is a set of evaluation
of free variable. Evaluation in solving set must at least satisfy essential constraint.
In additional, the solving set should also satisfy the constraints of other
evaluation. Among evaluation that satisfies essential constraint, there does not
exist more evaluations that satisfies non-essential constraint than evaluations in
the solving set. There are a variety of methods to compare satisfying degree
which evaluation satisfies constraint. To adopt which method depends on specific
application.
At the beginning, the evaluation of constraint hierarchy uses some methods to
make constraint hierarchy be satisfied to the greatest extent. But these methods
does not have declarative advantage of constraint representation system.
Therefore Wilson, Borning,et al. designed hierarchical constraint logic
programming language HCLP on the basis of constraint logic programming,
which embeds constraint hierarchy into Prolog and makes hierarchical constraint
system built totally on declarative representation. The minimal model theory of
nonmonotonic theory is used to define the semantics of HCLP model. HCLP
firstly utilizes backtracking method of common logic programming to obtain a
necessary solution, which may include limited variable domain rather than
variable value. Meanwhile, it also generates all constraints of current
instantiations(constraint hierarchy), and then gradually limits the necessary
solution by the generated constraint from stronger constraint to weaker constraint
until inconsistent situations appear. As to the constraints in the same hierarchy,
different orders of using constraints will cause different solutions.
The solution of constraint hierarchy is simple and swift, but incomplete,
because the generated solution may not correspond to the minimal model of
whole logic programming but a minimum model of reasoning path.
D
