Project : coprin

Section: New Results

Keywords : distance equations , numerical robustness .

Distance constraints

Systems of distance constraints occur frequently in various application fields such as mechanism theory, CAD, molecular biology. This motivates a large effort of the project to develop specific solvers, combining theoretical works on the analysis of these equations (including taking into account uncertainties in the constraints), effective implementation and extensive testing.

Improved exclusion scheme for distance constraints

Participant : Jean-Pierre Merlet.

An exclusion scheme allows one to calculate a box around a certified solution that is guaranteed to contain only this solution. Propagation of this box on the search space enables to reduce it, thereby improving the global efficiency of the solver.

For distance constraints we have already provided a specific version of the Kantorovitch scheme that produces a larger box than the general version of the theorem. We have then investigated the inflation approach of Neumaier [7] based on the H-matrix theory. In its general version this method determines incrementally the largest exclusion box and is relatively computer intensive. We have shown that for the specific case of distance constraints we may compute directly the width of the exclusion box without relying on an iterative scheme. This calculation has been implemented in the specific distance constraints solver of ALIAS.

Semantic decomposition for solving distance constraints

Participants : Heikel Batnini, Michel Rueher.

Most of the solver of numerical CSP are based on a relaxation of local consistencies. These techniques prune the domains of the variables by computing an external approximation of the solution space. However, the resulting domains may still contain a huge number of locally inconsistent values, especially when the solution space is composed of disjoint subspaces. Splitting techniques are often used to isolate solutions. However, splitting is ineffective in the presence of continuous subspaces of solutions. Moreover classical splitting methods do not take advantage of the properties of the constraints, especially and more particularly the properties of geometrical constraints.

We have introduced in [18] [19] a domain decomposition, based on the semantic properties of distance constraints. This method splits and reduces the domains of two points w.r.t. their distance relation, using the monotonic and convex parts of the canonical form of the equations. We halve also proposed a new pruning technique, named LDF (Local Decomposition Filtering), propagates this decomposition over the whole set of constraints, following the standard approximation scheme. The disjoint subspaces of solutions are represented by a graph of sub-domains which has the same structural properties as the arc-consistency graph of a CSP on finite domains. Thus, classical search algorithms, such as MAC (Maintaining Arc Consistency) or FC (Forward Checking), may be used to isolate potential solution subspaces. We have demonstrated that LDF achieves a better pruning than 2B-consistency, and is more efficient than a combination of 2B-consistency and splitting, for small but interesting problems.

Further works concern the integration of this semantic decomposition in a general splitting algorithm for solving a larger class of problems, such as classical robotic benchmarks.

Uncertainty management

Participants : Carlos Grandon, Bertrand Neveu.

We have studied how to manage small uncertainties in the parameters of a system of distance equations. The problem has no more isolated solution points, but isolated sub-spaces of solutions and we cannot directly apply classical interval solvers. We have proposed the following method: we first compute the solutions of the system without uncertainties and then we use these solutions to determine a dynamic splitting policy of the domains. Filtering algorithms (for example 3B-consistency) are then applied to each subspace to obtain boxes containing the solutions of the system with uncertainties. We have studied the limitations of this method. It is complete (no region with solutions is lost) but the regions finally found do not always correspond to an extension around the solution points without uncertainties. If new regions with solutions appear when the uncertainties are taken into account, the method is not able to isolate them. When regions overlap, the splitting will separate two regions that will be each smaller than the extensions of solution points. Finally, we have started to extend our method to other types of equations.