Impact of problem centralization in distributed constraint optimization algorithms
Impact of problem centralization in distributed constraint optimization algorithms
复制标题
分布式约束优化算法中问题集中的影响
DOI：
10.1145/1082473.1082633
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Pragnesh Jay Modi
中科院分区：
文献类型：
--
作者：
John Davin;Pragnesh Jay Modi
分布式约束优化问题（DCOP）的最新进展导致了现在可用的一系列算法，这些算法在问题集中程度上有所不同。问题集中化可能对代理所需的计算量产生重大影响，但不幸的是，“循环次数”这一主要评估指标未能考虑到这一成本。我们分析了最近两种DCOP算法的相对性能：OptAPO算法执行部分集中化，而Adopt算法保持DCOP的分布。之前对Adopt和OptAPO的比较发现，OptAPO比Adopt需要更少的周期。我们扩展了周期度量来定义“基于周期的运行时（CBR）”，以考虑每个周期中所需的计算量和周期之间的通信延迟。使用CBR度量，我们表明在一定范围的通信延迟下，Adopt优于OptAPO。我们还会问：对于给定的通信延迟，什么级别的集中化最适合？我们使用CBR来创建三种不同集中化程度的算法的性能曲线，即采用、OptAPO和集中式分支边界搜索。
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.
影响因子：
14.4
作者：
Modi, PJ;Shen, WM;Yokoo, M
通讯作者：
Yokoo, M