Sage Journals: Discover world-class research

Abstract

In this paper, we consider the optimal deployment of multiple assets in anti-submarine warfare (ASW) operations with time-dependent strategies. We model this as a zero-sum game that takes place over a finite time horizon. An agent, representing multiple assets, in an ASW operation, decides on the allocation of these assets (e.g., one or more frigates and helicopters) to prevent an intruder, an enemy submarine, from attacking a moving high-value unit (HVU), e.g., a tanker ship. Hereby, the agent aims to prevent an intruder, an enemy submarine, from attacking a moving HVU, e.g., a tanker ship. The intruder is deciding on a route that minimizes the detection probability given the agent’s strategy. We first consider a game model where a part of the agent’s strategy, namely the complete strategy of a frigate, is known to the intruder; and second, we consider a sequential game approach where the exact location of the frigate becomes known to the intruder at the start of each time interval. For both approaches, we construct (integer) linear programs, give complexity results, and use an algorithmic approach to determine optimal strategies. Finally, we explore the added value of this approach in comparison to a traditional ASW simulation model.

Keywords

Anti-submarine warfare game theory integer programming

1. Introduction

Submarines pose an important naval threat to naval fleets and capital ships, as previous conflicts show.^1,2 In this paper, we discuss a model to optimize anti-submarine warfare (ASW) operations. The aim of an ASW operation is to detect and hunt an enemy submarine or to protect one or multiple high-value units (HVUs), like a tanker ship or a navy task group, against attacks from enemy submarines. Different types of ASW operations exist depending on the aim (detection or preventing an attack) and whether the area of interest is stationary or in transit, i.e., moving with a task group. Preventing an attack can be achieved either by conducting a barrier search operation or a transit operation. The goal of a barrier search operation is to ensure that an enemy submarine will not cross a certain barrier. In a transit operation HVUs are moving from one side of an area to the other side. During this transit the HVUs have to be protected from the attacks of enemy submarines.

In this paper, we focus on a transit operation where one or multiple HVUs have to be protected. By adjusting the input parameters, however, the proposed model can also be used for (barrier) search operations. In order to tackle this problem we introduce two different game theoretic approaches for ASW operation and extend several aspects of known approaches to overcome their limitations. We also compare the results obtained with predefined tactics in a simulation approach

To prevent an attack, the defender (agent) can deploy various different platforms, each with their own characteristics. Frigates have a long endurance but are relatively slow, while helicopters are faster but have a shorter endurance. For the deployment of these units, tactics have been developed. A tactic describes when a unit is used, when it uses its sensors (for instance sonar) to detect the submarine, the path that is followed by the unit, and how it reacts to a positive detection. The optimal tactic depends upon, among other factors, the environment, e.g., the water depth, the detection distance, and the possibility for the submarine to hide; and the behavior of the submarine, e..g., when it attacks, whether it is prepared to take more risk in an attack, and how it makes use of the information it has about how the defender will act. Many of these aspects are unknown to the defender. This means that the number of possible tactics is very high, as well as there being uncertainty about the circumstances that determine which tactical is optimal.

The game discussed in this paper is a special variant of a search game.^3–8 In search games, an intruder is attacking one or multiple cells on a graph while an agent is searching the graph to prevent the attack. An overview of search games is given by Hohzaki.⁵ The main difference from these traditional search games is that we consider an agent that is able to deploy multiple assets of different types (frigates and helicopters), while in the traditional search games only a single asset type is used.

Several ASW models are discussed in the literature.^9–14 Mishra et al. give an overview of various papers related to ASW problems, and they describe several issues that may complicate the analysis, such as dimensionality of the resulting model and coordination of multiple assets.¹¹ Thomas describes different models for the planning of multiple ASW platforms for the protection of a HVU.¹⁴ The coordination of multiple platforms is considered using a game theoretic approach to take into account the intruder’s behavior. Hew and Yiap consider the patrolling at choke points. By patrolling at choke points, the enemy submarine is deterred or has to take a longer route.¹⁰ They develop an interdiction game to determine the optimal randomized allocation of resources to different choke points.

In Brown et al. ⁹ and Monsuur et al.¹² the authors developed a game theoretical ASW model for the protection of a single HVU. The intruder chooses a path from outside the area to the HVU. The agents can deploy multiple assets: frigates, helicopters, or submarines. The intruder can observe the frigates, so it is assumed that the locations of the frigates are fixed and common knowledge. The allocation of the helicopters and submarines follows a probability distribution. The work of Brown et al. and Monsuur et al. only models a fixed HVU and a static strategy of the agent, comparable to a barrier search operation. Usually, however, the HVU is moving from one location to another, and the frigate should be able to patrol at several locations over time. Therefore, we extend the static model by adding a time aspect. The HVU is moving over time, and the strategies of both the agent and the intruder are time-dependent. This allows us to model more realistic instances and better react to a moving intruder. When modeling this problem as a dynamic model, two different strategies are used. First, we assume that the frigate’s location is known for the complete time window. Second, we develop a model where the frigate’s current location becomes known to the intruder at the start of each time interval. Therefore, in this case the frigate’s location is also allowed to follow a probability distribution. For both models, the agent always aims at maximizing the probability that the intruder is detected.

In order to assess the effectiveness of ASW tactics, simulation approaches have been developed, like DEVS¹⁵ and ODIN.¹⁶ Another simulation approach has been developed at the Netherlands Organisation for Applied Scientific Research (TNO) for the support of the development and evaluation of operational tactics and future concepts for underwater operations: the Underwater Warfare Testbed (UWT).¹⁷ As opposed to DEVS¹⁵ and ODIN,¹⁶ this model includes the behavior of all platforms that play a role in the underwater domain: both surface platforms, submarines, and torpedoes. This behavior is scripted in the scenario and depends on the environment, detected contacts, the purpose of the mission of the platform, and the risk it is willing to take. In the UWT, existing and/or future platforms and underwater systems can be modeled in the underwater environment to evaluate the overall performance of several tactics and concepts. The modeling of the enemy submarine must, however, be scripted in advance. This means that interactions between submarine and defender are preferably relatively simple as otherwise the scripts become very complicated. For a transit operation, two basic strategies are available: a kamikaze-like approach in which the submarine chooses the shortest path towards the HVU, and a cautious approach in which the submarine tries to avoid detection. In order to more realistically model an enemy submarine as an intelligent intruder that takes into account the strategies of the defender, we use a game theoretic approach.

The rest of this paper is organized as follows. First, we consider the game with complete information about the frigate’s position. We shortly describe the static game model, and thereafter we develop the model used for dynamic allocation of assets where the strategies are time-dependent. Second, we consider a sequential game approach in which the location of the frigate (defending asset) is known to the intruder at the beginning of each time interval. We then present computations for the proposed game approaches as well as a comparison with the UWT simulation approach. We finish with some concluding remarks.

2. Complete information about the frigate’s location

In this section, we describe the game in which the frigate’s location is known for each time step. We first describe the static model as introduced by Brown et al.,⁹ and thereafter we describe the extended model with time-dependent strategies.

2.1 Protection of a static HVU

The static game is modeled as a zero-sum game where the agent (defender) is maximizing the detection probability for each route that the intruder, representing the enemy submarine, can choose from.⁹ For the agent, different assets (frigates, helicopters, and submarines) are modeled and the detection rates are specified for each asset. We only consider frigates and helicopters for the agent; submarines can be modeled similarly to helicopters.

