How do we coordinate the motion of many robots, vehicles, aircraft, or people? If each mobile agent has a destination in mind, how can it find an efficient route that avoids collisions with other agents as they simultaneously move to their destinations? These basic questions arise in many application domains, such as ground swarm robotics, aerial swarm robotics, air traffic control, warehouse management, and vehicular traffic networks. They also have a long tradition in Computational Geometry, reaching back at least until the seminal work of Schwartz and Sharir fro the early 1980s.
In this talk, I present a number of different algorithmic results. Starting with a labeled set of robots on a grid, we consider the total time for letting each agent reach its destination. We show that we can always achieve constant stretch, i.e., compute a well-choreographed set of trajectories in which the total time until completion is within a multiplicative constant of the largest initial distance. For settings in which the swarm needs to stay connected at all time, I present two additional sets of results, based on different approaches. Finally, I sketch some results for reconfiguring a swarm when agents do not have individual control, but have to follow uniform global forces.