Shortest Dubins paths through three points. (July 2019)

• Record Type: Journal Article
• Authors: Chen, Zheng; Shima, Tal
• Is Part Of: Automatica. Volume 105(2019)
• Page Start: 368
• Page End: 375
• Publication Date: 2019-07
• Subjects: Dubins vehicle -- Traveling salesman problem -- Motion planning; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2019.04.007
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: The 3-Point Dubins Problem (3PDP) consists of steering a Dubins vehicle through three consecutive points with prescribed heading orientations at initial and final points so that the resulting path is the shortest. Characterizing the path of the 3PDP is important because (1) it provides insightful views on the solution paths of the Dubins Traveling Salesman Problem (DTSP) and the Curvature-Constrained Shortest-Path Problem (CCSPP) as they are natural extensions of the 3PDP and (2) some algorithms in the literature for solving the DTSP and the CCSPP require efficient methods for solving the 3PDP. In this paper, Pontryagin's maximum principle is used to show that the path of 3PDP must lie in a sufficient family of 18 types. Moreover, a formula in terms of the parameters of the 3PDP for all the 18 types is established, and this formula reveals the relationship between the unknown orientation angle at mid point and known parameters. By observing that the formula can be converted into some polynomials, the 3PDP can therefore be efficiently solved by finding zeros of those polynomials. Finally, numerical simulations illustrate the developments by comparing with the straightforward discretization-based method.