An Iterative Dynamic Programming Approach to the Multipoint Markov-Dubins Problem

A new solution to the multipoint Markov-Dubins problem via iterative dynamic programming is herein presented. The shortest path problem connecting a sequence of given points in the plane while maintaining angle continuity and bounded curvature is presented. As in the classic two points Dubins problem, the solution is a juxtaposition of line segments and circle arcs. This problem is relevant for the path planning of a non-holonomic robot, such as a wheeled vehicle. The proposed method is robust and computationally inexpensive with respect to existing solutions and is therefore suitable to be integrated as motion primitive into Dubins-based applications, e.g. orienteering problems or waypoint following robotics.