A Survey on Weapon Target Allocation Models and Applications

Abstract

In Command and Control (C2), Threat Evaluation (TE) and Weapon Target Allocation (WTA) are two key components. To build an automated system in this area after modeling Threat Evaluation and Weapon Target Allocation processes, solving these models and finding the optimal solution are further important issues. This setting demands instantaneous operational planning and decision making under inherent severe stress conditions. The associated responsibilities are usually divided among a number of operators and also computerized decision support systems that aid these operators during the decision making process. In this Chapter, the literature in the area of WTA system with the emphasis on the modeling and solving methods are surveyed.

1. Introduction

The field of air defense is one of those areas where resource allocation is of great importance. Research on the resource allocation problem with military purposes dates back to the 1950s and 1960s where the first modeling issues for WTA problem were investigated [1]. Rapid developments in the field of battle and attention to advances in threat technology in the recent years, pose significant challenges for commanders in C2 Systems (CCSs). Furthermore, the complexity and diversity of engagement scenarios, and the volume and imperfect nature of data to be processed under time-critical conditions make the commander’s problems severe.

The WTA problem is a well-known military operations research problem which has many aspects and features. (a) It is a dynamic decision-making problem. Serial and interdependent decisions are made at different periods of time to deal with different threats. At each period, a decision (about one or several engagements) is made. The consequences or outcomes of decisions made at a given period change the characteristics of the problem for the next periods (e.g. ammunition availability, threats conditions, change in tactics, decreasing the data ambiguity). One important characteristic of dynamic decision-making problems is that the information is obtained gradually over time. (b) The WTA is a multiple criteria decision-making problem. In fact, the decision-making problem for the resource management is based on conflicting criteria. For example, minimizing the risk, maximizing the effectiveness measures and so on. (c) The resource allocation problem is subject to uncertainty (e.g., stochastic). The uncertainty is related to many aspects of the model such as the hit probability of the weapons and targets characteristics (e.g. maneuvering, tracking, identification/classification and so on). Therefore, decision consequences are uncertain and usually modeled by probabilistic distributions. Then, a kill assessment process checks the result of executed actions and reports either the threat is diminished or not. (d) The resource allocation problem is a time-critical decision-making problem. Decision makers have to decide and act under tight temporal constraints. The allocation of available weapons on priority bases to the correct targets needs complex calculations in a very short time.

Some important properties of the WTA problem are:

• It is NP-complete and consequently the computation time of any optimal algorithm grows exponentially with its size [2]. The complexity of this problem drastically increases if the temporal and spatial constraints of both the Blue Forces (BF) (i.e. friendly forces) and Red Forces (RF) (i.e. hostile targets) are considered.

• It is sequential (the results of previous engagements are observed before making present assignments) [3].

• The objective function is nonlinear (The WTA objective, often is a linear combination of nonlinear summand of expressions like ${\left[1-P_{\mathit{ik}}\right]}^{X_{\mathit{ik}}}$) [4].

• It is stochastic (weapon-target engagements are modeled as stochastic events) [5].

• It is large-scale (the combination of weapons-targets-time, grows exponentially) [2].

• It is mixed-integer; WTA is a combination of discrete and continuous variables.

Finding efficient solutions for WTA problem with these features, is the main challenge of the command. These WTA characteristics often make the solving process and finding the optimal solution difficult.

Researchers have suggested different mathematical formulations of the WTA problem and proposed exact algorithms and heuristic/meta-heuristic methods to solve the problem. The exact algorithms that have been introduced to solve the WTA problem are not comprehensive and usually run under the following conditions: (i) when all the defensive weapons are identical [6] or (ii) when the hostile targets can receive at most one defensive weapon [7]. Despite extensive attention of research in this field, a comprehensive and classificatory review will pave the path for more efficient and practical models and algorithms in accordance with the advent in the technology. Hence, in this survey different WTA models and solutions methods used for this problem are reviewed. Based on the modeling approaches, the available literature is classified into two groups. (i) defense allocation models, (ii) the game models. In the second part, the important characteristics for the WTA models and the solution process for the resource allocation problem are investigated. Like many other problems the WTA solution algorithms can be divided into three main categories, (a) enumerative techniques, (b) heuristic/approximate methods and (c) meta-heuristic methods. Finally, mission planning systems which have been developed in the military are listed. To cover the existing shortcomings and improve the weakness of models and solutions procedures some useful suggestions have been put forward for future studies.

The organization of this Chapter is as follows. In Section 2, we give a brief description of the problem and its components. In Section 3, the basic formulations of the WTA problem are presented and variations of modeling approaches are explained. Section 4 contains classification for algorithmic approaches. The last section contains some concluding remarks and providing directions for future research.

2. The WTA problem and its components

