Optimal Trajectory Planning for Multiple Waypoint Path Planning using Tabu Search
Karthika Balan, Chaomin Luo · 2018
A Tabu search algorithm associated with multiple waypoint real-time path planning and map building such as Traveling Salesman Problem is proposed in this paper. This application plays a major role in actual world scenarios just as the ones encountered by the robots functioning in disaster prone environments like service, rescue, mining robots, etc., where there is a need for the robot to travel to collective goals through the shortest distance possible. This paper examines the use of one such algorithm, Tabu search, for finding the shortest path possible. It basically does neighborhood search with a set of nodes termed as Tabu list, which comprises of nodes that have been previously evaluated, thereby avoiding getting stuck in the local minima. During every new iteration, the recent search candidates are compared with the best solution found so far, so that the best possible node is retained for later use. This strategy enables an autonomous robot to travel to multiple goals using the shortest possible path. As soon as a global route is generated by the Tabu search, a D*-Lite algorithm combined with VFH based local navigation is laid on to plan a collision less trajectory through a contour with simultaneous map building under unknown environments.