Robust and Adaptive Sequential Submodular Optimization

doi:10.1109/TAC.2020.3046222

Return

Robust and Adaptive Sequential Submodular Optimization

2022-01-01

Vasileios Tzoumas *

Ali Jadbabaie

George J. Pappas

DOI：10.1109/TAC.2020.3046222

Original

Original request for help

Save

Abstract

En 中文

Emerging applications of control, estimation, and machine learning, from target tracking to decentralized model fitting, pose resource constraints that limit which of the available sensors, actuators, or data can be simultaneously used across time. Therefore, many researchers have proposed solutions within discrete optimization frameworks where the optimization is performed over finite sets. By exploiting notions of discrete convexity, such as submodularity, the researchers have been able to provide scalable algorithms with provable suboptimality bounds. In this article, we consider such problems but in adversarial environments, where in every step a number of the chosen elements in the optimization is removed due to failures/attacks. Specifically, we consider for the first time a sequential version of the problem that allows us to observe the failures and adapt, while the attacker also adapts to our response. We call the novel problem robust sequential submodular maximization (RSM). Generally, the problem is computationally hard and no scalable algorithm is known for its solution. However, in this article, we propose robust and adaptive maximization (RAM), the first scalable algorithm. RAM runs in an online fashion, adapting in every step to the history of failures. Also, it guarantees a near-optimal performance, even against any number of failures among the used elements. Particularly, RAM has both provable per-instance a priori bounds and tight and/or optimal a posteriori bounds. Finally, we demonstrate RAM's near-optimality in simulations across various application scenarios, along with its robustness against several failure types, from worst-case to random.

Keywords:

Sensors

Random access memory

Optimization

History

Target tracking

Greedy algorithms

Actuators

Algorithm design and analysis

approximation algorithms

autonomous systems

combinatorial mathematics