Resilient Observation Selection in Adversarial Settings
Aron Laszka, Yevgeniy Vorobeychik, Xenofon Koutsoukos

Citation
Aron Laszka, Yevgeniy Vorobeychik, Xenofon Koutsoukos. "Resilient Observation Selection in Adversarial Settings". 54th IEEE Conference on Decision and Control (CDC), December, 2015.

Abstract
Monitoring large areas using sensors is fundamental in a number of applications, including electric power grid, traffic networks, and sensor-based pollution control systems. However, the number of sensors that can be deployed is often limited by financial or technological constraints. This problem is further complicated by the presence of strategic adversaries, who may disable some of the deployed sensors in order to impair the operator's ability to make predictions. Assuming that the operator employs a Gaussian-process-based regression model, we formulate the problem of attack-resilient sensor placement as the problem of selecting a subset from a set of possible observations, with the goal of minimizing the uncertainty of predictions. We show that both finding an optimal resilient subset and finding an optimal attack against a given subset are NP-hard problems. Since both the design and the attack problems are computationally complex, we propose efficient heuristic algorithms for solving them and present theoretical approximability results. Finally, we show that the proposed algorithms perform exceptionally well in practice using numerical results based on real-world datasets.

Electronic downloads

Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Aron Laszka, Yevgeniy Vorobeychik, Xenofon Koutsoukos. <a
  href="http://www.cps-forces.org/pubs/117.html"
  >Resilient Observation Selection in Adversarial
  Settings</a>, 54th IEEE Conference on Decision and
  Control (CDC), December, 2015.

• Plain text

  Aron Laszka, Yevgeniy Vorobeychik, Xenofon Koutsoukos.
  "Resilient Observation Selection in Adversarial
  Settings". 54th IEEE Conference on Decision and Control
  (CDC), December, 2015.

• BibTeX

  @inproceedings{LaszkaVorobeychikKoutsoukos15_ResilientObservationSelectionInAdversarialSettings,
      author = {Aron Laszka and Yevgeniy Vorobeychik and Xenofon
                Koutsoukos},
      title = {Resilient Observation Selection in Adversarial
                Settings},
      booktitle = {54th IEEE Conference on Decision and Control (CDC)},
      month = {December},
      year = {2015},
      abstract = {Monitoring large areas using sensors is
                fundamental in a number of applications, including
                electric power grid, traffic networks, and
                sensor-based pollution control systems. However,
                the number of sensors that can be deployed is
                often limited by financial or technological
                constraints. This problem is further complicated
                by the presence of strategic adversaries, who may
                disable some of the deployed sensors in order to
                impair the operator's ability to make predictions.
                Assuming that the operator employs a
                Gaussian-process-based regression model, we
                formulate the problem of attack-resilient sensor
                placement as the problem of selecting a subset
                from a set of possible observations, with the goal
                of minimizing the uncertainty of predictions. We
                show that both finding an optimal resilient subset
                and finding an optimal attack against a given
                subset are NP-hard problems. Since both the design
                and the attack problems are computationally
                complex, we propose efficient heuristic algorithms
                for solving them and present theoretical
                approximability results. Finally, we show that the
                proposed algorithms perform exceptionally well in
                practice using numerical results based on
                real-world datasets.},
      URL = {http://cps-forces.org/pubs/117.html}
  }
  

Posted by Aron Laszka on 15 Mar 2016.
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.