Computationally Efficient Trajectory Planning and Task Assignment for Large Teams of Unlabeled Robots

Abstract

This paper considers the problem of finding optimal time parameterized trajectories for N unlabeled robots navigating through a cluttered environment to N unlabeled goal locations where success is defined as every goal being reached by any robot. We propose a complete computationally-tractable algorithm for simultaneously finding trajectories and assignment of goal locations. This method is then demonstrated to have an upper complexity bound of that scales polynomially in the number of robots, O(N 3 ). The trajectories generated are guaranteed to be minimum length and collision free, while the assignment policy minimizes the maximum distance travelled. The key idea in the paper comes from the coupling between the optimal assignment, the properties of the resulting paths, and the set of valid priority assignments to the robots. These benefits result from structure in the solution to the optimal assignment to create a partial ordering of the robots, which in turn allows safe trajectories to be easily generated. Finally, we demonstrate the performance of the algorithm through simulations with tens and hundreds of robots operating in cluttered and confined environments.