Project C30

Automatic reconfiguration of robotic welding cells

Project description.

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.

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.

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.

Cooperation.

Within Matheon

External

Industrial

References (at project start).