Survey in Operations Research and Management ScienceThe Weapon-Target Assignment Problem
Introduction
Projectile weapons have been a consistent threat of hostilities throughout history. Military advantage has always been aided by the capacity to inflict damage from a distance. In the 20th century, missile technology advanced to the point that an adversary had the potential to attack a protected asset from great distances. To neutralize this stand off threat, the concept of air defense evolved. However, as the ability to reduce a missile threat increased, so too did the quantity and quality of missiles available, and research into the effective allocation of air defense resources emerged.
Originally introduced into the field of operations research by Manne (1958), the Weapon Target Assignment (WTA) Problem, or Missile Allocation Problem (MAP) as it is sometimes known, seeks to assign available interceptors to incoming missiles so as to minimize the probability of a missile destroying a protected asset. While much of the literature on the WTA focuses on the defensive perspective, some have considered the offensive perspective (Sikanen, 2008), wherein the objective is to maximize the probability of destroying enemy protected assets.
There are two distinct categories of the WTA: the Static WTA (SWTA) and the Dynamic WTA (DWTA). Originally modeled by Manne (1958), the SWTA defines a scenario wherein a known number of incoming missiles (targets) are observed and a finite number of interceptors (weapons), with known probabilities of successfully destroying the targets (probabilities of kill), are available for a single exchange. The solution to the SWTA informs the defense on how many of each weapon type to shoot at each target. In the SWTA, no subsequent engagements are considered since time is not a dimension considered in the problem.
By contrast, the DWTA includes time as a dimension. Variants of the DWTA include the two stage DWTA and the shoot-look-shoot DWTA. The two stage DWTA replicates the SWTA in its first stage, but includes a second stage wherein a number of targets of various types are known only to a probability distribution. In this variant, the solution to the DWTA informs the defense on how to allocate the weapons in the first stage and how many to reserve for the second stage in order to minimize the probability of destruction. The shoot-look-shoot variant also replicates the SWTA, however it enables the defense to observe which targets may have survived the engagement (leakers) and allows for a subsequent engagement opportunity. The solution to this variant similarly informs the defense on how to allocate the weapons and how many weapons to reserve to reengage any leakers.
The WTA has been solved to optimality with exact algorithms. However, as Lloyd and Witsenhausen (1986) showed that the WTA is NP-Complete, the majority of solution techniques seek to find near optimal solutions in real-time, or “fast enough to provide an engagement solution before the oncoming targets reached their goals” (Leboucher et al., 2013). These real-time solution techniques are products of heuristic algorithms or are solved using exact algorithms applied to transformations of the formulation.
The rest of this paper proceeds as follows. In Section 2, we review the various formulations for both the SWTA and DWTA. We examine the basic formulations of each and explore the transformations which have been implemented. We also review novel formulations which have sought to model and solve the problem in unique settings. In Section 3, we review the exact algorithms that have been used to solve the SWTA and DWTA. Some of these algorithms provide optimal solutions to the original formulations whereas others refer to the transformed formulations identified in Section 2. In Section 4, we review the heuristic and metaheuristic solution techniques for the SWTA and DWTA. In Section 5, we discuss the state of the WTA and present a metric with which we focused this examination of the literature.
Section snippets
Formulations
There have been many different formulations of the WTA. Early literature sought to transform the nonlinear formulation from Manne (1958) due to the computational limitations with nonlinear programming. As computational power increased, transformations which were better suited to global optimization tools emerged. Burr et al. (1985) introduced the DWTA which captured the value of subsequent engagements. Similar to the SWTA, variations to the original DWTA occur throughout the literature.
Herein,
Exact algorithms
There are few cases in the literature of exact algorithmic solutions to the WTA. The problem suffers due to its complexity as an NP-Complete problem (Lloyd and Witsenhausen, 1986) and, like routing problems, are simply hard to solve. For the SWTA, the number of possible permutations of assigning m weapons to n targets is nm, assuming that all weapons must be assigned, which, as the number of weapons and targets increases, grows exponentially and searching all possible solutions quickly becomes
Heuristic algorithms
Due to the computational complexity of the WTA, much of the literature focuses on heuristic algorithms which provide real time solutions rather than guaranteed optimal solutions. Many of these are of well known heuristic algorithms, such as the very large scale neighborhood (VLSN) search or the Genetic Algorithm (GA), but others are of new design, seeking to exploit the special structure of the WTA.
Evolution of WTA
Research on the WTA has evolved since the work of Manne (1958) with developments in both the formulation of the problem and the solution techniques implemented. In the earliest works, reference to the limited capacity to solve large nonlinear problems (Day, 1966) resulted in attention on simplified formulations of the SWTA (denBroeder et al., 1959) and solution techniques capable given the computational capacity of the day (i.e., (Lemus and David, 1963), (Day, 1966)). Eckler and Burr (1972)
Conclusion
The WTA has a rich breadth of literature which serves to improve upon the theory and techniques necessary to efficiently solve these complex problems. Early works sought to find methods to transform the problem into a simpler form, assume many of the complexities away, or do both in order to generate a formulation which was manageable with the computational capacity of the day. The theories and techniques proposed by the earliest researchers, such as Manne (1958) and denBroeder et al. (1959),
References (80)
- et al.
A weapon–target assignment approach to media allocation
Appl. Math. Comput.
(2006) - et al.
A mathematical immunochemoradiotherapy model: a multiobjective approach
Nonlinear Anal. Real World Appl.
(2008) - et al.
A two-resource allocation algorithm with an application to large-scale zero-sum defensive games
Comput. Oper. Res.
(2017) - et al.
Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities
Eur. J. Oper. Res.
(2018) Air defense missile-target allocation models for a naval task group
Comput. Oper. Res.
(2008)Constrained weapon–target assignment: enhanced very large scale neighborhood search algorithm
IEEE Trans. Syst. ManCybern. Part A
(2010)- et al.
A hybrid search algorithm with heuristics for resource allocation problem
Inf. Sci.
(2005) - et al.
An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem
Appl. Soft Comput.
(2002) - et al.
Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game
Eur. J. Oper. Res.
(2013) - et al.
Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm
J. Syst. Eng. Electron.
(2008)