Conflict-based pruning of a solution space within a constructive geometric constraint solver

摘要

The Computer-Aided Design field has developed sketching systems that automatically instantiate geometric objects from a rough sketch, annotated with dimensions and constraints input by the user. Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. The user is only interested in the intended solution that, besides fulfilling the geometric constraints, exhibits some additional properties. Metaheuristics have been successfully applied to solve this problem named as Root Identification Problem. However, these methods are very time-consuming because of the time required to evaluate every candidate solution. Pruning the search space is paramount to simplify the number of solution instances evaluated before finding the intended solution. In this work, we present an algorithm for pruning based on the detection of conflicts, i.e. patterns that drive to non-feasible solutions. Subsequent solutions will not be evaluated in case of matching a neighborhood corresponding to a previously detected conflicting pattern. The algorithm may be integrated in the evaluation phase of techniques that dynamically explore the search space, like metaheuristics, significantly improving the required computational time.