Coordination of robot paths for cycle time minimization

D. Spensieri, R. Bohlin, J. S. Carlson, IEEE International Conference on Automation Science and Engineering (CASE), August 17, 2013, 522-527


In this work we study the problem of coordinating robot paths sharing a common environment in order to minimize cycle time, by avoiding their mutual collisions. This problem is particularly relevant in the automotive industry where several robots perform welding operations to assemble and join a car body. The main contributions of this article are: to model the path coordination problem in a graph based way similar to job shop scheduling problem; to solve the path coordination problem by a branch and bound optimization algorithm exploiting the cylindrical structure of the problem. A computational study is presented where the correctness and performance of the new algorithm are evaluated by comparing it with a Mixed Integer Linear Programming formulation, solved by a general purpose package: good results are presented, with computing time differences of even three orders of magnitude. Finally, the algorithm has been interfaced with a state-of-the-art simulation software: within this framework an industrial test case from the automotive industry is solved. A straightforward way to modify pre-computed robot programs, implementing the optimized schedule is also described in pseudo-code. The efficiency of the solver and the robustness of the generated robot programs make the method very appealing in practice.


This work was carried out at the Wingquist Laboratory VINN Excellence Centre, and is part of the Sustainable Production Initiative and the Production Area of Advance at Chalmers University of Technology. It was supported by the Swedish Governmental Agency for Innovation Systems.

Authors and Affiliations

  • D. Spensieri,¬†Fraunhofer-Chalmers Centre
  • R. Bohlin,¬†Fraunhofer-Chalmers Centre
  • J. S. Carlson,¬†Fraunhofer-Chalmers Centre

Photo credits: Nic McPhee