Dubins Traveling Salesman Problem: Heading Discretization Look Ahead Algorithms  

The interest in autonomous vehicles, such as unmanned surface vehicles (USVs) and unmanned aerial vehicles (UAVs), has grown during the last years. These types of vehicles can be used for a number of civilian and military applications including intelligence, surveillance, and reconnaissance missions, as well as search and rescue operations. In this research, we study motion planning for a Dubins vehicle, i.e, a nonholonomic vehicle that is constrained to move in a constant speed without reversing along paths of bounded curvature in the plane. Motivated by autonomous vehicles` applications, we consider the traveling salesman problem for the Dubins vehicle (DTSP): finding the shortest path for a Dubins vehicle that has to visit a set of targets in the plane, and return to the starting point upon task completion. Decision variables include the visit order and the vehicle`s heading angle at each target. We discretize the DTSP by allowing a finite number of heading angles at each target.

We develop polynomial time algorithms that combine exact solutions to a mathematical program that finds minimal length sub-paths of the Discretized DTSP and a look ahead approach. We examine the performances of the suggested algorithms for three types of environments in which the targets are dispersed, mixed and crowded. An extensive  numerical study demonstrates that the suggested algorithms perform better than other alternatives. Finally, we demonstrate the ease of implementation of our approach using a robot that imitates a Dubins vehicle.