Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee

In this paper, we study the problem of controlling a group of indistinguishable agents with non-negligible sizes to take arbitrary desired formations. The agents, confined to an arbitrary connected graph, are capable of moving from one vertex to an adjacent vertex in one time step. The control policy must ensure that no collisions occur, which may happen when two agents attempt to move to the same vertex or move along the same edge. Counting each edge as having unit distance, we show that a (centralized) policy/schedule exists that moves the agents to the desired formation along paths having shortest total distance. The control policy also guarantees that a convergence time (the time when the formation is complete) of no more than n l 1, in which n is the number of agents,lis the maximum (shortest) distance between any two initial and goal vertices.