There are many different functions that must be handled in an air defense system. From a high-level command perspective, these functions can be divided in two main processes: picture compilation and picture exploitation [2].

The purpose of picture compilation process is generating a representation of the volume of interest (VOI) based on data and information received from a variety of sensors/sources. This step often includes the following sub-processes: (i) The target detection, (ii) target tracking, and (iii) target identification. The picture exploitation is the subsequent process that includes the following sub-processes: (i) Threat Evaluation (TE), (ii) Engageability assessment and (iii) weapons assignment (here referred to as WTA) [2]. In a military context this set of sub-problems also are known as combat power management (CPM). The WTA component, in a CPM system can be divided into three sub-problems:

• Response planning; this sub-problem deals with the combat resource allocation. During this process, one or more of available weapons are assigned to engage each threat.

• Response execution; in this phase the planned response is executed at the designated time.

• Outcome assessment; in this process the outcome of the executed actions or engagement is identified and/or verified. This process is well known as killing assessment (where outcomes are 0/1 for kill/alive) or damage assessment (where outcome is a value in [0, 1] i.e. partial damage is possible) in C2 domain.

This research concentrates only on the response planning procedure of WTA process. This process is about how and when to allocate the available defensive resources. In other words, response planning procedure has two aspects: resource allocation planning and scheduling.

2.1 Resource allocation: planning and scheduling

In C2 context the response planning mainly is pertained to resource allocation problem. Resource allocation is the assignment of resources to activities, where the start and end times of each activity is given [8]. This problem is concerned with optimally assigning weapons to the hostile targets so that after all engagements, the BF expectations are met as far as possible. Resource allocation scheduling is another important aspect of the response planning that consists of determining the start and end times of the activities. In pure scheduling problems, activities are already chosen (or given), leaving only the problem of determining a feasible and possibly best order among them. In defensive operations, scheduling determines when a specific defensive action (e.g. assigning a specific weapon against a specific threat) ought to take place [9]. Therefore, the response planning determines the best assignment of the resources and specifies the start and end times of the activities. This procedure defines a joint resource allocation planning & scheduling problem. In this Chapter we focus on the response allocation planning or determining optimal assignment of weapons to the hostile targets which is referred as WTA.

It is interesting to note that, in contrast with other CPM components like TE, WTA is well documented in the literature and possible solutions have been investigated for a number of years. The WTA process is one of critical decision making, that is consistent with the related own force mission objectives and compatible with the Rules of Engagement (RoE), Weapon Systems (WSs) and environmental constraints. In the next section the basic formulations of the WTA problem and variations of modeling approaches are explained.

3. WTA modeling approaches

The WTA problem is a model of combat operations where a finite number of weapons are assigned to hostile targets (i.e. RF). The BF expectation and objective must be fulfilled after all engagements. The BF objective could be minimizing the total expected value of surviving targets, minimizing military resource costs and so on. From mathematical point of view, the purpose of the WTA solving process has been determined as weapon-target pairs. In the following, this process will be described formally, but first, we need to introduce some notations. The notations employed in this context are listed in Table 1.

3.1 WTA basic models

Assuming a defensive scenario consisting of $\left|W\right|$ firing units and $\left|T\right|$ targets, from a defensive perspective, there are three basic models for WTA [5].

Basic model 1: The first basic model for WTA problem, which focuses on maximizing damage to the enemy/minimizing total expected target values, can be formulated as:

$$minF=\sum _{i=1}^{\mid T\mid }{V}_i\prod _{k=1}^{\mid W\mid }{\left(1-P_{\mathit{ik}}\right)}^{X_{\mathit{ik}}}$$E1

In this model the goal of the defender is to minimize the numbers of the surviving invading enemy, using the optimal allocation of available weapons.

Basic model 2: The second basic model for WTA is to allocate the available firing units to maximize the total expected protection value of surviving defended assets. This model can be formulated as follows:

$$maxJ=\sum _{j=1}^{\mid A\mid }{\omega }_j\prod _{i\in G_j}(1-{\pi }_{\mathit{ij}}\prod _{k=1}^{\mid W\mid }{\left(1-P_{\mathit{ik}}\right)}^{X_{\mathit{ik}}})$$E2

Basic model 3: If the total expected value of surviving assets after the current stage is employed as the objective of WTA for the current stage, then the formulation of the objective function for basic Dynamic WTA in stage t is well be as follows [10]:

$$\begin{array}{l}max{J}_t\left(X^t\right)=\sum _{j=1}^{\left|\mathrm{A}\left(t\right)\right|}{\omega }_j\prod _{i=1}^{\left|T\left(\mathrm{t}\right)\right|}\left[1-{\pi }_{\mathit{ij}}\prod _{h=t}^S\prod _{k=1}^{\left|W\left(t\right)\right|}{\left(1-p_{\mathit{ik}}\left(h\right)\right)}^{x_{\mathit{ik}}\left(h\right)}\right]\\ \mathit{\text{with}}t\in \left\{1,2,\dots ,S\right\}\end{array}$$E3

