Basic Approaches to Constraint Solving

Beginning with a set of geometric elements and certain constraints between the elements, there are two basic strategies for solving the problem. The first, an instance solver, uses the explicit values of the given constraints to determine the possible geometric configurations which satisfy the constraints. The second, a generic solver, determines whether the given geometric elements can be placed using the given constraints, independent of the values which are assigned to the constraints. That is, the constraints have a symbolic rather than numerical value. The determination of specific placement of the geometric elements in a generic solver takes place only after a decision has been made about whether or not the problem is generically well-constrained.

                             
      Figure 1: A well-constrained sketch for a generic solver

As an example of the two different approaches, consider the sketch of Figure 1. Here the constraints are given symbolically, rather than with actual values. A generic solver would be able to report that the configuration is well-constrained, and would be able to determine a method for constructing the possible configurations without needing the actual values of the constraints. An instance solver requires that the values of the constraints be given before it makes any solution determination. Generic solvers are often more elegant and more efficient than instance solvers. They also allow more flexibility in the choice of the underlying method applied to determine the actual positions of the geometric elements. However, generic solvers usually are not able to handle the case of overconstrained but consistent systems, while most instance solvers can find the solution. In the example above, a generic solver may be able to determine that there is a solution, yet may not be able to construct it, in the special case that the values of the constraints force the configuration to be an (overconstrained) triangle.

        
      Figure 2: A well-constrained sketch may yield fundamentally
                different solutions.

An underlying principle fundamental to most constraint solvers is the fact that the position of the geometric elements can be expressed as (nonlinear) algebraic equations, with the constraints as parameters in the equations. This means that a well-constrained profile may have an exponential number of distinct solutions, dependent on the number of geometric elements. For example, Figure 2 shows three possible solutions of a well-constrained profile that differ in the interpretation of the function of the arc, the tangency type, and the right angle constraint between two segments. From the user's perspective, only one solution will be correct.

Constraint solvers select what they consider the intended solution by deducing certain topological and metric properties from the user's sketch of the profile. The deductions are based on a few heuristic rules that succeed under normal circumstances with high probability. These rules are appropriate when the user sketch is, in a technical sense, ``close'' to the intended solution. This may or may not be the case, and is often not the case when the dimensional constraints of a profile are changed in value, a common occurrence in redesign.

Surprisingly, most solvers have almost no provisions that would allow the user to select a different solution if the solver's heuristics fail. Developing effective paradigms for redirecting a solver interactively is an important problem, and is addressed in papers by Hoffmann and Fudos [7], [33]. A discussion of the heuristics they suggest and the method for modifying solutions with their constraint solver is also available within this document.

In the following sections, we consider four different methods for constraint solving. For each, we consider its classification as a generic or instance solver.