Communication-Sensitive Pseudo-Tree Heuristics for DCOP Algorithms
Communication-Sensitive Pseudo-Tree Heuristics for DCOP Algorithms
复制标题
DCOP 算法的通信敏感伪树启发式
DOI：
10.1142/s0218213018600084
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Misra
中科院分区：
文献类型：
--
作者：
Atena M. Tabakhi;W. Yeoh;R. Tourani;Francisco Natividad;S. Misra
分布式约束优化问题（DCOP）是一个强大的范式，通过使多个代理相互协调，以解决一个问题的多代理系统建模。这些代理通常被认为是合作的，也就是说，他们与其他代理进行通信，以优化全局目标。然而，在大多数DCOP算法的评估中，所有代理对之间的通信时间被假设为是相同的。这个假设在几乎所有的实际应用中都是不切实际的。在本文中，我们研究的影响下，对代理之间的通信时间可以变化的假设，经验评估DCOP算法。此外，我们评估的DCOP算法使用ns-2，离散事件模拟器，广泛用于计算机网络社区，模拟通信时间，而不是标准的DCOP模拟器，用于评估DCOP算法在AI社区。此外，我们提出了利用非均匀的通信时间，以加快DCOP算法，伪树上操作的算法。我们的实证结果表明，所提出的算法提高了这些算法的运行时间高达20%。这些算法在不同的基准上进行评估，例如无标度图，随机图和智能电网的实例，客户驱动的微电网（CDMG）应用程序。
Distributed Constraint Optimization Problem (DCOP) is a powerful paradigm to model multi-agent systems through enabling multiple agents to coordinate with each other to solve a problem. These agents are often assumed to be cooperative, that is, they communicate with other agents in order to optimize a global objective. However, the communication times between all pairs of agents are assumed to be identical in the evaluation of most DCOP algorithms. This assumption is impractical in almost all real-world applications. In this paper, we study the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary. In addition, we evaluate a DCOP algorithm using ns-2, a discrete-event simulator that is widely used in the computer networking community, to simulate the communication times, as opposed to the standard DCOP simulators that are used to evaluate DCOP algorithms in the AI community. Furthermore, we propose heuristics that exploit the non-uniform communication times to speed up DCOP algorithms that operate on pseudo-trees. Our empirical results demonstrate that the proposed heuristics improve the runtime of those algorithms up to 20%. These heuristics are evaluated on different benchmarks such as scale-free graphs, random graphs, and an instance of the smart grid, Customer-Driven Microgrid (CDMG) application.