Département d'informatique, Institut d'informatique fondamentale IIF (Laboratoire d'intelligence artificielle LIA)

Constraint consistency techniques for continuous domains

Sam, Jamila ; Faltings, Boi V. (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 1995 ; no 1423.

Add to personal list
    Summary
    Constraint Satisfaction Problems (CSPs) are ubiquitous in computer science. Many problems, ranging from resource allocation and scheduling to fault diagnosis and design, involve constraint satisfaction as an essential component. A CSP is given by a set of variables and constraints on small subsets of these variables. It is solved by finding assignments of values to the variables such that all constraints are satisfied. In its most general form, a CSP is combinatorial and complex. In this thesis, we consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing a single optimal solution, we address the problem of computing a compact representation of the space of all solutions that satisfy the constraints. This has the advantage that no optimization criterion has to be formulated beforehand, and that the space of possibilities can be explored systematically. In certain applications, such as diagnosis and design, these advantages are crucial. In consistency techniques, the solution space is represented by labels assigned to individual variables or combinations of variables. When the labeling is globally consistent, each label contains only those values or combinations of values which appear in at least one solution. This kind of labeling is a compact, sound and complete representation of the solution space, and can be combined with other reasoning methods. In practice, computing a globally consistent labeling is too complex. This is usually tackled in two ways. One way is to enforce consistencies locally, using propagation algorithms. This prunes the search space and hence reduces the subsequent search effort. The other way is to identify simplifying properties which guarantee that global consistency can be enforced tractably using local propagation algorithms. When constraints are represented by mathematical expressions, implementing local consistency algorithms is difficult because it requires tools for solving arbitrary systems of equations. In this thesis, we propose to approximate feasible solution regions by 2k-trees, thus providing a means of combining constraints logically rather than numerically. This representation, commonly used in computer vision and image processing, avoids using complex mathematical tools. We propose simple and stable algorithms for computing labels of arbitrary degrees of consistency using this representation. For binary constraints, it is known that simplifying convexity properties reduces the complexity of solving a CSP. These properties guarantee that local degrees of consistency are sufficient to ensure global consistency. We show how, in continuous domains, these results can be generalized to ternary and in fact arbitrary n-ary constraints. This leads to polynomial-time algorithms for computing globally consistent labels for a large class of constraint satisfaction problems with continuous variables. We describe and justify our representation of constraints and our consistency algorithms. We also give a complete analysis of the theoretical results we present. Finally, the developed techniques are illustrated using practical examples.
    Résumé
    De nombreux problèmes pratiques, allant de l'allocation de ressources et à l'ordonnancement aux problèmes de conception et de diagnostic automatisés, se formulent aisément comme problèmes de satisfaction de contraintes (PSC). Un PSC se défini comme étant un ensemble de contraintes impliquant un certain nombre de variables. Le but consiste simplement à trouver un ensemble de valeurs à assigner aux variables, de sorte que l'ensemble des contraintes soient satisfaites. Dans le cas le plus général les problèmes de satisfaction de contraintes ont un aspect fortement combinatoire qui leur confère un grande complexité. Nous nous intéressons dans le cadre de cette thèse aux problèmes de satisfaction de contraintes en domaines numériques, continus. Contrairement aux méthodes mathématiques classiques qui tentent d'identifier une solution unique et optimale, nous nous intéressons à fournir une description concise — et la plus complète possible — de l'ensemble des solutions. L'avantage d'une telle description est qu'elle ne nécessite pas de formuler de critères d'optimisation et qu'il devient possible d'explorer systématiquement l'espace des possibilités. Ces avantages présentent un intérêt fondamental pour certaines disciplines pratiques telles que la conception ou le diagnostic. Les méthodes auxquelles nous nous intéressons pour obtenir de telles descriptions sont les méthodes dites de "cohérence" (consistency). Ces techniques construisent une description de l'ensemble des solutions, partielles ou complètes, en attachant à chaque variable (ou ensemble de variables) un label décrivant l'ensemble des valeurs admissibles. Lorsqu'un label est globalement cohérent, toutes les valeurs qu'il spécifie font partie d'au moins une solution du problème. Ces labels fournissent alors une description, concise et complète de l'espace des solutions et peuvent être utilisés par d'autres techniques de raisonnement. Comme le calcul de labels globalement cohérents peut s'avérer complexe, deux approches son généralement mises en oeuvre pour en contourner la difficulté. La première, consiste à se contenter de construire des labels partiellement cohérent en utilisant des algorithmes de cohérence locale. Ceci permet de supprimer de l'espace des solutions, des valeurs localement incohérentes. L'espace des solutions potentielles ainsi réduit peut alors être exploré à moindre coût. En domaines continus, si les contraintes sont représentées par des expressions mathématiques, l'implantation d'algorithmes de cohérence nécessite l'emploi d'outils numériques destinés à résoudre des systèmes arbitraires de contraintes. Dans le cas où les contraintes sont non linéaires, les outils existant sont difficiles à mettre en oeuvre et posent de nombreux problèmes — notamment en matière de convergence. Dans le cadre de cette thèse, nous nous proposons d'approximer les contraintes numériques en utilisant une décomposition hiérarchique des domaines de faisabilité — sous la forme d'arbres 2k (2k-trees). Cette représentation, fréquemment utilisée dans les domaines de la vision et du traitement de l'image, permet de combiner des contraintes logiquement plutôt que numériquement et évite l'emploi d'outils mathématiques sophistiqués. Nous proposons alors des algorithmes simples et stables calculant des labels de n'importe quel degré de cohérence locale. La seconde approche consiste à identifier des classes de problèmes pour lesquelles des labels globalement cohérents peuvent être calculés efficacement. Ainsi, il est prouvé que pour des contraintes binaires, certaines formes de convexité réduisent considérablement le complexité du problème et permettent de calculer des labels globalement cohérents en utilisant des algorithmes de cohérence locale. Nous montrons dans cette thèse que de tels résultats se généralisent à des contraintes d'arités arbitraires en domaine continu. Ceci permet d'identifier des solutions polynomiales pour des classes importantes de PSCs continus. Dans le cadre de cette dissertation, nous décrivons et justifions les représentations et algorithmes mis en oeuvre, nous effectuons une analyse théorique complète des résultats présentés et nous illustrons les techniques implantées au moyens d'exemples pratiques.