Coordinated Defense Allocation in Reach-Avoid Scenarios with Efficient Online Optimization

In this subsection, we provide an overview of the current state-of-the-art in single-attack defense coordination and defense allocation, highlighting the prevailing issues and unresolved challenges within each domain.

One approach to single-attack defense coordination involves constructing the HJI solution analytically [24], [25]. Garcia et al. [24] present the derivation of the optimal defense strategy for two defenders against a single attacker in a 3D scenario with a point target set and zero capture radii. Another approach employs mixed pursuit-defense strategies, where some defenders are designated as pursuers focusing on directly capturing the attacker [26], [27]. In [27], it is shown that the attacker is guaranteed capture outside a circular target set within a bounded 2D convex domain for a set of initial joint states. This is achieved by assigning one defender to perform defense, while the remaining defenders implement the area-minimization strategy based on the attacker’s Voronoi cell, as developed in [28, 29].

Recently, a series of geometric-based works by Yan et al. has been proposed for deriving defense coordination strategies [30, 31, 32, 33]. Central to these approaches is the set that characterizes the attacker’s locations which can be safely reached through admissible strategies. This concept was first introduced in [34] as the “safe region” and later reformulated for cooperative pursuit in [35] as the “safe-reachable set”. We adopt the term safe-reachable set to emphasize the combination of safety and reachability. In cases where the capture radii are zero and the maximum speeds of defenders are all greater than that of the attacker, the safe-reachable set reduces to the Apollonius circle/sphere. Building on the Apollonius circle (resp. sphere), an analytical defense strategy is given for a set of initial joint states involving two defenders in a 2D (or 3D) convex domain with a line segment (resp. plane) shaped target set [30] (resp. [32]), ensuring the attacker cannot enter the target set. This defense coordination technique has been extended to accommodate an arbitrary number of defenders in both specific 2D and 3D scenarios [31], [33]. Notably, the approach presented in [33] is capable of handling cases involving non-zero capture radii.

Despite the progress made in single-attack defense coordination strategies, the existing approaches have mainly concentrated on specific cases with particular target sets or scenarios with zero capture radii. As a result, a comprehensive solution for general convex target sets in convex environments and non-zero capture radii remains an open challenge. Moreover, the defense strategies developed thus far are applicable only to a portion of the joint space, which may not adequately address real-world situations in which the attacker deviates from the optimal strategy. These limitations underscore the need for more adaptable defense coordination methods that can be applied to a broader range of scenarios.

In the context of defense allocation, the problem can be reformulated into joint state-dependent ILPs. Distinct from classical multirobot allocation problems [36, 37], the objective function here hinges on the estimated outcomes involving all defenders against a single attacker, which generally suffers from computational burdens when attempting a direct solution. In [38], the authors rely on the HJI method to exclusively examine pairwise interactions between defenders and attackers. While this approach enables polynomial-time solutions through the Ford-Fulkerson algorithm [39] or its improvement, the Hopcroft-Karp algorithm [40], it oversimplifies the problem by reducing the level of cooperation among defenders. The study presented in [41] concentrates on the assignment of performance improvement under the assumption that all attackers can be captured, which restricts the applicability of their approach. By the results of the geometric-based approach to single-attack defense coordination, the ILP in [31] is resolved exclusively at the initial time, with the resulting assignment maintained throughout the entire process. This approach can guarantee the capture of a certain number of attackers, whereas it lacks robustness in response to the dynamic interactions among agents. To overcome this limitation, the approach introduced in [31] is further refined in [33] by approximately solving the ILPs with a polynomial-time method. Nevertheless, this solution entails employing all possible combinations of single-attack defense coordination, which can be time-consuming in practical applications.

From the preceding discussion, it is evident that existing defense allocation methods fail to tackle the time-consuming issue associated with identifying the estimated outcomes of selected pairs of defender coalitions and individual attackers, particularly when the estimated outcomes cannot be readily provided offline. Moreover, when the optimal solution of the ILP remains unattainable due to efficiency constraints, current approaches fall short in offering guidance to enhance cooperative defense performance. Consequently, there is a demand for innovative solutions on defense allocation that balance optimality and computational efficiency.

