Project C30

Automatic reconfiguration of robotic welding cells

DFG Research Center Matheon Weierstraß-Institut für Angewandte Analysis und Stochastik Technische Universität Berlin
Duration: June 2010 -
Project director: Priv.-Doz. Dr. René Henrion
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstrasse 39, 10117 Berlin, Germany
Tel: +49 (0)30-20372 540
email: rene.henrion [at]
Prof. Dr. Dietmar Hömberg
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30-314 28034
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstrasse 39, 10117 Berlin, Germany
Tel: +49 (0)30-20372 491
email: Dietmar.Hoemberg [at]
Prof. Dr. Martin Skutella
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30-314 78654
email: martin.skutella [at]
Researcher: Dr. Chantal Landry
Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstrasse 39, 10117 Berlin, Germany
Tel: +49 (0)30-20372 454
email: chantal.landry [at]
Wolfgang Welz
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30-314 78655
email: welz [at]
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)

Project description.


Industrial manufacturing in Germany has by now reached a high degree of automation. Complex production systems have been created and consist of robots and other machines grouped together in work cells and connected by conveyor belts and further devices for materials supply and temporary storage (cf, e.g., [10]).

However the competition with low-wage countries and the strive for meeting the customers needs requires a shortening of time to market as well as an efficient production also in the case of smaller batch sizes [5,10]. A key task in this connection is the fast reconfiguration of complex production systems.

The present project aims at contributing to this problem by developing methods and tools for the automatic reconfiguration of robotic welding cells, which are at the core of many complex production systems, especially in automotive industry. In these welding cells a certain number of robots perform spot welding tasks on a workpiece. For instance, four robots have to make 50 weld points on a car door. Up to now, the reconfiguration of such a weld cell is basically done by hand.

Top view of 4 robots working on a car door.

The goal of the project is to automate this process. Given the Computer Aided Design data (CAD) of the workpiece, the number and the location of weld points on it and the number of robots, the task is to assign weld points to the different robots and to do the sequencing as well as the path-planning for all the robots avoiding collisions. The total time taken by the robots to complete the job must be bounded by a given makespan. Alternatively, the makespan should be as small as possible.

The relaxation of the problem where collisions between robots are not taken into account is, from the viewpoint of discrete optimization, a variant of the vehicle routing problem (VRP); see, e.g., [11]. Classical exact approaches to solve large VRPs use column generation in mixed-integer models, see [3,6]. The VRP generalizes the famous traveling salesman problem (TSP); see, e.g., [1,7]. In our context, the following variants of the TSP (and of the VRP) are of particular interest: Group TSP or Generalized TSP, TSP with Neighborhoods, and TSP with Time Windows.

There is not much literature on the particular robot welding problem under consideration. An introduction and overview of various aspects of the robot welding problem together with a description of heuristic solution approaches is given in [9]. A somewhat related laser welding problem where robots have to share a limited number of laser sources is considered in [4,8].

The path-planning for single industrial robots is by now well understood [5,10]. Robot manufacturers like ABB and KUKA distribute software tools that are capable of solving tasks like inverse kinematics and trajectory planning or analysing the reachability of robot positions. To the very best of our knowledge there are no results available that deal with path-planning of one or several robots including collision avoidance. Existing results either refer to translational motions [12,13] or deal solely with the question of collision detection, see, e.g., [2].

Achievements of the project.

In order to successfully complete the project, two positions are required, one in the area of discrete optimization and one in the area of nonlinear optimization.

goal scheme

The outlines of work packages that need to be executed by the two positions are:

Current research.


Within Matheon

B14: the vehicle routing problem
B14, B21 and B24: mixed integer programs
C7: obstacle avoidance under uncertainty
C11: models for Joule heating and spot welding
F4: geometry reduction for unions of polyhedra


M. Gerdts, Universität der Bundeswehr München


Rücker EKS


To appear

  1. Skutella, M. and Welz, W., Route Planning for Robot Systems. To appear in the post proceedings of OR 2010 Munich.


  1. Welz, W., Route Planning for Robot Systems. Diploma thesis, TU Berlin (2010).

References (at project start).

[1] Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J., The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
[2] Choi, Y.-K., Chang, J.-W., Wang, W., Kim, M.-S., and Elber, G., Real-time continuous collision detection for moving ellipsoids under affine deformation. Technical Report HKU CS Tech Report TR-2006-02, The University of Honk Kong, 2006.
[3] Desroisers, J., Dumas, Y., Solomon, M. M., and Soumis, F., Time constraint routing and scheduling. In M. Ball, T.L. Magnanti, C.L. Monma, and G. Nemhauser, editors, Network Routing, volume 8 of Handbooks in Operations Research and Management Science, pp. 35--140. Elsevier, Amsterdam, 1995.
[4] Grötschel, M., Hinrichs, H., Schröer, K., and Tuchscherer, A., A mixed integer programming model for a laser welding problem in car body manufacturing. Technical Report 06-21, ZIB, 2006.
[5] Heim, A. and von Stryk, O., Trajectory optimization fo industrial robots with application to computer-aided robotics and robot controllers. Optimization, 47(3-4):407-420, 2000. Numerical methods for stochastic optimization and real-time control of robots (Neubiberg/Munich, 1998).
[6] Krumke, S. O., Rambau, J., and Torres, L. M., Realtime dispatching of guided and unguided automobile service units with soft time windows. In Algorithms - ESA '02, volume 2461 of Lecture Notes in Computer Science, pp. 637--648. Springer, 2002.
[7] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985.
[8] Rambau, J. and Schwarz, C., On the benefits of using np-hard problems in branch & bound. In Proceedings of the International Conference Operations Research 2008. Springer, 2008.
[9] Rupp, M., Zeitoptimale Bearbeitungsreihenfolgen für mehrere Schweissroboter: Modelle und Algorithmen. Master's thesis, Institut für Informatik, Universität Frankfurt, 2004.
[10] Steinbach, M. C., Bock, H. G., Kostin, G. V., and Longman, R. W., Mathematical optimization in robotics: towards automated high-speed motion planning. Surveys Math. Indust., 7(4):303-340, 1998.
[11] Toth, P. and Vigo, D., editors. The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.
[12] Varadhan, G., Krishnan, S., Sriram, T. V. N., and Manocha, D. A simple algorithm for complete motion planning of translating polyhedral robots. INTRR, 24(11):983-995, 2005.
[13] Varadhan, G., and Manocha, D. Accurate Minkowski sum approximation of polyhedral models. Graphical Models, 68(4):343-355, 2006.