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

Marco Frego; Paolo Bevilacqua; Enrico Saccon; Luigi Palopoli; Daniele Fontanelli

RA-L 202012 citations

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

Marco Frego, Paolo Bevilacqua, Enrico Saccon, Luigi Palopoli, Daniele Fontanelli

Abstract

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.

BibTeX

@inproceedings{ral2020_aniterativedynam,
  title = {An Iterative Dynamic Programming Approach to the Multipoint Markov-Dubins Problem},
  author = {Marco Frego and Paolo Bevilacqua and Enrico Saccon and Luigi Palopoli and Daniele Fontanelli},
  booktitle = {RA-L 2020},
  year = {2020}
}