Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points Academic Article uri icon


  • © 2017, Springer Science+Business Media Dordrecht (outside the USA). This article addresses an important path planning problem for robots and Unmanned Aerial Vehicles (UAVs), which is to find the shortest path of bounded curvature passing through a given sequence of target points on a ground plane. Currently, no algorithm exists 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 are solved using tools from optimal control theory. Using these approaches, two lower bounding algorithms are presented and these bounds are then compared with existing results in the literature. Computational results are presented to corroborate the performance of the proposed algorithms; the average reduction in the difference between upper bounds and lower bounds is 80 % to 85 % with respect to the trivial Euclidean lower bounds.

altmetric score

  • 3

author list (cited authors)

  • Manyam, S. G., Rathinam, S., Casbeer, D., & Garcia, E.

citation count

  • 21

publication date

  • January 2017