Dubins paths through a sequence of points: Lower and upper bounds

Abstract

This article addresses an important path planning problem for robots and Unmanned Aerial Vehicles (UAVs) which aims to find a shortest path of bounded curvature passing through a given sequence of target points on a ground plane. Currently, there is no algorithm that can compute an optimal solution to this problem. Therefore, tight lower bounds are vital in determining the quality of any feasible solution to this problem. Novel tight lower bounding algorithms are presented in this article by relaxing some of the heading angle constraints at the target points. The proposed approach requires us to solve variants of an optimization problem called the Dubins interval problem between two points where the heading angles at the points are constrained to be within a specified interval. These variants can be solved using tools from optimal control theory. Specifically, two lower bounding algorithms are presented in this article using this approach and these bounds are then compared with the existing results in the literature. Computational results are also presented to corroborate the performance of the proposed algorithms.