Using coalitions with stochastic search to solve distributed constraint optimization problems

Distributed Constraint Optimization Problems (DCOP) provide a convenient way of representing multi-agent decision problems. Many stochastic search methods have been developed for solving DCOPs, however, as problem size grows and becomes more complex, fully decentralized stochastic methods tend to suffer from a degradation in solution quality. We present Propensity-based Coalition-DSA (PC-DSA), a new coalition formation algorithm for solving DCOPs that uses stochastic search and mitigates the degradation of solution quality seen in large, complex problems. We introduce a Markov network formulation of the k-Coloring problem and show how a structure-based estimation of the Markov network can be used by agents during the coalition formation process to find partners with high propensity towards one another; Agents that have a high probability of having the same joint assignment when the problem is solved. This allows for a single agent in the coalition to solve the problem for all members of the coalition using simple stochastic search. We report empirical results that show solution quality gains over non-coalition forming stochastic search in the distributed k-Coloring problem and discuss how we can generalize propensity to apply to general DCOPs.