Markov–Dubins path via optimal control theory

• Published in: Computational optimization and applications 2017-12, Vol.68 (3), p.719-747
• Main Author: Kaya, C. Yalçın
• Format: Article
• Language: English
• Subjects: Control theory; Convex and Discrete Geometry; Curvature; Management Science; Markov processes; Mathematics; Mathematics and Statistics; Maximum principle; Numerical analysis; Operations Research; Operations Research/Decision Theory; Optimal control; Optimization; Statistics; Tangents
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-017-9923-8

Markov–Dubins path is the shortest planar curve joining two points with prescribed tangents, with a specified bound on its curvature. Its structure, as proved by Dubins in 1957, nearly 70 years after Markov posed the problem of finding it, is elegantly simple: a selection of at most three arcs are concatenated, each of which is either a circular arc of maximum (prescribed) curvature or a straight line. The Markov–Dubins problem and its variants have since been extensively studied in practical and theoretical settings. A reformulation of the Markov–Dubins problem as an optimal control problem was subsequently studied by various researchers using the Pontryagin maximum principle and additional techniques, to reproduce Dubins’ result. In the present paper, we study the same reformulation, and apply the maximum principle, with new insights, to derive Dubins’ result again. We prove that abnormal control solutions do exist. We characterize these solutions, which were not studied adequately in the literature previously, as a concatenation of at most two circular arcs and show that they are also solutions of the normal problem. Moreover, we prove that any feasible path of the types mentioned in Dubins’ result is a stationary solution, i.e., that it satisfies the Pontryagin maximum principle. We propose a numerical method for computing Markov–Dubins path. We illustrate the theory and the numerical approach by three qualitatively different examples.