### Page Content

# Matheon C30: Automatic Reconfiguration of Robotic Welding Cells

- [1]
- © DFG Matheon

Duration: | May 2010
- |
---|---|

Project
heads: | René Henrion [2] Martin Skutella [3] Dietmar Hömberg [4] |

Researcher: | Chantal Landry Wolfgang Welz [5] |

Support: | DFG Research Center
"Mathematics for Key Technologies" (Matheon
[6]) |

### Background

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

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

- [7]
- © DFG Matheon

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.

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.

### 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. |

### Cooperation

- Matheon B21: Optical Access Network [8]
- Matheon B24: [9]Scheduling Material Flows in Logistics Networks [10]
- Matheon C7: Mean-risk optimization of electricity production in liberalized markets [11]
- Matheon C11: Modeling and optimization of phase transitions in steel [12]
- Matheon F4: Geometric Shape Optimization [13]

Rücker EKS GmbH [14]

M. Gerdts, Universität der Bundeswehr München [15]

J.
Rambau, Universität Bayreuth [16]

## Publications

Landry, C. and Gerdts, M. and Henrion, R. and
Hömberg, D. (2011). A time optimal control problem for the
collision-free robot motion planning [17]. *Special Issue: 82nd
Annual Meeting of the International Association of Applied Mathematics
and Mechanics (GAMM)*. Wiley-VCH, 725–726.

Gerdts, M. and Henrion, R. and Hömberg, D. and
Landry, C. (2011). Path planning and collision avoidance for robots
[18]. *Numer. Algebra Control Optim.*

Skutella, M. and Welz, W. (2011). Route Planning
for Robot Systems [19]. *Operations Research Proceedings 2010*.
Springer, 307–312.

Landry, C. and Gerdts, M. and Henrion, R. and
Hömberg, D. (2012). Path-planning with collision avoidance in
automotive industry [20]. *Proceedings of 25th IFIP TC7 Conference
on System Modeling and Optimization*. Springer.

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/logos/DFG-Matheon

-Logo-engl.jpg

dr_martin_skutella/parameter/en/font5/maxhilfe/

ang_welz/wolfgang_welz/parameter/en/font5/maxhilfe/

/AG_DiskAlg/FG_KombOptGraphAlg/welz/c30_goal_scheme.png

/B21/

eon_b24/parameter/en/font5/maxhilfe/

heon_b24/parameter/en/font5/maxhilfe/

ZC7/electricity.html

dex.html

gerdts

heon_c30/parameter/en/font5/maxhilfe/?tx_sibibtex_pi1%5

Bcontentelement%5D=tt_content%3A433457&tx_sibibtex_

pi1%5BshowUid%5D=280690&cHash=f0b5dbfbe3e2b50071ddc

8b982b72138

heon_c30/parameter/en/font5/maxhilfe/?tx_sibibtex_pi1%5

Bcontentelement%5D=tt_content%3A433457&tx_sibibtex_

pi1%5BshowUid%5D=280691&cHash=393ce1b054bf6d4a07afa

97bd0157e49

heon_c30/parameter/en/font5/maxhilfe/?tx_sibibtex_pi1%5

Bcontentelement%5D=tt_content%3A433457&tx_sibibtex_

pi1%5BshowUid%5D=280692&cHash=3c72ed5fd07af7e3433d5

e7cc6fda729

heon_c30/parameter/en/font5/maxhilfe/?tx_sibibtex_pi1%5

Bcontentelement%5D=tt_content%3A433457&tx_sibibtex_

pi1%5BshowUid%5D=280694&cHash=e645cbc42b43c088fe4ee

ac5728676fc