Reactive Dubins Traveling Salesman Problem for Replanning of Information Gathering by UAVs

Robert Pěnička, Martin Saska, Christophe Reymann and Simon Lacroix

Supporting material for ECMR 2017

Abstract

In this paper, we introduce a novel online replanning method for robotic information gathering by Unmanned Aerial Vehicles~(UAVs) which we call Reactive Dubins Traveling Salesman Problem~(RDTSP). In this task, a set of target locations of the required sensory measurement is given to be visited by the robot. From an initial information gathering plan, obtained as an offline solution of either the Dubins Traveling Salesman Problem~(DTSP) or the Coverage Path Planning~(CPP), the proposed RDTSP ensures robust information gathering in each given target location by replanning over possible missed target locations. Furthermore, a simple decision making is a part of the proposed RDTSP to determine which target locations are marked as missed and also to control appropriate time of applying the repair plan into the initial information gathering plan. The proposed method for replanning is based on the Variable Neighborhood Search metaheuristic which ensures visiting of all possibly missed target locations by minimizing the length of the repair plan and by utilizing the preplanned offline solution of the particular information gathering task. The novel method is evaluated in a realistic outdoor robotic information gathering experiment with UAV for both the Dubins Traveling Salesman Problem and the Coverage Path Planning scenarios.