On the computational complexity of a scheduling problem related to motion coordination of multiple robots
Yi C. S. Lee · ThinkTech (Texas Tech University) · 1987
The following schedule problem can be regarded as an abstract model of motion coordination of multiple robots: A number of distinct pebbles are placed on distinct vertices of a graph.A set of pebbles can be moved simultaneously along the edges of the graph, provided that, at any moment, at most one pebble is placed on a vertex and at most one pebble passes through an edge.Given distinct final positions for the pebbles, obtain a schedule, if it exists, for moving all pebbles to their final positions.In this for the scheduling problem in which each pebble is assumed to represent an autonomous robot which can compute its own schedule.We prove that, if a graph is a tree and the number of robots is three, then the algorithm allows a maximum possible number of robots to reach their final positions.