Solving partially observable agent-intruder games with an application to border security problems

Corine M. Laan (Corresponding Author), Ana Isabel Barros, Richard Boucherie, Herman Monsuur, Judith Timmer

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

Abstract

In this paper, we introduce partially observable agent-intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent’s movement. We formulate the problem as a two-person zero-sum game, and develop efficient algorithms to compute each player’s optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ɛ-optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ɛ-optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.
Original languageEnglish
Article number21834
Pages (from-to)174-190
Number of pages17
JournalNaval research logistics
Volume66
Issue number2
DOIs
Publication statusPublished - Mar 2019

Fingerprint

Game
Optimal Strategy
Imperfect
Horizon
Search Game
Sensor
Belief Functions
Two-person Games
Dynamic Games
Zero sum game
Sensors
Approximation algorithms
Approximation Algorithms
Dynamic models
Efficient Algorithms
Choose
Numerical Results
Graph in graph theory
Optimal strategy

Keywords

  • UT-Hybrid-D
  • Incomplete information
  • Sequence form
  • Stochastic games
  • Defense applications

Cite this

@article{3426d309848642239f33c7a1486fb3eb,
title = "Solving partially observable agent-intruder games with an application to border security problems",
abstract = "In this paper, we introduce partially observable agent-intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent’s movement. We formulate the problem as a two-person zero-sum game, and develop efficient algorithms to compute each player’s optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ɛ-optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ɛ-optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.",
keywords = "UT-Hybrid-D, Incomplete information, Sequence form, Stochastic games, Defense applications",
author = "Laan, {Corine M.} and Barros, {Ana Isabel} and Richard Boucherie and Herman Monsuur and Judith Timmer",
note = "Wiley deal",
year = "2019",
month = "3",
doi = "10.1002/nav.21834",
language = "English",
volume = "66",
pages = "174--190",
journal = "Naval research logistics",
issn = "0894-069X",
publisher = "Wiley",
number = "2",

}

Solving partially observable agent-intruder games with an application to border security problems. / Laan, Corine M. (Corresponding Author); Barros, Ana Isabel; Boucherie, Richard; Monsuur, Herman; Timmer, Judith.

In: Naval research logistics, Vol. 66, No. 2, 21834, 03.2019, p. 174-190.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Solving partially observable agent-intruder games with an application to border security problems

AU - Laan, Corine M.

AU - Barros, Ana Isabel

AU - Boucherie, Richard

AU - Monsuur, Herman

AU - Timmer, Judith

N1 - Wiley deal

PY - 2019/3

Y1 - 2019/3

N2 - In this paper, we introduce partially observable agent-intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent’s movement. We formulate the problem as a two-person zero-sum game, and develop efficient algorithms to compute each player’s optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ɛ-optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ɛ-optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.

AB - In this paper, we introduce partially observable agent-intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent’s movement. We formulate the problem as a two-person zero-sum game, and develop efficient algorithms to compute each player’s optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ɛ-optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ɛ-optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.

KW - UT-Hybrid-D

KW - Incomplete information

KW - Sequence form

KW - Stochastic games

KW - Defense applications

U2 - 10.1002/nav.21834

DO - 10.1002/nav.21834

M3 - Article

VL - 66

SP - 174

EP - 190

JO - Naval research logistics

JF - Naval research logistics

SN - 0894-069X

IS - 2

M1 - 21834

ER -