The game is played over a network with cells, $C$ . The set of possible start cells for the intruder is $C_{S}$ , and the target cell is $C_{T}$ . The strategy set of the agent is the set of all possible allocations for the frigates and helicopters. For the frigates of the agent, there is a decision variable $x^{F}$ that specifies the probability that the frigate is located in each cell. Because the exact locations of the frigates are assumed to be known to the intruders, these probabilities are only allowed to equal 0 or 1. There are $N^{F}$ frigates and the variable $x_{mi}^{F}$ is $1$ if frigate $m$ , $m = 1, . ., N^{F}$ is located at cell $i$ , $i \in C$ , and $0$ otherwise. Additionally, for each frigate $m$ , there are $N_{m}^{H}$ helicopters. The exact location of the helicopter is not known in advance by the intruder. The allocation of the helicopters is given by a variable $x_{mnij}^{H}$ that specifies for each cell $i$ the probability that helicopter $n$ , corresponding to frigate $m$ allocated to cell $i$ , is allocated to cell $j$ .

By choosing the allocation of frigates and helicopters, the detection rate at each cell $d_{i}$ , $i \in C$ , can be decided. Let $D_{ij}^{F}$ be the detection rate in cell $i$ of a frigate that is located in cell $j$ , and $D_{ijk}^{H}$ the detection rate in cell $i$ by a helicopter, corresponding to a frigate in $j$ , that is located in cell $k$ . The intruder chooses a route over a set of routes with minimal detection rate. Let $v_{i}$ be the expected detection rate from a start point to cell $i$ for the intruder. $B^{I}$ gives the possible moves of the intruder where $B_{ij}^{I}$ equals $1$ if cell $j$ is adjacent to cell $i$ , otherwise $0$ . The time to move from cell $i$ to cell $j$ for the intruder is $τ_{ij}$ .

The agent’s strategy can be found by solving⁹:

\begin{matrix} max_{x^{F}, x^{H}} v_{C_{T}} \\ s . t . \sum_{i} x_{mi}^{F} = 1, & m = 1, . . ., N^{F}, \\ \sum_{j} x_{mnij}^{H} = x_{mi}^{F}, & m = 1, . . ., N^{F}, n = 1, . . ., N^{H}, \\ d_{i} = \sum_{j, m} D_{ij}^{F} x_{mj}^{F} + \sum_{i, j, n, m} D_{ijk}^{H} x_{mnjk}^{H}, & i \in C, \\ v_{j} \leq v_{i} + τ_{ij} \frac{(d_{i} + d_{j})}{2} + (1 - B_{ij}^{I}) M, & j \in C \ C_{S}, i \in C, \\ v_{i} = 0, & i \in C_{S}, \\ x_{mi}^{F} \in {0, 1}, & m = 1, . . ., N^{F}, i \in C, \\ x_{ni}^{H} \geq 0, & n = 1, . . ., N^{H}, i \in C . \end{matrix}

The first constraint ensures that each frigate is only assigned to one location. The second constraint makes sure that all helicopters are assigned to a cell such that helicopters corresponding to a frigate in a specific cell can only be assigned if the frigate is in that cell. The third constraint calculates the total detection probability for each cell. The fourth constraint is used to calculate for each cell the probability of detecting the intruder when this intruder is choosing a route to that cell. Here, it is assumed that the intruders will always choose the route to the cell that minimizes this detection probability. $M$ is a large number used to ensure that only possible routes are chosen by the intruder. The fifth constraint says that this detection probability is zero for the starting cells of the intruder.

The agent wants to maximize the probability of detecting the intruder. The agent is only interested in maximizing the detection probabilities over the routes that end at the target cell $C_{T}$ .

2.2 Dynamic game with time-dependent strategies

In this section, we extend the static model of Brown et al.⁹ by modeling a moving HVU and time-dependent strategies for both the agent and the intruder. The HVU is moving during the game, and the position of the HVU is known in advance to both the agent and the intruder.

For the agent’s strategy, we only consider frigates and helicopters. Other assets, such as submarines, can be added in a similar way. At each time step, the agent can decide on a new position for the frigates and the helicopters, similar to the static game. The location of each frigate is limited by the speed of that frigate. As in the static game, the location of each frigate is known to the intruder, while the exact locations of the helicopters are not. The intruder represents the enemy submarine that is aiming at attacking the HVU. The intruder’s strategy also changes, when compared to the static game. The intruder is still allowed to choose any path starting in one of the starting locations. Additionally, it might be optimal for the intruder to wait at a cell for a fixed amount of time.

2.2.1 Model description

The game takes place over a network of $N + 1$ cells. The set of possible cells is given by $C = {0, 1, . . ., N}$ . The possible start cells for the intruder are $C_{S}$ , the frigate can start in every cell. During the game, both the frigates of the agent and the intruder follow a route. The time it takes for a frigate to move from cell $i$ to cell $j$ is $τ_{ij}^{F}$ and similar for the intruder, $τ_{ij}^{I}$ . For modeling convenience, we assume that the time is discrete and that the game takes place during a fixed time window $T$ . By choosing the length of each interval to be small enough, the real time can be approximated.

The HVU follows a fixed path that is known to both the agent and the intruder. For each time $t = 0, 1, . . ., T$ , the target cells (corresponding to the HVU’s location) are given by $C_{T} (t)$ .

The actions of the agents consist of two elements: the allocation of the frigates, which is known to the intruder, and the allocation of the helicopters, which is randomized. There are $N^{F}$ frigates and $N_{m}^{H}$ helicopters for each frigate $m$ . For each frigate, the agents decided on a fixed route. The time it takes for a frigate to move from $i$ to $j$ is given by $τ_{ij}^{F}$ . The frigates are only allowed to move between connected cells given by the matrix $B^{F}$ , where $B_{ij}^{F}$ is $1$ if $i$ and $j$ are connected, and $0$ otherwise.

The location of the frigates during each time window is given by $x_{mit}^{F}$ , so that $x_{mit}^{F}$ equals $1$ if frigate $m$ is in cell $i$ during time $t$ , and $0$ otherwise. The frigate’s location has to be chosen such that it complies with $τ_{ij}^{F}$ and $B^{F}$ , which will be taken into account by the construction of the mathematical program.

Each frigate has a number of helicopters that can be deployed. An action of a single helicopter is modeled by a probability distribution over the cells depending on the frigate’s location. Let $x_{mnijt}^{H}$ be the probability that a helicopter $n$ corresponding to frigate $m$ located in cell $i$ is deployed at cell $j$ during time window $t$ . The strategy space of a single helicopter $n$ corresponding to frigate $m$ is given by:

{x^{H} | x_{mnijt}^{H} \geq 0, \sum_{j} x_{mnijt}^{H} = x_{mit}^{F}, j \in C, t = 0, . . ., T} .

(1)

