Virtual structure reduction for distributed constraint problem solving

Nathaniel Gemelli, Jeffrey Hudack, Jae C. Oh

Research output: Chapter in Book/Entry/PoemConference contribution


Distributed Constraint Problem solving represents a fundamental research area in distributed artificial intelligence and multi-agent systems. The constraint density, or the ratio of the number of constraints to the number of variables, determines the difficulty of either finding a solution or minimizing the set of variable assignment conflicts. Reducing density typically reduces difficulty. We present a fully distributed technique for reducing the effective density of constraint graphs, called Virtual Structure Reduction (VSR). The VSR technique leverages the occurrence of variables that must be assigned the same value based on shared constraints and can improve solver performance using existing algorithms. We discuss our Distributed Constraint Optimization Problem (DCOP) solver, integrated with the Distributed Stochastic Algorithm (DSA), called VSR-DSA. The VSR-DSA algorithm demonstrates performance gains vs DSA in both solution quality and time on 3-coloring problems.

Original languageEnglish (US)
Title of host publicationLate-Breaking Developments in the Field of Artificial Intelligence - Papers Presented at the 27th AAAI Conference on Artificial Intelligence, Technical Report
PublisherAI Access Foundation
Number of pages3
ISBN (Print)9781577356288
StatePublished - 2013
Event27th AAAI Conference on Artificial Intelligence, AAAI 2013 - Bellevue, WA, United States
Duration: Jul 14 2013Jul 18 2013

Publication series

NameAAAI Workshop - Technical Report


Other27th AAAI Conference on Artificial Intelligence, AAAI 2013
Country/TerritoryUnited States
CityBellevue, WA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Virtual structure reduction for distributed constraint problem solving'. Together they form a unique fingerprint.

Cite this