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

2 Citations (Scopus)
1 Downloads (Pure)


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
Issue number2
Publication statusPublished - Mar 2019


  • UT-Hybrid-D
  • Incomplete information
  • Sequence form
  • Stochastic games
  • Defense applications
  • 22/4 OA procedure


Dive into the research topics of 'Solving partially observable agent-intruder games with an application to border security problems'. Together they form a unique fingerprint.

Cite this