Where $h$ is an index of stages and the defender have $S$ engagement opportunities which depends on the time–space conditions of the interception and weapon characteristics. Here $A\left(t\right),T\left(t\right)$ and $W\left(t\right)$ are sets of defended assets, hostile targets and available weapons in stage $t$, respectively. These three basic models are reference for the other models which have been incorporated in the applications.

3.2 Variation of modeling approaches

The WTA problem may be considered from a number of different perspectives. In this section, first a framework is provided for identifying key elements of WTA problem and then based on these characteristics we describe particular sets of modeling techniques which have been proposed for these problems.

In terms of interaction with the environment and modeling of these interactions, there are two general formulations that are investigated in literature for WTA problem: static and dynamic WTA model.

1. Static WTA (SWTA), in this approach of modeling, all weapons engage targets in a single stage and assume that the decision maker is aware of all parameters for the problem, while the outcomes of the assignments could be stochastic. Thus, the goal of SWTA is to find the optimal assignment for a temporary defense task (the basic models 1 and 2 are static models). This WTA problem was first formally posed in 1958 [1]. It is interesting to note that the majority of the literature in WTA domain have been dedicated to efficiently solving the SWTA problem formulation and few optimal methods have been presented for solving SWTA with some simplifications. For example, optimal methods have been proposed by denBroeder [11] under a homogenous weapon set assumption, known as the maximum marginal return (MMR) algorithm. Orlin [12] developed optimal algorithms under the assumption that each target can have no more than one weapon assigned to it. A survey of WTA solution methods has been provided in section 7 of present Chapter.

2. Dynamic WTA (DWTA), in this approach, WTA is molded as a multi-stage problem and the outcome of each engagement is assessed for subsequent decisions. This variation of WTA problem was firstly formulated by Hosein et al. in 1989 [13]. The DWTA problem has similar stochastic elements as the SWTA problem, but assignments are made in multiple stages. In other words, the time parameter is defined in dynamic models and the goal is to find a global optimal assignment for the whole defense process. The DWTA often have been presented as a sequential decision making problem. The basic assumptions of the DWTA are outlined as follows [14]:

   • In each stage, a subset of the available weapons is selected and allocated simultaneously.

   • The outcomes of each stage are observed prior to the preceding stage (i.e. the problem re-solved at each stage using previous stage information).

The DWTA problem suffers from the curse of dimensionality. Therefore, traditional solution methods become intractable. The curse of dimensionality arises from three elements of the problem i.e. state space, decision space, outcome space, or their combination [2]. Intuitively, DWTA can be achieved by a series of SWTAs through all stages. However, although SWTA can at best, guarantee the optimality of the WTA decisions for its corresponding defense stage, the combination of all SWTA decisions may not be optimal for the whole defense process (because of its greedy nature). In a real-world situation, the decision of which weapon system to be allocated to which target needs to be complemented with scheduling of when to engage a target.

Moreover, apart from the modeling approaches being static or dynamic; the WTA problem can be formulated based on two different defense scenarios. The air defense capability may be limited to self-defense or may be extended to area defense where a set of assets within a certain range should be defended. For example, in a military task group, the individual defense units work together as a team to provide mutual support and defense against incoming threats. These units are typically arrayed into a formation, called a screen, in which the most valuable and important units (i.e. high value units (HVUs)) are surrounded and protected by the escorting units (e.g. vessels and airplanes). Within the screen, the escort units often are stationed in sectors away from the HVU. In such a situation important issues such as positioning and coordination between these units are aroused [10]. Therefore, in WTA problem the following two perspectives are usually adopted:

1. The single platform perspective: a single platform intends to protect an asset (may be itself) from incoming threats, where assignment relates to selecting the most suitable WS to counter a threat (e.g. a ship that intends to defend itself against invading threats). In this case often the defense and the defended property (i.e. assets) are the same.

2. The force coordination perspective: a C2 platform providing protection (e.g. TE and WTA) for third party Defended Assets (DAs), where assessment relates to the identification of the most suitable armed platform to engage or counter a threat. In this case the defense and the defended property are different (likely separated) and the purpose of defense is to maximize the chance of survival of the being-defended assets.

The main objective of the invading enemy is harming the defended valuable assets, but for making these assets defenseless, they may first destroy the protective weapon platforms. So the arrangement of platforms (i.e. defense units) is one of the major issues that must be handled in this type of WTA problem. This positioning must maximize asset protection while minimizing the possible damage to them [10].

