A Scalable Algorithm to Solve Distributed Constraint Optimization

Recently, Distributed Constraint Optimization Problems (DCOP) have been drawing a growing body of attention as an important research area in multi agent systems as a large body of real problems can be modeled by them. The primary goal of this research is to design a distributed and effective algorithm to solve DCOP. There are various criteria that measure the efficiency of DCOP algorithms, but the most efficient algorithm for DCOP is the one by which the computation and communication cost is as low as possible and the quality of the solution is high. In this paper, we focus on an approximate DCOP algorithm called DALO (Distributed Asynchronous Local Optimization). Using the main idea of the DALO algorithm, we propose a new algorithm to solve DCOP, which exhibits two important improvements over the DALO algorithm. First we use a sequential partial approach to select a coefficient of leaders to compute the best assignment for agents by which the computation and communication cost decrease in the whole DCOP. The second improvement is an evolutionary approach by which the computation and communication burden for each agent decreases. We present some empirical evidences that show our algorithm performs better than the DALO algorithm.

Keywords:

distributed constraint optimization , multi agent system