The Orbiting Dubins Traveling Salesman Problem: planning inspection tours for a minehunting AUV

The Orbiting Dubins Traveling Salesman Problem (ODTSP) is to plan a minimum-time tour for a Dubins vehicle model to inspect a set of targets in the plane by orbiting each target along a circular arc. This problem arises in underwater minehunting, where targets are mine-like objects on the sea bottom that are inspected by a sonar-equipped underwater vehicle. Each orbit subtends a prescribed angle so that the target’s acoustic response is measured from a variety of target-sensor relative geometries to aid in classifying it. ODTSP tours consist of circular-arc orbits joined by Dubins paths, and the optimization problem is to partition the set of targets into orbits and determine the position, radius, direction, and vehicle entry angle of each. Algorithms are presented for the restricted case, where each orbit inspects a single target (only), and the general case, where orbits inspect multiple targets. The approach is facilitated by analytical conditions that identify admissible clusters of targets as cliques of a disk graph. The ODTSP is extended to consider path planning in the presence of a steady uniform current.