Transformer model plans multiple agents paths quickly in real time
A Transformer-based Approach for Real-time Multi-agent Path Planning with Varying Initial/Final Conditions
Machine Learning
Summary
Planning routes for many moving agents, like robots or drones, without collisions is very hard and slow with traditional methods. The authors created a special Transformer-based neural network called OCFormer that quickly produces near-best routes from start to finish points, even for many agents, all in around 220 milliseconds. This model learns by following physics rules rather than needing example paths to learn from, and it can adapt quickly to new conditions. This makes real-time multi-agent movement planning more practical, even in complex environments with many obstacles and agents.
What this means in practice
- •For robotic fleet operators: Generate near-optimal real-time routes for fleets of robots navigating crowded spaces without collisions using a single fast model pass.
- •For video game developers: Create dynamic pathfinding for many game characters simultaneously, enabling smooth navigation and avoidance behaviors without costly computations.
Authors
Qian Zhang, Shanqing Liu, Jerome Darbon, George Karniadakis
Abstract
We address the problem of real-time multi-agent path planning under prescribed initial and final configurations, formulated as a high-dimensional optimal control problem subject to inter-agent collision avoidance and obstacle constraints. Classical solvers based on the Hamilton--Jacobi--Bellman equation or Pontryagin's maximum principle (PMP) become computationally intractable as the number of agents grows, due to the curse of dimensionality and the non-convexity introduced by interaction constraints. We propose OCFormer, a transformer-based neural network that parameterizes the inverse of a coordinate transformation mapping a simple, analytically tractable latent space, in which agents evolve independently under a decoupled Hamiltonian, to the physical space of the coupled, interacting system. The model is trained by minimizing a physics-informed loss comprising the Hamiltonian ODE residual from the PMP and a boundary matching term, without requiring pre-computed trajectory data. The self-attention mechanism endows OCFormer with permutation equivariance over agents, a structural symmetry that prior symplectic network approaches do not natively enforce. When trained on a distribution of boundary conditions, the amortized OCFormer produces near-optimal trajectories for unseen initial and final configurations in a single forward pass ($\sim$220ms), enabling real-time inference without retraining. We further introduce a lightweight transfer learning framework that adapts a pretrained OCFormer to out-of-distribution perturbations in seconds via L-BFGS fine-tuning. Numerical experiments on two- and three-dimensional multi-agent navigation with up to 128 agents demonstrate the scalability and efficiency of the proposed approach.