Using coalitions with stochastic search to solve distributed constraint optimization problems

Nathaniel Gemelli, Jeffrey Hudack, Steven Loscalzo, Jae C Oh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationICAART 2015 - 7th International Conference on Agents and Artificial Intelligence, Proceedings
PublisherSciTePress
Pages443-450
Number of pages8
Volume2
ISBN (Print)9789897580741
StatePublished - 2015
Event7th International Conference on Agents and Artificial Intelligence, ICAART 2015 - Lisbon, Portugal
Duration: Jan 10 2015Jan 12 2015

Other

Other7th International Conference on Agents and Artificial Intelligence, ICAART 2015
CountryPortugal
CityLisbon
Period1/10/151/12/15

Keywords

  • Coalition formation
  • Distributed Constraint Optimization
  • K-Coloring

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software

Fingerprint Dive into the research topics of 'Using coalitions with stochastic search to solve distributed constraint optimization problems'. Together they form a unique fingerprint.

Cite this