.png){kind=icon}
返回
A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.automatica.2022.110493.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Several important problems in multi-agent systems, machine learning, data mining, scheduling and others, may be formulated as set function maximization problems subject to cardinality constraints. In such problems, the set (objective) functions of interest often have monotonicity and submodularity properties. Hence, the class of monotone submodular set function maximization problems has been widely studied in the literature. Owing to its challenging nature, almost all existing solutions for this class of problems are based on greedy algorithms. A seminal work on this topic has exploited the submodularity property to prove a (1-1/e) performance bound for such greedy solutions. More recent literature on this topic has been focused on exploiting different curvature properties to establish improved (tighter) performance bounds. However, such improvements come at the cost of enforcing additional assumptions and increasing computational complexity while facing significant inherent limitations. In this paper, first, a brief review of existing performance bounds is provided. Then, a new performance bound that does not require any additional assumptions and is both practical and computationally inexpensive is proposed. In particular, this new performance bound is established based on a series of upper bounds derived for the objective function that can be computed in parallel with the execution of the greedy algorithm. Finally, to highlight the effectiveness of the proposed performance bound, extensive numerical results obtained from a well-known class of multi-agent coverage problems are provided. (C) 2022 Elsevier Ltd. All rights reserved.
Keyword:
Multi-agent systems
Optimization
Cooperative control
Control of networks
Persistent monitoring
Parametric control
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
5.9
论文数:
1.2W
被引数:
5.2W
机构
引用论文
Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees具有性能约束保证的覆盖问题的异构多代理团队的最佳组合.png)
AUTOMATICAOAAI
AUTOMATICAIF5.9
OAAI分享收藏Exploiting submodularity to quantify near-optimality in multi-agent coverage problemsAUTOMATICAOAAI
AUTOMATICAIF5.9
OAAI分享收藏分享收藏分享收藏
查看更多内容