Our contributions are summarized as fourfold:

1. 1.

   Our defense strategy extends the applicability over previous methods to convex domains that contain a general convex target set in both 2D and 3D spaces, and it accommodates scenarios involving defenders with nonzero capture radii.

2. 2.

   Our single-attack defense coordination algorithm, which is implemented through online convex programming, is designed to yield the maximum defense-winning region. The algorithm is applicable to all joint states, rather than being confined to a limited portion of the joint space as seen in existing strategies. This allows for a higher chance of winning when facing non-optimal attack strategies.

3. 3.

   We propose a defense allocation algorithm that effectively reduces the computational load associated with determining the predicted outcomes of selected defender coalition-attacker pairs. This efficiency is a major advancement, as existing methods often struggle with time-consuming computations that hinder their practical use. Moreover, our algorithm is designed to incrementally improve defense performance, ensuring continual enhancement over time. This is particularly valuable in situations where the optimal allocation is unattainable due to efficiency constraints.

4. 4.

   We provide a comprehensive evaluation of our algorithm through both simulations and real-world physics engine validations in 2D and 3D scenarios. This rigorous testing showcases the superiority of our algorithm in comparison to existing state-of-the-art approaches, demonstrating improvements in both optimality and efficiency.

The remainder of this paper is organized as follows. In Section II, we formulate the problem of cooperative defense in multiplayer reach-avoid games and decompose it into two subproblems: single-attack defense coordination and defense allocation. In Section III, we present a defense strategy for a coalition against a single attacker. Section IV reformulates the defense allocation problem as an ILP and presents a heuristic method to approximate the solution. Finally, Section V presents the simulation results that benchmark the effectiveness of our approach.

We use the following notation throughout the paper. Let $\mathbb{R}^{n}$ be the $n$-dimensional Euclidean space, and $||\cdot||$ be the Euclidean norm. Given a vector $v$, the normalizer $\mathscr{N}(v)$ is defined as $\mathscr{N}(v)=\frac{v}{||v||}$ if $v\neq 0$ and $0$ otherwise. In the scalar case, $\mathscr{N}$ is equivalent to the sign function. The indicator function of a set $S$ is denoted by $\mathbf{1}_{S}(\cdot)$ and defined as $\mathbf{1}_{S}(x)=1$ if $x\in S$ and $0$ otherwise. The cardinality of a set $S$ is denoted by $|S|$. Given a set of vectors $v_{1},\ldots,v_{n}$, $(v_{1},\ldots,v_{n})$ is used to denote the column vector consisting of the entries of $v_{i}$ for $i=1,\ldots,n$ in sequence. The Cartesian product of $N$ copies of a set $S$ is denoted by $S^{N}$.

In the multiplayer reach-avoid game with a single attacker, the binary outcome of an initial joint state is determined by the reach-avoid set [18]. This set comprises joint states from which the attacker can reach the target set without being captured by any of the defenders. By solving an HJI equation numerically, the reach-avoid set can be represented as a sublevel set of the HJI solution [42]. However, the backward computation associated with this method suffers from the curse of dimensionality, hindering its application to multi-agent systems [23]. In contrast, the safe-reachable set seeks to collect the attacker’s reachable locations that remain capture-free given the current joint state [35]. This set can be computed using forward computation, which only concerns the attacker’s position state and does not involve solving for the target set reachability, making it more computationally efficient. We will demonstrate that under our problem settings, the binary outcome of an initial joint state can also be characterized by the safe-reachable set.

A formal definition of the safe-reachable set for a coalition-attacker pair is given below. Consider a coalition $\mathcal{C}$ and an attacker $j$ with dynamics described by (3) and (4), respectively, and denote their joint state as $x^{\mathcal{C}}_{j}=(p^{d}_{i},i\in\mathcal{C};p^{a}_{j})$. In light of (9), the capture-free condition for attacker $j$ can be expressed as follows:

