Randomized Sensing in Adversarial Environments

Krause, Andreas; Roper, Alex; Golovin, Daniel

doi:10.5591/978-1-57735-516-8/IJCAI11-356

Randomized Sensing in Adversarial Environments

Andreas Krause, Alex Roper, Daniel Golovin

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2133-2138.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-356

Abstract

How should we manage a sensor network to optimally guard security-critical infrastructure? How should we coordinate search and rescue helicopters to best locate survivors after a major disaster? In both applications, we would like to control sensing resources in uncertain, adversarial environments. In this paper, we introduce RSense, an efficient algorithm which guarantees near-optimal randomized sensing strategies whenever the detection performance satisfies submodularity, a natural diminishing returns property, for any fixed adversarial scenario. Our approach combines techniques from game theory with submodular optimization. The RSense algorithm applies to settings where the goal is to manage a deployed sensor network or to coordinate mobile sensing resources (such as unmanned aerial vehicles). We evaluate our algorithms on two real-world sensing problems.

Andreas Krause, Alex Roper, and Daniel Golovin. 2011. Randomized Sensing in Adversarial Environments. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2133–2138. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-356

@inproceedings{ijcai2011p356,
  title     = {Randomized Sensing in Adversarial Environments},
  author    = {Krause, Andreas and Roper, Alex and Golovin, Daniel},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2133--2138},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-356},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-356},
}

TY  - CPAPER
TI  - Randomized Sensing in Adversarial Environments
AU  - Krause, Andreas
AU  - Roper, Alex
AU  - Golovin, Daniel
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2133
EP  - 2138
DO  - 10.5591/978-1-57735-516-8/IJCAI11-356
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-356
ER  -