Real-Time Heuristics and Metaheuristics for Static and Dynamic Weapon Target Assignments

Improved predictability could increase the accuracy of missile defense systems in multiple engagements.

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, 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 & 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”. These real-time solution techniques are products of heuristic algorithms or are solved using exact algorithms applied to transformations of the formulation.

The research report goes on to review the various formulations for both the SWTA and DWTA. The basic formulations of each are examined and the transformations that have been implemented are explored. Novel formulations that have sought to model and solve the problem in unique settings are reviewed, as are the exact algorithms that have been used to solve the SWTA and DWTA.

This work was done by Captain Alexander G. Kline for the Air Force Institute of Technology. AFRL-0273



This Brief includes a Technical Support Package (TSP).
Document cover
Real-Time Heuristics and Metaheuristics for Static and Dynamic Weapon Target Assignments

(reference AFRL-0273) is currently available for download from the TSP library.

Don't have an account? Sign up here.