Abstract
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 the 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 the cases, our method requires just seconds to generate feasible, collision-free trajectories for the entire swarm.
Introduction: The Challenge of Swarm Coupling
Planning paths for a single robot is a well-understood problem. However, as the number of robots in a shared workspace increases, the computational complexity grows exponentially. This is primarily due to coupling: a valid trajectory for one robot is strictly dependent on the instantaneous positions of all other robots to ensure collision avoidance.
Traditional optimization techniques, such as Mixed-Integer Linear Programming (MILP), often fail to scale to hundreds of agents because the search space becomes prohibitively large. Existing real-time solutions frequently rely on simplifications that sacrifice robot agility or path optimality. This research addresses the need for a high-speed solver capable of generating feasible trajectories for massive swarms by leveraging the parallel processing power of modern Graphics Processing Units (GPUs).
Methodology
The proposed framework reformulates trajectory optimization into a structure compatible with GPU architectures. The approach rests on three technical pillars:
1. Soft Constraint Formulation
Rather than treating collision avoidance as a hard geometric constraint, the authors model it as a differentiable "soft" loss function. When robots approach a minimum safety distance, the loss increases. The optimization goal is to minimize the aggregate loss across the entire swarm, including terms for goal reaching and control effort.
2. Parallelized Dynamics via Cumulative Sums
Robot dynamics are typically expressed as recursive difference equations, which are inherently sequential. The authors demonstrate that these can be mathematically rewritten as cumulative sums (prefix sums). This allows the GPU to compute the entire state history of a robot in $O(\log T)$ time rather than $O(T)$ time, where $T$ is the number of time steps.
3. Efficient Collision Detection
A naive collision check between $R$ robots requires $O(R^2)$ operations. To optimize this, the system employs a parallel sorting algorithm to order robots along a primary spatial axis. Each robot then only needs to check for collisions with its immediate neighbors in the sorted list, significantly reducing the computational load.
The optimization itself is executed using Adam, a momentum-based gradient descent optimizer widely used in deep learning, implemented within an auto-differentiation framework.
Experimental Evaluation
The method was benchmarked using two challenging simulated scenarios:
- Quadcopter Maze ("Sort 200"): 200 quadcopters must navigate from random internal positions to unique external goals through a complex 2D maze. This requires 3D collision avoidance as agents adjust altitude to pass one another.
- Bicycle Robot Transition: 100 ground robots with non-holonomic "bicycle" dynamics must swap positions to form a specific pattern. This tests the algorithm's ability to handle heterogeneous constraints and complex steering dynamics.
Results and Discussion
Testing on a consumer-grade NVIDIA GTX 1080 Ti yielded impressive performance metrics:
- Speed: The median time to solve the 200-quadcopter maze was 2.28 seconds, with 90% of cases solved under 3.38 seconds. The 100-bicycle robot transition required a median of only 1.6 seconds.
- Scalability: The results suggest that the method scales gracefully with the number of agents, maintaining sub-second or low-second performance for swarms that would paralyze traditional solvers.
- Hardware Efficiency: GPU utilization remained between 20% and 40%, indicating significant headroom for even more complex scenarios or further software-level optimizations.
Conclusion
By reframing trajectory optimization as a parallelizable gradient descent problem, this work enables the rapid generation of collision-free paths for large-scale robot swarms. While the method is currently centralized and relies on local minima search, its speed opens the door for real-time Model Predictive Control (MPC) and the development of decentralized local policies in future research.
Summary updated