Intersection-free load balancing for industrial robots – Modelling and algorithm development

E. Åblad. Master thesis, Chalmers University of Technology and University of Gothenburg, supervisor D. Spensieri, examinator A-B Strömberg, August 2016.


This thesis considers the problem of minimizing cycle time while avoiding collisions within a robot station consisting of multiple industrial robots that collectively should cover a set of tasks, e.g. welding operations, on a workpiece. The cycle time is the time required to perform all tasks. Nowadays, in order to prevent the robots from colliding, their programs usually synchronise by adding synchronisation/interlocking signals when necessary. Here, the aim is instead to partition the space within the station, separating the robots. There are three main advantages in this approach: -the simplicity of the robot programs due to the total absence of synchronisation need; -the stability of the station in case of unexpected events; -lower maintenance cost. The problem is thus to find a space partition allowing all tasks to be performed in a minimal time. In order to retrieve the space partition, an approximate problem is repeatedly solved using the Dantzig-Wolfe decomposition principle and from the solutions provided, generalised Voronoi diagrams are approximated. For each of the resulting candidate partitions the robot module in the software IPS is used to determine the robot station cycle time. Results on existing industrial test cases show that using this approach the cycle time was increased by around 5% as compared with synchronising the robot programs. It is however not determined whether this approach finds an optimal partitioning since the generalised Voronoi diagram is generated from some stationary position of the robots, which might cause nonoptimal paths between these positions.

Photo credits: Nic McPhee