Coordination of robot paths for cycle time minimization

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.