**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Constraint consistency techniques for continuous domains

Résumé

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.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (31)

Computing

Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and developm

Informatique

alt=Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève|vignette|Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève (2017).
L'informatique est un domaine d'acti

Vision par ordinateur

La vision par ordinateur est un domaine scientifique et une branche de l’intelligence artificielle qui traite de la façon dont les ordinateurs peuvent acquérir une compréhension de haut niveau à par

Publications associées (59)

Chargement

Chargement

Chargement

In this thesis, we revisit classic problems in shared-memory distributed computing through the lenses of (1) emerging hardware technologies and (2) changing requirements. Our contributions consist, on the one hand, in providing a better understanding of the fundamental benefits and limitations of new technologies, and on the other hand, in introducing novel, efficient tools and systems to ease the task of leveraging new technologies or meeting new requirements. First, we look at Remote Direct Memory Access (RDMA), a networking hardware feature which enables a computer to access the memory of a remote computer without involving the remote CPU. In recent years, the distributed computing community has taken an interest in RDMA due to its ultra-low latency and high throughput and has designed systems that take advantage of these characteristics. However, we argue that the potential of RDMA for distributed computing remains largely untapped. We show that RDMAâs unique semantics enable agreement algorithms which improve on fundamental trade-offs in distributed computing between performance and failure-tolerance. Furthermore, we show the practical applicability of our theoretical results through Mu, a state machine replication system which can replicate requests in under 2 microseconds, and can fail-over in under 1 millisecond when failures occur. Muâs replication and fail-over latencies are at least 61% and 90% lower, respectively, than those of prior work. Second, we focus on persistent memory, a novel class of memory technologies which is only now starting to become available. Persistent memory provides byte-addressable persistent storage with access times comparable to traditional DRAM. Recent work has focused on designing tools for working with persistent memory, but little is known about the fundamental cost of providing consistency in persistent memory. Furthermore, important shared-memory primitives do not yet have efficient persistent implementations. We provide an answer to the former question through a tight bound on the number of persistent fences required to implement a lock-free persistent object. We address the latter problem by presenting a novel efficient multi-word compare-and-swap algorithm for persistent memory. Third and finally, we consider the current exponential increase in the amount of data worldwide. Memory capacity has been on the rise for decades, but remains scarce when compared to the rate of data growth. Given this scarcity and the prevalence of concurrent in-memory processing, the classic problem of concurrent memory reclamation remains highly relevant to this day. Previous work in this area has produced solutions which are either (a) fast but easily disrupted by process delays, or (b) slow but robust to process delays. We combine the best of both worlds in QSense, a memory reclamation algorithm which is fast in the common case when there are no process delays and falls back to a robust reclamation algorithm when process delays prevent the fast path from making progress.

, , ,

Sinal-processing on graphs has developed into a very active field of research during the last decade. In particular, the number of applications using frames con-structed from graphs, like wavelets on graphs, has substantially increased. To attain scalability for large graphs, fast graph-signal filtering techniques are needed. In this contribution, we propose an accelerated algorithm based on the Lanczos method that adapts to the Laplacian spectrum without explicitly computing it. The result is an accurate, robust, scalable and efficient algorithm. Compared to existing methods based on Chebyshev polynomials, our solution achieves higher accuracy without increasing the overall complexity significantly. Furthermore, it is particularly well suited for graphs with large spectral gaps.

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.