Dynamic Air Battle Planning

Software systems employing genetic processing algorithms rapidly create valid air tasking orders.

An air tasking order (ATO) implements air operations supporting the joint force commander's campaign by assigning aircraft and munitions to targets and specifying the timing and grouping of air missions. Currently, creating an ATO is a routine, but manually intensive process that underutilizes the skills of the Master Air Attack Plan (MAAP) chief and his or her team. The current ATO creation software employs constraint-based linear programming and indicates only if a proposed mission is valid; it does not identify whether the ATO is the optimal plan given the MAAP team's objectives, target list, and available inventories of aircraft and munitions. Software engineers from 21st Century Technologies (Austin, Texas) are developing two products— ATO-Link and ATO-Stream—to automate and optimize the ATO creation process, shorten the ATO development cycle to minutes, and reduce mundane planning work. AFRL's Small Business Innovation Research program is administering both project efforts.

ATO-Link and ATO-Stream are genetic-algorithm-based software systems that automatically generate a valid ATO tailored to battlefield conditions and campaign objectives. ATO-Link implements a fixed air campaign valid for a 24- hour period, allocating limited inventories of aircraft and munitions to achieve multiple objectives, while honoring numerous complex constraints. ATO-Stream leverages ATO-Link capabilities to manipulate a kinetic stream of targets, resources, and battlefield conditions and produce a continuously updated ATO. The ATO-Stream product dynamically considers a host of competing and changing priorities and evaluates changes in the status of air resources to perform continuous ATO planning and replanning.

Diagram depicting an overview of genetic processing. Percentages indicated are user-configurable.

The 21st Century Technologies team chose a genetic processing approach to solve the multiple-goal, multiple-constraint problems posed by ATO-Link and ATO-Stream. In this approach, each solution generates numerous ATOs with the routine, assigning each ATO a "fitness" score. The fitness score is a function of the quantity and attributes of all serviced targets, including aircraft characteristics, risk of aircraft loss, target size, and probability of target destruction. ATO solutions with the highest fitness scores—designated "elite"—live (unchanged) into the next generation, whereas solutions with the lowest scores immediately die out. The algorithm retains ATOs earning midrange scores, combining (breeding) them with elite solutions in the hope of forming ever-higher-scoring solutions in the next generation—solutions which would then replace the elite of the current generation. The algorithm thus mimics the biological "survive and reproduce" process. The accompanying figure depicts an overview of the genetic processing approach as applied to ATO planning.

The genetic processing approach is also easy to modify as ATO requirements and goals change. Using the alternative solution approach—linear programming—software engineers must rewrite the equations defining the system when requirements change. In the worst case, the new requirements may even change the problem beyond a linear state. Genetic processing, due to its dynamic nature, is thus a better-suited approach for solving problems with changing requirements—the very nature of a combat environment.

The ATO-Link and ATO-Stream packages augment the genetic algorithm framework, with the addition of expert system rules and conventional deterministic algorithms that result in improved processing speed and better results. At the end of a genetic algorithm's execution time, for example, planners can insert other, deterministic algorithms to assign any remaining unserviced targets to similarly unassigned resources. They can also inject such deterministic algorithms and rules to seed the genetic algorithm's first generation with reasonable solutions and to repopulate the solutions that die off each generation.

The ATO-Link and ATO-Stream software systems output a valid ATO that honors all imposed constraints and is tailored to the MAAP chief's objectives. Generating the optimal solution to the ATO problem is "NPhard" (a classification of the complexity of an algorithm employed in solving an NP, or nondeterministic polynomial, time problem). Therefore, it is unreasonable to expect the generation of an optimal ATO in a time frame suitable for the battlefield. Rather than seeking the optimal ATO, planners can instead specify the execution time of the genetic routine and quickly generate a "good" solution—an important strength of the genetic processing approach. Depending on the time available, the user can specify a 5 min, or even a 45 min, solution. In general, the longer operators allow the system to process, the more optimal the resulting ATO will be. Nevertheless, stopping system execution at any point beyond the shortest processing period still produces a complete, valid ATO solution optimized for the allotted execution time. With most linear programming algorithms, the flexibility of variable execution time is not available because there is an unknown, situation- or data-dependent, amount of computation time that yields a single solution rather than intermediate results.

After a series of successful demonstrations, the Air Force (AF) Command and Control (C2) Battlelab selected ATO-Link for participation in its FastMAAP initiative. As a FastMAAP partner, the C2 Battlelab deployed ATOLink during the Joint Expeditionary Force Experiment 2004 and used it to identify inconsistencies in other MAAP planning databases. C2 Battlelab planners compared the performance of ATO-Link to another optimizer in terms of overall acceptability of output, quality of optimizer feedback, quality of optimizer results, and processing speed. ATO-Link was significantly faster than the other firm's ATO optimizer; it computed 500 desired mean points of impact (DMPI) in 6 min, compared to the competing system's 200 DMPI computed in 15 min.

AFRL has targeted ATO-Link for product transition to the Air Operations Center Weapon System Block 10.2 and will leverage the success of ATO-Link to pursue commercialization of ATOStream. The ATO-Link and ATOStream technologies will enable the AF to maintain air superiority as a result of improved execution throughout the campaign, consequently saving lives and reducing costs.

Ms. Victoria Hwang, of the Air Force Research Laboratory's Information Directorate, wrote this article. For more information, access the Technical Support Package free online at http://www.afrlhorizons.com,  contact TECH CONNECT at (800) 203-6451, or place a request at http://www.afrl.af.mil/techconn_index.asp . Reference document IF-H-06-02.