General Markov Model for Solving Patrolling Games
Andrzej Nagórko, Marcin Waniek, Małgorzata Róg, Michał Godziszewski, Barbara Rosiak, Tomasz Paweł Michalak
Abstract
Safeguarding critical infrastructure has recently emerged as a global challenge. To address complex security concerns raised by broadening array of threats, effective mobile security forces are essential. A key aspect involves designing optimal patrolling strategies for mobile units. Two bodies of research dealt with this: stochastic patrolling and partially observable stochastic games. Alas, the first approach makes too-far-reaching simplifying assumption and the second one is more expressive but computationally challenging. The model proposed in this paper is inspired by partially observable stochastic games so that it is general enough to enable comprehensive modeling of attacker-defender interactions but a the same time remains computationally friendly. With our proposed robust SHIELD algorithm, we are able to find a defense strategy where the probability of apprehending the attacker can be nearly doubled compared to the state of the art.
BibTeX
@InProceedings{pmlr-v244-nagorko24a,
title = {General Markov Model for Solving Patrolling Games},
author = {Nag\'orko, Andrzej and Waniek, Marcin and R\'og, Ma{\l}gorzata and Godziszewski, Micha{\l} and Rosiak, Barbara and Michalak, Tomasz Pawe{\l}},
booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence},
pages = {2646--2669},
year = {2024},
editor = {Kiyavash, Negar and Mooij, Joris M.},
volume = {244},
series = {Proceedings of Machine Learning Research},
month = {15--19 Jul},
publisher = {PMLR},
pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/nagorko24a/nagorko24a.pdf},
url = {https://proceedings.mlr.press/v244/nagorko24a.html},
abstract = {Safeguarding critical infrastructure has recently emerged as a global challenge. To address complex security concerns raised by broadening array of threats, effective mobile security forces are essential. A key aspect involves designing optimal patrolling strategies for mobile units. Two bodies of research dealt with this: stochastic patrolling and partially observable stochastic games. Alas, the first approach makes too-far-reaching simplifying assumption and the second one is more expressive but computationally challenging. The model proposed in this paper is inspired by partially observable stochastic games so that it is general enough to enable comprehensive modeling of attacker-defender interactions but a the same time remains computationally friendly. With our proposed robust SHIELD algorithm, we are able to find a defense strategy where the probability of apprehending the attacker can be nearly doubled compared to the state of the art.}
}