|
iDEA: Drexel E-repository and Archives >
Drexel Academic Community >
College of Engineering >
Department of Computer Science >
Faculty Research and Publications (Comp Sci) >
Impact of problem centralization in distributed constraint optimization algorithms
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1860/814
|
| Title: | Impact of problem centralization in distributed constraint optimization algorithms |
| Authors: | Davin, John
Modi, Pragnesh Jay |
| Issue Date: | 2005 |
| Publisher: | IEEE |
| Citation: | Proceedings of Autonomous Agents and Multi-Agent Systems, (AAMAS) 2005. Retrieved 3/16/2006 from http://www.cs.drexel.edu/~pmodi/papers/modi-aamas05a.pdf. |
| Abstract: | Recent progress in Distributed Constraint Optimization
Problems (DCOP) has led to a range of algorithms now
available which differ in their amount of problem centralization.
Problem centralization can have a significant impact
on the amount of computation required by an agent
but unfortunately the dominant evaluation metric of “number
of cycles” fails to account for this cost. We analyze the
relative performance of two recent algorithms for DCOP:
OptAPO, which performs partial centralization, and Adopt,
which maintains distribution of the DCOP. Previous comparison
of Adopt and OptAPO has found that OptAPO requires
fewer cycles than Adopt. We extend the cycles metric
to define “Cycle-Based Runtime (CBR)” to account for
both the amount of computation required in each cycle and
the communication latency between cycles. Using the CBR
metric, we show that Adopt outperforms OptAPO under a
range of communication latencies. We also ask: What level
of centralization is most suitable for a given communication
latency? We use CBR to create performance curves
for three algorithms that vary in degree of centralization,
namely Adopt, OptAPO, and centralized Branch and Bound
search. |
| URI: | http://hdl.handle.net/1860/814 |
| Appears in Collections: | Faculty Research and Publications (Comp Sci)
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
