Evolutionary Approaches to Path Planning Through Uncertain Environments
David B. Rathbun, Brian J. Capozzi · 1st UAV Conference · 2002
Evolutionary algorithms (EA) have been successfully used to compute near-optimal paths through obstructed, dynamically changing environments. The locations of the obstacles that form the obstructions in these environ-ments may only be known with limited accuracy. Ex-plicitly accounting for this uncertainty 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. Specifically, we focus on the “cost function” utilized by the evolutionary algorithm to judge the like-lihood of a given path successfully traversing the uncer-tain environment. We first show a method for computing a cost function based on the exact probability of inter-section of the vehicle with an obstacle. A more compu-tationally tractable approximation technique for this cost function is then derived. Both cost functions are com-pared to the weighted graph search technique found in much of the literature on path planning.