Selective Sorting and Smart Nogood-Based Complex Distributed Constraint Satisfaction Problems

Abstract

Distributed Constraint Satisfaction Problem (DisCSP) is a formalism which represents elegantly a mathematical problem distributed among a set of agents, as several sub-problems. Each DisCSP sub-problem consists of a set of variables, linked by constraints. The agents have to collaborate in order to resolve the problem. Because of the simplicity assumptions, the existing DisCSP algorithms assume that there is just one variable per agent. But, actually, the local problems are complex (i.e. each agent can handle multiple variables). To cope with complex problems, several methods have been proposed as the compilation and the decomposition, which transform the complex problem to a simple one, so as it can be solved with the existing algorithms. The compilation is about finding all solutions to each local problem and building a new compiled domain containing these solutions. Local
problems are transformed, afterward, to simple abstract variables whose domains are the compiled ones. Some improvements have been proposed to the compilation method, as the interchangeability and the Neighborhood Partial Interchangeability. In this paper, we propose other new contributions to the compilation based on the Constraint Optimization Problem (COP) formalism and the Nogood shape, and we show how to integrate these improvements into well known DisCSP algorithms. Experimental results prove the effectiveness of our contributions.