In addition to the number of deployed defensive units, the defense scenarios usually involve more than one hostile target. Therefore, when investigating the WTA modeling approach where the available WSs are assigned, two perspectives are prevalent:

1. The threat-by-threat perspective, which refers to the assignment of WSs sequentially in such a way that the best WS is essentially assigned to each threat in turn (from the highest priority to the lowest priority).

2. The multi-threat perspective, which refers to the assignment of WSs to the current set of threats concurrently so that the assignment is best in some overall sense.

Technically, both of the above mentioned approaches employ some form of optimization techniques. What distinguishes them is the threat-by-threat assignment which usually is based on some type of greedy algorithms, whereas the multi-threat assignment typically involves the optimization of a given objective function (e.g. maximize the damage to the targets/minimize the value of any remaining targets, maximize the asset protection and so on) subject to certain constraints (e.g. the target priority, the number of simultaneous engagement and so on) [10].

Furthermore, depending on the defense priorities and attitude of the modeling, the WTA problem can be stated as two different optimization problems:

1. Target-based (weighted subtractive) defense; the BF allocates firing units to minimize the expected total target value of the RF targets.

2. Asset-based (preferential) defense; the WTA problem is stated as an optimization problem where the objective becomes to maximize the total expected survivability of the defended assets.

Target-based objectives lead to subtractive defense strategies (basic model 1). In other words, the defense tries to destroy as many of the most lethal targets as possible, or at least the most valuable ones. On the other hand, asset-based objectives lead to preferential defense strategies (basic models 2 for SWTA and basic models 3 for DWTA). In order to save an asset, the defense must, with high probability, destroy all of the targets aimed for it or divert them. For these purposes each of the hostile targets must be attacked with appropriate hard-kill or soft-kill weapons (e.g. jammers, decoys and etc.). In this case the defense may not have enough weapons to defend all the assets. Therefore, the defense must decide which of the assets should be protected (i.e. which one is preferred) and to assign its defensive resources to protect them. However, no weapons may be assigned to the targets aimed for the other low valued defended assets (i.e. this asset is immolated to save other valuable assets). This is known as a preferential defense strategy.

The main difference between the target-based WTA problem and the asset-based WTA problem is that in the latter, the aims of the enemy are assumed to be known. In other words, the asset-based formulation demands knowledge of which hostile targets are headed for which defended assets. Therefore, the asset-based WTA problem formulation is suitable for ballistic missile defense problems (such as base camp protection against artillery and mortars) while the target-based formulation is more appropriate when the intended aims of the targets are not known for sure [15]. The target intention determination can be thought of as a data association problem [2].

In defense scenarios, the defender may look for optimizing different objectives. According to the number of goals which need to be optimized, the WTA is modeled in two ways:

1. Single-objective WTA problem: if the quantity to be optimized is expressed using only one objective function, the WTA problem is modeled as a single-objective problem. The objective function might be minimizing survival probability of hostile target or maximizing protection value of surviving defended assets (see e.g. Eq. 1 and 2).

2. Multi-objective WTA problem: if the problem concerns on many objectives simultaneously then WTA will be a multi-objective problem. These objectives cloud be minimizing the risk and cost, maximizing the effectiveness measures and so on. Normally these objectives are conflicting each other.

The WTA problem has been designed to support human operators in real world condition. Therefore, the proposed WTA model should be able to cope with numerous and heterogeneous real-world objectives and constraints to help the operator to make appropriate decisions. This implies that WTA is required to be formulated as a multi-objective optimization (MOO) problem. However, relatively few researchers studied the WTA as a MOO problem. The research work by Ghanbari et al. [3], Newman et al. [16] and Leboucher et al. [17] applied MOO to formulate the model for the WTA problem.

A summarizing list of WTA modeling approaches from a BF perspective is given in Table 2. In WTA modeling miscellaneous limitations must be considered, these constraints will be discussed in the next section.

Sets

$T_i$: the set of detected threats, $i=1,2,\cdots ,I$.

$w_k$: the set of resources, $k=1,2,\cdots ,K$.

$A_j$: the set of assets $j=1,2,\cdots ,J$.

$s=1,2,\cdots ,S$: the set of engagement stages.

Parameters

$P_{\mathit{ik}}$: the estimated effectiveness, i.e. probability that resource $w_k\in W$ neutralize threat $T_i\in T$ if assigned to it.

${\pi }_{\mathit{ij}}$: the estimated probability that threat $T_i\in T$ destroys the asset $A_j\in A$.

$V_{\mathit{ij}}$: the threat value of the threat-asset pair $\left(T_i,A_j\right)$.

${\omega }_j$: the protection value of asset $A_j\in A$.

$C_{\mathit{ik}}$: a resource usage cost for assigning resource $w_k\in W$ to target $T_i\in T$.

Variables

