Motion planning algorithms for the Dubins Travelling Salesperson Problem

Two motion planning algorithms for the so-called Dubins Travelling Salesperson Problem are presented, and compared via simulations with existing algorithms from the literature. The first algorithm-dubbed “k-step look-ahead algorithm”-stems naturally from the formulation of the Dubins Travelling Salesperson Problem as a minimum-time control problem and is suitable for obtaining short tours when the number of cities is relatively small. The second algorithm is an adaptation of the classic 2-Opt algorithm for the Travelling Salesperson Problem and can be applied to larger instances of the Dubins Travelling Salesperson Problem. In this sense, the two algorithms complement each other in terms of their range of applicability. Instead of being decoupled, the combinatorial and motion planning aspects of the Dubins Travelling Salesperson Problem are treated in an integrated manner by both algorithms and no assumptions are made on the magnitude of the intercity distances.