Autonomous Navigation Control of UAVs Using Genetic Programming

Introduction: An autonomous navigation capability is required for unmanned air vehicles (UAVs) used in electronic warfare applications. Because the electronic battlefield is dynamic, UAVs will need to move reactively to threat locations in ways that cannot be preprogrammed. We have created a new approach that satisfies both the autonomy and optimization needs of UAV navigation by using an artificial intelligence technique. This new approach is quite distinct from current preprogrammed waypoint navigation methods. Genetic programming (GP)1 is used to create an algorithm that uses noisy and relatively crude input sensor data to generate roll-angle commands for UAV flight control.

Genetic Programming: GP is a computation technique to evolve near-optimized computer programs that produce some desired output when presented with particular input. GP is based on LISP-like expressions1 and operates on tree data structures. In GP, populations of hundreds or thousands of computer programs are genetically bred. This breeding is done using the Darwinian principle of survival and reproduction of the fittest, along with a genetic recombination (crossover) operation appropriate for mating computer programs. Figure 5 is a flowchart for a GP evolutionary computational process. The inputs to the GP are function and terminal sets. A fitness function evaluates each member (program) of the population over each cycle of the computation. To evolve a successful program (rule tree), function sets, terminal sets, and fitness measures must be designed that are appropriate and effective for the specific application.

FIGURE 5
Flowchart of GP computational procedure. Index i refers to an individual in the population of size M. The variable Gen is the number of the current generation. The Pr and Pm are crossover and mutational rate, respectively.

Electronic Warfare Simulation Environment: The simulation environment is a square, 100 nmi on each side. The simulator gives the UAV a random initial position in the middle half of the southern edge of the environment and the radar site a random position within the environment. The navigation controller receives only two pieces of information as input: the amplitude and the angle of arrival (AoA) of incoming radar signals. The navigation controller then changes the desired roll angle of the UAV control surface based on the GP-developed control algorithm. For this first stage of research, a stationary, continuously emitting radar is used as the signal source. To increase the robustness of the system, only the sidelobes of the radar emissions are modeled. Gaussian noise is added to the radar signal. Also, the simulation models an imprecise AoA. The main goal of the controller is to autonomously move the UAV to the vicinity of the radar as quickly and efficiently as possible and then circle around the radar.

Evolving UAV Navigation Control Logic: There are two sensor inputs: amplitude of the incoming radar signal and its angle of arrival. The UAV is modeled to have a GPS onboard, therefore position information is available. Additionally, the slope of the signal amplitude is made available. A function set was constructed with nearly 30 members, most of which are common operators (+, >, IfThen, etc.) typical of GP experiments, and some are specific to this problem such as AoA > 0 or AmplitudeSlope < 0. When turning, six actions (terminal sets) are available. Turns may be hard (10° changes in the roll angle) or shallow (2° changes) in left and right. The WingsLevel terminal sets the roll angle to 0°, and the NoChange terminal keeps the roll angle the same. The fitness measure to optimize the flight path is to minimize the distance between the UAV and the radar. Because of the intensive computational power required to evolve rule sets by GP, all evolutionary computations were done on a Beowulf cluster parallel computer with 92 2.4 GHz Pentium 4 processors.

New Autonomous UAV Navigation Controller: Figure 6 shows best, worst, and average fitness profiles over 500 generations. Figure 7 shows the UAV flight paths of UAV for an evolved controller when using the near-optimal control logic generated by GP. The evolved controllers were able to overcome a noisy environment and inaccurate sensor data in tracking and locating a radar site. A significant aspect of the research was developing the right function and terminal sets for the problem as well as fitness measures that would generate a realistic control command rule set for realizable UAV navigation.

FIGURE 6
Fitness score profiles over 500 generations. Average fitness score is calculated over 500 individuals.

FIGURE 7
UAV flight path from (49, 0) to the target radar located at (46, 88).

Summary: In simulation using GP, we were able to evolve navigation controllers for UAVs capable of flying to a target radar while using inaccurate sensor inputs in a noisy environment. We selected realistic flight parameters and sensor inputs to aid the transference of the controllers evolved in simulation to real UAVs. The next stage is to demonstrate the method in hardware by having a UAV autonomously navigate under the command of GP evolved control logic.

[Sponsored by ONR]