$X_{\mathit{ik}}=\left\{\begin{array}{l}1\mathit{\text{if}}\mathit{\text{resource}}{w}_k\in W\mathit{\text{is}}\mathit{\text{assigned}}\mathit{\text{to}}targ\mathit{et}{T}_i\in T\\ 0\mathit{\text{otherwise}}\end{array}\right.$

${\left[X_{\mathit{ik}}^s\right]}_{I\times K}$: is a decision matrix at stage $s$.

Table 1.

Notations.

Table 2.

The WTA modeling approaches.

From Table 2 it can be deduced that the simplest approach for formulation the WTA problem is a static, single-objective, target-based, threat-by-threat and single platform model; while the most complex formulation is a dynamic, multi-objectives, asset-based, multi-threat and force coordination model. The asset-based formulation increases the model complicity because it demands hostile targets intention analysis. The models proposed in WTA literature are in a state between the easiest and the hardest one. While the real-world situations tend towards to the latter (i.e. the most complicated case).

Apart from the above WTA problem characteristics, the literature on WTA problem can be categorized into two general groups (see Table 3).

1. The first category of approaches includes defensive allocation models where defensive weapons are allocated to targets without taking the behavior of the opposing side into account. The actions of the opposing side are presumed in the scenarios as a given input.

2. The second class of approaches takes the defensive allocation models into account as well as the opposing side’s moves. These models often employ the two-person-zero-sum-game concept from game theory in the solution process. But we believe that in reality, war is not a zero-sum game and both sides have losses. They reach the

3. solution value of the game by assuming best defensive and offensive moves. The defense wants to minimize the maximum offense’s return while the offense acts to maximize the minimum expected return. This approach is more suitable when the inventories of a defender as well as the opposing sides are known to some degree.

Literature category	Reference
Defense allocation models	Newman et al. [16], Benaskeur et al. [18], Zhang et al. [19], Turan [20], Yuming et al. [21], Leboucher et al. [17], Tokgöz and Bulkan [22], Ahner and Parson [4], Kalyanam et al. [8], Davis et al. [23], Naseem et al. [24], Gülpınar et al. [25], Hocaoğlu [26], Kline et al. [27].
Game Models	Matheson [28], Soland [29], Haaland and Wigner [30], Bracken and Brooks [31], Bracken et al. [32], Golany et al. [33], Leboucher et al. [17], Parson [34], Zhang and Zhuang [35].

Table 3.

Classification of the WTA approaches.

This Chapter is focused on defensive scenarios. It is interesting to note that early foundation literature in the WTA field deal mainly on the offensive scenarios, while more recent studies have been focused on defense.

Air defense is a vast area and defensive resource allocation or WTA is a component for which numerous scenarios, models and algorithmic approaches (i.e. techniques for computing solutions) have been proposed. However, an exhaustive categorization for WTA models can be quite large. This section will focus on those aspects that provide for distinctive characteristics of the proposed models. The important characteristics for the modeling and the solution process in the air defense applications are:

1. Simultaneous or sequential attack,

2. Point or area defense systems,

3. Number of attacking and defending weapon types,

4. One or multiple layers of defense,

5. Interceptor WTA policy,

6. Online or Offline application.

In order to better understand the role and importance of these aspects and how to provide a distinctive feature of WTA problem in an air defense system, we shall consider each in further details.

Simultaneous or Sequential Attack: A simultaneous attack is one for which the defense sees all the incoming threats to intercept. The term “known attack size” is also used synonymously for simultaneous attack [36] and is often used in air defense WTA systems on Above Water Warfare (AWW). A sequential attack is the case for which the defense does not know the number of attacking groups in a raid and the number of attackers in each attack group is often used in a ground based air defense context. A mixture of simultaneous and sequential attack may exist for real world situations.

Weapon Types: In a defense scenario in general, attackers and/or defenders may be identical or multiple types. In air defense scenarios in particular, the same pattern holds as well. In practice defender and attackers usually have different types and are equipped with different weapon systems. These attributes usually complicate the WTA problem.

Layered Defense: With reference to the significance of the defended assets, various weapon types are deployed for their protection (i.e. hard-kill and soft-kill weapons). Defense systems of different types, protecting the same targets might have different effective ranges and different functionality. This issue constitutes the layers of defense. In real-word situations, the numbers of these layers are varied and typically have overlaps.

Interceptor Allocation Policy: The defense’s interceptor allocation policy such as salvo, shoot-look-shoot and shoot-shoot-look affects the performance and modeling of the air defense system. Defensive systems may have single or multiple engagement opportunities depending on the time–space conditions of the interception and weapon characteristics. Moreover, in WTA literature the defender’s interceptors are generally organized into two categories: hard-kill and soft-kill weapons. The hard-kill weapons aim at physically destroying an incoming threat by collision or explosion. The soft-kill weapons aim at diverting the threat from its target using various electronic counter measures [37]. A high volume of research pertains to consideration of hard-kill weapons; generally, this two weapon types are supervised by different control operators. The optimal combining and scheduling of these weapon types, is the responsibility of the higher level commander. This process often is a complex task and usually is studied in the planning systems designing field [37].

Online or Offline Applications: Optimal defensive resource allocation has two main classes of applications, these are, 1) the Online scenario, that is, deploying defensive resources in real time, during real engagements and 2) the Offline scenario, when using allocation algorithms to simulate and model the effectiveness of defensive resources against a given threat scenario. The real-time aspect is one of the major characteristics of real-world air defense situations. Operations research community is the flagship of this area. But despite these initiatives, in many studies in this field real-time aspect of the problem could not be traced.

