TY - GEN

T1 - Virtual structure reduction on distributed k-coloring problems

AU - Gemelli, Nathaniel

AU - Hudack, Jeffrey

AU - Oh, Jae C.

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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 in a constraint problem. Reducing the active density of a problem typically reduces difficulty in finding a solution. We present a fully distributed technique for reducing the active density of constraint graphs that represent Distributed Constraint Optimization Problems (DCOP), called Virtual Structure Reduction (VSR). The VSR technique leverages the occurrence of frozen pairs, or variables that must be assigned the same value based on shared constraints between variables within the local neighborhood. We show how frozen pairs can be used to identify surrogate relationships between variables which reduces the active set of nodes in the constraint graph and leads to a reduction in active density. We discuss our DCOP solver, integrated with the Distributed Stochastic Algorithm (DSA), called VSR-DSA. The VSR-DSA algorithm demonstrates significant performance gains compared to the DSA-B and MGM algorithms in messages, cycles, solution quality, and time on randomized instances of the 3-coloring problem.

AB - 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 in a constraint problem. Reducing the active density of a problem typically reduces difficulty in finding a solution. We present a fully distributed technique for reducing the active density of constraint graphs that represent Distributed Constraint Optimization Problems (DCOP), called Virtual Structure Reduction (VSR). The VSR technique leverages the occurrence of frozen pairs, or variables that must be assigned the same value based on shared constraints between variables within the local neighborhood. We show how frozen pairs can be used to identify surrogate relationships between variables which reduces the active set of nodes in the constraint graph and leads to a reduction in active density. We discuss our DCOP solver, integrated with the Distributed Stochastic Algorithm (DSA), called VSR-DSA. The VSR-DSA algorithm demonstrates significant performance gains compared to the DSA-B and MGM algorithms in messages, cycles, solution quality, and time on randomized instances of the 3-coloring problem.

KW - Distributed AI

KW - Distributed Constraint Problem

KW - Multi-agent Collaboration

UR - http://www.scopus.com/inward/record.url?scp=84893257366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893257366&partnerID=8YFLogxK

U2 - 10.1109/WI-IAT.2013.89

DO - 10.1109/WI-IAT.2013.89

M3 - Conference contribution

AN - SCOPUS:84893257366

SN - 9781479929023

T3 - Proceedings - 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2013

SP - 46

EP - 52

BT - Proceedings - 2013 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2013

PB - IEEE Computer Society

T2 - 2013 12th IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2013

Y2 - 17 November 2013 through 20 November 2013

ER -