Site Home
Contact Us
å

iDEA: DREXEL LIBRARIES E-REPOSITORY AND ARCHIVES

iDEA: DREXEL LIBRARIES E-REPOSITORY AND ARCHIVES

Main sections

Impact of problem centralization in distributed constraint optimization algorithms

Details
Title
Impact of problem centralization in distributed constraint optimization algorithms
Author(s)
Davin, John; Modi, Pragnesh Jay
Date
2005
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.
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.
URI
http://hdl.handle.net/1860/814
In Collections
Drexel Research

Search iDEA

Advanced Search