Title
Online stochastic UAV mission planning with time windows and time-sensitive targets
Author
Evers, L.
Barros, A.I.
Monsuur, H.
Wagelmans, A.
Publication year
2014
Abstract
In this paper 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, 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, so-called time-sensitive targets, which need to be visited immediately if possible. We tackle this online stochastic AV mission planning problem with time windows and time-sensitive targets using a re-planning approach. To this end, we introduce the Maximum Coverage Stochastic Orienteering Problem with Time Windows (MCS-OPTW). It aims at constructing a tour with maximum expected profit of targets that were already known before the flight. Secondly, it directs the planned tour to predefined areas where time-sensitive targets are expected to appear. We have developed a fast heuristic that can be used to re-plan the tour, each time before leaving a target. In our computational experiments we illustrate the benefits of the MCS-OPTW planning approach with respect to balancing the two objectives: the expected profits of foreseen targets, and expected percentage of time-sensitive targets reached on time. We compare it to a deterministic planning approach and show how it deals with uncertainty in travel and recording times and the appearance of time-sensitive targets
Subject
Operations Modelling
MO - Military Operations
ELSS - Earth, Life and Social Sciences
Defence Research
Operations Research
Defence, Safety and Security
Stochastic orienteering problem
Time windows
Online planning
Unmanned Aerial Vehicles UAV
Mission planning
To reference this document use:
http://resolver.tudelft.nl/uuid:18e29e8a-3bad-4a74-8c3b-26526d9594e3
DOI
https://doi.org/10.1016/j.ejor.2014.03.014
TNO identifier
492778
Source
European Journal of Operational Research, 239 (1), 348-362
Bibliographical note
Article available online 17 March 2014
Document type
article