where $s_{i}(p^{d}_{i},p^{a}_{j})=r_{i}-||p^{d}_{i}-p^{a}_{j}||$. To account for the dependence of agent trajectories on their initial states and strategies, we introduce the notations $\chi^{a}_{j}(\cdot;p^{a}_{j}(0),\pi^{a}_{j})$ and $\chi^{d}_{i}(\cdot;p^{d}_{i}(0),\pi^{d}_{i})$, which respectively denote the trajectory of attacker $j$ over time starting from $p^{a}_{j}(0)$ using the attack strategy $\pi^{a}_{j}$, and the trajectory of defender $i$ over time starting from $p^{d}_{i}(0)$ using the defense strategy $\pi^{d}_{i}$.

The SRS offers a predictive way to evaluate the capture-free condition (13) by incorporating the dynamic and input constraints of both opponents. When the SRS is nonempty, it implies that the attacker is currently situated within the SRS, and the capture-free condition is satisfied for the current joint state, as per Definition 1. Moreover, the size of the SRS can be used to anticipate the attacker’s ability to move freely without compromising safety. A larger SRS indicates that the attacker has more options for safe movement, regardless of any defense strategies that may be employed.

Similar to the reach-avoid set, the SRS admits a sublevel set representation. Consider a point $q$ inside the SRS that attacker $j$ can reach at time $\tau$. Simultaneously, defender $i$ can arrive at point $q^{d}_{i}=p^{d}_{i}+v^{d}_{i,\max}\frac{q-p^{d}_{i}}{||q-p^{d}_{i}||}\tau$ using the constant strategy $v^{d}_{i,\max}\frac{q-p^{d}_{i}}{||q-p^{d}_{i}||}$. According to Definition 1, $q$ adheres to the capture-free condition $\max_{i\in\mathcal{C}}s_{i}(q^{d}_{i},q)=\max_{i\in\mathcal{C}}(r_{i}-\bigl{\lvert}||q-p^{d}_{i}||-v^{d}_{i,\max}\tau\bigr{\rvert})\leq 0$. On the other hand, since attacker $j$ can safely reach $q$, the time $\tau$ must fulfill $\tau\in[\tau_{\min},\frac{||q-p^{d}_{i}||}{v^{d}_{i,\max}})$, with $\tau_{\min}=\frac{||q-p^{a}_{j}||}{v^{a}_{j,\max}}$ representing the minimum time for attacker $j$ to reach $q$. This leads to $\max_{i\in\mathcal{C}}(r_{i}-\bigl{\lvert}||q-p^{d}_{i}||-v^{d}_{i,\max}\tau_{\min}\bigr{\rvert})=\max_{i\in\mathcal{C}}(r_{i}+\gamma_{ij}||q-p^{a}_{j}||-||q-p^{d}_{i}||)\leq 0$, which can be rewritten as $\max_{i\in\mathcal{C}}c_{ij}(q,x_{ij})\leq 0$ with

and $x_{ij}=(p^{d}_{i},p^{a}_{j})$. Moreover, satisfying inequality (14) for every $i\in\mathcal{C}$ is sufficient to ensure that $q$ lies within the SRS.

The SRS serves as a generalization of both the Voronoi diagram and Apollonius diagram by accommodating nonzero capture radii. As evident from equation (15), when all the capture radii equal zero, the SRS simplifies to the Voronoi cell if $\gamma_{ij}=1$ and to the Apollonius circle/sphere if $\gamma_{ij}>1$. Unlike the Voronoi diagram and Apollonius diagram, the SRS partitions the space based on the attacker’s capacity to move freely without being captured, factoring in the defenders’ capture radii, as depicted in Fig. 2. This distinctive characteristic of the SRS enables a more realistic representation of the interaction between the attacker and defenders, enhancing defense coordination with unpredictable attacker movements.

