Efficient Algorithms for Boundary Defense with Heterogeneous Defenders

The DP algorithm builds a recursion formula on the last attacks intercepted by the defenders. Without loss of generality, we assume that each attack is only intercepted by one defender. For a DP state $a_{1},\dots,a_{k}$ where $a_{i}$ is the last attack defender $i$ intercepts, let $T[a_{1}]\dots[a_{k}]$ store the maximum number of attacks that can be intercepted when the $i^{th}$ defender’s last intercepted attack events is $a_{i}$ $(i\in[1,k])$, and denote $a_{ma}$ as the maximum of $a_{1},\dots,a_{k}$. Base on which attack the $ma^{th}$ defender intercepts before intercepting attack $a_{ma}$, we can write the DP recursion formula as follows.

Pseudo-code in Alg. 1 provides a sketch of a possible implementation of the dynamic programming algorithm. Effectively implemented, the time complexity of running Alg. 1 is $O((n+1)^{k+1})$, which is polynomial when $k$, the number of defenders, is fixed.

The algorithm presented here is a slight modification of the DP algorithm in [1] with two subtle differences. First, we enforce that an attack event can only be handled by one defender. Second, we explicitly use the initial locations of the defenders in the algorithm, which is essential for handling the finite horizon extension.

It is not difficult to see that BDHD can also be seen as a network flow problem by treating each attack event as a node and the reachability between each pair of attack events for each defender as the edges in the graph.

Specifically, there are $n$ nodes in the graph, representing the $n$ attack events. There are also $O(n^{2}k)$ connections between nodes inside the graph. If defender $j$ can reach attack event $i^{\prime}$ from $i$, there is an connection $edge[i][i^{\prime}][j]$ between node $i$ and $i^{\prime}$. Also, we use a binary variable $intercept[i]$ to denote whether attack event $i$ is successfully intercepted. These give rise to the following integer linear programming (ILP) formulation of the problem.

Eq. (4) sets the criteria of an attack $i$ being intercepted as at least one defender to come into the node $i$, which means intercept attack $i$. Eq. (5) sets the defender flow conservation rule that the number of type $j$ defender exiting node $i$ must be larger than or equal to the number of type $j$ defender coming to node $i$. Eq. (6) sets the initial constraints on the number of each type of defender used (coming out from node 0).

Denote $M$ as the number of connections in the graph, clearly $M<n^{2}k$. This integer linear programming formulation uses $M+n$ variables, and $nk+n$ constraints.

We now develop a heuristic search method using the dynamic programming algorithm discussed in Alg. 1 applied on two defenders. The DP algorithm that computes the optimal solution for two defenders is used as a local improvement primitive for the local search heuristic algorithm.

We call the resulting algorithm exhaustive defender pairing (EDP). In each iteration, EDP pick two defenders, and the attack events the two defenders have intercepted and the attack events that have not been intercepted by any defender. Then, EDP uses the DP algorithm in Alg. 1 to increase the number of attack events intercepted by the two defenders selected. The complete algorithm is sketched in Alg. 2.

We can try different defender pairing orders and choose the best one. In our EDP implementation, we choose to run line 3 of Alg. 2 in 3 different iteration ordering of $u,v$. Alg. 2’s running time is $O(k^{2}n^{3})$ as we try $O(k^{2})$ pairs of defenders, and each run of the DP algorithm takes $O(n^{3})$.

For Problem II.2 where the attacks $\big{\langle}loc_{i},t_{i}\big{\rangle}_{i=1}^{\infty}$ may be infinite, and the look-ahead horizon is finite, not all attacks are revealed at once. As such, previous methods cannot be directly applied. As the future attack sequence cannot be foreseen, defenders need to react to information (e.g., the attack events in the next $T$ time interval) obtained so far.

Towards addressing the problem, a greedy replanning approach can be applied. Whenever an attack event is observed, the defender team replans the capture sequence given the new attacks added to the attack queue. This gives rise to an online algorithm sketched in Alg. 3.

This section provides experimental study and comparisons between the three methods described in the paper: dynamic programming (DP), integer linear programming (ILP), and exhaustive defender pairing (EDP) algorithms.

To test and compare the general performance of these methods, we set the defending task on $S^{1}$ (i.e., a circular boundary with a distance of $2\pi$) with the attack sequence’s coming rate $\lambda$ (used in the Poisson process) proportional to $k$, the number of defenders. The results on computational time and interception rate are given in Figs. 3 and 4.

