A Stochastic Surveillance Stackelberg Game: Co-Optimizing Defense Placement and Patrol Strategy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909571867475968 |
|---|---|
| author | John, Yohan Diaz-Garcia, Gilberto Duan, Xiaoming Marden, Jason R. Bullo, Francesco |
| author_facet | John, Yohan Diaz-Garcia, Gilberto Duan, Xiaoming Marden, Jason R. Bullo, Francesco |
| contents | Stochastic patrol routing is known to be advantageous in adversarial settings; however, the optimal choice of stochastic routing strategy is dependent on a model of the adversary. We adopt a worst-case omniscient adversary model from the literature and extend the formulation to accommodate heterogeneous defenses at the various nodes of the graph. Introducing this heterogeneity leads to interesting new patrol strategies. We identify efficient methods for computing these strategies in certain classes of graphs. We assess the effectiveness of these strategies via comparison to an upper bound on the value of the game. Finally, we leverage the heterogeneous defense formulation to develop novel defense placement algorithms that complement the patrol strategies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14714 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Stochastic Surveillance Stackelberg Game: Co-Optimizing Defense Placement and Patrol Strategy John, Yohan Diaz-Garcia, Gilberto Duan, Xiaoming Marden, Jason R. Bullo, Francesco Systems and Control Computer Science and Game Theory Optimization and Control Stochastic patrol routing is known to be advantageous in adversarial settings; however, the optimal choice of stochastic routing strategy is dependent on a model of the adversary. We adopt a worst-case omniscient adversary model from the literature and extend the formulation to accommodate heterogeneous defenses at the various nodes of the graph. Introducing this heterogeneity leads to interesting new patrol strategies. We identify efficient methods for computing these strategies in certain classes of graphs. We assess the effectiveness of these strategies via comparison to an upper bound on the value of the game. Finally, we leverage the heterogeneous defense formulation to develop novel defense placement algorithms that complement the patrol strategies. |
| title | A Stochastic Surveillance Stackelberg Game: Co-Optimizing Defense Placement and Patrol Strategy |
| topic | Systems and Control Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2308.14714 |