Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach

Corine Maartje Laan, Ana Isabel Barros, Richard Boucherie, Herman Monsuur

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

In this chapter we consider a security game between an agent and an intruder to find optimal strategies for patrolling against illegal fishery. When patrolling large areas that consist of multiple cells, several aspects have to be taken into account. First, the current risk of the cells has to be considered such that cells with high risk are visited more often. Moreover, it is important to be unpredictable in order to increase the patrolling effectiveness countering illegal fishery. Finally, patrolling strategies have to be chosen in such a manner that they satisfy given operational requirements. For example, the agent might be required to patrol some cells more often than others imposing extra restrictions on the agent strategies. In this chapter, we develop a dynamic variant of the security game with restrictions on the agent’s strategy so that all these requirements are taken into account. We model this game as a stochastic game with a final penalty to ensure that the operational requirements are met. In this way, strategies are formed that both consider past actions and expected future risk levels. Due to the curse of dimensionality, these stochastic games cannot be solved for large scale instances. We develop an approximate dynamic programming algorithm to find approximate solutions.
Original languageEnglish
Title of host publicationNL ARMS Netherlands Annual Review of Military Studies 2018
Subtitle of host publicationCoastal Border Control: From Data and Tasks to Deployment and Law Enforcement
EditorsHerman Monsuur
Place of PublicationThe Hague
PublisherT.M.C. Asser Press
Chapter9
Pages171-191
Number of pages21
ISBN (Electronic)978-94-6265-246-0
ISBN (Print)978-94-6265-246-0_9
DOIs
Publication statusPublished - 13 Jul 2018

Publication series

NameNL ARMS : Netherlands Annual Review of Military Studies
PublisherT.M.C. Asser Press
ISSN (Print)1387-8050
ISSN (Electronic)2452-235X

Fingerprint

Approximate Dynamic Programming
Game
Stochastic Games
Cell
Requirements
Restriction
Curse of Dimensionality
Optimal Strategy
Penalty
Approximate Solution
Strategy

Keywords

  • Stochastic games
  • Security
  • Patrolling
  • Restricted strategies
  • Approximate dynamic programming
  • Aggregation

Cite this

Laan, C. M., Barros, A. I., Boucherie, R., & Monsuur, H. (2018). Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach. In H. Monsuur (Ed.), NL ARMS Netherlands Annual Review of Military Studies 2018: Coastal Border Control: From Data and Tasks to Deployment and Law Enforcement (pp. 171-191). (NL ARMS : Netherlands Annual Review of Military Studies). The Hague: T.M.C. Asser Press. https://doi.org/10.1007%2F978-94-6265-246-0_9
Laan, Corine Maartje ; Barros, Ana Isabel ; Boucherie, Richard ; Monsuur, Herman. / Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach. NL ARMS Netherlands Annual Review of Military Studies 2018: Coastal Border Control: From Data and Tasks to Deployment and Law Enforcement. editor / Herman Monsuur. The Hague : T.M.C. Asser Press, 2018. pp. 171-191 (NL ARMS : Netherlands Annual Review of Military Studies).
@inbook{41321dc352ef4e8bafde1a2f44668540,
title = "Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach",
abstract = "In this chapter we consider a security game between an agent and an intruder to find optimal strategies for patrolling against illegal fishery. When patrolling large areas that consist of multiple cells, several aspects have to be taken into account. First, the current risk of the cells has to be considered such that cells with high risk are visited more often. Moreover, it is important to be unpredictable in order to increase the patrolling effectiveness countering illegal fishery. Finally, patrolling strategies have to be chosen in such a manner that they satisfy given operational requirements. For example, the agent might be required to patrol some cells more often than others imposing extra restrictions on the agent strategies. In this chapter, we develop a dynamic variant of the security game with restrictions on the agent’s strategy so that all these requirements are taken into account. We model this game as a stochastic game with a final penalty to ensure that the operational requirements are met. In this way, strategies are formed that both consider past actions and expected future risk levels. Due to the curse of dimensionality, these stochastic games cannot be solved for large scale instances. We develop an approximate dynamic programming algorithm to find approximate solutions.",
keywords = "Stochastic games, Security, Patrolling, Restricted strategies, Approximate dynamic programming, Aggregation",
author = "Laan, {Corine Maartje} and Barros, {Ana Isabel} and Richard Boucherie and Herman Monsuur",
year = "2018",
month = "7",
day = "13",
doi = "10.1007{\%}2F978-94-6265-246-0_9",
language = "English",
isbn = "978-94-6265-246-0_9",
series = "NL ARMS : Netherlands Annual Review of Military Studies",
publisher = "T.M.C. Asser Press",
pages = "171--191",
editor = "Herman Monsuur",
booktitle = "NL ARMS Netherlands Annual Review of Military Studies 2018",

}

