Motion planning algorithms for the Dubins Travelling Salesperson Problem. (March 2015)

• Record Type: Journal Article
• Authors: Isaiah, Pantelis; Shima, Tal
• Is Part Of: Automatica. Volume 53(2015)
• Page Start: 247
• Page End: 255
• Publication Date: 2015-03
• Subjects: Trajectory planning -- Algorithms -- Optimal control -- Autonomous vehicles; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2014.12.041
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: 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.