Coordinating multiple robots with assigned paths

This paper describes a method for coordinating the motions of a group of robotsfollowing predefined paths in a common workspace. Coordination Diagrams (CD) are used forrepresenting the possible collisions among the robots. We propose an algorithm that computesa complete coordination plan for the overall missions that each vehicle have to execute. Thealgorithm generates a set of possible coordination plans and then gives the optimal one. Previousworks apply traditional path planning techniques (such as D* or A*) to compute a coordinatedmotion. However these techniques do not take into account the fact that the CD has a cylindricalstructure. This important features enables our algorithm to explore the CD in a more efficientlyway.