The welding techniques used in the automotive industry have recently changed a lot. There is a new, faster, more effective way to perform the welding; it's called Remote Laser Welding (RLW). It is taking the place of the Resistance Spot Welding (RSW), used earlier. The key innovation of the new technology is a robot shooting at the work piece with laser beam from a long distance, typically 25-160 cm.
The new technique leads to new problems that the industry needs to solve. The main task is calculating the sequence of the seams, and in parallel, the computation of the robot path. It is important for the industry to build an algorithm that gives solutions that respect the structural and technological constraints and specifications.
With the essential knowledge about the technology in mind, I developed an algorithm that is able to compute such solutions. Given the geometrical information about the work piece and the seams, as well as the detailed specification of the robot, the system calculates a close-to-optimal task sequence and robot path. It provides a fast and efficient way for its purpose.
The program first creates a mathematical model using the information in its input file, and then solves the problem in that model. I represented the problem as a generalize Travelling Salesman Problem (TSP) and solved it using a local search algorithm.
To ensure a feasible path, I added visibility analysis and collision detection. The visibility analysis ensures that there cannot be any object in the way of the laser beam during the welding, while collision detection filters out the positions where the robot head hits the work piece. The calculations are performed on triangle mesh reppresentations of the work piece.
I tested the algorithm with various input files and evaluated the solutions. The good results, the speed of the calculation and the length of the path make it possible to use the software in a real workflow, provided that there is enough geometrical and technological information about the seams and the robot.