Location of presentation:
Monday June 27, 2005
Wean 4623
2:00pm
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.