Resilient Monotone Sequential Maximization
© 2018 IEEE. Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148595 |
| _version_ | 1811070266855391232 |
|---|---|
| author | Tzoumas, V Jadbabaie, A Pappas, GJ |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Tzoumas, V Jadbabaie, A Pappas, GJ |
| author_sort | Tzoumas, V |
| collection | MIT |
| description | © 2018 IEEE. Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and actuators fail. Thence, traditional sequential design paradigms become insufficient and, in contrast, resilient sequential designs that adapt against system-wide attacks, deletions, or failures become important. In general, resilient sequential design problems are computationally hard. Also, even though they often involve objective functions that are monotone and (possibly) submodular, no scalable approximation algorithms are known for their solution. In this paper, we provide the first scalable algorithm, that achieves the following characteristics: system-wide resiliency, i.e., the algorithm is valid for any number of denial-of-service attacks, deletions, or failures; adaptiveness, i.e., at each time step, the algorithm selects system elements based on the history of inflicted attacks, deletions, or failures; and provable approximation performance, i.e., the algorithm guarantees for monotone objective functions a solution close to the optimal. We quantify the algorithm's approximation performance using a notion of curvature for monotone (not necessarily submodular) set functions. Finally, we support our theoretical analyses with simulated experiments, by considering a control-aware sensor scheduling scenario, namely, sensing-constrained robot navigation. |
| first_indexed | 2024-09-23T08:33:45Z |
| format | Article |
| id | mit-1721.1/148595 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:33:45Z |
| publishDate | 2023 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1485952023-03-18T03:49:07Z Resilient Monotone Sequential Maximization Tzoumas, V Jadbabaie, A Pappas, GJ Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society © 2018 IEEE. Applications in machine learning, optimization, and control require the sequential selection of a few system elements, such as sensors, data, or actuators, to optimize the system performance across multiple time steps. However, in failure-prone and adversarial environments, sensors get attacked, data get deleted, and actuators fail. Thence, traditional sequential design paradigms become insufficient and, in contrast, resilient sequential designs that adapt against system-wide attacks, deletions, or failures become important. In general, resilient sequential design problems are computationally hard. Also, even though they often involve objective functions that are monotone and (possibly) submodular, no scalable approximation algorithms are known for their solution. In this paper, we provide the first scalable algorithm, that achieves the following characteristics: system-wide resiliency, i.e., the algorithm is valid for any number of denial-of-service attacks, deletions, or failures; adaptiveness, i.e., at each time step, the algorithm selects system elements based on the history of inflicted attacks, deletions, or failures; and provable approximation performance, i.e., the algorithm guarantees for monotone objective functions a solution close to the optimal. We quantify the algorithm's approximation performance using a notion of curvature for monotone (not necessarily submodular) set functions. Finally, we support our theoretical analyses with simulated experiments, by considering a control-aware sensor scheduling scenario, namely, sensing-constrained robot navigation. 2023-03-17T15:56:27Z 2023-03-17T15:56:27Z 2019-01-18 2023-03-17T15:51:16Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/148595 Tzoumas, V, Jadbabaie, A and Pappas, GJ. 2019. "Resilient Monotone Sequential Maximization." Proceedings of the IEEE Conference on Decision and Control, 2018-December. en 10.1109/CDC.2018.8618873 Proceedings of the IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Tzoumas, V Jadbabaie, A Pappas, GJ Resilient Monotone Sequential Maximization |
| title | Resilient Monotone Sequential Maximization |
| title_full | Resilient Monotone Sequential Maximization |
| title_fullStr | Resilient Monotone Sequential Maximization |
| title_full_unstemmed | Resilient Monotone Sequential Maximization |
| title_short | Resilient Monotone Sequential Maximization |
| title_sort | resilient monotone sequential maximization |
| url | https://hdl.handle.net/1721.1/148595 |
| work_keys_str_mv | AT tzoumasv resilientmonotonesequentialmaximization AT jadbabaiea resilientmonotonesequentialmaximization AT pappasgj resilientmonotonesequentialmaximization |