The importance of the online scenario is immediate; however, the offline scenario also has significant value and can perceivably be used to aid acquisition or to estimate a measure of preparedness. Further, a capability to consider offline scenarios will most likely enhance the development of online algorithms. This claim follows naturally from the inherent complexity in defensive resource allocation problems, which often necessitates unavoidable approximation for online applications [38].

The classification of related literature that was discussed in preceding section is summarized in Table 4. This table contains only the related research which has the above-mentioned properties and those papers which do not talk on their model and their characteristics are excluded. A comprehensive categorization for WTA problem formulation approaches is illustrated in Figure 1.

Reference	Features	Point/Area Defense systems	Weapon Types	One/Multiple Layers of defense	Interceptor weapon allocation policy	Online/ offline application	Simultaneous/Sequential attack
Bin Xin et al. [39]		AD	Diff	Mul	S-L-S	Offline	Seq
Johansson [5]		AD	Diff	One	S-L	Online	Simul
Bin Xin et al. [40]		AD	Diff	Mul	S-L-S	Offline	Seq
Zhang et al. [41]		PD	Diff	One	S-L	Online	Simul
Turan [20]		PD	Diff	One	S-L	Online	Simul
Yuming et al. [21]		PD	Diff	One	S-L	Offline	Simul
Leboucher et al. [17]		PD	Diff	Mul	S-L-S	Offline	Seq
Tokgöz and Bulkan [22]		AD	Diff	Mul	S-L-S	Offline	Seq
Parson [34]		AD	Diff	Mul	S-L-S	Offline	Seq
Kalyanam et al. [8]		PD	Diff	Mul	S-L-S	Offline	Seq
Naseem et al. [24]		AD	Diff	Mul	S-L-S	Online	Seq
Zhang and Zhuang [35]		AD	Diff	Mul	S-L-S	Offline	Seq
Kline et al. [27]		AD	Diff	Mul	S-L-S	Offline	Seq

Table 4.

The main characteristics of the WTA approaches.

Area Defense (AD), Point Defense (PD), Different Weapon Types (Diff), Identical Weapon Types (Iden), Multiple Layers of defense (Mul),One Layers of defense (One), Shot (S), Look (L), Simultaneous attack (Simul), Sequential attack (Seq).

Figure 1.

A general categorization for WTA problem formulation approaches.

4. Constraints

The WTA problem is subject to various limitations that must be satisfied prior to optimization process. In this section the set of constraints discussed in the WTA literature are reviewed. It is interesting to note that, duo to emergence of time parameter in dynamic mode (i.e. DWTA) the constraints are more diverse.

4.1 SWTA constraints

The following constraints are often raised in the SWTA model and here are called as general constraints:

$$\sum _{i=1}^{\left|T\right|}{X}_{\mathit{ik}}=1,\forall k\in \left\{1,2,\dots ,\left|W\right|\right\}$$E4

$$\sum _{i=1}^{\left|T\right|}{X}_{\mathit{ik}}\le 1,\forall k\in \left\{1,2,\dots ,\left|W\right|\right\}$$E5

$$X_{\mathit{ik}}\in \left\{0,1\right\},\forall i\in \left\{1,2,\dots ,\left|T\right|\right\},\forall k\in \left\{1,2,\dots ,\left|W\right|\right\}$$E6

Eq. (4) means that each firing unit should be assigned to a target and Eq. (6) shows that fractional assignments of firing units to targets are not possible [5]. If the allocation of a certain firing unit to a target is not mandatory the Eq. (4) will be replaced as (5).

4.2 DWTA constraints

The DWTA often divides the total duration of a defensive operation into several discrete time steps in which information is obtained about the allocation outcomes of the previous stages. The DWTA problem aims to assign weapons optimally over time and this feature increases the diversity of constraints in dynamic mode. Therefore, in addition to the limitations listed for SWTA, the following constraints are also considered: capability constraints, strategy constraints, resource constraints, and engagement feasibility constraints.

