Optimum path planning using convex hull and local search heuristic algorithms

Whether in improving quality or productivity the impact of mechatronic systems such as robots in industry is unquestionable. One aspect of interest in robotics is planning the optimum path for a mobile robot or the optimum trajectory for link movements of a stationary robot in order to increase their efficiency. However, for a given set of points complete enumeration of all the possible paths to establish an optimal one is not feasible as the search space increases exponentially (explodes combinatorially) as the number of points increases. This problem, traditionally known as the "Traveling Salesman Problem" (TSP) has attracted a great deal of attention for a long time. Proven enumerative techniques such as "nearest neighbour algorithm", "branch and bound", "cutting planes", and "dynamic programming" as well as approximation methods such as "tabu search", "greedy algorithm", "simulated annealing" and "genetic algorithm", have had only a limited success in solving this problem. Recently "convex hull", a minimum area and perimeter shape, has been used as an initial sub-tour along with enumerative techniques such as minimising insertion costs to solve the TSP problem. We present a system which uses heuristic rules to augment the convex hull initial sub-tour created by the Graham scan algorithm. The system is able to provide a solution in a polynomial time.