A Genetic Programming Methodology for Strategy Optimization
Under Uncertainty
Frank W. Moore
Department of Computer Science and Engineering
Wright State University, Dayton, OH 45435
fmoore@cs.wright.edu
ABSTRACT
This poster paper summarizes ongoing dissertation research defining a genetic programming (GP) methodology for solving strategy optimization problems for intelligent, autonomous agents operating under conditions of uncertainty. This dissertation provides an overview of current state-of-the-art approaches to strategy optimization problems; defines the Missile Countermeasures Optimization (MCO) problem as an instance of a strategy optimization problem; describes various types and degrees of uncertainty that may be introduced into the MCO problem; and develops a new methodology for solving the MCO problem under conditions of uncertainty. The new methodology promises significant improvements over current control-theoretic and analytical approaches.
Phase I of this research establishes a GP methodology for solving the MCO problem. The Extended Two-dimensional Pursuer/Evader (E2dPE) problem is an abstracted, simplified MCO problem that models an evading aircraft and a pursuing surface-launched anti-aircraft missile (SAM) as point masses that use thrusting and turning forces to control their trajectory across a plane. The pursuer uses proportional navigation to pursue and destroy the evader. GP is used to evolve control programs that optimize evader survivability.
Best-of-run programs evolved by GP systems frequently prove to be brittle when subsequently used in situations not explicitly anticipated during program evolution. Phase II investigates the technique of randomly selecting a new set of fitness cases prior to evaluation of each generation of the E2dPE problem, and determines whether this technique helps evolve best-of-run programs that are less brittle than programs evolved using fixed training populations.
Uncertainty introduces a degree of complexity that is difficult to model using traditional analytical methods. Best-of-run programs evolved for one type of pursuer generally exhibit sub-optimal performance when subsequently tested against other pursuer types. Phase III introduces uncertainty about the type of pursuer, and evolves programs that solve the E2dPE problem for pursuer populations described by a probability distribution over possible types. During many encounters, the current state of the SAM (its relative displacement, velocity, and acceleration) may also be unknown or uncertain. Phase IV investigates the impact of uncertainty about the pursuer’s state, evolves programs under various conditions of uncertainty, and establishes upper and lower bounds on the probable fitness of the resulting best-of-run programs.
For many encounters, maneuvers alone are inadequate to successfully evade an incoming SAM. For this reason, modern aircraft combine the use of chaff, flares, jamming, and other countermeasures with maneuvers to increase survivability. In general, the effectiveness of these countermeasures depends upon the state of the aircraft and SAM at the time the countermeasure is deployed. Phase V introduces the use of additional countermeasures into the E2dPE problem, and evolves programs that combine these countermeasures with maneuvers to optimize evader survivability. This dissertation concludes during Phase VI by extending the GP methodology of Phases I-V to solve the three-dimensional MCO problem.
The author gratefully acknowledges Wright State University and the Dayton Area Graduate Studies Institute for its support of this research.