Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle

Abstract

Multi-goal curvature-constrained planning such as the Dubins Traveling Salesman Problem (DTSP) combines NP-hard combinatorial routing with continuous optimization to determine the optimal vehicle heading angle for each target location. The problem can be addressed as combinatorial routing using a finite set of heading samples at target locations. In such a case, optimal heading samples can be determined for a sequence of targets in polynomial time, and the DTSP can be solved as searching for a sequence with the minimal cost. However, the examination of sequences can be computationally demanding for high numbers of heading samples and target locations. A fast rejection schema is proposed to quickly examine unfavorable sequences using lower bound estimation of Dubins tour cost based on windowing technique that evaluates short subtours of the sequences. Furthermore, the computation using small problem instances can benefit from reusing stored results and thus speed up the search. The reported results indicate that the computational burden is decreased about two orders of magnitude, and the proposed approach supports finding high-quality solutions of routing problems with Dubins vehicle.