Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDeng, Yanchenen_US
dc.contributor.authorAn, Boen_US
dc.identifier.citationDeng, 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).
dc.description.abstractBelief 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.en_US
dc.description.sponsorshipNanyang Technological Universityen_US
dc.description.sponsorshipNational Research Foundation (NRF)en_US
dc.relation.ispartofAutonomous Agents and Multi-Agent Systemsen_US
dc.rights© 2021 Springer Science+Business Media, LLC, part of Springer Nature. All rights reserved.en_US
dc.subjectEngineering::Computer science and engineeringen_US
dc.titleUtility distribution matters: enabling fast belief propagation for multi-agent optimization with dense local utility functionen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.subject.keywordsDomain Pruningen_US
dc.description.acknowledgementThis research was supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG-RP-2019-0013), National Satellite of Excellence in Trustworthy Software Systems (Award No: NSOE-TSS2019-01), and NTU.en_US
item.fulltextNo 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.