Dubins Orienteering Problem

 

Robert Pěnička, Jan Faigl, Petr Váňa and Martin Saska

Supporting material for RA-L and ICRA 2017

 

Abstract

In this paper, we address the Orienteering Problem (OP) for curvature constrained vehicle. For a given set of target locations, each with associated reward, the OP stands to find a tour from a prescribed starting location to a given ending location such that it maximizes collected rewards while the tour length is within a given travel budget constraint. The addressed generalization of the Euclidean OP is called the Dubins Orienteering Problem (DOP) in which the reward collecting tour has to satisfy the limited turning radius of the Dubins vehicle. The DOP consists not only of selecting the most valuable targets and determination of the optimal sequence to visit them, but it also involves the determination of the vehicle's heading angle at each target location. The proposed solution is based on the Variable neighborhood search technique and its feasibility is supported by an empirical evaluation in existing OP benchmarks. Moreover, an experimental verification in a real practical scenario further demonstrates the necessity of the proposed direct solution of the Dubins Orienteering Problem.

 

Video from outdoor experiment:

 

Path plan with traveled path from outdoor experiment using Euclidean Orienteering Problem and Dubins Orienteering Problem:

Tables with comparisons of Euclidean Orienteering Problem (EOP) and Dubins Orienteering Problem (DOP) on existing datasets:

The tables contains comparison with existing EOP approaches proposed by Chao et al., Four-phase heuristic, and the original VNS-based method. For individual budgets Tmax and radii ρ , the upper number indicates collcted maximal reward and the lower numbers shows average "number of iterations/computational time".