Routing and Path Planning for a Dubins Vehicle

Project Summary

In this Project, the generation of an optimal sequence of visits of nodes for a Dubins vehicle was addressed. The generation of optimal paths for a Dubins vehicle was described, which includes the derivation of expressions for tangent lines and the angle traversed on a circle of a minimum turning radius. The optimal Dubins path was presented for two cases.

The generation of an optimal ring graph using the Lin-Kernighan-Helsgaun (LKH) algorithm is then discussed. Numerical results are presented for a set of 15 randomly generated nodes. The use of the Dubins result to generate the pairwise path length between nodes and a minimum spanning tree to obtain the lower and upper bounds for the optimal solution has been described for this case study. Finally, numerical results are presented for five more test runs, for which the optimal solution, the lower bounds, and the upper bounds are compared. The report is attached below for further elaboration.