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

Corine M. Laan, Ana Isabel Barros, Richard J. Boucherie, Herman Monsuur and Judith Timmer

Naval Research Logistics (NRL), 2019, vol. 66, issue 2, 174-190

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.

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.21834

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:66:y:2019:i:2:p:174-190

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().