...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Autonomous agents and multi-agent systems >Utility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility function
【24h】

Utility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility function

机译：公用事业分配事项：使多功能局部函数的多代理优化能够快速信仰传播

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Belief propagation algorithms including Max-sum and its variants are important methods for multi-agent optimization. However, they face a significant scalability challenge as the computational overhead grows exponentially with respect to the arity of each utility function. To date, a number of acceleration algorithms for belief propagation algorithms were proposed. These algorithms maintain a lower bound on total utility and employ either a domain pruning technique or branch and bound to reduce the search space. However, these algorithms still suffer from low-quality bounds and the inability of filtering out suboptimal tied entries. In this paper, we first show that these issues are exacerbated and can considerably degenerate the performance of the state-of-the-art methods when dealing with the problems with dense utility functions, which widely exist in many real-world domains. Built on this observation, we then develop several novel acceleration algorithms that alleviate the effect of densely distributed local utility values from the perspectives of both bound quality and search space organization. Specifically, we build a search tree for each distinct local utility value to enable efficient branch and bound on tied entries and tighten a running lower bound to perform dynamic domain pruning. That is, we integrate both search and pruning to iteratively reduce the search space. Besides, we propose a discretization mechanism to offer a tradeoff between the reconstruction overhead and the pruning efficiency. Finally, a K-depth partial tree-sorting scheme with different sorting criteria is proposed to reduce the memory consumption. We demonstrate the superiorities of our algorithms over the state-of-the-art acceleration algorithms from both theoretical and experimental perspectives.
机译：信仰传播算法，包括MAX-SUM及其变体是用于多种子体优化的重要方法。然而，当计算开销相对于每个公用事业函数的ARINY呈指数逐渐增长，它们面临显着的可扩展性挑战。迄今为止，提出了许多用于信仰传播算法的加速算法。这些算法在总实用程序上维持下限，并采用域修剪技术或分支并绑定以减少搜索空间。然而，这些算法仍然遭受低质量的界限，并且无法过滤次优相关的条目。在本文中，我们首先表明这些问题加剧了，并且在处理密集的实用功能问题时，可以大大退化最先进的方法的性能，这在许多真实世界领域中广泛存在。然后，我们建立了这种观察，我们开发了几种新的加速算法，可从绑定质量和搜索空间组织的角度来缓解密集分布的本效公用事业公司的效果。具体而言，我们为每个不同的本地实用程序值构建一个搜索树，以便在绑定的条目上绑定有效分支并绑定并绑定运行的下限以执行动态域修剪。也就是说，我们整合了搜索和修剪以迭代地减少搜索空间。此外，我们提出了一种离散化机制，在重建开销和修剪效率之间提供权衡。最后，提出了一种具有不同分类标准的K-Deave部分树分类方案以降低存储器消耗。我们从理论和实验视角展示了我们最先进的加速算法的算法的优势。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号