Efficiently Solving Joint Activity Based Security Games

Shieh, Eric Anyung; Jain, Manish; Jiang, Albert Xin; Tambe, Milind

Efficiently Solving Joint Activity Based Security Games

Eric Anyung Shieh, Manish Jain, Albert Xin Jiang, Milind Tambe

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 346-351.

Abstract

Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.

Eric Anyung Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. Efficiently Solving Joint Activity Based Security Games. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 346–351. https://ijcai.org/proceedings/2013/59

@inproceedings{ijcai2013p59,
  title     = {Efficiently Solving Joint Activity Based Security Games},
  author    = {Shieh, Eric Anyung and Jain, Manish and Jiang, Albert Xin and Tambe, Milind},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {346--351},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/59},
}

TY  - CPAPER
TI  - Efficiently Solving Joint Activity Based Security Games
AU  - Shieh, Eric Anyung
AU  - Jain, Manish
AU  - Jiang, Albert Xin
AU  - Tambe, Milind
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 346
EP  - 351
UR  - https://ijcai.org/proceedings/2013/59
ER  -