Zheng Chen (Technion) – Shortest Dubins Paths through Three Points
Friday 6 July 2018, 11:00-12:00 (salle Galois Coriolis, Inria Sophia)
Abstract. The Dubins vehicle, moving only forward at a constant speed with a minimum turning radius, provides a good kinematic prototype for various types of nonholonomic robots, such as unmanned aerial vehicles and fixed-wing aircrafts. In this work, the 3-Point Dubins Problem (3PDP), which consists of steering such vehicles through three consecutive points with prescribed heading orientations at initial and final points, is thoroughly studied. By applying the Pontryagin Maximum Principle, some necessary conditions are formulated and studied so that some geometric properties for the 3PDP are presented. As a result, we are able to show that the shortest path of 3PDP must lie in a sufficient family of eighteen candidates. Moreover, a common formula is established for the eighteen candidates and analysing this formula from a geometric point of view not only covers existing results in the literature but also presents new geometric properties for the solution path of 3PDP. By observing that the common formula can be converted into some polynomials, the 3PDP can therefore be efficiently solved by finding zeros of those polynomials. As an application of the polynomial-based solution, an efficient gradient-free descent method is employed for solving a typical heuristic variant of the Dubins Traveling Salesman Problem, which is crucial for motion planning of unmanned aerial vehicles.