Bounding optimal headings in the Dubins Touring Problem
Petr Váňa, Jan Faigl · Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing · 2022
The Dubins Touring Problem (DTP) stands to find the shortest curvature-constrained multi-goal path connecting a prescribed sequence of locations. The problem is to determine the optimal vehicle heading angle at each location and thus find the shortest sequence of Dubins paths. The heading angles can be determined by iterative refinement of possible heading intervals for which finer resolution yields a shorter path at the cost of increased computational requirements. In this paper, we introduce a novel method to bound the optimal heading angles by eliminating unpromising intervals that cannot contribute to the optimal solution. The method is employed in the branch-and-bound solution of the DTP, where it significantly reduces the search space in finding the optimal solution.