ALIAS, a System Solving Library Based on Interval Analysis

by Jean-Pierre Merlet

ALIAS is a C++/Maple library based on interval arithmetics, designed for system solving and optimization problems. It has been developed in the framework of the COPRIN project since 1999. Next to general purpose schemes it addresses systems with a particular structure, and intensively uses symbolic computation.

Interval arithmetics is a well known method that enables one to compute bounds for almost any analytically defined expression F(X), being given ranges for the unknowns.

Such computations are required to determine, for example, the range of action of a robot, or possible molecular structures, satisfying certain constraints. The interval obtained by applying interval arithmetics on a mathematical expression is called the ‘interval evaluation’ of the expression and can be implemented so that numerical round-off errors are taken into account, ie the interval evaluation will always include the exact value of the mathematical expression for any instance of the unknowns within their ranges.

A direct application of this property for systems solving is that if the interval evaluation of the left hand side of at least one equation of the system F(X) = 0 does not include 0, then there is no solution for the system within the given ranges for the unknowns. A straightforward solving algorithm for determining the real roots of a system within some search space can easily be implemented using a branch-and-bound method. A ‘box’ is defined as a set of ranges, one for each unknown, and a list L of boxes B₀, B₁, B₂, ...,B_n will be maintained during the solving procedure and will be initialized with a box B₀ which describes the initial search space. An index i, initialized to 0, will indicate the number of the currently processed box in L.
The solving algorithm proceeds along the following steps:

• compute the interval evaluation of all equations of the system for the unknowns with the range indicated in box Bi
• if the interval evaluation of one equation does not include 0, then increment i and goto step 1
• if all interval evaluations include 0:
  • a) if the widths of the ranges for all unknowns is lower than a given threshold, then store Bi as a solution. Increment i and goto step 1
  • b) otherwise choose one unknown and bisect its range. Two new boxes are created and are put at the end of L. Increment i and goto step 1.

This algorithm stops when all boxes in L have been processed, and returns as solutions a set of boxes. It may be seen already that this basic algorithm may be extended without effort to deal with inequalities constraints and global optimization. Furthermore, distributed implementation is possible as the processing of one box is independent from the processing of all other boxes in L.
This basic algorithm may be drastically improved by using:

• ‘filtering operators’: these operators use the structure of the equation to reduce the width of the ranges of a given box
• ‘exclusion operators’: these operators determine that there is no solution to the system within a given box. Interval evaluation is one example of an exclusion operator
• ‘existence and uniqueness operators’: these operators may determine that there is one unique solution within some sub-box of a given box and, if this is the case, provide a numerical scheme that allows to safely compute this solution. One example of an existence operator is the Kantorovitch theorem, which uses the Jacobian and Hessian of the system, and allows to determine a box such that the Newton scheme will always converge toward the unique solution that lies within the box.

Possible operators have been proposed from different disciplines, numerical analysis and constraints programming, but no available software offers the possibility of hybrid solving based on a combination of operators. However, various experimental trials have shown that an appropriate combination of numerical analysis and constraints programming operators leads to the most efficient solver. Hence, our objectives are twofold:

• implement and combine already proposed operators
• develop new operators and improve existing ones. New operators and their mathematical analysis have already been provided by COPRIN (for example the 3B operator), but we are also working on the mathematical background of existing operators. For example we have proven that for distance equations (see the molecular biology example below) the result of the general purpose existence operator based on the Kantorovitch theorem may drastically be improved.

ALIAS is a relatively large C++ library (200,000 lines of code) that implements various general purpose solving schemes for systems solving and optimization problems. It includes a large library of filtering, exclusion and existence operators, some of them quite original in this field.

ALIAS also includes a set of specific purpose solving schemes devoted to classes of systems with a particular structure (such as distance equations). A theoretical analysis based on the structure of the equations has been used to optimize the efficiency of the general purpose operators and to develop operators that are specific to the system, thereby drastically improving the efficiency of the schemes.

Another important feature of ALIAS is its intensive use of symbolic computation. First of all, the ALIAS C++ library may be used directly from Maple: within a Maple session it is possible to call a specific solving Maple procedure that will automatically create the necessary C++ code, compile and execute it, and return the result to the Maple session. Symbolic computation is also used to improve the efficiency of the C++ code and to create the C++ code of operators that are completely specific to the system at hand.

ALIAS is the software platform of the COPRIN project and has been in development since 1999. The library can freely be downloaded (see the information at http://www-sop.inria.fr/ coprin/logiciels/ALIAS/ALIAS.html). ALIAS has been used to solve various problems in very different domains. Here we give four examples.

Robotics 1
We consider a robot with 3 translation degrees of freedom x, y, z. Due to the mechanical structure of the robot only a limited workspace may be reached by the hand of the robot. Find the largest cube enclosed in this workspace such that all real roots r of a given polynomial, whose coefficients depend on x, y, z, satisfy 1/3 &Mac178; r &Mac178; 1.

Robotics 2
We consider a robot with 3 successive revolving joints. The geometry of the robot is defined by a set of 30 parameters that indicate the direction of the joint axis, the lengths and respective orientations of the links connecting the joints, and the location of the base of the robot. Find the possible values of these parameters such that the hand of the robot may reach 5 pre-defined poses. This is a very demanding problem that has never been solved previously. After 5 days of computation on a cluster of 25 PCs we have been able to find 98 possible solutions within a relatively large search space.

Molecular Biology
Being given a molecule with approximately 100 atoms and constraints equations indicating that the distances between some pairs of atoms should be equal to a constant, find all possible 3D shapes of the molecule, ie find all possible locations of the atoms. This involves solving a system of about 400 distance equations. The results have been obtained in 15 minutes on a laptop.

Networking
Design of an algorithm for processor sharing policy in an integrated service network. We have here a problem in two variables a, b and it must be shown that there exists at least one solution for b > 1 to a system of one equation F(a,b) = 0 and one inequality G(a) &Mac178; 0.2, where F and G contain algebraic and exponential functions.

Links:
ALIAS software library: http://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS.html

Please contact:
Jean-Pierre Merlet, INRIA
Tel: +33 4 92 38 77 61
E-mail: jean-pierre.merlet@inria.fr