Applications of Traveling Salesman Problem Solvers for Path Planning of Parallel Robots

In industrial settings, for instance in pick-and-place operations, a robot may be required to visit some target points. In some tasks, such as spot soldering, the visiting order can be chosen freely: this allows us to optimize the motion, by finding the shortest path that visits all points before returning to the starting one. This is an instance of the Traveling Salesman Problem (TSP), a classic problem in operations research, for whose solution several algorithms and software libraries are available. The TSP is commonly applied in mobile robotics, for example in drones, and to serial robot arms. Here, we apply the TSP to parallel robots, where the base is connected to the end-effector (EE) by multiple kinematic chains. We show how to define the TSP in this case to minimize the motion time, assumed to be proportional to the largest absolute variation in joint coordinates. We then show that this is not equivalent to minimizing the distance traveled by the EE. We also compare the performance of different solvers on an example problem and for an example planar parallel robot, in terms of the time for converging to a solution. We consider both heuristic methods, which are generally fast but may not always find the optimal solution, and exact solvers, which can be used as a reference. This can improve the efficiency of industrial parallel robots, coherently with the objectives of the UN Sustainable Development Goal (SDG) 7.