Laan, CM, Barros, AI, Boucherie, R & Monsuur, H 2018, Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach. in H Monsuur (ed.), NL ARMS Netherlands Annual Review of Military Studies 2018: Coastal Border Control: From Data and Tasks to Deployment and Law Enforcement. NL ARMS : Netherlands Annual Review of Military Studies, T.M.C. Asser Press, The Hague, pp. 171-191. https://doi.org/10.1007%2F978-94-6265-246-0_9

Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach. / Laan, Corine Maartje; Barros, Ana Isabel; Boucherie, Richard; Monsuur, Herman.

NL ARMS Netherlands Annual Review of Military Studies 2018: Coastal Border Control: From Data and Tasks to Deployment and Law Enforcement. ed. / Herman Monsuur. The Hague : T.M.C. Asser Press, 2018. p. 171-191 (NL ARMS : Netherlands Annual Review of Military Studies).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach

AU - Laan, Corine Maartje

AU - Barros, Ana Isabel

AU - Boucherie, Richard

AU - Monsuur, Herman

PY - 2018/7/13

Y1 - 2018/7/13

N2 - In this chapter we consider a security game between an agent and an intruder to find optimal strategies for patrolling against illegal fishery. When patrolling large areas that consist of multiple cells, several aspects have to be taken into account. First, the current risk of the cells has to be considered such that cells with high risk are visited more often. Moreover, it is important to be unpredictable in order to increase the patrolling effectiveness countering illegal fishery. Finally, patrolling strategies have to be chosen in such a manner that they satisfy given operational requirements. For example, the agent might be required to patrol some cells more often than others imposing extra restrictions on the agent strategies. In this chapter, we develop a dynamic variant of the security game with restrictions on the agent’s strategy so that all these requirements are taken into account. We model this game as a stochastic game with a final penalty to ensure that the operational requirements are met. In this way, strategies are formed that both consider past actions and expected future risk levels. Due to the curse of dimensionality, these stochastic games cannot be solved for large scale instances. We develop an approximate dynamic programming algorithm to find approximate solutions.

AB - In this chapter we consider a security game between an agent and an intruder to find optimal strategies for patrolling against illegal fishery. When patrolling large areas that consist of multiple cells, several aspects have to be taken into account. First, the current risk of the cells has to be considered such that cells with high risk are visited more often. Moreover, it is important to be unpredictable in order to increase the patrolling effectiveness countering illegal fishery. Finally, patrolling strategies have to be chosen in such a manner that they satisfy given operational requirements. For example, the agent might be required to patrol some cells more often than others imposing extra restrictions on the agent strategies. In this chapter, we develop a dynamic variant of the security game with restrictions on the agent’s strategy so that all these requirements are taken into account. We model this game as a stochastic game with a final penalty to ensure that the operational requirements are met. In this way, strategies are formed that both consider past actions and expected future risk levels. Due to the curse of dimensionality, these stochastic games cannot be solved for large scale instances. We develop an approximate dynamic programming algorithm to find approximate solutions.

KW - Stochastic games

KW - Security

KW - Patrolling

KW - Restricted strategies

KW - Approximate dynamic programming

KW - Aggregation

U2 - 10.1007%2F978-94-6265-246-0_9

DO - 10.1007%2F978-94-6265-246-0_9

M3 - Chapter

SN - 978-94-6265-246-0_9

T3 - NL ARMS : Netherlands Annual Review of Military Studies

SP - 171

EP - 191

BT - NL ARMS Netherlands Annual Review of Military Studies 2018

A2 - Monsuur, Herman

PB - T.M.C. Asser Press

CY - The Hague

ER -

Laan CM, Barros AI, Boucherie R, Monsuur H. Security Games with Restricted Strategies: An Approximate Dynamic Programming Approach. In Monsuur H, editor, NL ARMS Netherlands Annual Review of Military Studies 2018: Coastal Border Control: From Data and Tasks to Deployment and Law Enforcement. The Hague: T.M.C. Asser Press. 2018. p. 171-191. (NL ARMS : Netherlands Annual Review of Military Studies). https://doi.org/10.1007%2F978-94-6265-246-0_9