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

On the generation of locally consistent solution spaces in mixed dynamic constraint problems

Gelle, Esther ; Faltings, Boi V. (Dir.)

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

Ajouter à la liste personnelle
    Summary
    The development of industrial products such as cars, mechanical tools as well as civil engineering structures includes the task of identifying components and arranging them in a product structure. This task is commonly called configuration. It can be formalized as a constraint satisfaction problem (CSP), which provides a concise mathematical model for combinatorial tasks. A CSP is defined by the variables of interest, each with a domain of possible values, and a set of constraints which restrict the allowed value combinations. The formulation of a configuration task as a CSP gives flexibility required to apply complex optimization criteria during search which often cannot be expressed by a single utility function. Solving a CSP corresponds to finding a consistent assignment to the variables that satisfies all constraints. Solution methods for CSPs encompass consistency and search techniques. Consistency techniques are preprocessing methods which remove inconsistent value combinations before search thus reducing the search space; Furthermore, a dynamic CSP model (DCSP) makes possible the introduction of new variables and constraints during problem resolution. However, CSP techniques have been weak for handling mixed (discrete-continuous) as well as dynamic problems. In this thesis, I present a new algorithm for solving DCSPs with mixed, continuous and discrete, constraints. It isolates and approximates the solution sets of a DCSP by local consistency techniques. To this purpose, local consistency techniques for continuous constraints had to be enhanced and integrated with existing discrete local consistency methods. Some advantages of this algorithm are: It can solve problems in which the existence of a variable depends on a decision taken over a continuous value domain. Different locally consistent solution spaces can be compared, thus providing additional information for decision making. Local consistency techniques are also applied to search for a single solution within the resulting locally consistent solution spaces. These techniques are particularly efficient for searching in continuous domains. The algorithm proposed is applied to a number of different problems such as conceptual bridge design, design of steel structures, configuration of trains, and industrial mixers.
    Résumé
    Le développement de produits industriels, comme par exemple une voiture, une pièce mécanique mais également une structure métallique en génie civil, implique l'identification des composants du produit ainsi que leur arrangement dans l'espace. Cette tâche est appelée configuration. Elle peut être formalisée comme un problème de satisfaction de contraintes (CSP en anglais), qui fournit un modèle mathématique concis pour des problèmes combinatoires. Un CSP est défini par un ensemble de variables caractérisant le problème et un ensemble de contraintes qui restreignent les combinaisons de valeurs des variables dans une solution. La formulation d'une tâche de configuration comme CSP permet d'appliquer des critères d'optimisation complexes pendant la recherche qui ne peuvent guère s'exprimer sous la forme d'une fonction objective. Résoudre un CSP correspond à trouver une assignation de valeurs aux variables qui satisfait toutes les contraintes. Les méthodes pour résoudre un CSP incluent des techniques de consistance et de recherche. Les techniques de consistance permettent de découvrir des combinaisons de valeurs incompatibles et de les enlever avant de lancer la recherche d'une solution. Elles visent ainsi à réduire l'espace de recherche. En outre, un modèle de CSP dynamique, appelé DCSP en anglais, permet d'introduire de nouvelles variables et contraintes pendant la recherche. Cependant, les méthodes de résolution actuelles de CSP ne sont pas bien adaptées aux problèmes mixtes (traitant des données continues et discrètes) et dynamiques. Dans cette thèse, je présente un nouvel algorithme de résolution de DCSP défini sur des contraintes discrètes et continues. L'algorithme trouve une approximation de l'ensemble de solutions du DCSP par des méthodes de consistance locale. Pour parvenir à ce but, des techniques de consistance locale pour les contraintes continues ont été améliorées et intégrées dans un algorithme comprenant des méthodes de consistance locale pour contraintes discrètes. Les avantages de l'algorithme proposé sont: Des problèmes dans lesquels l'existence d'une variable dépend d'un choix dans le domaine continu peuvent être résolus. Les espaces de solution localement consistants peuvent être comparés, ce qui fournit des informations complémentaires utile à la prise de décision. Les techniques de consistance locale sont aussi appliquées à la recherche d'une solution individuelle dans un espace localement consistant. Ces algorithmes sont particulièrement efficaces dans le domaine continu. L'algorithme proposé est appliqué à différents problèmes réels comme la conception préliminaire de ponts, la conception de structures métalliques en génie civil, la configuration de trains ou de mixers industriels.
    Zusammenfassung
    Die Entwicklung und Optimierung von Produkten wie Autos, mechanische Werkzeuge und Gebäudestrukturen besteht unter anderem darin, Einzelkomponenten aus einem Katalog zu bestimmen sowie deren Anordnung im Endprodukt festzulegen. Dieser Teil der Produkteentwicklung wird als Konfiguration bezeichnet. Konfiguration ist ein kombinatorisches Problem und kann daher als Constraint Satisfaction Problem (CSP) mathematisch modelliert werden. Ein CSP besteht aus Variablen und Constraints. Jede Variable besitzt eine Wertemenge aus der ihr ein Wert zugewiesen wird. Constraints definieren erlaubte Wertekombinationen über diese Variablen (z.B. (Un)gleichungen, diskrete Wertekombinationen). Die Lösung eines CSPs weist den Variablen konsistente Werte zu; d. h. Werte, die keine der Constraints verletzen. CSPs werden mit speziellen Such- sowie mit Hilfe von Konsistenz-Algorithmen gelöst. Konsistenz-Algorithmen entfernen inkonsistente Wertekombinationen aus dem Suchraum und vereinfachen dadurch eine anschliessende Suche nach Lösungen. Dynamische CSPs erweitern das Modell, indem sie das Hinzufügen von Variablen und Constraints während der Suche ermöglichen. Die bisherigen Lösungsansätze unterschieden streng zwischen numerischen und diskreten CSPs. Ausserdem existierten Ansätze zur Lösung dynamischer CSPs nur im diskreten Bereich. Komplexe Konfigurationsprobleme erfordern jedoch die Kombination diskreter und numerischer Variablen sowie eine dynamische Formulierung. In der vorliegenden Dissertation beschreibe ich ein Verfahren, das die Lösung solch kombinierter dynamischer CSPs ermöglicht. Das Verfahren isoliert die verschiedenen Lösungsräume innerhalb des Suchraumes und approximiert diese mit Hilfe von lokalen Konsistenz-Algorithmen. Dies erforderte eine Erweiterung der bestehenden lokalen Konsistenz-Methoden insbesondere für numerische Constraints und auch die Integration von numerischen und diskreten Methoden. Vorteile unserers Verfahrens sind: Verschiedene lokal konsistente Lösungsräume können verglichen werden bevor eine Design-Entscheidung getroffen wird. Konsistenz-Methoden erlauben zudem eine Optimierung der Suchalgorithmen, indem der Suchraum zusätzlich beschränkt wird. Dieses Verfahren wurde an mehreren Beispielen wie Brücken-Design, Konfiguration von Zügen and Mixern, sowie bei der Konfiguration von Gebäudestrukturen angewendet.