An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments

Adaptive and intelligent on-board path planning is a required part of a fully autonomous UAV. In controlled airspace, such a UAV would have to interact with other vehicles moving though its environment. The locations of obstacles (other vehicles) that form obstructions in the environment may only be known with limited accuracy. Evolutionary algorithms (EA) have been successfully used to compute near-optimal paths through obstructed, dynamically changing environments. Explicitly accounting for the uncertainty of the obstacles can result in the survival of "best" paths which differ from those that would be favored in a purely deterministic environment. In this paper, we consider the application of evolution-based path planning to the motion of an unmanned air vehicle (UAV) through a field of obstacles at uncertain locations. We begin with the static form of the EA algorithm for generating a path at a single point in time. We describe the algorithm and show its behavior, specifically how it responds differently based on the known accuracy of the predictions of the environment. We then show how the static structure can be extended to consider the uncertainties which change with time. We demonstrate by application to path planning through a field of moving obstacles whose future motion is uncertain.