The action of the intruder is also given by a route through the network. Similar to the frigate, the time to move between cells is given by $τ_{ij}^{I}$ , and possible moves are displayed in the matrix $B^{I}$ , where $B_{ijt}^{I}$ equals $1$ if the intruder is allowed to move from cell $i$ to cell $j$ during $t$ , and $0$ otherwise. The routes of the intruder are given by $x^{I}$ such that $x_{ijt}^{I}$ equals 1 if the intruder moves from $i$ to $j$ during $t$ . Similar to the frigate, the intruder’s location has to comply with $τ_{ij}^{I}$ and $B^{I}$ .

The detection rate of the frigates and helicopters is given by $D^{F}$ and $D^{H}$ , respectively, where $D_{ij}^{F}$ is the detection rate in cell $i$ if the frigate is in cell $j$ and $D_{ijk}^{H}$ is the detection rate in cell $i$ for a helicopter that is located in cell $j$ corresponding to a frigate in cell $k$ . The detection rate $d_{it}$ can be different for each time period depending on the allocation of the frigates and helicopters:

d_{it} = \sum_{j, m} D_{ij}^{F} x_{mjt}^{F} + \sum_{j, m, n, k} D_{ijk}^{H} x_{mnjkt}^{H}, i \in C, t = 0, . . ., T .

(2)

For modelling purposes we introduce a fictive cell, cell $0$ , which has a detection rate of $0$ . In order to model that the frigate can start at every possible cell, we assume that cell $0$ is adjacent to all $i \in C$ and $B_{0 j}^{F}$ equals $1$ for each $j \in C$ . On the other hand, the intruder can only start from cell $0$ , and thus $B_{0 jt}^{I}$ equals $1$ for all $j \in C_{s}$ , $t = 0$ . Moreover, the intruder can move to cell $0$ after reaching a target cell, so $B_{i 0 t}^{I} = 1$ if $i \in C_{T} (t)$ .

Given the detection probabilities $d_{it}$ and an intruder’s strategy $x^{I}$ , the game value, which is the total detection rate, is:

