The Online UAV Mission Planning Problem

Abstract

In the Online UAV Mission Planning Problem a reconnaissance mission has to be planned in a given area that contains both targets that are given beforehand and new targets that arise during the flight. The goal of the mission is to gather information from a subset of the targets, in such a way that the gathered amount of information is maximal, whilst keeping the fuel required for the mission within predefined limits. We developed five strategies by which the planned tour can be reoptimized during the flight, either for the general problem where the new targets appear in the entire target area, or for the special case where all new targets appear in some prespecified zone. All strategies were composed of two steps: finding an optimal initial tour first and adjusting the tour later on during the flight, when information about new targets was released. Theoretical as well as empirical performance bounds were found for the strategies that were developed for the general problem. Finally, the performance of the strategy for the special case was compared to the performance of the other strategies, when applied to this case.