Paper Info
Title
Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points.
Abstract
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.
Year
DOI
Venue
2017
https://doi.org/10.1007/s10846-016-0459-4
Journal of Intelligent and Robotic Systems
Keywords
Field
DocType
Dubins paths,Curvature constrained paths,Lower bounds,Pontryagin’s minimum principle,Dubins interval problem
Motion planning,Mathematical optimization,Optimal control,Shortest path problem,Ground plane,Euclidean geometry,Robot,Optimization problem,Mathematics,Bounding overwatch
Journal
Volume
Issue
ISSN
88
2-4
0921-0296
Citations 
PageRank 
References 
1
0.35
18
Authors
4
Name
Order
Citations
PageRank
Satyanarayana G. Manyam1106.26
Sivakumar Rathinam221623.81
David W. Casbeer346147.13
Eloy Garcia410513.99