• Capability constraint:

$$\sum _{i=1}^{\left|T\right|}{x}_{\mathit{ik}}\left(t\right)\le n_k,\forall t\in \left\{1,2,\dots ,S\right\},\forall k\in \left\{1,2,\dots ,\left|W\right|\right\}$$E7

The constraint set (7) reflects the capability of weapons for firing at multiple targets at the same time and known as capability constraints. Most of actual weapons can shoot only one target at a time. Besides, a special weapon that is capable of engaging multiple targets simultaneously can be viewed as multiple separate weapons. Therefore in most of the WTA literature $n_k=1$ for $\forall k\in \left\{1,2,\dots ,W\right\}$.

• Strategy constraint:

$$\sum _{k=1}^{\left|W\right|}{x}_{\mathit{ik}}\left(t\right)\le m_i,\forall t\in \left\{1,2,\dots ,S\right\},\forall i\in \left\{1,2,\dots ,\left|\mathrm{T}\right|\right\}$$E8

The constraint set (8) limits the weapon cost for each target at each stage, therefore, they express as strategy constraints. The setting of $m_i\left(i=1,2,\dots ,\mathrm{T}\right)$ usually depends on the combat performance of available weapons and defender’s strategy. For missile-based defense systems and the SLS engagement policy, often $m_i=1$. For artillery-based defense systems, the value of $m_i$ might be increased greatly under the same demand on defense strength [40].

• Resource constraint:

$$\sum _{t=1}^S\sum _{i=1}^{\left|T\right|}{x}_{\mathit{ik}}\left(t\right)\le N_k,\forall k\in \left\{1,2,\dots ,\left|W\right|\right\}$$E9

The constraint set (9) depicts the amount of ammunition available for weapons and the constraints are known as resource constraints. In DWTA modeling often it is assumed that, the deployment of additional ammunition is not possible in a particular operation.

• Engagement feasibility constraint:

$$\begin{array}{l}{x}_{\mathit{ik}}\left(t\right)\le f_{\mathit{ik}}\left(\mathrm{t}\right),\forall t\in \left\{1,2,\dots ,S\right\}\\ \forall k\in \left\{1,2,\dots ,\left|W\right|\right\},\forall i\in \left\{1,2,\dots ,\left|\mathrm{T}\right|\right\}\end{array}$$E10

Constraint set (10) is very important to actual dynamic WTA problems since it takes into account the influence of time windows on the engagement feasibility of weapons (In fact, it represents the difference between static and dynamic modeling). $f_{\mathit{ik}}\left(\mathrm{t}\right)$ is the indication of actual engagement feasibility for weapon $k$ assigned to target $i$ in stage t. If weapon $k$ can shoot at target $i$ in stage t with any potential reason then $f_{\mathit{ik}}\left(\mathrm{t}\right)=1$; $f_{\mathit{ik}}\left(\mathrm{t}\right)=0$ otherwise [5]. This set of constrains increases the complexity of DWTA problems and the difficulty of generating feasible solutions [5].

In addition to the above constraints, there are a class of technical constrains as well. Constraints such as blind zones (i.e. for fining units and hostile targets), bounds on the survival value of an asset/hostile target [42], scheduling constraints (e.g. constraints such that a weapon has to be shot at a target by a specified time or it is rendered unusable), as well as correlations and heterogeneity between different defensive weapon types (e.g. hard-kill and soft-kill) and so on [43].

5. Algorithmic approach/solution methods

As it is evident from the available literature, a lot of different algorithmic approaches have been suggested for solving the WTA problem in air defense systems. A review of the algorithmic approaches proposed in the literature of WTA is presented in this section and a summary of them is depicted in Table 5.

Solving technique	References
Exact algorithms	Malcolm [38], Ahuja et al. [7], Sikanen [44], Karasakal [10], Johansson [5], Turan [20], Bogdanowicz [45], Ahner and Parson [4], Kline [6]
Heuristic algorithms	Newman et al. [16], Tokgöz and Bulkan [22], Yuming et al. [21], Parson [34], Kalyanam et al. [8], Davis et al. [23], Kline [6], Kline et al. [46, 47], Gülpınar et al. [25], Zhang and Zhuang [35], Hocaoğlu [26].
Meta-Heuristic algorithms	Turan [20], Tokgöz and Bulkan [22], Sahin and Leblebicioglu [48], Bogdanowicz et al. [45], Yuming et al. [21], Han et al. [49, 50], Ahner and Parson [4], Pendharkar [51], Davis et al. [23], Gong et al. [52], Klinkowski et al. [53], Gülpınar et al. [25], Wang et al. [54], Ma et al. [55], Kline et al. [27], Rudek and Heppner [43], Kalaiselvi and Selvi [56], Shooli and Javidi [57], Zhu et al. [58], Xu et al. [59], Ejaz et al. [60]