Having the SRS concept, we next develop an objective function for the single-attack defense coordination problem. Given that the SRS pertains to the attacker’s forward reachability, it is natural to define an objective function that connects the SRS and the target set in terms of their minimum distance. With this in mind, we propose the minimum squared distance between the SRS and the target set as the objective function, which we refer to as the single-attack objective function:

Since both the SRS and the target set are convex and admit sublevel set representations, according to Proposition 1 and the assumption on the target set, the value of $\Phi^{\mathcal{C}}_{j}$ can be determined by solving the following parametric convex program:

where the joint state $x^{\mathcal{C}}_{j}$ serves as the parametric vector.

The single-attack objective function provides a quantitative measure for the binary outcome of the single-attacker multi-defender reach-avoid game. It is essential to note that the value of $\Phi^{\mathcal{C}}_{j}$ is always nonnegative for a nonempty SRS, and positive if the intersection between the SRS and the target set is empty. This suggests that retaining the positivity of $\Phi^{\mathcal{C}}_{j}$ is critical in preventing the attacker from reaching the target set. Consequently, a winning guarantee condition for the coalition can be derived in terms of the single-attack objective function.

We proceed to derive a defense-winning strategy for the coalition $\mathcal{C}$ by performing online robust maximization of the single-attack objective function $\Phi^{\mathcal{C}}_{j}$ when it has a positive value. In light of Pontryagin’s Maximum Principle for differential games (cf. Theorem 8.2 in [44]), robustly maximizing $\Phi^{\mathcal{C}}_{j}$ for the coalition $\mathcal{C}$ amounts to robustly maximizing its time derivative $\dot{\Phi}^{\mathcal{C}}_{j}$ with respect to the inputs $u^{d}_{i}$, $i\in\mathcal{C}$. Note that, the time derivative of $\Phi^{\mathcal{C}}_{j}$ along the joint state trajectory is given by

To measure the effect of each agent’s input on $\dot{\Phi}^{\mathcal{C}}_{j}$, we need to determine the gradients of $\Phi^{\mathcal{C}}_{j}$ concerning the positions of all agents. Fortunately, by invoking the Karush–Kuhn–Tucker (KKT) conditions (cf. Theorem 12.1 in [44]), a linear correspondence can be made almost everywhere between the gradients of $\Phi^{\mathcal{C}}_{j}$ and those of $c_{ij}$, $i\in\mathcal{C}$ given in (14).

Proposition 2 provides a tractable procedure for generating a defense strategy that approximately robustly maximizes $\Phi^{\mathcal{C}}_{j}$, assuming that (20) holds almost everywhere. This procedure entails deriving the gradient of the functions $c_{ij}$, $i\in\mathcal{C}$ for each $q\in\Omega^{\mathcal{C}}_{j}(x^{\mathcal{C}}_{j})$ and $q\neq p^{a}_{j}$ as follows:

where $\zeta_{ij}(q,p^{a}_{j})=\gamma_{ij}^{2}+\frac{r_{i}\gamma_{ij}}{||q-p^{a}_{j}||}$. By substituting (20) with $q=\xi^{\mathcal{C}}_{j}$ into (19) and noting that the parameter $\lambda_{ij}^{*}$ is nonnegative, we can obtain an almost robust optimal defense strategy for defender $i$ in coalition $\mathcal{C}$ given by:

for $x^{\mathcal{C}}_{j}\in\mathcal{D}^{\prime}$ such that the convex program (17) has a unique solution. Moreover, it can be shown that the uniqueness of the solution to (17) is guaranteed as long as $\Phi^{\mathcal{C}}_{j}$ remains positive.

We are now ready to present the main result of this section, which asserts that the almost robust optimal defense strategy given by (21) guarantees a win for the coalition once the joint state $x^{\mathcal{C}}_{j}$ lies within the region $\mathcal{D}^{\mathcal{C}}_{j}$.

