Controller-Agent based approach for Solving Distributed Constraint Problem

摘要

The interesting domain of constraint programming has been studied for years. Using Constraint Satisfaction Problem in association with Multi-Agent System has emerged the research in a new field known as Distributed Constraint Satisfaction Problem (DCSP). Many algorithms are proposed to solve DCSP. Inspired from ABT algorithm, we introduce in this paper our algorithm for solving DCSP where we divide agents in the system into two groups: Variables' and Controller Agents, which allow reformulating of different inter-agent communication algorithm in our framework. This division allows the separation between the constraints verification and other functions of agents. The proposed algorithm is not only capable of treating binary constraints; it can be used easily in order to treat non-binary constraints. This facility gives also the possibility of grouping constraints in order to form a set of quasi-independent sub-problems. These sub-problems may be interconnected by some common variables. The instantiation of these variables can be done by negotiation in order to separate the subproblems into totally independent ones.