Abstract
Large teams of robots have been implemented to great success in Kiva’s automated warehouses as well as UPenn’s and KMel Robotics’ swarms of quadrotors. In settings such as these, robots must plan paths which avoid collisions with other robots and obstacles in the environment. Unfortunately, trajectory planning for large teams of robots generally suffers from either the curse of dimensionality or lack of completeness. I will demonstrate that relaxing the assumption of labeling each robot and specifying a fixed assignment of robots to destinations in the trajectory generation problem yields a number of computational and performance benefits. My algorithm to solve this Concurrent Assignment and Planning of Trajectories (CAPT) problem has bounded computational complexity of O(N^3), preserves completeness properties of a user specified single agent motion planner, and tends to minimize effort exerted by any one robot. This algorithm generates solutions to variants of the CAPT problem in settings ranging from kinematic robots in an obstacle free environment to teams of robots with 4th order dynamics in a cluttered environment. Finally, I will show experimental results of the algorithm applied on teams of second order aquatic vehicles as well as on quadrotor micro aerial vehicles. I will also outline how time consuming aspects of this approach can be parallelized and discuss possible decentralized implementations.