Report Number: CS-TR-87-1142
Institution: Stanford University, Department of Computer Science
Title: A Heuristic Refinement for Spacial Constraint Satisfaction
Author: Brinkley, J.
Author: Buchanan, B.
Author: Altman, R.
Author: Duncan, B.
Author: Cornelius, C.
Date: January 1987
Abstract: The problem of arranging a set of physical objects according
to a set of constraints is formulated as a geometric
constraint satisfaction problem (GCSP), in which the
variables are the objects, the possible locations of the
objects are the possible values for the variables, and the
constraints are geometric constraints between objects. A GCSP
is a type of multidimensional constraint satisfaction problem
in which the number of objects and/or the number of possible
locations per object is too large to permit direct solution
by backtrack search. A method is described for reducing these
numbers by refinement along two dimensions. The number of
objects is reduced by refinement of the structure,
representing a group of objects as a single abstract object
before considering each object individually. The abstraction
used depends on domain specific knowledge. The number of
locations per object is reduced by applying node and arc
consistency algorithms to refine the accessible volume of
each object. Heuristics are employed to control the order of
operations (and hence to affect the efficiency of search) but
not to change the correctness in the sense that no solutions
that would be found by backtrack search are eliminated.
Application of the method to the problem of protein structure
determination is described.