Genetic algorithms for shortest path routing of autonomous gliders

Abstract

Onboard power resources pose inevitable limitations on the flight performance of any aerial vehicle regardless of its type, size or mission. Popular soaring techniques recognized to be providing significant energy savings are primarily based on climbing air currents with upward trends called thermals. Intelligent routing strategies yet need to be developed in order to increase the autonomy of the vehicles applying soaring flight methods. One of the main concerns associated with the thermals is their physical nature which requires addressing non-stationary rising air currents potentially drifting in time. In such dynamic applications the performance of the routing schemes evaluated a priori deviates from the optimal one. If the changes on the thermal map are accommodated using online soaring algorithms, an emerging discussion would be focused on the extent to which the prohibitive computational costs of these routing strategies can be supported. In this paper we propose a path planning algorithm serving the purpose of energy efficient soaring route generation with the requirements formulated in the form of a Vehicle Routing Problem (VRP). We define the flight mission of the autonomous aerial vehicle as reaching the assigned destination in minimum time with no expenditure of an onboard power supply and interpret this formulation as Shortest Path (SP) routing. Genetic Algorithms (GAs) based on the natural evolution paradigm are used to reach near-optimal solutions. Accordingly, the thermal locations are represented by the genes on the chromosomes describing the feasible thermal soaring routes. A specific problem scenario is presented for an Unmanned Aerial Vehicle (UAV) where the flight path generated via GAs is compared to the solution reached by an available exact thermal soaring algorithm. Simulation results are provided to confirm the route reached by the GAs to be coinciding with the optimal route obtained by iterating the Floyd-Warshall (FW) Algorithm. © 2008 by the American Institute of Aeronautics and Astronautics, Inc.