On Autonomous Vehicles and Planning Efficient Routes

http://commons.wikimedia.org
ISE Magazine – Volume 49 : Number 01

During the last decade, autonomous vehicles have become increasingly popular substitutes for manned vehicles in the civil and military arenas. Civil applications include seafloor mapping and data gathering, Military applications include clearing minefields in hostile areas, reconnaissance and intelligence gathering. For such missions, the vehicle route and order of tasks need to be planned. In a closely packed environment, optimally ordering the tasks depends on the vehicle’s kinematic constraints, e.g., its minimum turn radius.

Researchers investigate this route planning problem in “On the Discretized Dubins Traveling Salesman Problem.” In this version of the wellknown traveling salesman problem, the route length to be minimized depends on the kinematic capabilities of the vehicle, not just the distance between tasks.

The modeling approach replicates each city/task to be visited and assigns it a different visitation heading angle by the vehicle. The discretization of visitation heading enables using efficient graph search techniques and achieves tighter performance bounds on route lengths compared to other available approaches.  The research provides practical guidelines, such as indicating that low discretization values of the visitation heading angle, as low as four or eight (i.e., 90 or 45 degrees), may be suitable for many practical applications since they achieve shorter computational times and tour lengths compared to other solutions.