The improved local cost simulation algorithms based on coalition structure generation for solving distributed constraint optimization problems

Distributed constraint optimization problems (DCOPs) are a fundamental framework for modeling multi-agent systems (MAS) where agents coordinate their decision-making to optimize a global objective. However, existing incomplete local search algorithms for solving DCOPs face a huge challenge of falling into the local optimum since the information and controls are distributed among multiple autonomous agents. Considering this, two improved local cost simulation algorithms based on coalition structure generation (CSG) named LCS-CSG-F and LCS-CSG-C that execute CSG in fixed and consecutive rounds, respectively, are proposed in this paper to expand the search for solution space. CSG involves partitioning a set of agents into disjoint exhaustive coalitions according to the neighbor relationship between agents, where agents of the original DCOPs are partitioned into coalitions to relax constraints between agents. To verify the effectiveness of the CSG strategy, two competing schemes that execute neighbor ignoring in fixed rounds, named asymmetric single neighbor ignoring (ASI-F) and asymmetric multiple neighbor ignoring (AMI-F), are designed since the CSG strategy symmetrically ignores multiple neighbors in different coalitions simultaneously. From statistical perspective, the Friedman test reveals significant differences between the LCS-CSG algorithm and other algorithms. Extensive experimental results indicate that the proposed CSG-based algorithms significantly outperform the state-of-the-art DCOPs incomplete algorithms in various benchmarks.