Coordinating the motions of multiple robots with specified trajectories

Abstract

Coordinating the motions of multiple robots operating in a shared workspace without collisions is an important ca- pability. We address the task of coordinating the motions of multiple robots when their trajectories (defined by both the path and velocity along the path) are specified. This prob- lem of collision-free trajectory coordination arises in weld- ing and painting workcells in the automotive industry. We identify sufficient and necessary conditions for collision-free coordination of the robots when only the robot start times can be varied, and define corresponding optimization prob- lems. We develop mixed integer programming formulations of these problems to automatically generate minimum time solutions. This method is applicable to both mobile robots and articulated arms, and places no restrictions on the num- ber of degrees of freedom of the robots. The primary advan- tage of this method is its ability to coordinate the motions of several robots, with as many as 20 robots being considered. We show that, even when the robot trajectories are specified, minimum time coordination of multiple robots is NP-hard.