We have identified a region $\mathcal{D}^{\mathcal{C}}_{j}$ of joint states within which the almost robust optimal defense strategy (21) ensures victory for the coalition. This defense strategy relies on the solution of the convex program (17), which typically does not guarantee solution uniqueness for joint states outside $\mathcal{D}^{\mathcal{C}}_{j}$. In real-world scenarios, as the attack strategy is unknown, it would be advantageous for the defense strategy to handle any joint state, not just those within the region $\mathcal{D}^{\mathcal{C}}_{j}$. By doing so, the chances of winning for the coalition against non-optimal attack strategies are increased. In the remainder of this section, we focus on utilizing the concept of SRS to extend the defense strategy to cover the entire joint state space.

We start by proposing a novel objective function specifically designed for joint states outside the region $\mathcal{D}^{\mathcal{C}}_{j}$. The single-attack objective function $\Phi^{\mathcal{C}}_{j}$ is not suitable for this purpose, as it cannot distinguish between joint states that are not in $\mathcal{D}^{\mathcal{C}}_{j}$, resulting in zero values for all such joint states. Given that an intelligent attacker tends to reach the target set safely and rapidly, and the intersection between the SRS and the target set is nonempty for $x^{\mathcal{C}}_{j}\notin\mathcal{D}^{\mathcal{C}}_{j}$, the objective function is defined as the minimum squared distance between the attacker’s position and the intersection between the SRS and the target set:

The convexity of the SRS enables the determination of $\bar{\Phi}^{\mathcal{C}}_{j}(x^{\mathcal{C}}_{j})$ through the solution of the parametric convex program:

The uniqueness of the solution to (23) is guaranteed since the projection of $p^{a}_{j}$ onto the convex and closed set $\Omega^{\mathcal{C}}_{j}(x^{\mathcal{C}}_{j})\cap\mathcal{G}$ is unique [45].

The objective function $\bar{\Phi}^{\mathcal{C}}_{j}$ is then employed to derive a defense strategy for which $x^{\mathcal{C}}_{j}\notin\mathcal{D}^{C}_{j}$. Based on the definition of $\bar{\Phi}^{\mathcal{C}}_{j}$, the goal of the coalition is to robustly maximize $\bar{\Phi}^{\mathcal{C}}_{j}$ over time, which can be accomplished by robustly maximizing the time derivative of $\bar{\Phi}^{\mathcal{C}}_{j}$. To achieve this, we need to determine the gradient of $\bar{\Phi}^{\mathcal{C}}_{j}$ with respect to the position of each defender in the coalition. Analogous to Proposition 2, it can be shown that for almost every $x^{\mathcal{C}}_{j}\notin\mathcal{D}^{\mathcal{C}}_{j}$, there is a set of nonnegative constants $\mu^{*}_{ij}$, $i\in\mathcal{N}$, such that

where $\bar{\xi}^{\mathcal{C}}_{j}$ is the unique solution to the convex program (23). The proof of (24), owing to its similarity to that of Proposition 2, can be found in Appendix -B. Considering the almost everywhere holding of (24), substituting (20) with $q=\bar{\xi}^{\mathcal{C}}_{j}$ into (24) yields an almost robust optimal defense strategy for $x^{\mathcal{C}}_{j}\notin\mathcal{D}^{C}_{j}$:

This defense strategy, together with the defense strategy (21) for $x^{\mathcal{C}}_{j}\in\mathcal{D}^{C}_{j}$, constitutes a dual-mode switching defense strategy applicable to the entire joint state space. The proposed algorithm for coordinating the defense against a single attacker is outlined in Algorithm 1.

