A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems

From Tetherless World Wiki

Jump to: navigation, search

Citation: James F. Brinkley and Bruce G. Buchanan and Russ B. Altman and Bruce S. Duncan and Craig Cornelius. (1987) A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems. In , January,1987.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author James F. Brinkley and Bruce G. Buchanan and Russ B. Altman and Bruce S. Duncan and Craig Cornelius
title A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems
number KSL-87-05
institution Knowledge Systems, AI Laboratory
year 1987
month January
Bibtex more
note STAN-CS-87-1142 15 pages.
Access Paper
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.

KSL Technical Report ID: KSL-87-05
Facts about A Heuristic Refinement Method for Spatial Constraint Satisfaction ProblemsRDF feed
Abstract The problem of arranging a set of physical … 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. tein structure determination is described.
Author James F. Brinkley and Bruce G. Buchanan and Russ B. Altman and Bruce S. Duncan and Craig Cornelius  +
Bibtype techreport  +
Has author James F. Brinkley and Bruce G. Buchanan and Russ B. Altman and Bruce S. Duncan and Craig Cornelius  +
Has identifier KSL-87-05  +
Has publishing details January,1987  +
Has title A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems  +
Has year 1987  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-87-05  +
Month January  +
Note STAN-CS-87-1142 15 pages.  +
Number KSL-87-05  +
Process note YES  +
Title A Heuristic Refinement Method for Spatial Constraint Satisfaction Problems  +
Year 1987  +
Retrieved from "http://tw.rpi.edu/wiki/A_Heuristic_Refinement_Method_for_Spatial_Constraint_Satisfaction_Problems"
Personal tools