EUVIMEDEUVIMED entdecken
Crossref

Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games

Vojtěch Kůr, Vít Musil, Vojtěch Řehák

Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 142-151

DOI: 10.1609/icaps.v36i1.42823 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Vojtěch Kůr und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Adversarial Patrolling games form a subclass of Security games where a Defender moves between locations, guarding vulnerable targets. The main algorithmic problem is constructing a strategy for the Defender that minimizes the worst damage an Attacker can cause. We focus on the class of finite-memory (also known as regular) Defender’s strategies that experimentally outperformed other competing classes. A finite-memory strategy can be seen as a positional strategy on a finite set of states. Each state consists of a pair of a location and a certain integer value–called memory. Existing algorithms improve the transitional probabilities between the states, but require that the available memory size itself is assigned at each location manually. Choosing the right memory assignment is a well-known open and hard problem that hinders the usability of finite-memory strategies. We solve this issue by developing a general method that iteratively changes the memory assignment. Our algorithm can be used in connection with any black-box strategy optimization tool. We evaluate our method on various experiments and show its robustness by solving instances of various patrolling models.

Zitieren

APA

Kůr, V., Musil, V., & Řehák, V. (2026). Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 142-151. https://doi.org/10.1609/icaps.v36i1.42823

Vancouver

Kůr V, Musil V, Řehák V. Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):142-151. doi:10.1609/icaps.v36i1.42823

BibTeX
@article{Kr2026,
  author = {Kůr, Vojtěch and Musil, Vít and Řehák, Vojtěch},
  title = {Memory Assignment for Finite-Memory Strategies in Adversarial Patrolling Games},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {142--151},
  doi = {10.1609/icaps.v36i1.42823}
}
Kostenlos starten →