Faculté informatique et communications IC, Section d'informatique, Institut d'informatique fondamentale IIF (Laboratoire d'intelligence artificielle LIA)

Rigorous solution techniques for numerical constraint satisfaction problems

Vu, Xuan-Ha ; Sam, Jamila (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3155.

Ajouter à la liste personnelle
    Summary
    A constraint satisfaction problem (e.g., a system of equations and inequalities) consists of a finite set of constraints specifying which value combinations from given variable domains are admitted. It is called numerical if its variable domains are continuous. Such problems arise in many applications, but form a difficult problem class since they are NP-hard. Solving a constraint satisfaction problem is to find one or more value combinations satisfying all its constraints. Numerical computations on floating-point numbers in computers often suffer from rounding errors. The rigorous control of rounding errors during numerical computations is highly desired in many applications because it would benefit the quality and reliability of the decisions based on the solutions found by the computations. Various aspects of rigorous numerical computations in solving constraint satisfaction problems are addressed in this thesis: search, constraint propagation, combination of inclusion techniques, and post-processing. The solution of a constraint satisfaction problem is essentially performed by a search. In this thesis, we propose a new complete search technique (i.e., it can find all solutions within a predetermined tolerance) for numerical constraint satisfaction problems. This technique is general and can be used in place of branching steps in most branch-and-prune methods. Moreover, this new technique speeds up the most recent general search strategy (often by an order of magnitude) and provides a concise representation of solutions. To make a constraint satisfaction problem easier to solve, a major approach, called constraint propagation, in the constraint programming1 field is often used to reduce the variable domains (by discarding redundant value combinations from the domains). Basing on directed acyclic graphs, we propose a new constraint propagation technique and a method for coordinating constraint propagation and search. More importantly, we propose a novel generic scheme for combining multiple inclusion techniques2 in numerical constraint propagation. This scheme allows bringing into the constraint propagation framework the strengths of various techniques coming from different fields. To illustrate the flexibility and efficiency of the generic scheme, we base on this scheme and devise several specific combination strategies for rigorous numerical constraint propagation using interval constraint propagation, interval arithmetic, affine arithmetic, and linear programming. Our experiments show that the new propagation techniques outperform previously available methods by 1 to 4 orders of magnitude or more in speed. We also propose several post-processing techniques for the representation of continuums of solutions. Based on connectedness, they allow grouping each cluster of connected solution subsets into a larger subset, thus allowing getting additional grouping information. Potentially, these techniques enable interval-based solution techniques to be alternatives to bounding-volume techniques in applications such as collision detection and interactive graphics. __________________________________________________ 1 Constraint programming is an approach to programming that relies on both reasoning and computing. 2 An inclusion technique is to include a set of interest into enclosures. It is also called an enclosure technique.
    Résumé
    Un problème de satisfaction de contraintes se compose d'un ensemble d'énoncé de contraintes quel tuples des valeurs dans les domaines des variables sont admis. Il s'appelle numérique si ses domaines des variables sont continus. La résolution d'un problème de satisfaction de contraintes est de trouver un ou plusieurs tuples des valeurs satisfaisant à toutes ses contraintes. Les calculs numériques sur les nombres en points flottants des ordinateurs souffrent souvent d'erreurs d'arrondis. Le contrôle rigoureux de ces erreurs d'arrondis est fortement désiré dans de nombreuse applications, parce qu'il permet d'améliorer la qualité et la fiabilité des décisions basées sur les solutions trouvées. Cette thèse est consacrée à divers aspects du calcul numérique rigoureux lors de la résolution de problèmes de satisfaction de contraintes: la recherche, la propagation de contraintes, la combinaison des techniques d'inclusion, et le post-traitement. La résolution d'un problème de satisfaction de contraintes est habituellement exécutée par une recherche. Nous proposons une nouvelle technique de recherche complète (c-à-d, elle peut trouver toutes les solutions à une tolérance prédéterminée) pour des problèmes de satisfaction de contraintes avec des domaines continus. Cette technique est générique et peut être utilisée en guise de la technique de branchement dans la plupart des méthodes de type branch-and-prune. De plus, cette technique accélère la technique de recherche générale la plus récente (souvent par un ordre de magnitude) et fournit une représentation concise des solutions. Pour faciliter un problème de satisfaction de contraintes à résoudre, une approche dans la programmation par contrainte1, appelée la propagation de contraintes, est souvent utilisée pour réduire les domaines des variables (en enlevant quelques tuples de valeurs redondantes des domaines). Basée sur les graphes acycliques orientés, nous proposons une nouvelle technique de propagation de contraintes et une méthode pour coordonner la propagation de contraintes et la recherche. De plus, nous proposons un nouveau schéma générique pour combiner des techniques d'inclusion2 multiples dans la propagation de contraintes numériques. Ce schéma permet de bénéficier de la propagation de contraintes de la puissance de techniques provenant de diverses disciplines. Pour illustrer la flexibilité et l'efficacité du schéma générique, nous imaginons du schéma plusieurs stratégies spécifiques de combinaison impliquant la propagation de contraintes d'intervalles, l'arithmétique d'intervalle, l'arithmétique affine, et la programmation linéaire. Nos expériences prouvent que la nouvelle approche surpasse des techniques précédemment disponibles par un à quatre ordres de magnitude ou plus en vitesse. En plus, nous proposons plusieurs techniques de post-traitement pour la représentation des continuums de solutions. Elles permettent de grouper des sous-ensembles de solutions connectées dans de plus grand sous-ensembles, améliorant ainsi la concision de la représentation. Ceci permet potentiellement aux techniques de résolution basées sur des intervalles de se substituer aux techniques de bounding-volume classiques dans des applications telles que la détection de collision ou le graphisme interactif. __________________________________________________ 1 La programmation par contrainte est une approche qui combine raisonnement et calcul. 2 Une technique d'inclusion (ou technique de clôture) doit inclure un ensemble d'intérêts dans des clôtures.