For 2 to 7 defenders, in Fig. 3, we show the computation time of running the algorithms. Each data point is an average of 20 runs. We remind the readers that both DP and ILP guarantee to produce an optimal solution (if they can finish). For the two-defender scenario, which is the main focus of [1], DP is the most efficient. However, DP only fully scales for $k=2,3$ defenders, and start to peter out for $k=4$ defenders due to memory limit (so its running time is not shown for $k>4$). As can be observed, ILP demonstrates much better scalability in comparison to DP, but fails to find a solution for $k>5$ defenders.

As expected, exhaustive defender pairing (EDP) has the least time cost for $k\geq 3$. Fig. 4 shows the corresponding solution qualities of these methods. We observe that, while EDP does not guarantee solution optimality, it generated solutions that are virtually the same as the exact methods (DP and ILP). Through these empirical evaluations, EDP demonstrates superior scalability with negligible solution optimality loss.

The number of defenders appears in the index term of the time complexity of the DP algorithm, which limits it from scaling up the number of defenders. Hence, we compare the performance of ILP and the local search algorithm when pushing the number of defenders up to dozens. With the main goal being the evaluation of optimality, we limit the attack events to $200$ so that the ILP method can return the optimal solution in $60$ seconds. At the same time, to make the problem more challenging, $\lambda$ is increased to $2\cdot k$ from $k$ so that not all attacks can be intercepted. Fig. 5 and Fig.  6 show the corresponding computation time and interception rate, each data point is the average of 20 runs.

As can be observed, EDP, due to its quadratic dependence on the number of defenders, consistently and significantly outperforms the ILP method in terms of computation time. At the same time, it yields virtually the same level of optimality as ILP, which guarantees that the result is optimal.

To explore the impact of the diversity of defender speeds on interception rate, we focus on a $5$-defender setting and to make the difference more visible, $\lambda$ is set to be $5\cdot k=25$ so that the interception rate no more than 80%. Here, the defender speed diversity is tested by setting the $v_{min}$ as 1, and $v_{max}$ from 1 (uniform speed) to 10, and then normalizing the defender speed to make them sum up to $15$ (i.e., with an average of $3.0$). Each data point is based on 100 runs. The result is summarized in Fig. 7, from which we can observe that uniform speed $v_{max}=1$ has the least interception rate, while the interception rate gets into its maximum after $v_{max}:v_{min}=3$ or $4$. This suggests that heterogeneity can significantly enhance the interception rate, warrant the effort going into the current study (and previous study of heterogeneous defender setups). At the same time, as heterogeneity continues to increase, the effect becomes negligible. This also follows intuition: when the capability of the defenders varies too much, they can no longer effectively collaboratively intercept attacks.

With the increase of $\lambda$ in the Poisson process for the attack sequence, there will be fewer attacks intercepted, and more defenders will be required to reach the same interception rate. In this regard, we test the interception rate computed using EDP for $1$ to $20$ defenders and different $\lambda$ from $1.0$ to $60.0$. The number of attacks is set to be $400$, and each data point represents an average of 20 runs. Fig. 8 shows the resulting capture rate with respect to the attack rate $\lambda$ as a heat map for a different number of defenders $k$, which, unsurprisingly, suggests a gradual change as one might expect. Nevertheless, such a graph can serve as a quick reference for selecting an appropriate number defenders given an expected attack rate.

EDP applies to BDHD with arbitrary boundary topology; we evaluated EDP on $I=[0,1]$ (unit interval), $S^{1}$ (circle with a total circumference shrinked to $1$), $I^{2}$ (unit square), and $S^{2}$ (sphere with surface area of $1$) (see Fig. 9) with $k=5$, $v_{max}=5$ and $\lambda$ from 1 to 200. The results are shown in Fig. 10, where each data point is the average of 20 runs. We observe that $I$ and $S^{1}$ have similar difficulty to defend, with $I$ being a bit more challenging due to having boundaries. The same is observed for $I^{2}$ and $S^{2}$.

Alg. 3 describes an online EDP algorithm for handling the finite horizon version of the problem where the defenders only have the information about attacks in the next $T$ time frame. Here, we present some simulation studies using the 5-defender and 400 attacks setup on an $S^{1}$ boundary with $v_{max}=5$. Fig. 11 gives the interception rate with respect to varying defender horizons. Each data point is an average of 20 runs. The interception rate converges to around $1$ with a fairly short horizon, indicating that a long look-ahead horizon may not be necessary for effectively intercepting attacks.

Lastly, in Fig. 12, we provide the interception trajectories of a typical run for ILP, EDP, and online EDP.