论文标题
通过最大共识的单调下调函数的多代理最大化
Multi-Agent Maximization of a Monotone Submodular Function via Maximum Consensus
论文作者
论文摘要
受离散可行的集合的多代理决策问题中经常出现受约束的集合设置功能最大化问题。一个突出的例子是在离散域上放置多代理移动传感器的问题。但是，已知Subsodular集合功能优化问题是NP-HARD。在本文中，我们考虑了一类的下一个功能优化问题，这些问题包括对单调和下二个集合功能的最大化，但会受到一组通过连接的无方向图通信的网络代理的均匀矩阵约束。我们的目标是获得分布式的次优多项式算法，该算法使每个代理通过与其相邻代理的局部互动来获得其各自的策略。我们的解决方案是使用子解体集合函数的多线性扩展并利用最大共识方案的完全分布的基于梯度的算法。该算法导致策略集，即当在最坏情况下评估团队目标函数时，目标函数值为最佳解决方案的$ 1-1/e-O（1/t）$。一个例子证明了我们的结果。
Constrained submodular set function maximization problems often appear in multi-agent decision-making problems with a discrete feasible set. A prominent example is the problem of multi-agent mobile sensor placement over a discrete domain. However, submodular set function optimization problems are known to be NP-hard. In this paper, we consider a class of submodular optimization problems that consists of maximization of a monotone and submodular set function subject to a uniform matroid constraint over a group of networked agents that communicate over a connected undirected graph. Our objective is to obtain a distributed suboptimal polynomial-time algorithm that enables each agent to obtain its respective policy via local interactions with its neighboring agents. Our solution is a fully distributed gradient-based algorithm using the multilinear extension of the submodular set functions and exploiting a maximum consensus scheme. This algorithm results in a policy set that when the team objective function is evaluated at worst case the objective function value is in $1-1/e-O(1/T)$ of the optimal solution. An example demonstrates our results.
