KSL-87-05
## A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems

**Reference: **
Brinkley, J. F.;
Buchanan, B. G.;
Altman, R. B.;
Duncan, B. S.; &
Cornelius, C. W. A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems. 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 the objects. A GCSP is type of multi-
dimensional 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. Heristics 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.

**Notes:** STAN-CS-87-1142
15 pages.

*Jump to*...
[KSL]
[SMI]
[Reports by Author]
[Reports by KSL Number]
[Reports by Year]

Send mail to:
ksl-info@ksl.stanford.edu to send a message to the maintainer of the
KSL Reports.