Resumen de Distributed constraint satisfaction
Ismel Brito Rodriguez
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 (DisCSP). Various application problems in multi-agent systems can be formalized as DisCSPs. This thesis is dedicated to the development of distributed complete algorithms for solving 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: 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 minimumdomain heuristic for dynamic variable reordering. 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. Hybrid Algorithms: We present a novel algorithm which combines synchronous and asynchronous elements. This algorithm outperforms the reference asynchronous algorithm. Non-binary Constraints: Although m
