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

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.