Following the classical taxonomy of multirobot task allocation proposed by Gerkey et al. [36], the defense allocation problem can be categorized as a single-task robot, multirobot task, and instantaneous assignment problem. Under the current joint state, each defender can defend against at most one attacker at a time, each attacker can be simultaneously guarded by multiple defenders, and the assignment only concerns the present moment. To represent the assignment, a binary matrix called the assignment matrix $\mathcal{A}=(a_{ij})_{N\times M}$ is used, where the entry $a_{ij}=1$ if attacker $j$ is assigned to defender $i$, and 0 otherwise. In addition, since all defenders are single-task, the assignment matrix must respect the conflict-free constraint, i.e., the row sum of the assignment matrix should not exceed 1.

To better model the effect of each coalition-attacker pair on the defense performance, we introduce an alternative matrix representation. Let $\mathcal{C}_{k}$, $k=1,\ldots,\tilde{N}$ be the list of all different coalitions in which $\tilde{N}=2^{N}-1$. We define the coalition assignment matrix to be $\Theta=(\theta_{kj})_{\tilde{N}\times M}$ such that

and $\theta_{kj}=1$ if attacker $j$ is allocated to coalition $\mathcal{C}_{k}$. The coalition assignment matrix $\Theta$ inherently induces an assignment matrix $\mathcal{A}$ through the linear transformation:

where $\mathcal{B}=(b_{ik})_{N\times\tilde{N}}$ denotes the incidence matrix representing the binary relationship between defenders and coalitions. Specifically, $b_{ik}=1$ if $i\in\mathcal{C}_{k}$ and 0 otherwise. To maintain the single-task property, the conflict-free constraint is defined through the induced assignment matrix as

Additionally, the redundancy-free constraint is imposed on $\Theta$:

ensuring that each attacker is assigned to at most one coalition.

We now present an objective function incorporating decision variables as elements of the coalition assignment matrix. Recalling Theorem 1, if $\Phi^{\mathcal{C}_{k}}_{j}>0$ at the joint state $x^{\mathcal{C}_{k}}_{j}$, an admissible defense strategy for $\mathcal{C}_{k}$ exists that prevents attacker $j$ from reaching the target set. In light of this, we designate $(\mathcal{C}_{k},j)$ as a feasible coalition-attacker pair at $x^{\mathcal{C}_{k}}_{j}$ if $\Phi^{\mathcal{C}_{k}}_{j}(x^{\mathcal{C}_{k}}_{j})>0$. In line with the payoff function given in (12), the reward for assigning attacker $j$ to coalition $\mathcal{C}_{k}$, denoted by $w_{kj}$, is set as 1 if $(\mathcal{C}_{k},j)$ is feasible and attacker $j$ is active, and 0 otherwise, i.e.,

with $\rho_{j}$ given in (10). Subsequently, the objective function, depending on the choice of a coalition assignment matrix $\Theta$ at a given joint state $x$, is defined as the total sum of the rewards of all assigned coalition-attacker pairs:

We refer to $\Gamma$ as the multi-attack objective function, which signifies the expected number of attackers that will be unable to access the target set from the current joint state. The reason behind this objective function is that it enables the assessment of defense performance in multi-attack scenarios.

Although solving the ILP (34) provides an optimal solution to the defense allocation problem, it entails a substantial computational burden, particularly as the number of agents increases. This is mainly due to the vast amount of possible coalition-attack pairs, which not only leads to a large-scale ILP but more importantly, requires considerable computational effort to determine the multi-attack objective function. In the case of $N$ defenders and $M_{a}$ active attackers, there are $\tilde{N}M_{a}$ possible coalition-attacker pairs, implying that the same amount of convex programs of the form (17) need to be calculated to specify the corresponding rewards. To alleviate the computational burden, we propose a heuristic algorithm for the ILP (34) in Section IV-C to generate a suboptimal solution, which will then be fed into an allocation algorithm to ensure the monotonicity constraint (35) in Section IV-D. In particular, prior to detailing the heuristic algorithm, we will derive two critical components in the next section, which together construct a hierarchy that facilitates the generation of a suboptimal solution for the ILP (34).