f (d, x^{I}) = {\begin{matrix} \sum_{t = 1}^{T} \sum_{i \in C} d_{it} x_{it}^{I}, & if \exists i \in C_{T} (t) s . t . x_{it}^{I} = 1, \\ \infty, & otherwise . \end{matrix}

The agent is maximizing this function by choosing the routes for the frigates and allocations for the helicopters, while the intruder is minimizing this by deciding on a route.

2.2.2 Construction of the integer linear program

We write $max_{d} min_{r \in R^{I}} f (d, r^{I})$ as a mathematical program by constructing the number of cells and matrices $B^{F}$ and $B^{I}$ of the agent and intruder such that the travel time to each possible cell takes exactly $1$ time step. Note that by adjusting the number of cells, different travel times can be modeled. We show this with the following example.

Example 1. Consider the original ASW game with a single frigate. The frigate moves twice as fast as the intruder, so $τ_{ij}^{F} = 1$ and $τ_{ij}^{I} = 2$ for each $i, j \in C$ . $B^{F}$ and $B^{I}$ give the possible movements of the frigate and intruder, respectively. We now construct a new game such that ${\tilde{τ}}_{ij}^{F} = {\tilde{τ}}_{ij}^{I} = 1$ . To ensure that this game is equivalent with the original game, we construct $\tilde{C}$ , ${\tilde{B}}^{F}$ and ${\tilde{B}}^{I}$ . in the following way. The number of cells is twice as large as the number of cells in the original game, so $\tilde{C} = {0, 1, 2, . . ., 2 N}$ , where each second element corresponds with an element from $C$ , so $i \in \tilde{C}$ corresponds with $i / 2$ in $C$ . ${\tilde{B}}_{ij}^{F}$ equals $1$ if $i$ and $j$ are even and $B_{(i / 2) (j / 2)}^{F} = 1$ , and $0$ otherwise. Finally, ${\tilde{B}}_{ij}^{I}$ equals $1$ if $i$ is odd and $j = i + 1$ , or when $i$ is even and $B_{(i / 2) ((j + 1) / 2)}^{I} = 1$ . By constructing ${\tilde{B}}^{F}$ and ${\tilde{B}}^{I}$ in this way, the frigates only move between the even cells, and the intruder always has to travel through one additional (odd) cell. Therefore, the intruder needs to move two times as many steps between cells corresponding to the original game.

Consider the agent’s allocation of the frigates and helicopters to determine the detection rates $d_{it}$ . The strategies of the agent can then be found by solving the following maxmin formulation:

\begin{matrix} max_{x^{F}, x^{H}} min_{x^{I}} f (d, x^{I}) \\ s . t . \sum_{i} x_{mit}^{F} = 1, & m = 1, . ., N^{F}, t = 0, . . ., T, \\ x_{mit}^{F} \leq (1 - x_{mit'}^{F}) + B_{mij}^{F}, & i, j \in C, t' = t - 1, t = 1, . . ., T, \\ \sum_{j} x_{mnijt}^{H} = 1, & m = 1, . ., N^{F}, n = 1, . ., N_{m}^{H}, i \in C, t = 0, . . ., T, \\ d_{it} = \sum_{j, m} D_{ij}^{F} x_{mjt}^{F} + \sum_{j, m, n, k} D_{ijk}^{H} x_{mnjkt}^{H}, & i \in C, t = 0, . . ., T, \\ x_{mit}^{F} \in {0, 1}, m = 1, . . . N^{F}, & i \in C, t = 0, . . ., T, \\ x_{mnijt}^{H} \geq 0, m = 1, . . . N^{H}, & i \in C, t = 0, . . ., T . \end{matrix}

where the first three constraints ensure that each frigate follows a feasible route and each helicopter is scheduled with probability one. With the fourth constraint, the total detection rate for each cell and each time step is calculated.

Intruder’s program

To construct a linear program (LP), we formulate the intruder’s program $min_{x^{I}} f (d, x^{I})$ separately. Thereafter, we can show that relaxing the integer constraints gives the same value. By taking the dual of the resulting LP, we can rewrite the maxmin problem as a maximization problem. Given the detection probability $d_{it}$ the intruder’s strategy can be determined by:

min_{x_{ijt}^{I}} \sum_{ijt} d_{jt} x_{ijt}^{I}

(3)

s . t . \sum_{j} x_{jit}^{I} = \sum_{j} x_{ijt'}^{I}, i \in C, t' = t + 1, t = 0, . . ., T - 1,

(4)

\sum_{j \in C_{S}} x_{ijt}^{I} = 1, i = 0, t = 0,

(5)

x_{ijt}^{I} \leq B_{ijt}^{I}, i, j \in C, t = 0, . . ., T,

(6)

x_{ijt}^{I} \in {0, 1}, i, j \in C, t = 0, . . ., T .

(7)

The first constraint ensures that the flow into a cell equals the flow out of a cell. The second constraint makes sure that the intruders start at one of the start cells. The third constraint ensures that only allowed routes are chosen by the intruder.

Theorem 1. The matrix corresponding to Constraints (4)–(7) of the intruder’s problem is totally unimodular.

Proof. To show that $A$ is totally unimodular, we use the following property. A matrix is totally unimodular if: (1) each column contains at most two nonzero elements; and (2) there is a subset $R$ of the rows such that: (2a) if a column has two non-zero elements with the same sign, one of these elements is in $K$ and the other not or; (2b) if the two non-zero elements have opposite signs, then they either both contained in $R$ or both not contained in $R$ .¹⁸

For each combination of $ijt$ , $i, j \in C$ , $t \geq 0$ , there is a column in $A$ . Consider the submatrix $\tilde{A}$ of $A$ , which consists of the rows corresponding to Constraint (4). We first show that $\tilde{A}$ is totally unimodular. For the first rows representing Constraint (4), each combination of $ijt$ , $i, j \in C$ and $t$ appears at most once on the lefthand side and one time on the righthand side. So there are at most two non-zero elements in each column; and if there are exactly two, they have opposite signs. Therefore, $\tilde{A}$ is totally unimodular.

Now consider $\hat{A}$ consisting of $\tilde{A}$ and one additional row representing Constraint (5). Only columns representing $i = 0$ are contained in these constraints. Note that these columns have at most one non-zero element from Constraint (4) with positive sign. Now, at most one non-zero element is also added with positive sign. By choosing the last row as $R$ , the conditions for total unimodularity are still satisfied.

To prove that $A$ is totally unimodular, we use the following property. Total unimodularity is preserved under the following operation: adding a row or column with at most one non-zero entry. This is exactly what is done by adding Constraint (6) to $\hat{A}$ . So, it follows that $A$ , representing Constraints (4)–(6), is totally unimodular, which proves our theorem.

Complete integer linear program

From Theorem 1, we know that relaxing the integer constraints of $x_{ijt}^{I}$ still gives an integer solution. Therefore, we can take the dual of the relaxed intruder’s problem to reformulate the maxmin formulation. By replacing the intruder’s problem of the maxmin formulation with the dual, the maxmin formulation can be rewritten as a single maximization problem. The agent’s strategy can then be found by solving the following integer linear program (ILP), where Equations (8), (13)–(16), (19) correspond to the dual formulation:

max_{y, x^{F}, x^{H}} y^{(2)} + \sum_{i, j, t} y_{ijt}^{(3)} B_{ijt}^{I}

(8)

s . t . \sum_{i} x_{mit}^{F} = 1, m = 1, . ., N^{F}, t = 0, . . ., T,

(9)

x_{mjt}^{F} \leq (1 - x_{mit'}^{F}) + B_{mij}^{F}, i, j \in C, t' = t - 1, t = 1, . . ., T,

(10)

\sum_{j} x_{mnijt}^{H} = x_{mjt}^{F}, m = 1, . ., N^{F}, n = 1, . ., N_{m}^{H}, i \in C, t = 0, . . ., T,

(11)

\begin{matrix} d_{it} = \sum_{j, m} D_{ij}^{F} x_{mjt}^{F} + \sum_{j, m, n, k} D_{ijk}^{H} x_{mnjkt}^{H}, i \in C, t = 0, . . ., T, \end{matrix}

(12)

\begin{matrix} y_{jt}^{(1)} - y_{it'}^{(1)} + y_{ijt}^{(3)} \leq d_{jt}, i, j \in C, t = 1, . . ., T - 1, t' = t - 1, \end{matrix}

(13)

y_{jt}^{(1)} + y_{ijt}^{(3)} \leq d_{jt}, i, j \in C, t = 1,

(14)

- y_{it'}^{(1)} + y_{ijt}^{(3)} \leq d_{jt}, i, j \in C, t = T, t' = t - 1,

(15)

y_{jt}^{(1)} + y^{(2)} + y_{ijt}^{(3)} \leq d_{jt}, i = 0, j \in C_{s}, t = 0,

(16)

x_{mit}^{F} \in {0, 1}, m = 1, . . . N^{F}, i \in C, t = 0, . . ., T,

(17)

x_{mnijt}^{H} \geq 0, m = 1, . . . N^{H}, i \in C, t = 0, . . ., T,

(18)

y_{ijt}^{(3)} \leq 0, i \in C, t \geq 0 .

(19)

Theorem 2. Solving (8)–(19) to optimality is NP-hard.

Proof. In order to show that the problem is NP-hard we give a reduction from the set-covering problem. The decision problem of set covering is NP-hard and described by the following. Given a universe $U = {1, . . ., n}$ , a set of sets $S$ such that for each $S_{i} \in S$ holds that $S_{i} \subset U$ and $⋃_{i = 1}^{| S |} S_{i} = U$ , and an integer $k$ , does there exist a subset of $S$ with at most $k$ elements such that the universe is covered by the union of this subset? We show that each instance of the set-covering problem with universe size $n$ , sets $S$ and integer $k$ can be reduced to an instance of the ILP used to found a strategy for the agent. This proves that finding an optimal strategy for the agent is NP-hard.

The ILP instance is constructed as follows. Let $N^{F} = 1$ and $N^{H} = 0$ . The game is played on a network of $nk + | S | + 1$ cells, $C = {1, . ., nk, nk + 1, . . ., nk + | S |, nk + | S | + 1}$ , over a time period $k$ . The HVU is always at the same target cell, so $C_{T} (t) = nk + | S |$ , $t = 0, . . ., T$ . For each element $i$ , $i = 1, . . ., n$ from the universe there is a path from a start point $(i - 1) k + 1$ to the target cell $nk + | S |$ . For example, for $i = 1$ , there is a path $1, 2, . . ., k, nk + | S |$ . $B^{I}$ is constructed according to this, so $B_{ijt}^{I}$ equals $1$ if $j = i + 1$ , and $0$ otherwise. Additionally, there is a cell $nk + i$ corresponding to each element $i$ , $i = 1, . . ., | S |$ from the set $S$ and all these cells are connected for the frigates, so $B_{ij}^{F} = 1$ for all $i, j = nk + 1, . . ., nk + | S |$ . Finally, construct $D^{F}$ in the following way: for each $j \in nk + 1, . . ., nk + | S |$ corresponding to a set $S_{j}$ let $D_{ij}^{F}$ equal $1$ if $i$ is a cell in the path corresponding to an element from the universe that is also contained in $S_{i}$ , and $0$ otherwise.

Solving this instance of the ILP with the parameters described above gives a solution for the decision of the set-covering problem. If it results in a solution with a value larger than $0$ , this means that for each path at least once the detection probability was larger than $0$ and thus there exists a set cover with at most $k$ element. If the optimal solution equals $0$ then there is no set cover with $k$ sets.

To overcome the complexity of the ILP and to speed up the solving process, we use a branch and price approach. The branch and price algorithm is a combination of column generation and branch and bound, where the relaxation of the ILP is solved first using column generation, and then branch and bound is applied to create integer solutions.¹⁹ To be able to apply column generation, we introduce fixed routes for the frigate. The variables $x^{F}$ that describe the movement of the frigate in each time interval are replaced by a set of fixed routes that considers the frigate’s routes at once. Let $S$ be the set of the frigate’s routes. A route $s$ is given by the parameters ${\tilde{x}}_{mits}^{F}$ similar to the variables $x_{mit}^{F}$ , such that ${\tilde{x}}_{mits}^{F}$ equals $1$ if in route $s$ frigate $f$ is in cell $i$ during $t$ , and zero otherwise. To construct the ILP with routes, Constraints (9), (10), and (17) are replaced by:

\begin{matrix} x_{mit}^{F} = \sum_{s} q_{s} {\tilde{x}}_{mits}^{F}, i, j \in C, t = 0, . . ., T, \\ \sum_{s} q_{s} = 1, \\ q_{s} \in {0, 1}, s \in S . \end{matrix}

If $S$ is the set of all routes, this ILP finds the agent’s optimal strategy. Since the number of routes is exponential in the number of cells, we approximate the optimal solution using branch and price. Computational results are given in the Results section.

3. Sequential game approach

In the previous section, we assumed that the frigate’s route is known completely to the intruder at the beginning of the game. In this section we consider the case where the frigate’s position is only known at the beginning of each time step. This game can be modeled as a sequential game, where the intruder decides on his next move at the beginning of each time interval. Since the agent does not get any information about the intruder’s action during the game, he can decide on a complete strategy at the beginning of the game. The intruder’s strategy depends on the movement of the frigate. Therefore, the variable $x^{I}$ depends on the position of the frigate. For this model, we assume that there is only one frigate, but the model can be easily extended in a similar way for multiple frigates.

The agent’s strategy consists of the route for the frigates and the allocation of the helicopters. In contrast to the approach discussed in the previous section, the agent is allowed to randomize over the routes of the frigates. Similar to the column generation method described in the previous section, the agent can choose a route for the frigates out of the set of all possible routes $S$ , where ${\tilde{x}}_{mits}^{F}$ equals $1$ if in route $s$ frigate $m$ is in cell $i$ during $t$ , and $0$ otherwise. The set $S$ and values of ${\tilde{x}}_{mits}^{F}$ are given. Additionally, we introduce for each $s$ the parameter $o_{kts}$ that equals $1$ if the frigate is observed in $k$ , $k \in C$ , by the intruder during $t$ , and $0$ otherwise. This parameter is used to determine the intruder’s strategy for each $s$ .

Since the helicopter’s allocation and detection probability depends on the frigate’s route, the total detection rate $d_{its}$ and the helicopter’s allocation $x_{mnijts}^{H}$ depend on the route $s$ . The probability that route $s$ is chosen by the agent is given by $q_{s}$ . So, the agent’s decision variables are $q_{s}$ and $x_{mnijts}^{H}$ , which results in a value for $d_{its}$ . Similarly to the previous approach, a linear program can be formulated by first considering the intruder’s problem separately.

3.1 Intruder’s problem

The intruder’s strategy $x^{I}$ depends on the location of the frigate. Let $x_{ijkt}^{I}$ equals $1$ if the intruder moves from $i$ to $j$ after observing the frigate at $k$ during time $t$ . The route that is eventually chosen by the intruder depends on the the route $s$ and is determined by $o_{kts}$ . Let ${\tilde{x}}_{ijts}^{I}$ be the intruder’s route if the agent selects route $s$ . The intruder’s optimization problem with $d_{its}$ and $q_{s}$ is:

\begin{matrix} min_{{\tilde{x}}_{ijts}^{I}, x_{ijkt}^{I}} \sum_{s} q_{s} \sum_{ijt} d_{jts} {\tilde{x}}_{ijts}^{I} \\ s . t . o_{kts} {\tilde{x}}_{ijts}^{I} \leq x_{ijkt}^{I}, & i, j, k \in C, t = 0, . . ., T, s \in S, \\ \sum_{j} x_{ijkt}^{I} = 1, & i, k \in C, t = 0, . . ., T, \\ \sum_{j} {\tilde{x}}_{ijts}^{I} = \sum_{j} {\tilde{x}}_{ijt' s}^{I}, & i \in C, t = 0, . . ., T - 1, \\ t' = t + 1, s \in S, \\ \sum_{j \in C_{S}} {\tilde{x}}_{i jts}^{I} = 1, & i = 0, t = 0, s \in S, \\ {\tilde{x}}_{ijts}^{I} \leq B_{ijt}^{I}, & i, j \in C, t = 0, . . ., T, s \in S, \\ {\tilde{x}}_{ijts}^{I}, x_{ijkt}^{I} \geq 0, & i, j, k \in C, t = 0, . . ., T, s \in S . \end{matrix}

The route that is actually executed is ${\tilde{x}}^{I}$ , and depends on $x^{I}$ , which is the intruder’s strategy. The first constraint ensures that $x^{I}$ corresponds with the choice of ${\tilde{x}}^{I}$ , and the second constraint ensures that for each possible combinations of locations and observations a choice is made. The third, fourth, and fifth constraints ensure that the executed routes also satisfy the flow equations and only possible routes are chosen.

3.2 Complete linear program

By taking the dual of the relaxation of the intruder’s problem, the complete mathematical program to find the agent’s strategy is given by:

\begin{matrix} max_{y, x^{F}, x^{H}} \sum_{s} y_{s}^{(2)} + \sum_{i, j, t, s} y_{ijts}^{(3)} B_{ijt}^{I} + \sum_{ikt} y_{ikt}^{(5)} \\ s . t . \sum_{j} x_{mnijts}^{H} = {\tilde{x}}_{mjts}^{F}, & m = 1, . ., N^{F}, n = 1, . ., N_{m}^{H}, i \in C, t = 0, . . ., T, s \in S, \\ d_{its} = \sum_{j, m} D_{ij}^{F} {\tilde{x}}_{mjts}^{F} + \sum_{j, m, n, k} D_{ijk}^{H} x_{mnjkts}^{H}, & i \in C, t = 0, . . ., T, \\ - \sum_{s} y_{ijkts}^{(4)} + y_{ikt}^{(5)} \leq 0, & i, j, k \in C, t = 0, . . ., T, \\ y_{jts}^{(1)} - y_{it' s}^{(1)} + y_{ijts}^{(3)} + \sum_{k} o_{kts} y_{ijkts}^{(4)} \leq q_{s} d_{jts}, & i, j \in C, t = 1, . . ., T - 1, t' = t - 1, s \in S, \\ y_{jts}^{(1)} + y_{ijts}^{(3)} + \sum_{k} o_{kts} y_{ijkts}^{(4)} \leq q_{s} d_{jts}, & i, j \in C, t = 0, s \in S, \\ - y_{it' s}^{(1)} + y_{ijts}^{(3)} + \sum_{k} o_{kts} y_{ijkts}^{(4)} \leq q_{s} d_{jts}, & i, j \in C, t = T, t' = t - 1, s \in S, \\ y_{jts}^{(1)} + y^{(2)} + y_{ijts}^{(3)} + \sum_{k} o_{kts} y_{ijkts}^{(4)} \leq q_{s} d_{jts}, & i = 0, j \in C_{s}, t = 0, s \in S, \\ \sum_{s} q_{s} = 1, \\ q_{s} \geq 0, & s \in S, \\ x_{mnijt}^{H} \geq 0, & m = 1, . ., N^{F}, n = 1, . ., N_{m}^{H}, i \in C, t = 0, . . ., T, s \in S, \\ y_{ijts}^{(3)}, y_{ijkts}^{(4)}, y_{ikt}^{(5)} \leq 0, & i, j \in {0, C}, t \geq 0, s \in S, \end{matrix}

This mathematical problem can be linearized by multiplying the first two constraints with $q_{s}$ and introducing the new variables $d_{jts}^{q} = q_{s} d_{jts}$ and $x_{mnijts}^{H, q} = q_{s} x_{mnijts}^{H}$ . The first two constraints are then replaced by:

\sum_{j} x_{mnijts}^{H, q} = {\tilde{x}}_{mjts}^{F} q_{s}, m = 1, . ., N^{F}, n = 1, . ., N_{m}^{H}, i \in C, t = 0, . . ., T, s \in S,

d_{its}^{q} = \sum_{j, m} D_{ij}^{F} {\tilde{x}}_{mjts}^{F} q_{s} + \sum_{j, m, n, k} D_{ijk}^{H} x_{mnjkts}^{H, q}, i \in C, t = 0, . . ., T .

In the sequential game approach, the probability that a route is chosen, $q_{s}$ , is allowed to be non-integer. This is in contrast with the approach used in the previous section, because there the complete frigate’s path is assumed to be known by the intruder in advance, while this is not the case for the sequential game approach. Since, however, the number of routes grows exponentially according to the number of cells, this linear program is still difficult to solve. Note that we cannot apply column generation to this LP, since the allocation of the helicopters also depends on the chosen route. Therefore, we use the routes generated by using column generation for complete information games as an input for this LP. Computational results are given in the next section.

4. Results

In this section, we evaluate the models introduced in this paper, and we provide results for several instances. First, we consider the model where the complete path of the frigates is known to the intruder. For small instances, we give the optimal agent’s allocation of the frigate(s) and the helicopter(s), and we describe the intruder’s strategy. Since finding the optimal agent’s strategies is NP-hard, we are unable to solve the model for larger instances efficiently. Therefore, we use a branch and price algorithm to approximate optimal solutions and evaluate the quality of this algorithm. Second, we give results for the second method using the sequential game approach. Finally, we compare the results obtained by our models with the TNO UWT simulation. The computational results were obtained using Gurobipy in Python version 2.7.13 on an Intel^® Core(TM) i7 CPU, 2.4GHz, with 8 GB of RAM.

4.1 Complete path frigate known

In this section, we evaluate different instances for the game with complete information of the frigate’s location.

4.1.1 Small examples for different asset configurations

We test our model on a small instance for different asset configurations. Consider a game on a 5 × 5 grid and a time horizon $T = 12$ . There is an intruder that can start at any bottom cell in the area (see Figures 1 –3), which is also known to the agent. We test the model for three asset configurations: one frigate (Figure 1), two frigates (Figure 2), and one frigate and one helicopter (Figure 3). The frigate is twice as fast as the intruder, meaning that the frigate can move one step per time interval, and the intruder can only move one step per two time intervals. The frigate has a detection probability of $0.75$ if the intruder and frigate are located at the same cell. The helicopter is able to move two steps from the frigate and has a detection probability of $0.5$ if the helicopter and intruder are in the same cell. The optimal solutions are displayed in Figures 1 –3 in the following way. Each subfigure gives the allocations of frigates and helicopters during one time interval. The letter $F$ gives the position of the frigate, and the gray circles give the helicopter’s allocation. The larger the circle, the higher the probability that the helicopter is allocated to that cell. Given the frigate’s and the helicopter’s allocation by the agent, an optimal strategy for the intruder can be calculated. This route is given by the letter $I$ . Note that the intruder always stays at least two time steps at the same node, since the intruder is twice as slow as the frigate. In the previous sections, we have used detection rates in order to make it easier to add the rates for different cells and time windows. In this section, these rates are translated to equivalent detection probabilities. The detection probabilities and running times can be found in Table 1.

Figure 1.

One frigate,0 helicopters.

Figure 2.

Two frigates,0 helicopters.

Figure 3.

One frigate,1 helicopter.

Table 1.

Results for different asset configurations.

Instance	Detection probability	Running time(s)
1 frigate	0.68	56
2 frigates	0.95	574
1 frigate, 1 helicopter	0.93	33

One can see in Figures 1 and 2 that the frigate starts in or near to one of the possible start locations of the intruder and then moves towards the HVU while scanning a large number of cells. Since the intruder can only start at one of the lower cells, it is not possible for the intruder to already attack the HVU at the beginning. Therefore, the agent can use this time to actively search for the intruder; and since the frigate is faster than the intruder, the frigate is able to move towards the HVU before it can be reached by the intruder. As can be expected, two frigates will have a higher detection probability and are able to cover both one side of the area, as can be seen in Figure 2. Also, when an additional helicopter can be deployed (Figure 3), the detection probability will increase. This increase is, however, slightly smaller than when an additional frigate is used, since the frigate is more flexible and has a higher detection probability.

4.1.2 Realistic sized example

We now investigate a larger instance of the ASW model to illustrate a strategy for a moving target. Consider a grid of 7 × 10 with a HVU that is moving over a time window of $16$ (see Figure 4). The detection probability of the frigate is $0.5$ if the intruder is in the same cell. The helicopter can be located two steps from the frigate and observes the intruder with a probability of $0.5$ . The possible start locations of the intruder are given by an × in the first subfigure of Figure 4. The agent’s optimal strategy is displayed in Figure 4, and this results in a total detection probability of $0.61$ . Again, the frigate and the helicopter first search the area where the intruder could be and thereafter move in the direction of the HVU. We will use this example to compare our method with the UWT simulation at the end of this section.

Figure 4.

Large instance: 1 frigates,1 helicopter

As the problem is NP-hard (Theorem 2), the running time increases exponentially as the number of cells increases. To solve the instance on a 7 × 10 grid, the running time is more than two weeks. We use a branch and price algorithm to speed up the solving time. With this algorithm, we are able to find an approximate solution with an error of 14.1% within a couple of hours. We have tested the branch and price algorithm for smaller instances, and from these tests it follows that the approximate solutions is always within 15% of the optimal solution and, for several instances, the optimal solution is found. Due, however, to the number of routes and the fact that only one of these routes is used in an optimal solution, it is not possible to always guarantee a high solution quality. For the small examples with different asset configurations considered above, an approximate solution within 14.2%, 3.2%, and 3.1%, respectively, of the optimal solution is found by the branch and price algorithm.

4.2 Sequential game approach

In the second part of this paper, we deviated from the assumption that the intruder has complete information about the position of the frigate during the complete time interval. Therefore, the agent is allowed to randomize over the different frigate’s routes and will be less predictable, resulting in a higher payoff. Since the number of routes exponentially rises following the number of cells, however, the number of variables is large and the LP to find optimal agent’s solutions cannot be solved efficiently. Therefore, we only optimize over a limited set of routes, and we use the column generation approach to determine these routes. Even with a limited number of routes, however, the number of variables is very high because, for each route, we need separate variables for the helicopter’s allocation, detection probability, and the corresponding intruder’s routes.

First, we give a small example to show what the impact of this sequential approach can be. Thereafter, we compare the sequential game approach to the instances with complete information.

Example 2. Small sequential game. Consider a game on a 3 × 1 grid with the target at cell 2. The possible start cells of the intruder are 1 and 3, from where he can immediately move to the target cell. The agent has a single frigate available with a detection probability of 1 if the frigate is at the intruder’s location and 0 otherwise. All possible strategies for the agent are starting at cells 1, 2, or 3. When the complete location of the frigate is known in advance by the intruder, the intruder can always start at a cell where the agent is not present and the total detection probability equals 0. If, however, the frigate’s location is not known to the intruder in advance, the optimal strategy of the agent is patrolling cell 1 with probability 0.5 and patrolling cell 3 with probability 0.5, resulting in a total detection probability of 0.5.

In the example above, we described an extreme case where the sequential game approach will lead to a significantly higher detection probability than the game in which complete information of the frigate’s location is considered. We now investigate the impact on a more realistically sized instance.

Consider the small instance on a 5 × 5 grid. We test the same asset configurations, but with the sequential game approach. We use the first 20 routes that are generated using column generation for the model with complete information about the frigate’s location.

As these results show, the agent’s detection probability increases a lot for the first instance, since the agent can also randomize over the frigate’s position and is therefore less predictable. Since, however, the number of variables is very large as the number of cells increase, the running time increases quickly and we are not able to solve this model for larger instances (see Table 2).

Table 2.

Impact sequential approach.

Instance	Game value	Running time(s)
1 frigate	0.79	1077
2 frigates	0.96	3472
1 frigate, 1 helicopter	0.95	2201

4.3 Simulation approach

The instance with one frigate and one helicopter was als osimulated in the UWT, to find out whether the optimal path that was found using the game approach has a high effectiveness when used in the simulation model

The UWT is a simulation model developed by TNO.¹⁷ It can be used to develop and evaluate operational tactics and future concepts for underwater operations. In the model, platforms that are part of an underwater operation, such as frigates, helicopters, submarines, mines, torpedoes, and unmanned systems are modeled as agents. They are equipped with sensors, and possibly with separate weapons.

The behavior of the platforms (agent) is modeled in two ways. First, they follow a predefined pattern, e..g., defined by way-points, through the modeled operational area. When an agent detects an opponent, it can react by attacking or avoiding this opponent, or ignoring it. Agents of the same side can coordinate their actions. These reactions are scripted (e.g., reduce speed to $v$ when a helicopter sonar is detected within $R$ nautical miles).

For the detection of a contact, several levels of detail exist. The simplest model uses a cookie-cutter sensor with fixed detection ranges. The sensor detects a contact as soon as it is within range. The most advanced model calculates acoustic propagation through the environment and translates this into a probability of detection. Several intermediate levels of detail are also possible. For the comparison in this paper, it is assumed that a sensor can detect a contact with probability $p$ when it is within the sensor’s range and not if it is outside the sensor’s range.

Typically, the way-points that are followed depend on the tactic that is chosen. Usually, a set of tactics is defined in close cooperation with operational experts, taking into account operational requirements and limitations (e..g., the tactic is not too complicated and can be carried out during an operation). The effectiveness of each tactic is determined with the simulation. The main outcome of a simulation run is whether the defense against the incoming submarine was successful or not. Monte Carlo simulation provides an estimation of the probability of success. The simulation model also produces other results like the ranges at which platforms were detected and by which agents, and the number of possibilities of launching an attack.

It follows that the UWT does not automatically determine the optimal tactic. In practice, the definition of different tactics is the task of the analyst. Using this input, simulations can be executed that will help to determine which of these tactics is the most effective. This analysis may lead to the development of a new set of tactics or advice about the preferred tactic.

For the intruder, two types of behavior are available: a kamikaze-like approach in which the submarine chooses the shortest path towards the HVU, and a cautious approach in which the submarine tries to avoid detection. It must be noted that both types of behavior do not correspond to the optimal path found in the game theoretic approach. Due to time constraints, however, it was decided to use both types of existing behavior in the Monte Carlo simulation.

Detection of contacts in the UWT is modeled by the transmission of sonar pings. Each ping can lead to a detection. The probability of a detection in the UWT depends on the distance between sensor and contact. The grid cells are not modeled explicitly in the UWT, but the speed of the HVU, frigates, and intruders are modeled in such a way that they correspond with the game model. Moreover, the detection rates for the frigate and helicopter are modeled such that they correspond with the game theoretic approach. Since, however, we use a square grid for our model and a detection radius is used in the simulation, they are not exactly the same.

In particular, the behavior of the intruder and the way in which the detection process is modeled will cause a difference in outcome between the game theoretic approach and the simulation with the UWT. Furthermore, tactics are UWT input instead of output. Therefore, the optimal search pattern from the game theoretic models is compared to three other tactics (see also Figure 5):

Frigate in front of the HVU covers the righthand part of the area in front of the HVU; helicopter covers the lefthand part;

Frigate moving from left to right and back in front of the HVU. Helicopter dipping at positions near the frigate;

Frigate in front of the HVU covers the righthand path in front of the HVU; helicopter covers the lefthand part of the area before the HVU.

Figure 5.

Different agent tactics in the UWT simulation

4.4 Comparison of approaches

For the simulation, we used 55 different intruder starting positions to account for the uncertainty in where the submarine starts its attack. For each starting point, we simulated 25 runs. The average agent’s detection probability for the two intruder tactics and four agent’s tactics are given in Table 3.

Table 3.

Impact sequential approach.

Tactic	Kamikaze approach	Cautious approach
Optimal agent’s game tactic	0.58	0.59
Tactic 1	0.43	0.50
Tactic 2	0.44	0.49
Tactic 3	0.47	0.68

Because of the modeling aspects mentioned above, it is likely that the performance determined by the simulation differs from the performance of the optimal tactic as determined by the sequential game approach. Therefore, it is more useful to look at the difference in performance between the selected tactics. It can be observed that the optimal tactic of the game approach performs in most cases better than the alternative tactics 1 and 2. Tactic 3 performs slightly better for the cautious intruder.

An advantage of using the game theory approach is that the analyst does not have to define tactics in advance. Regarding the approach for selecting tactics, it is very likely that the analyst limits himself to tactics that are already well-known or widely accepted. The game theory approach can come up with unconventional alternatives that might be difficult to carry out in practice, but may lead to innovating ideas about new tactics. For example, the optimal tactic from the game theory approach shows that it is advantageous to deploy the frigate andthe helicopter far upfront if it is known that the submarine did not have time to approach the HVU. This enables early detection and warning. Later in the scenario, the submarine could have come close to the HVU, and the frigate and helicopter need to be closer to the HVU to cover the area around the HVU to prevent an attack on the HVU.

5. Conclusions

In this paper, we have introduced a new model for the protection of large areas against enemy submarines. In this model, we address several limitations of current models that are proposed for anti-submarine warfare operations. By introducing a time aspect, we extend the model of Brown et al.⁹ and Monsuur et al.¹² such that time-dependent strategies and moving HVUs can also be modeled. Moreover, by using a game theoretic approach, our model is able to model an intelligent intruder.

For modeling an ASW transit operation with time-dependent strategies, we have proposed two different approaches: one with complete information about the frigate’s location for the complete time interval, and one sequential game approach where the intruder only becomes aware of the frigate’s location during each time interval. The sequential game approach gives higher solution quality for the agent, since the agent has the possibility to randomize over frigate routes. Since, however, for every possible route a helicopter’s strategy has to be specified, the number of variables is very large and we are unable to solve realistically sized instances. Future research include investigating methods to solve large instances efficiently.

For the approach with complete information about the frigate’s location, we are able to solve larger instances and compare these with the UWT simulation. It should be noted that since, in the UWT approach, more parameters and features can be modeled than with our game models, the exact outcomes are difficult to compare. We can, however, compare the relative performance of the agent’s strategies for both models. Furthermore, the running time of our model increases according to the number of cells. We have used a branch and price algorithm to overcome the complexity, which generates solutions within 15% of the optimal solution. For future research, it would be interesting to improve the approximation algorithms, for example by using cutting planes. In the current approach we allow for all possible routes, but routes that will never be used, for example when they will not cross the intruder’s path, can be excluded in advance.

An advantage of our game approach compared with the UWT is that we do not have to specify the agent’s tactics in advance and can model the intruder as an intelligent adversary. Therefore, our game approach is not limited to the usual tactics and can generate unconventional ones. This is of added value when evaluating new tactics, as it triggers military analysts to consider other modus operandi. Moreover, simulating the optimal strategy from the game theoretic approach with complete information in the UWT shows that the detection probability is higher than when standard tactics are used. With our game approach we are therefore able to generate agents’ routes that may serve as a starting point for the development of new tactics and their further evaluation using simulation.

Footnotes

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

ORCID iD

Corine M Laan

Author biographies

Corine M. Laan is a researcher at the Urban Analytics group at the Amsterdam University of Applied Sciences. She received a MSc degree in Applied Mathematics from the University of Twente. Thereafter, she conducted her PhD research in game theory and security at the Stochastic Operations Research group of the University of Twente, TNO, and the Netherlands Defense Academy.

Ana Isabel Barros is a principal scientist at TNO and a fellow at the University of Amsterdam, Institute for Advanced Study (IAS). After completing her Masters degree on operational research and statistics, she obtained a PhD degree at the Erasmus University Rotterdam in 1995. Her PhD thesis Discrete and fractional programming techniques for location models received the INFORMS Best Dissertation on Location Analysis of 1995 award. In the last twenty years she has been actively involved in international defense, security, and logistic projects. Her research interests are in applications of military and security operations research, intelligence analysis, and complexity theory.

Richard J Boucherie is full professor of stochastic operations research in the Department of Applied Mathematics of the University of Twente, co-founder and co-chair of the University of Twente Center for Healthcare Operations Improvement and Research (CHOIR) in the area of healthcare logistics, and co-founder of the spin-off company Rhythm, which carries out actual implementations of healthcare logistics solutions in healthcare organizations. Richard received MSc degrees in Mathematics (stochastic operations research) and theoretical physics (statistical physics) from the Universiteit Leiden, and received the PhD degree in econometrics from the Vrije Universiteit, Amsterdam. His research interests are in queuing theory, Petri nets, and Markov decision theory, with application areas including wireless and sensor networks, road traffic, network intrusion detection and prevention, and healthcare operations research.

Herman Monsuur is full professor of military operations research at the Faculty of Military Sciences of the Netherlands Defense Academy. He is also head of the expertise center for military operations research at the Defense Academy. His research interests are in network science, game theory, adversarial risk management for security, and strategic defense analysis.

Wouter Noordkamp is a research scientist at TNO. He graduated in applied mathematics at the University of Twente in Enschede in 1999. Since then he has been working at the Operational Analysis department of TNO. His main activities are building quantitative models and using them in support of the Royal Netherlands Navy in the fields of acquiring new materiel and improving the deployment of new systems, mainly in the area of anti-submarine warfare.

References

Owen

. Anti-submarine warfare: An illustrated history. Barnsley: Seaforth Publishing, 2007.

Maurer

. The struggle for sea power: Lessons from the Great War. Orbis 2018; 62: 184–203.

Basilico

Gatti

Amigoni

. Leader–follower strategies for robotic patrolling in environments with arbitrary topologies. In: Proceedings of the 8th international conference on autonomous agents and multiagent systems—Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, Budapest, 2009, pp. 57–64. Richmond: International Foundation for Autonomous Agents and Multiagent Systems.

Gal

. Search games with mobile and immobile hider. SIAM J Control Optim 1979; 17: 99–122.

Hohzaki

. Search games: Literature and survey. J Oper Res Soc Japan 2016; 59: 1–34.

Lin

Atkinson

Glazebrook

. Optimal patrol to uncover threats in time when detection is imperfect. Nav Res Log 2014; 61: 557–576.

Neuts

. A multistage search game. SIAM J Appl Math 1963; 11: 502–507.

Thomas

Washburn

. Dynamic search games. Oper Res 1991; 39: 415–422.

Brown

Kline

Thomas

, et al. A game-theoretic model for defense of an oceanic bastion against submarines. Mil Oper Res 2011; 16: 25–40.

10.

Hew

Yiap

. Optimally randomized patrolling of chokepoints for theatre antisubmarine warfare. Mil Oper Res 2018; 23: 49–56.

11.

Mishra

Sidoti

, et al. Context-aware decision support for anti-submarine warfare mission planning within a dynamic environment. IEEE Trans Syst Man Cybern Syst 2017; 99: 1–18.

12.

Monsuur

Janssen

Jutte

. A game-theoretic attacker–defender model for a sea base: Optimal deployment at the maritime battleground. In: van der Wal

POA

(ed) NL ARMS – Optimal Deployment of Military Systems: Technologies for Military Missions in the Next Decade. Den Haag: Asser Press, 2014.

13.

Regnier

Singham

. Targeting an asymmetric maritime threat: Workshop report. Technical report, Monterey, California. Naval Postgraduate School, 2013.

14.

Thomas

. Tri-level optimization for anti-submarine warfare mission planning. PhD Thesis, Naval Postgraduate School, Monterey, 2008.

15.

Seo

Song

Kwon

, et al. Measurement of effectiveness for an anti-torpedo combat system using a discrete event systems speciﬁcation-based underwater warfare simulator. J Def Model Simul 2011; 8: 157–171.

16.

Robinson

. Simulation in support of military operations, tactics, and planning: ODIN: An underwater warfare simulation environment. In: Peters

Smith

Medeiros

Rohrer

(Eds) Winter simulation conference in Arlington, 2001, pp. 672–679. Piscataway, NJ: IEEE Computer Society.

17.

Keus

Benders

Fitski

, et al. Multi-platform operations in the Underwater Warfare Testbed (UWT). In: UDT Europe 2009 - Conference Proceedings Undersea Defence Technology, Cannes, 9–11 June 2009. Kent: Nexus Media.

18.

Dantzig

Dufﬁn

Fan

, et al. An extension of a theorem of Dantzig’s. In: Linear inequalities and related systems. Volume 38. Princeton, NJ: Princeton University Press, 1956.

19.

Barnhart

Johnson

Nemhauser

, et al. Branch-and-price: Column generation for solving huge integer programs. Oper Res 1998; 46: 316–329.

Optimal deployment for anti-submarine operations with time-dependent strategies

Abstract

Keywords

1. Introduction

2. Complete information about the frigate’s location

2.1 Protection of a static HVU

2.2 Dynamic game with time-dependent strategies

2.2.1 Model description

2.2.2 Construction of the integer linear program

Intruder’s program

Complete integer linear program

3. Sequential game approach

3.1 Intruder’s problem

3.2 Complete linear program

4. Results

4.1 Complete path frigate known

4.1.1 Small examples for different asset configurations

4.1.2 Realistic sized example

4.2 Sequential game approach

4.3 Simulation approach

4.4 Comparison of approaches

5. Conclusions

Footnotes

Funding

ORCID iD

Author biographies

References