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, Strasse 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, Strasse 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, Strasse 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:

  • Develop fast routine for estimating distances between pairs of weld points for each robot. (nonlinear)
  • Develop routine for optimal path planning for given robot and sequence of weld points, including time required for welding at each point. (nonlinear)
  • Develop several mixed integer programming models for simplified problem variants. Perform tests with standard MIP-software like CPLEX and SCIP. (discrete)
  • Develop routine for collision detection for pairs of sub-paths. (nonlinear)
  • Develop solution methods for mixed integer programs, including preprocessing, column generation approaches, branch-and-bound, branch-and-cut, etc. (discrete)
  • Develop models and solution techniques for problem in its full generality. (discrete)

Current research.

  • Discrete optimization: On the basis of the given specifications, a slight simplification is considered, so that it is possible to concentrating on the discrete optimization aspects of the problem: We, therefore, assume that the time a robot needs to travel from one weld point to another is given a priori, always identical and does not depend on the orientation of the robot arm or other factors. Further the collision avoidance is simplified to a compatibility test between the paths the robots use between two weld points. This problem can then be modeled as a set partitioning problem where branch-and-price algorithm is used to solve the problem. In this context, branching is used to assure feasible as well as collision free solutions. The corresponding pricing problem then corresponds to a Shortest Path Problem with Time Windows where waiting in nodes is also only allowed in feasible time intervals. Using this approach, we are able to solve generated test instances based on the real world welding cell problems of reasonable sizes with four robots processing about 30 weld points to optimality.
  • Nonlinear optimization: Motion planning consists of finding a collision-free trajectory of a robot which evolves in a space containing obstacles. In our project we additionally require the motion to be as fast as possible. So we write the sought trajectory as the solution of an optimal control problem where the function to minimize is the time needed for the robot to join two given positions. The robot and the obstacles are represented as finite unions of convex compact polyhedra. Each object is then described by a system of linear inequalities. This description combined with linear programming arguments allows us to include the collision avoidance criteria as state linear constraints in the optimal control problem. The resulting problem is solved with a sequential quadratic programming method. In order to decrease the number of unknowns and constraints we add an active set strategy based on back-face culling to the resolution technique.


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

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.