Ing. Robert Pěnička presents Data Collection Planning for Distance and Curvature constrained UAV

On 2019-03-07 14:30:00 at E112, Karlovo náměstí 13, Praha 2
Title 1:
Data Collection Planning with Non-zero Sensing Distance for a Budget and
Curvature Constrained Unmanned Aerial Vehicle

Abstract 1:
Data collection missions are one of the many effective use cases of Unmanned
Aerial Vehicles (UAVs), where the UAV is required to visit a predefined set of
target locations to retrieve data. However, the flight time of a real UAV is
time constrained, and therefore only a limited number of target locations can
typically be visited within the mission. In this paper, we address the data
collection planning problem called the Dubins Orienteering Problem with
Neighborhoods (DOPN), which sets out to determine the sequence of visits to the
most rewarding subset of target locations, each with an associated reward,
within a given travel budget. The objective of the DOPN is thus to maximize the
sum of the rewards collected from the visited target locations using a budget
constrained path between predefined starting and ending locations. The variant
of the Orienteering Problem (OP) addressed here uses curvature-constrained
Dubins vehicle model for planning the data collection missions for UAV.
Moreover, in the DOPN, it is also assumed that the data, and thus the reward,
may be collected from a close neighborhood sensing distance around the target
locations, e.g., taking a snapshot by an onboard camera with a wide field of
view, or using a sensor with a long range. We propose a novel approach based on
the Variable Neighborhood Search (VNS) metaheuristic for the DOPN, in which
combinatorial optimization of the sequence for visiting the target locations is
simultaneously addressed with continuous optimization for finding Dubins
waypoints inside the neighborhoods of the visited targets. The proposed
VNS-based DOPN algorithm is evaluated in numerous benchmark instances, and the
results show that it significantly outperforms the existing methods in both
solution quality and computational time. The practical deployability of the
proposed approach is experimentally verified in a data collection scenario with
a real hexarotor UAV.

Title 2:
Variable Neighborhood Search for the Set Orienteering Problem and its
application to other Orienteering Problem variants

Abstract 2:
This paper addresses the recently proposed generalization of the Orienteering
Problem (OP), referred to as the Set Orienteering Problem (SOP). The OP stands
to find a tour over a subset of customers, each with an associated profit, such
that the profit collected from the visited customers is maximized and the tour
length is within the given limited budget. In the SOP, the customers are
in clusters, and the profit associated with each cluster is collected by
visiting at least one of the customers in the respective cluster. Similarly to
the OP, the SOP limits the tour cost by a given budget constraint, and
therefore, only a subset of clusters can usually be served. We propose to
the Variable Neighborhood Search (VNS) metaheuristic for solving the SOP. In
addition, a novel Integer Linear Programming (ILP) formulation of the SOP is
proposed to find the optimal solution for small and medium-sized problems.
Furthermore, we show other OP variants that can be addressed as the SOP, i.e.,
the Orienteering Problem with Neighborhoods (OPN) and the Dubins Orienteering
Problem (DOP). While the OPN extends the OP by collecting a profit within the
neighborhood radius of each customer, the DOP uses airplane-like smooth
trajectories to connect individual customers. The presented computational
results indicate the feasibility of the proposed VNS algorithm and ILP
formulation, by improving the solutions of several existing SOP benchmark
instances and requiring significantly lower computational time than the
Responsible person: Petr Pošík