Online Stochastic UAV Mission Planning with Time Windows and Time-Sensitive Targets



In this presentation we simultaneously consider three extensions to the standard Orienteering Problem (OP) to model characteristics that are of practical relevance in planning reconnaissance missions of Unmanned Aerial Vehicles (UAVs). First of all, travel and recording times are uncertain. Secondly, the information about each target can only be obtained within a predefined time window. Due to the travel and recording time uncertainty, it is also uncertain whether a target can be reached before the end of its time window. Finally, we consider the appearance of new targets during the flight, the so-called time-sensitive targets, which need to be visited immediately if possible. We tackle this problem by introducing the Maximum Coverage Stochastic Orienteering Problem with Time Windows (MCS-OPTW), which balances two objectives. The first objective is to find a planned tour of maximum expected profit by selecting and sequencing a subset of the targets that were already known before the flight. The aim of the second objective, where we measure the ability of the UAV to timely reach time-sensitive targets, is to direct the planned tour to predefined areas where time-sensitive targets are expected to appear. We develop a fast heuristic that can be used to real-time re-plan the tour, each time before leaving a target. In our computational experiments we illustrate the benefits of the MCS-OPTW compared to a deterministic approach, with respect to dealing with uncertainty in travel and recording times and the appearance of time-sensitive targets.

  • Registration to Remy Spliet, is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars