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

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.

Collaborative design using solution spaces

Claudio Lottaz

Complex design tasks from many domains such as mechanical, electrical and civil engineering make the collaboration of many partners unavoidable for several reasons: knowledge from various experts is necessary, often more than one enterprises are involved and deadlines impose concurrent engineering. However, collaboration also leads to certain in-conveniences such as information loss and misunderstandings during communication and iterative negotiation when suggested partial solutions for sub-tasks conflict. Moreover, major problems are related to management of changes and ensuring design consistency. This thesis conjectures that many of these problems are caused by the use of single solutions during negotiation. Currently, project partners assign single values for sub-tasks and then proceed, often after tedious negotiations with other partners, to integrate these partial solutions into solutions for the whole project. While partners determine one single solution for a sub-task, much information about potential alternatives is lost and premature decisions are taken. The integration of partial solutions then often leads to artificial conflicts which are not due. to incompatible design goals but arise because information about possible compromises is no longer available. Consequently, many changes usually occur during negotiation about parameter values and much, effort must be invested in. order to keep the design consistent. Therefore, we investigate the use of solution spaces instead of single solutions. When solution. spaces are used during negotiation, more information about alternatives is avail-able, premature decisions are avoided and thus, no artificial conflicts arise. Moreover, since project partners provide formal information about project requirements, real conflicts between diverging project goals can be detected. However, the implementation of a collaboration system using solution spaces is far from trivial, since in general the computation of exact solution spaces is intractable. We employ constraint satisfaction techniques in order to calculate solution space approximations. Constraints arise naturally in many fields of engineering and are therefore suited to formally express project requirements. Using constraints on design parameters, project partners can describe large families of acceptable solutions. Moreover, descriptions using constraints can be easily adapted to changes in the project's context. When project descriptions in terms of constraints are available, constraint satisfaction techniques such as consistency can be employed to provide computational support during collaboration. Consistency algorithms use local inconsistencies to prune regions from the original search space where no solution can be expected and thus provide approximations of solution spaces. Algorithms which ensure low degrees of consistency provide a rough over-estimation of the solution space but have low complexity, while algorithms which enforce high degrees of consistency provide a tight estimation of the solution space but suffer from high complexity. Since consistency algorithms provide over-estimations of solution spaces they are suited to find real conflicts between the various project requirements. In fact, using constraint satisfaction techniques in collaboration splits negotiation into two phases: negotiation of project requirements and negotiation about parameter values. During the negotiation of requirements, expressed as constraints, partners search for a feasible set of restrictions. Given such a set of restrictions, partners can negotiate about parameter values within the corresponding solution space approximation. During negotiation about parameter values some support for decision-making can be provided by analysing the shape of the solution space approximations. In order to illustrate the use of constraint satisfaction techniques in collaborative de-sign, a prototype of an Internet-based communication platform has been implemented, which focuses on the exchange of data related to constraints and solution spaces, including the visualisation of constraints and projections of solution space approximation. It provides access to several constraint satisfaction algorithms. Moreover, some standard techniques were extended as follows: A reformulation algorithm transforms algebraic constraint satisfaction problems (CSPs) into ternary form, i.e., such that they contain exclusively constraints involving at most three variables. Thereby, few auxiliary variables are introduced and certain intermediary variables are removed in order to provide a small CSP in ternary form. In addition, the use of interval arithmetic techniques to discretise continuous constraints is proposed. Moreover, variants of 2-consistency and 3-consistency for ternary CSPs have been developed and an improvement of (3,2)-relational consistency's space efficiency. Finally, a description of search heuristics for interactive use is described. The results of this research have been evaluated in the context of the construction industry. Construction projects are suitable test cases for collaboration systems, since they always imply complex interactions between several partners from various domains. With the help of practitioners, three realistic examples have been modelled. These projects demonstrate the usefulness of constraint satisfaction techniques during negotiation and collaboration within design projects. Constraint-based support leads to better management of changes and easier implementation of least commitment decision strategies. The results of this research may therefore improve the performance of collaboration systems currently in use.

EPFL2000

Automated Design: A Journey Across Modelling, Optimization, and Education

Cyril Picard

Machine intelligence greatly impacts almost all domains of our societies. It is profoundly changing the field of mechanical engineering with new technical possibilities and processes. The education of future engineers also needs to adapt in terms of techniques and even skills. Using the design of electro-mechanical actuators as a common thread, this work explores the many-facets of automated design: modeling, optimization, and education, and looks for the prerequisites essential to its successful application. The journey starts by building a modular and integrated model. It focuses on the prediction of system-level specifications that yield high added-value for decision-makers and shorten the path from the model to the final product. Combined with multi-objective evolutionary algorithms (MOEAs) and visualization tools, the model forms an automated design tool that helps engineers and decision-makers to rapidly get important insights into their design task. Its potential and benefits are validated through two specific applications. The results, however, also highlight a gap between the reported performance of optimizers on common benchmark problems and the actual performance on these problems. To further develop optimizers, appropriate and realistic benchmark problems are needed. A subset of the integrated design model is used to formulate a new test suite called MODAct, composed of 20 constrained multi-objective optimization problems (CMOPs) with variable levels of complexity. In addition, numerical approaches to evaluate the constraint landscape of CMOPs are introduced and applied to identify the differences in features of MODAct against 45 benchmark problems from literature. Further, the convergence performance of three algorithms on the same problems highlights the key role of constraints and, in particular, the number of simultaneously violated constraints in MODAct problems. In a next step, existing constraint handling strategies suitable for MOEAs along with a newly proposed technique for many-constraint problems are evaluated. Their parameters are tuned for different problems. The performance of the various configurations further highlights the difference between MODAct and other benchmark problems and show the highly competitive results of the proposed constraint handling technique on realistic design problems. As the technical limits are removed, the impact of automated design on the work of future engineers should be considered. On the one hand, the development of professional skills by students working on team project in different settings has been evaluated thanks to 205 students from three classes. Explicitly addressing these skills within the project seems key to support stronger and broader learning, suggesting changes that do not require a full curriculum redesign. On the other hand, nine groups (33 students) have been asked to design an actuator using a conventional approach followed by an automated design approach. The actuators suggested by students using the automated tool outperform the designs obtained through the traditional approach. Six groups even suggest solutions cheaper, three of which are also smaller, than the product of experienced industry engineers. Students proved thus capable of leveraging the tool within a short time. The analysis of their mistakes suggests possible improvements for future tools. As these students leave university, they carry the hope to see such methods spread in industry.

EPFL2021

Constraint consistency techniques for continuous domains

Jamila Sam

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.

EPFL1995