Distributed strategy selection: A submodular set function maximization approach

卷:153

Article

关键词: ALGORITHM;    APPROXIMATIONS;    OPTIMIZATION;   

DOI  :  10.1016/j.automatica.2023.111000

来源: SCIE

【 摘 要 】

Joint utility-maximization problems for multi-agent systems often should be addressed by distributed strategy-selection formulation. Constrained by discrete feasible strategy sets, these problems are broadly formulated as NP-hard combinatorial optimization problems. In many cases, these problems can be cast as constrained submodular set function maximization problems, which also belong to the NP-hard domain of problems. A prominent example is the problem of multi-agent mobile sensor dispatching over a discrete domain. This paper considers a class of submodular optimization problems that consist of maximization of a monotone and submodular set function subject to a partition matroid constraint over a group of networked agents that communicate over a connected undirected graph. We work with the value oracle model. Consequently, the only access of the agents to the utility function is through a black box that returns the utility function value given a specific strategy set. We propose a distributed suboptimal polynomial-time algorithm that enables each agent to obtain its respective strategy via local interactions with its neighboring agents. Our solution is a fully distributed gradient -based algorithm using the submodular set functions' multilinear extension followed by a distributed stochastic Pipage rounding procedure. This algorithm results in a strategy set that when the team utility function is evaluated at the worst case, the utility function value is in c1 (1 - e-c - O(1/T)) of the optimal solution with c being the curvature of the submodular function. An example demonstrates our results.(c) 2023 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

【 授权许可】

Free