The optimal solution to the ILP (34) tends to favor feasible coalition-attacker pairs comprising smaller coalitions. On one hand, the multi-attack objective function is influenced only by feasible coalition-attacker pairs, as the reward for an infeasible pair is zero. On the other hand, smaller coalitions are less likely to violate the conflict-free constraint (30), and thus more likely to contribute positively to the multi-attack objective function. As a result, the key to striking a balance between optimality and efficiency in solving the ILP (34) is to identify as many feasible sub-pairs of coalition-attacker pairs with small amounts of defenders as possible while keeping the computational cost low. Here, a sub-pair of a coalition-attacker pair refers to a subset of the coalition that is also paired with the same attacker. To this end, we will focus on seeking feasible sub-pairs of a coalition-attacker pair from the aspects of optimality and efficiency in the subsequent analysis.

As a point of departure, we revisit the convex program (17) subject to a feasible coalition-attacker pair $(\mathcal{C},j)$. As shown in Theorem 1, the vector $\xi^{\mathcal{C}}_{j}$ extracted from the solution to (17) establishes an almost-optimal waypoint for the coalition $\mathcal{C}$, which must lie on the boundary of the SRS $\Omega^{\mathcal{C}}_{j}$. Moreover, owing to the convexity of the SRS, some of the inequality constraints $c_{ij}(q,x_{ij})\leq 0$, $i\in\mathcal{C}$ must be active at $q=\xi^{\mathcal{C}}_{j}$. As such, we can define an index set of defenders through an active set in the convex program (17) that incorporates the almost-optimal waypoint $\xi^{\mathcal{C}}_{j}$.

The construction of the ADS does not necessitate the computation of any additional convex programs. This is because the feasibility of the coalition-attacker pair has already been verified using a convex program of the form (17), and the almost-optimal waypoint can be determined as a byproduct of this computation. It is worth noting that the ADS concept indeed provides a proximity-based method for obtaining a specific sub-pair, which is associated with both locations of the attacker and the target set, as illustrated in Fig. 4. Furthermore, it can be shown that such a sub-pair inherits the feasibility of the original coalition-attacker pair.

We turn to look at how to generate feasible sub-pairs of a sufficiently small scale. While the ADS allows for feasible sub-pair generation without incurring additional computational effort, the resulting sub-pair size may not be minimum with respect to feasibility. In other words, the sub-pair may include redundant defenders that could be removed without affecting the feasibility of the sub-pair. To precisely quantify the redundancy, we introduce the following definition.

Given a feasible coalition-attacker pair $(\mathcal{C},j)$, we can develop an iterative procedure to generate all irreducible sub-pairs. The process commences by evaluating size-1 subsets of $\mathcal{C}$. If $|\mathcal{C}|=1$, $(\mathcal{C},j)$ is inherently deemed irreducible and the process terminates. Otherwise, we check each size-1 subset $\mathcal{C}^{\prime}$ for irreducibility by confirming whether $\Phi^{\mathcal{C}^{\prime}}_{j}>0$. Then, we remove the element of $\mathcal{C}^{\prime}$ from $\mathcal{C}$ for which $(\mathcal{C}^{\prime},j)$ is irreducible, forming a new set $\mathcal{C}_{r}^{(1)}$. If $|\mathcal{C}_{r}^{(1)}|\leq 1$, all irreducible sub-pairs have been identified, and the process ends. In case further iterations are required, we repeat with all size-$l$ subsets of $\mathcal{C}_{r}^{(l-1)}$ for $l=2,\ldots,|\mathcal{C}|$, where $\mathcal{C}_{r}^{(l)}$ is analogously defined by removing elements from $\mathcal{C}_{r}^{(l-1)}$. The procedure continues until either $|\mathcal{C}_{r}^{(l)}|\leq l$ or $|\mathcal{C}|=l$ at the iteration $l$. Moreover, the number of iterations can be reduced by noting that the cardinality of the coalition for any irreducible sub-pair is upper bounded by the dimension of the domain.