## Invited Session Fri.1.H 0106

#### Friday, 10:30 - 12:00 h, Room: H 0106

**Cluster 13: Logistics, traffic, and transportation** [...]

### Optimizing robot welding cells

**Chair: Jörg Rambau and Martin Skutella**

**Friday, 10:30 - 10:55 h, Room: H 0106, Talk 1**

**Jürgen Pannek**

Collision avoidance via distributed feedback design

**Abstract:**

We consider a distributed non cooperative control setting in which systems are interconnected via state constraints. Each of these systems is governed by an agent which is responsible for exchanging information with its neighbours and computing a feedback law using a nonlinear model predictive controller to avoid collisions. For this setting we present an algorithm which generates a parallelizable hierarchy among the systems. Moreover, we show both feasibility and stability of the closed loop using only abstract properties of this algorithm. To this end, we utilize a trajectory based stability result which we extend to the distributed setting.

**Friday, 11:00 - 11:25 h, Room: H 0106, Talk 2**

**Cornelius Schwarz**

The laser sharing problem with fixed tours

**Coauthor: Joachim Schauer**

**Abstract:**

In the Laser Sharing Problem (LSP) a set of industrial arc

welding robots has to perform a series of welding seams. For this task they need

to be connected to a laser source supplying them with the necessary energy.

In principle, a laser source can serve up to six

robots but only one at a time. The task of the LSP is to find an assignment of a given set

of laser sources to robots and collision-free robot tours so that welding seams

performed using the same laser source do not overlap in time and the overall

makespan is minimal.

Prescribing the robot tours we obtain a pure scheduling problem referred to as LSP-T.

We will show that LSP-T can be seen as an extension of the famous job-shop problem. Then

we extend the geometric approach of Akers for the two job-shop problem to LSP-T

leading to a polynomial algorithm for the two robot case.

Since the job-shop problem is a special case of LSP-T the three robot case is

already NP-hard. We will propose a pseudo-polynomial algorithm for it based on

transversal graphs and show how to derive a FPTAS. By this we fully settle the

complexity of LSP-T with a constant number of robots.

**Friday, 11:30 - 11:55 h, Room: H 0106, Talk 3**

**Wolfgang Welz**

Conflict-free job assignment and tour planing of welding robots

**Abstract:**

In welding cells a certain number of robots performs spot welding tasks on a workpiece. The tours of the welding robots are planned in such a way that all weld points on the component are visited and processed within the cycle time of the production line. During this operation, the robot arms must not collide with each other and safety clearances have

to be kept.

On the basis of these specifications, we show an approach how methods of discrete optimization can be used in combination with nonlinear optimization to find solutions for the stated problem. Intermediate results from the combinatorial collision-aware dispatching problem can be used to identify promising tours. Calculating the exact trajectories for those tours only keeps the computational expensive calculations to a minimum.

The discrete part leads to a Vehicle Routing based problem with additional scheduling and timing aspects induced by the necessary collision avoidance. This problem can be solved as an integer linear program by column generation techniques. In this context, we adapt a version of the shortest path problem with time windows so that it can be used to solve the pricing problem with collision avoidance.