ctong@lightning.rutgers.edu (Chris Tong) (04/15/88)
Please post this on the AIlist.
The following thesis proposal defense will be held at 10am, Mar. 29,
in Hill Center, room 423, Busch Campus, Rutgers University, New
Brunswick, NJ., and will be chaired by Chris Tong.
CONSTRAINT INCORPORATION
USING CONSTRAINED REFORMULATION
Wesley Braudaway
wes@aramis.rutgers.edu
ABSTRACT. The goal of this research is to develop knowledge
compilation techniques to produce a problem-solving system from a
declarative solution description. It has been shown that a
Generate-and-Test problem-solver can be compiled from a declarative
language that represents solutions as instances of a (hierarchically
organized) solution frame; the generator systematically constructs
instances of the solution frame, until one is found that meets all the
tests. However, this Generate-and-Test architecture is
computationally infeasible as a problem-solver for all but trivial
problems. Optimization techniques must be used to improve the
efficiency of the resulting problem-solving system. Test
Incorporation is one such optimization technique that moves testers,
which test the satisfaction of the problem constraints, back into the
generator sequence to provide early pruning.
This proposal defines a special kind of test incorporation called
Constraint Incorporation. This technique modifies the generators so
they enumerate only those generator values that satisfy the problem
constraints defined by the tests. Because of this complete
incorporation, the tests defining the incorporated constraints can be
removed from the Generate-and-Test architecture. This results in a
significant increase of problem-solving efficiency over test
incorporation when the test cannot be partitioned into subtests that
affect a single generator. These cases seem to occur when a mismatch
exists between the language used to represent (and construct)
solutions and the language used to define the problem constraints. To
incorporate these constraints, the representations of solutions and
problem constraints should be shifted (i.e., reformulated) so as to
bridge the gap between them.
One method for bridging the gap is to search the space of solution and
problem representations until incorporation is enabled. However,
because of the difficulties encountered (e.g., the space is large and
difficult to generate), an alternative method is proposed that will
constrain the reformulation process. This method incorporates
constraints by compiling an abstract solution description into a
problem-solver. By using an abstract solution description, the system
does not commit prematurely to a detailed and biased representation of
the solution description. The problem constraints are refined into
procedural specifications and merged to form a partial specification
of the problem-solver. The problem-solver is partial in that it only
generates those solution details mentioned in the constraints. In
this way, the compiler is focusing on just those details of the
solution language that are relevant to incorporating the constraints.
The partial problem-solver is then extended into a complete one by
adding generators for the remaining details. Any such extension is
guaranteed to have successfully incorporated all the constraints.
This method has been applied to a house floorplanning domain, using
extensive paper traces. It is currently being implemented, and will be
applied to a second domain.