logo epfl    School of Computer and Communication Sciences I&C LIA logo
Ecole Polytechnique Fédérale de Lausanne

EPFL > IC > LIA > Research > Archive > Distributed Constraint Satisfaction

Artificial Intelligence Laboratory LIA


Distributed Constraint Satisfaction and Optimization

Constraint satisfaction and optimization is a general framework for expressing many combinatorial problems, and is widely used, particularly for resource allocation, scheduling and planning applications. Often, such problems are distributed over multiple agents that control parts of the variables and constraints, and might want to apply different methods to solve them. Over the past decade, we have developed a series of methods for distributed constraint satisfaction and optimization.

  • Asynchronous Aggregation Search (AAS) was our first distributed CSP algorithm. It forms aggregates of values and thus dramatically reduces the complexity of earlier methods such as asynchronous backtracking (ABT). By the same token, it also allows constraints to be controlled by single agents.
  • In the context of AAS, we also developed new techniques for variable reordering and maintaining arc concistency. A cleaned-up overview appears here.
  • We considered coordination problems in large projects with multiple agents, such as the LHC constructed at CERN. We developed new techniques based on local search and validated them on real planning data from CERN. Carlos Eisenberg has started a company, Synctec, mostly based on this work.
  • We have considered the question of how to minimize the amount of information that must be collected from agents to compute a consistent or optimal solution to a constraint satisfaction problem. We have defined the framework of open constraint programming to characterize this situation. In open constraint programming, variable domains are not known a priori and are only discovered through queries to agents. In most cases, even optimal solutions require only partial knowledge of domains. For optimization, we have an algorithm that is provably optimal, and we also have a distributed version of this algorithm.
  • We have developed a series of algorithms based on dynamic programming. They exploit the fact that distributed problems often have a relatively low treewidth and are thus very suitable for solution by dynamic programming methods. Starting with the basic algorithm, DPOP, we have developed a series of algorithms that build on it and address various shortcomings of dynamic programming. This framework has turned out to be many orders of magnitude more efficient than search-based approaches and has allowed us to solve much larger problems than any earlier algorithm. An overview of the large amount of work on this topic can be gained from the publications of Adrian Petcu.
  • To address the issue of privacy, we have proposed a family of variants of DPOP that make use of code names, obfuscation and homomorphic encryption to provide strong guarantees that any agent's private knowledge of the problem will not be revealed to the other agents. We have applied these algorithms to various problem classes including vehicle routing problems, and we have shown that our algorithms could largely outperform the previous state of the art in privacy-preserving algorithms.
  • We have also investigated the issue of uncertainty in the problem data, by extending the traditional DCOP framework to that of DCOP under Stochastic Uncertainty (StochDCOP), in which sources of uncertainty are modeled by random variables with known probability distributions. Our novel StochDCOP algorithms are able to discover and exploit the locality of each source of uncertainty to improve efficiency.

Additionally, we have developed and publicly released a "FRamework for Open/Distibuted Optimization" FRODO, which is a Java platform that provides implementations for a large number of algorithms, including SynchBB, MGM and MGM-2, ADOPT, DSA, DPOP, S-DPOP, MPC-Dis(W)CSP4, O-DPOP, AFB, MB-DPOP, Max-Sum, ASO-DPOP, P-DPOP, P2-DPOP, E[DPOP], Param-DPOP, and P3/2-DPOP. The platform makes it possible to simulate multiple agents on a single machine, and also to solve problems in a fully distributed fashion, involving multiple machines communicating over TCP/IP. Random problem generators are provided to carry out performance experiments on a number of problem classes, including graph coloring, meeting scheduling, random Max-DisCSPs, combinatorial auctions, kidney exchange, graphical games, and vehicle routing. The platform is available under an free software license from the dedicated FRODO website

Current projects:

Past projects:

© 2011 EPFL all rights reserved Login