General Markov Model for Solving Patrolling Games

Andrzej Nagórko, Marcin Waniek, Małgorzata Róg, Michał Godziszewski, Barbara Rosiak, Tomasz Paweł Michalak
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:2646-2669, 2024.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T General Markov Model for Solving Patrolling Games %A Andrzej Nagórko %A Marcin Waniek %A Małgorzata Róg %A Michał Godziszewski %A Barbara Rosiak %A Tomasz Paweł Michalak %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-nagorko24a %I PMLR %P 2646--2669 %U https://proceedings.mlr.press/v244/nagorko24a.html %V 244 %X 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.
APA
Nagórko, A., Waniek, M., Róg, M., Godziszewski, M., Rosiak, B. & Michalak, T.P.. (2024). General Markov Model for Solving Patrolling Games. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:2646-2669 Available from https://proceedings.mlr.press/v244/nagorko24a.html.

Related Material