Penicka, Robert (Czech Technical University in Prague, Faculty of Electrical Engi), Faigl, Jan (Czech Technical University in Prague), Váňa, Petr (Czech Technical University in Prague), Saska, Martin (Czech Technical University in Prague)

Dubins Orienteering Problem with Neighborhoods

Scheduled for presentation during the "Path Planning - V" (FrB3), Friday, June 16, 2017, 14:25−14:45, Salon CD

2017 International Conference on Unmanned Aircraft Systems, June 13-16, 2017, Miami Marriott Biscayne Bay, Miami, FL,

This information is tentative and subject to change. Compiled on April 19, 2024

Abstract

In this paper, we address the Dubins Orienteering Problem with Neighborhoods (DOPN) a novel problem derived from the regular Orienteering Problem (OP). In the OP, one tries to find a maximal reward collecting path through a subset of given target locations, each with associated reward, such that the resulting path length does not exceed the specified travel budget. The Dubins Orienteering Problem (DOP) requires the reward collecting path to satisfy the curvature-constrained model of the Dubins vehicle while reaching precise positions of the target locations. In the newly introduced DOPN, the resulting path also respects the curvature constrained Dubins vehicle as in the DOP; however, the reward can be collected within a close distant neighborhood of the target locations. The studied problem is inspired by data collection scenarios for an Unmanned Aerial Vehicle (UAV), that can be modeled as the Dubins vehicle. Furthermore, the DOPN is a useful problem formulation of data collection scenarios for a UAV with the limited travel budget due to battery discharge and in scenarios where the sensoric data can be collected from a proximity of each target location. The proposed solution of the DOPN is based on the Variable Neighborhood Search method, and the presented computational results in the OP benchmarks support feasibility of the proposed approach.