Algorithmic and Domain Centralization in Distributed Constraint Optimization Problems

摘要

A class of problems known as Distributed Constraint Optimization Problems (DCOP) has become a growing research interest in computer science because of its difficulty (NP-Complete) and many real-world applications (meeting scheduling, sensor networks, military planning). In this thesis we identify two types of centralization relevant to DCOPs: algorithmic centralization, in which a DCOP algorithm actively centralizes part (or all) of the problem structure, and domain centralization, in which inherent centralization already exists in the domain specification. We explore algorithmic centralization by empirically studying Adopt and OptAPO, two DCOP algorithms which differ in the amount of centralization they use. Our results show that centralizing a problem's structure decreases communication overhead, but increases local computation. We compare the algorithms through our contribution of a new performance metric, Cycle-Based Runtime, which takes both communication costs and local computation time into account. We then explore domain centralization by studying meeting scheduling, which has problem structure clustered at scheduling agents. We present a novel variant of Adopt, called AdoptMVA, which uses a centralized search within agents to take advantage of the partially centralized structure. We show that when agent ordering is controlled for, AdoptMVA outperforms Adopt in situations where communication costs are high. We contribute a Branch & Bound search heuristic which works well for meeting scheduling problems with multiple variables per agent. We also empirically experiment with meeting scheduling, showing that meeting size is in some cases a better indicator of solution difficulty than the number of agents in a problem.