Aggregating local behaviors based upon a discrete Lagrange multiplier method

When solving a distributed problem based on a multi-agent system, the local behaviors of agents are aggregated to the global behaviors of the multi-agent system towards a solution state. This work presents a distributed discrete Lagrange multiplier (DDLM) method for solving distributed constraint satisfaction problems (distributed CSPs). In this method, the local behaviors of agents are aggregated as a descent direction of an objective function corresponding to the problem at hand. Thus, a trend to a solution state are formed. Furthermore, we provide three techniques to speed up the aggregation of agents´ local behaviors. Through experiments on benchmark graph coloring problems, we validate the effectiveness of the presented DDLM method as well as the three techniques in solving distributed CSPs.