The Traveling Salesman Problem in parallel robotics: definitions, optimization and performance

The Traveling Salesman Problem in parallel robotics: definitions, optimization and performance Giovanni Mottola1, Pietro Davide Maddio2, Alessandro Cammarata2, Rosario Sinatra2, Francesca Garescì1 1Department of Engineering, University of Messina, Messina, Italy 2Department of Civil Engineering and Architecture, University of Catania, Catania, Italy Contact author: Giovanni Mottola, email: giov[email protected] Abstract—A frequent task for industrial robots is to visit a set of target points in a closed path. If the sequence of operations is not constrained by the task, one may wish to minimize the path length. This means solving a Traveling Salesman Problem (TSP), a classic topic in Operations Research. The TSP has already been applied to mobile robots and to serial manipulators. We formulate the TSP for parallel robots, whose end-effector is connected to the base by two or more kinematic chains. We define the goal function as the maximum absolute change in joint coordinates (for all motors), which we take as proportional to the task time. We show that this is not equivalent to minimizing the geometric distance. Finally, we benchmark representative TSP solvers on an example planar robot, comparing heuristic methods and an exact solver based on mixed integer programming, which provides a reference optimal solution. We then report the solution time and quality. Our results show that TSP-based path planning with appropriate definitions can improve the efficiency of parallel robots. Index Terms—parallel robot, path planning, kinematics, TSP I. Introduction Many tasks performed by industrial robots, such as pickand-place operations, spot soldering, and drilling, require the end-effector (EE) to pass through a set of points, but set no constraints on the visiting order. Thus, the order can be chosen to minimize task time or energy consumption. This is essentially a form of the Traveling Salesman Problem (TSP), a well-studied combinatorial problem for which many algorithms are known. The TSP is widely applied in mobile robotics [ 2 ] and for serial robots [ 3 , 4 ]. Parallel robots (PRs), whose EE is moved by at least two kinematic chains, have received less attention in this sense; their path is often chosen manually, which is tedious and time-consuming. PRs have better stiffness and dynamic performances (but also more complex kinematics) than serial arms. Previous works considered very specific applications, such as Delta robots in agriculture [ 5 ] or over conveyor belts [ 6 ]. Some TSP solvers are heuristic [ 6 ] and may find less than (but always close to) optimal solutions. Others are exact [ 5 ]: they guarantee optimality but are more computationally expensive. Our research question is: how should the TSP be adapted to PRs? We pick a simple design and show that a naive form of the TSP may give suboptimal solutions in joint space. We propose a different definition, compatible with existing solvers; we then compare their convergence times and solution quality, using a Python code we developed to solve the TSP for PRs. The financial support of PRIN project number 20225YF2S4 is gratefully acknowledged. An early version of this work was presented at the I4SDG Conference, Jun. 9–12, 2025, Villa San Giovanni, Italy [1]. 20 40 60 80 100 0 10 20 30 40 50 Number of points 𝑁 (𝛥′ 𝐶−𝛥′ 𝐽)/𝛥′ 𝐽[%] Figure 1. relative joint-space cost increase (100 problems for each 𝑁). II. Definitions The standard formulation of the TSP is as follows: given the matrix D =(𝑑𝑖 𝑗 ) of the distances 𝑑𝑖 𝑗 between any two 𝑃𝑖 and 𝑃𝑗 in a set Sof 𝑁 points, find the permutation 𝜎 of S with minimal total cost 𝛥=Í𝑑𝑖 𝑗 . Each point is visited once; without loss of generality, set 𝑃1as the first and last point1. Abrute force approach, where all 𝑁 !permutations are considered, cannot be used in practice save for very small problems. In our tests, we used Concorde, a state-of-the-art tool, generally considered the fastest exact TSP solver [ 7 ]. For comparison, we also considered two heuristic algorithms, namely, Simulated Annealing (SA) and Iterated Local Search (ILS): the solution they find at each run (for a given D) may change, but is always close to the optimum from Concorde. As a proof of concept, we consider one of the simplest non-trivial PR designs, namely, the planar PR in [ 1 , Fig. 2]. It has five links and five rotary joints, two of which (connected to the fixed frame 0) are actuated. The joint coordinates are angles 𝜃1 and 𝜃4 , which control the motion of point 𝑃 (fixed on link 2). 𝑃 has position [𝑥𝑝0, 𝑦𝑝0]𝑇 in fixed frame F0 . F0 has origin 𝑂0 at the joint between links 0 and 1, and axis 𝑋0 directed toward 𝑂4 (between 0 and 4). The design is defined by the link lengths 𝑙𝑖 and by the coordinates [𝑥𝑝2, 𝑦𝑝2]𝑇 of 𝑃 in the moving frame F2 attached to 2 (with origin in 𝑂2 and axis 𝑋2 directed toward 𝐶 , between 2 and 3). These parameters are defined in a configuration file, loaded by our code at runtime. For a given 𝑃≡𝑃𝑖∈ S, there are up to four [ 1 ] possible vectors of joint coordinates (which are found solving the inverse kinematics, or IK), each defining a configuration. Switching between configurations can be of interest [ 3 , 4 ], but then the problem is no longer equivalent to the classical TSP. Thus, for 1We assume that paths must be closed: the first point is also the last one. 2025 I-RIM Conference October 17-19, Rome, Italy ISBN: 9788894580570 10.5281/zenodo.17629823 189 500 1000 1500 1 10 100 1000 10 1000 Number of points 𝑁 Solution time [s] Concorde ILS SA (a) 500 1000 1500 0 5 10 15 20 Number of points 𝑁 Length increase [%] ILS SA (b) Figure 2. (a): solution time. (b): length of the path from ILS and SA, compared to the path from Concorde. The lines show the mean value across the five problems, while the shaded areas show the minimum and maximum values. simplicity, we assume that the robot remains in the configuration it has at the motion start, so the IK solution is unique for each 𝑃𝑖 . The direct kinematics has up to two solutions. Optionally, our code also checks whether the path between two points switches between these solutions (thus, passing through a singularity, which may be risky for the control). In short, we associate each 𝑃𝑖with one vector of joint coordinates [𝜃1𝑖, 𝜃4𝑖]𝑇. We consider two cost functions: the Euclidean distance 𝑑𝑖 𝑗 = ∥𝑃𝑖−𝑃𝑗∥ and a distance 𝑑′ 𝑖 𝑗 =max{|𝜃1𝑖−𝜃1𝑗|,|𝜃4𝑖−𝜃4𝑗|} . The latter is the maximum absolute change ( 𝐿∞ norm) in joint angles and is proportional to the motion time 𝑡𝑖 𝑗 if the motors move together at the same speed. Even for a more realistic motion of class 𝐶2 that stops at each 𝑃𝑖 and respects the motors’ performance limits, 𝑑′ 𝑖 𝑗 will be roughly proportional 2 to 𝑡𝑖 𝑗 . Then, we provide the solvers with a distance matrix D′=(𝑑′ 𝑖 𝑗 ) instead of D, at no significant increase in computation time 3 . Since 𝑑′ 𝑖 𝑗 is not a linear function of 𝑑𝑖 𝑗 , the optimal path will be different. While this metric is not novel [ 1 , 3 , 4 ], to the best of our knowledge it has not been applied to PRs before. III. Numerical Tests Our code takes as input the point coordinates and outputs the optimal visiting order, a plot of the path, the total cost (either 𝛥 or 𝛥′=Í𝑑′ 𝑖 𝑗 ) and the solution time. We tested the code on TSPs with 𝑁∈ { 20 , 40 , 60 , 80 , 100 } randomly-generated points using Concorde, for both D′ and D. We then compared 𝛥′ (which is roughly proportional to the total motion time) for the paths 𝐽 and 𝐶 that minimize respectively 𝛥′ and 𝛥 . The results show that the two costs differ significantly (Fig. 1), up to over 50%, and that the difference tends to increase with 𝑁 . We also compared the solution time and quality on five random problems for each 𝑁∈ { 250 , 500 , 750 , 1000 , 1250 , 1500 } (Fig. 2). As expected, the solution from Concorde is always the best one, while those from ILS and SA are between 8% and 20% worse. Concorde is also the fastest for problems up to a few thousand points, due to its efficient implementation in C. We expect heuristic methods to be faster for larger problems. Finally, we tested 200 random problems (with 𝑁= 250), 30 times each, for each solver. We found that the solution times 2 In any case, one could choose a general motion law for all segments and define 𝑑′ 𝑖 𝑗 =𝑡𝑖 𝑗 : our solver would then work exactly in the same way. 3We assume that there are no obstacles between any two points in S. A B C D E F 0 10 20 30 Problem Solution time [s] Concorde ILS Figure 3. Solution times for the three “easiest” (A, B and C) and “hardest” (D, E and F) problems out of 200. The minimum, mean and maximum values for Concorde on problems A to C are indistinguishable due to the plot scale. for Concorde are more variable than for the heuristic methods, with some problems having especially long solution times; on some of these, ILS was faster than Concorde (Fig. 3). IV. Conclusions and Future Work We applied the TSP to PRs, showing that minimizing the Euclidean path length may be suboptimal. We propose a metric better related to the motion time, which should be the real goal, and test our ideas in simulation on a simple robot design. We chose to use solvers that were already proven robust and efficient, showing that they can be easily adapted to the task. In future work, we aim to consider workspace boundaries and general spatial robots with orientation capabilities. We also aim to include the robot dynamics in the distance metrics and to verify our concepts on a prototype. Allowing the PR to switch between IK solutions leads to a Generalized TSP [ 4 ], where a point can be reached in multiple configurations; our solver could then be extended to serial robots, to compare it with previous works [ 3 ]. Participants could be asked to manually define a path, to measure how close it is to the optimum. Finally, we are developing a new, Ising-model-based heuristic solver. In early tests, it can reach a good approximate solution in a time close to the one for Concorde for some TSP classes. References 1. Mottola, G., Maddio, P.D., Cammarata, A., Sinatra, R., Garescì, F.: Applications of traveling salesman problem solvers for path planning of parallel robots. In: Proceedings of I4SDG Workshop. pp. 118–127 (2025), doi:10.1007/978-3-031-91151-4_13 2. Morando, L., Recchiuto, C.T., Sgorbissa, A.: Social drone sharing to increase the UAV patrolling autonomy in emergency scenarios. In: Proc. of RO-MAN. pp. 539–546 (2020), doi:10.1109/ROMAN47096.2020.9223567 3. Bottin, M., Boschetti, G., Rosati, G.: Optimizing cycle time of industrial robotic tasks with multiple feasible configurations at the working points. Robotics 11(1), 16 (2022), doi:10.3390/robotics11010016 4. Suárez-Ruiz, F., Lembono, T.S., Pham, Q.C.: RoboTSP – A fast solution to the robotic task sequencing problem. In: Proc. of the ICRA, pp. 1611–1616. IEEE (2018), doi:10.1109/icra.2018.8460581 5. Hasan, M., Haque, M., Mominuzzaman, S., Troyee, T.: Optimization of CDPR path planning using a branch and bound algorithm. In: Proc. of EICT. pp. 1–6 (2023), doi:10.1109/EICT61409.2023.10427901 6. Zhang, H., Su, T., Wu, S., Zheng, J., Wang, Y.: Simultaneous path planning and trajectory optimization for high-speed sorting system. Int. J. Adv. Robot. Syst. 15(5) (2018), doi:10.1177/1729881418797870 7. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The traveling salesman problem: a computational study. Princeton University Press (2011), doi:10.1515/9781400841103 190