Distributed Constraint Satisfaction

Author: Ismel Brito
University: Universitat Politècnica de Catalunya
Advisor: Pedro Meseguer
Year: 2007

In recent years, the Artificial Intelligence community has shown an increasing interest in solving distributed problems using the agents paradigm. When multiple agents in a shared environment pursue a common goal, there are usually constraints among the possible actions of these agents. Finding a consistent combination of actions that satisfies agents' constraints can be seen as a Distributed Constraint Satisfaction problem (\emph{DisCSP}). Various application problems in multi-agent systems can be formalized as \emph{DisCSPs}. This thesis is dedicated to the development of distributed complete algorithms for solving \emph{DisCSP}. In it, we study three types of algorithms: synchronous, asynchronous and hybrid. We evaluate the proposed algorithms in two dimensions: efficiency and privacy. Regarding efficiency, we propose new distributed algorithms which mainly are faster and consume less network resources than state-of-the-art algorithms. Regarding privacy, we propose novel algorithms to enforce the privacy of the local information held by agents without using cryptographic tools. The main ideas that we have developed in this thesis are: \emph{Synchronous Algorithms}: The use of variable reordering heuristics for constraint satisfaction problems has been shown to be a powerful strategy in order to improve efficiency. Inspired in this idea, we present two approximations of the popular minimum-domain heuristic for dynamic variable reordering. \emph{Asynchronous Algorithms}: We present a basic kernel for grouping asynchronous backtracking algorithms. By implementing the condition for termination in this kernel, we obtain four asynchronous algorithms. One of these algorithms does not add links between agents not sharing constraints, which can be useful for solving problems where privacy is the main concern. \emph{Hybrid Algorithms}: We present a novel algorithm which combines synchronous and asynchronous elements. This algorithm outperforms the reference asynchronous algorithm. \emph{Non-binary Constraints}: Although most of state-of-the-art methods for \emph{DisCSP} assume that every constraint involves two variables, they can be extended to handle constraints involving more than two variables. We present new versions of existing algorithms to deal with non-binary constraints, including the addition of redundant constraint projections. \emph{Assignment Privacy}: We propose an asynchronous algorithm that allows agents to maintain their variable assignments private during problem resolution. \emph{Constrain Privacy}: We present the Partially Known Constraint model (\emph{PKC}), a new \emph{DisCSP} model in which constraints are kept private and are only partially known to agents. We propose two algorithms for solving \emph{DisCSP} expressed under the \emph{PKC} model. Both algorithms also consider assignment privacy. \emph{Enforcing Privacy with Lies}: We present a novel algorithm that further enforces constraint privacy. This is algorithm is based on the idea that agents may lie. It requires a single extra condition: if an agent lies, it has to tell the truth in finite time afterwards. \emph{Applications}: We consider naturally distributed constraint problems which have a clear motivation to be tried with distributed techniques: \emph{Meeting Scheduling} and \emph{Stable Matching problems}. For each these problems we present distributed versions. Regarding \emph{Stable Matching problems}, we consider two well-known problems: \emph{Stable Marriage} and \emph{Stable Roommates} problems. We propose ways to solve these problems while keeping personal preferences private. All proposed algorithms in this thesis have been implemented, evaluated and formally proven to be correct, complete and terminate.