Table 5.

Classification of the algorithmic approaches used to solve the WTA models.

The results show that the WTA problem solving algorithms like many other problems can be divided into three main categories: enumerative techniques, heuristic/approximate techniques and meta-heuristic algorithms. Enumerative techniques are typically guaranteed to find an optimal solution in bounded time for every finite size problem instance; hence, they are referred to as exact algorithms or exhaustive search. The problem with exact algorithms is that the computation times needed often are too high for practical applications. For this reason, in solving the real-world problems with large sizes heuristic methods are commonly used. With heuristic/meta-heuristic algorithms (e.g. guided random search techniques/Genetic Algorithm (GA)), finding an optimal solution is not guaranteed, but instead we can find good solutions in a significantly reduced amount of time [2]. Hence, heuristic/meta-heuristic algorithms are used when we seek good feasible solutions for optimization problems in circumstances where the complexity of the problem or the limited available time for its solution does not allow using the exact algorithms [3]. A summary of the algorithms proposed for WTA is shown in Table 5; as mentioned they include exact algorithm, heuristic algorithm as well as meta-heuristic algorithms.

In addition to the algorithmic approaches mentioned in Table 5, various variants and combinations of these algorithms also have been suggested in literature for WTA. For example, Khosla [61] developed an algorithm by merging and modifying Simulated Annealing (SA) and GA, Metler and Preston [62] used the solution returned from the MMR algorithm and applied local search on this solution. A GA combined with local search is suggested by Lee et al. [63]. In their study they used Partially Mapped Crossover (PMX), inversion mutation and simulated annealing as local search. In another study they try to resolve the WTA problem with an improved GA, they used greedy reformation scheme so as to have locally optimal offspring (greedy eugenics) which is a kind of novel crossover operator (EX) that try to inherit the good genes from the parents [64]. In the work done by Lu et al. dynamic probability of mutation and crossover in GA have been used to generate new offspring [65]. Shang et al. added an extra step to the GA, after creating new chromosomes by crossover and mutation operators. A local search is applied to create new chromosomes and then evaluates them [66]. They also used a crossover operator called an elite preserving crossover operator to enrich a more effective search. Dou et al. uses chromosomes in matrix representation and adopts the dynamically adjusting punishment gene and self-regulating punishment rates [67]. Li et al. uses matrix-type encoding for chromosomes and a new crossover/mutation operator called “circle swap” [68]. Sahin and Leblebicioglu applied fuzzy reasoning to approximate optimum allocations in real-time for use on a battlefield [48]. Lagrangian relaxation was proposed by Yu Z et al. to decompose the problem into two tractable sub-problems while iteratively updating the Lagrange multipliers [69].

Similar to the SWTA, numerous methods have been employed to provide solutions for various types of DWTA problems. The DWTA divides the total duration of a defensive operation into several discrete time steps in which information is obtained about the allocation outcomes of the previous stages. Any hostile targets destroyed during a stage will be no longer targeted in subsequent stages, allowing the operator to make better use of their weapons. Hosein is an originator of the dynamic instance. He provided several results which are generalizable to the DWTA problem [13]. Murphey used stochastic decomposition for the two-stage DWTA problem [15]. Chang used a static WTA approximation scheme within an iterative linear network flow framework to efficiently provide high-quality solutions for the DWTA [70]. Wu et al. applied a modified GA to the DWTA and introduced weapon use deadlines within the problem formulation [71]. Xin et al. developed a heuristic which uses problem information (domain knowledge) and constraint programming to assign priorities to assignments [40]. Evolutionary heuristics which use a hybridized GA with memetic algorithms have also been applied by Chen et al. [72]. Other researches have been done to solve the WTA problem which are listed in Table 5.

Though it has not been researched to the extent of the SWTA problem, the DWTA problem provides a more practical implementation by including a temporal component. As such, the DWTA is a much more complex problem from a mathematical standpoint and has received a fair amount of attention in the literature. Due to the increasing computing power of computers and progress of science such as artificial intelligence (AI), researchers are moved towards the use of meta-heuristic algorithms to solving the WTA especially for DWTA problem.

6. Conclusions

In this Chapter, the literature in the area of WTA system with the emphasis on the modeling and solving approaches has been reviewed. Based on modeling approaches the literature has been classified into two groups. The first class of approaches allocates the defensive sources to targets without taking the behavior of the opposing side into account. The second class of approaches considers the opposing side’s moves as well as the defensive moves. In the second part, the important characteristics for the WTA models and the solution process for solving the WTA problem are reviewed. The results show that solving algorithms, like many other problems, can be divided in three main categories: enumerative techniques (i.e. exact or exhaustive methods), heuristic/approximate techniques and the meta-heuristic ones.