Fast generation of collision-free trajectories for robot swarms using GPU acceleration

As the capabilities of robots and their control systems improve, we see an increasing number of use-cases where the simultaneous operation of robots within a space is advantageous. Although trajectories for individual robots can be computed quickly using existing methods, when robots operate simultaneously and in close proximity, the requirement for collision avoidance introduces a coupling between robot trajectories and makes the trajectory generation problem difficult to solve quickly. In this paper we propose a parallelizable formulation of such problems and a method for solving them quickly on modern graphics processing units, using momentum-based gradient descent. We demonstrate the proposed framework in simulation using two case studies: a swarm of 200 quadcopters traversing a maze, and a fleet of 100 bicycle robots changing their formation. In both cases, our method requires just seconds to generate feasible, collision-free trajectories for the entire swarm.
(IEEE Xplore)

Quadcopter maze

Image Intro

An example of the type of problem that we address in this paper. In this benchmark example, 200 quadcopters are tasked with finding their way out of a maze without colliding with each other or with the maze. Our method takes roughly 2.3 seconds to generate feasible, collision-free trajectories for all 200 quadcopters.

Source code

Ground-robot transitions

Image Intro

A further example of the type of problem addressed in this paper. In this example, 100 robots with bicycle dynamics (e.g. cars, warehouse robots, etc.) are tasked with exchanging positions in a smiley face formation without colliding. To exemplify the application of our method to heterogeneous fleets of robots, we constrain the steering angle of 50 robots (colored black) to 20 degrees, and the steering angle of the other 50 robots (colored red) to 70 degrees. Our method takes roughly 1.6 seconds to generate feasible, collision-free trajectories for the 100 robots.

Source code