On the Discretized Dubins Traveling Salesman Problem

摘要

This paper deals with minimizing the visitation cost of a kinematicrnconstrained vehicle through a set of targets. We are motivated by real{rnworld scenarios that include motion planning for manned and unmannedrnmarine and aerial vehicles and motion planning for robots, just to namernsome possible application outlets. We discretize the original continuousrnproblem and explicitly formulate it as an integer optimization problem.rnThen we analyze its performance and develop an upper bound as a func-rntion of the discretization level and the number of targets. The suggestedrnlinkage between discretization level, number of targets and performancernprovides an opportunity to guide discretization level choices for the so-rnlution of motion planning scenarios.