Coordinating the Motions of Multiple Robots with Specified Trajectories

2002 IEEE International Conference on Robotics and Automation, Washington D.C., May 2002.

Srinivas Akella and Seth Hutchinson

Abstract

Coordinating the motions of multiple robots operating in a shared workspace is an important capability. 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 problem of collision-free motion coordination arises in welding and painting workcells in the automotive industry. We identify sufficient and necessary conditions for collision-free coordination of the robots and define corresponding optimization problems. We develop mixed integer programming formulations of these problems to automatically generate minimum time solutions for the case when only the robot start times can be varied. This method is applicable to both mobile robots and articulated arms, and places no restrictions on the number of degrees of freedom of the robots. The primary advantage 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.

Paper

Animations

Note: The animations appear a bit jerky because alternate frames were used to create them.