Please use this identifier to cite or link to this item:
Title: Utility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility function
Authors: Deng, Yanchen
An, Bo
Keywords: Engineering::Computer science and engineering
Issue Date: 2021
Source: Deng, Y. & An, B. (2021). Utility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility function. Autonomous Agents and Multi-Agent Systems, 35(2).
Project: AISG-RP-2019-0013
Journal: Autonomous Agents and Multi-Agent Systems
Abstract: 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.
ISSN: 1387-2532
DOI: 10.1007/s10458-021-09511-z
Rights: © 2021 Springer Science+Business Media, LLC, part of Springer Nature. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Jan 28, 2023

Web of ScienceTM
Citations 50

Updated on Jan 17, 2023

Page view(s)

Updated on Jan 28, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.