TY - JOUR
T1 - BDBM
T2 - A distributed network simplification method for solving task allocation problems
AU - Liao, Bin
AU - Wan, Fangyi
AU - Hua, Yi
AU - Zhu, Shenrui
AU - Ma, Ting
AU - Qing, Xinlin
N1 - Publisher Copyright:
© 2024 Elsevier Ltd
PY - 2024/7/15
Y1 - 2024/7/15
N2 - Existing task allocation algorithms often fail to consider communication load and do not meet the scalability requirements of large-scale systems in practical applications. Furthermore, many general network simplification algorithms are centralized and not designed for task allocation scenarios, thus losing their superiority when applied to solve task allocation problems in distributed systems. Inspired by recent network simplification algorithms, this paper introduces a novel network simplification algorithm called bid-based distributed broken-motifs (BDBM), which simplifies the communication network by reducing the number of closed-loop triangles. The BDBM algorithm keeps those communication edges that facilitate the deconfliction based on the initial bids, thus avoiding the surge in the number of convergence iterations caused by the simplification. In addition, CBBA is distributed and requires only two iterations to complete the communication network simplification. Theoretical analysis confirms that the simplified network of BDBM remains connected and can be used in combination with improved task allocation algorithms based on consensus-based bundle algorithm (CBBA). In terms of experiments, we conducted comprehensive experiments in different settings and found that the proposed algorithm does not lead to worse allocation solutions. The statistical results also show that BDBM outperforms state-of-the-art network simplification algorithms in terms of solving efficiency and scalability in assisting CBBA solve large-scale complex task allocation problems.
AB - Existing task allocation algorithms often fail to consider communication load and do not meet the scalability requirements of large-scale systems in practical applications. Furthermore, many general network simplification algorithms are centralized and not designed for task allocation scenarios, thus losing their superiority when applied to solve task allocation problems in distributed systems. Inspired by recent network simplification algorithms, this paper introduces a novel network simplification algorithm called bid-based distributed broken-motifs (BDBM), which simplifies the communication network by reducing the number of closed-loop triangles. The BDBM algorithm keeps those communication edges that facilitate the deconfliction based on the initial bids, thus avoiding the surge in the number of convergence iterations caused by the simplification. In addition, CBBA is distributed and requires only two iterations to complete the communication network simplification. Theoretical analysis confirms that the simplified network of BDBM remains connected and can be used in combination with improved task allocation algorithms based on consensus-based bundle algorithm (CBBA). In terms of experiments, we conducted comprehensive experiments in different settings and found that the proposed algorithm does not lead to worse allocation solutions. The statistical results also show that BDBM outperforms state-of-the-art network simplification algorithms in terms of solving efficiency and scalability in assisting CBBA solve large-scale complex task allocation problems.
KW - Communication reduction
KW - Consensus-based bundle algorithm
KW - Distributed multi-agent system
KW - Network simplification
KW - Task allocation
UR - http://www.scopus.com/inward/record.url?scp=85182877605&partnerID=8YFLogxK
U2 - 10.1016/j.eswa.2024.123170
DO - 10.1016/j.eswa.2024.123170
M3 - 文章
AN - SCOPUS:85182877605
SN - 0957-4174
VL - 246
JO - Expert Systems with Applications
JF - Expert Systems with Applications
M1 - 123170
ER -