A Hybrid Multi-Population Genetic Algorithm for UAV Path Planning

Abstract

This paper proposes a hybrid method to define a path planning for unmanned aerial vehicles in a non-convex environment with uncertainties. The environment becomes non-convex by the presence of no-fly zones such as mountains, cities and airports. Due to the uncertainties related to the path planning in real situations, risk of collision can not be avoided. Therefore, the planner must take into account a lower level of risk than one tolerated by the user. The proposed hybrid method combines a multi-population genetic algorithm with visibility graph. This is done by encoding all possible paths as individuals and solving a linear programming model to define the full path to be executed by the aircraft. The hybrid method is evaluated from a set of 50 maps and compared against an exact and heuristic approaches with promising results reported.