Intersection-free load balancing for industrial robots

My name is Edvin Åblad, and I am an industrial PhD student at the Fraunhofer Chalmers Research Centre  (FCC) in the department of geometry and motion planning. I am also part of the optimization group at the Department of Mathematical Sciences, Chalmers University of Technology and University of Gothenburg.  My research project is part of the project Smart Assembly 4.0 that is supported by the Swedish Foundation for Strategic Research (SSF). The main supervisors to my project are Ann-Brith Strömberg (Chalmers), Robert Bohlin (FCC), and Johan S. Carlson (FCC).
The project Smart Assembly 4.0 focuses on how to utilize real-time data in the automotive manufacturing to increase product quality, where the main idea is to move from mass production to a more individualized production; see [1] for details. This product individualization creates several new research issues. One of them is considered in my project: the robot programmes, i.e., weld task sequences and corresponding robot motions, will also need to be optimized for each individual product. One approach to solve this issue is to find robust robot programmes that are valid for or easily adaptable to a large set of individual products.

path-planning-profilprojektsbilder7In [2] we studied the effects of enforcing the robot programmes to be intersection-free, i.e., encapsulating each robot in a separate and time-independent geometrical partition of the robot station; we call the existence of such partitions the partition constraints. We found that for many industrial problem instances these additional constraints did not affect the stations’ throughput negatively. This result is impressive since the flexibility of the robot station was also increased, considering that each robot has an assigned space that is free from other robots. An implication of this is that one might change the weld sequence and the corresponding motions of each robot separately. Without the partition constraints, the change of the motion of a single robot in the line might invalidate other robots’ motions.  Another possibility is if a weld task should be slightly moved in space but remain in the partition, we might reuse the same partition and again modify the motion of the involved robot only.

Therefore, by making the robots’ motions intersection-free the robot programme becomes more robust, in the sense that for certain problem perturbations it becomes computationally much cheaper to modify the robot programme into a valid one.

However, the procedure to generate intersection-free robot programmes described in [2] is only a proof of concept and has a great potential for further development. For example, the tasks are assigned to the robots without accounting for the corresponding task sequences, which are decided only after the partitions have been created, ensuring that the robots’ motions are separated in space. To reduce the impact of unbalanced task assignments the algorithm described in [2] is composed by numerous time-consuming iterations. We suggest to instead consider this problem as a special kind of vehicle routing problem (VRP), where the vehicles and customers correspond to the robots and tasks, respectively. This has been attempted for similar problem settings; see e.g., [3]. What is of particular interest and possibly new in our VRP formulation is the partition constraints between the robots. These can be described through a rather large set of logical constraints, i.e., if a robot ever occupies an area/task, then no other robot can ever access the adjacent areas/tasks. Another related possible improvement of the model presented in [2] is to find a tighter –w.r.t. integer linear programming– formulation of the partition constraints; the formulation employed in [2] introduced a large so-called integrality gap [4, p. 229], thus resulting in a computationally more expensive model to solve.

So, a part of my current work is to expand on the models and methods presented in [2]. E.g., to make the intersection-free robot programmes even more competitive in terms of a higher station throughput and, in the future, to examine their use within the Smart Assembly 4.0 project.


[1] R. Söderberg, K. Wärmefjord, J. S. Carlson, and L. Lindkvist, “Toward a Digital Twin for real-time geometry assurance in individualized production”, CIRP Annals, vol. 66, no. 1, pp. 137-140, 2017.
[2] E. Åblad, D. Spensieri, R. Bohlin, and J. S. Carlson, “Intersection-free geometrical partitioning of multirobot stations for cycle time optimization”, IEEE Transactions on Automation Science and Engineering, vol. PP, no. 99, pp. 1-10, 2017.
[3] J. Rambau and C. Schwarz, “Solving a vehicle routing problem with resource conflicts and makespan objective with an application in car body manufacturing”, Optimization Methods and Software, vol. 29, no. 2, pp. 353-375, 2014.
[4] M. Conforti, G. Cornuéjols, and G. Zambelli, “Integer Programming”, Springer International Publishing, 2014.