Source-linked AI summary
A Transformer-based Approach for Real-time Multi-agent Path Planning with Varying Initial/Final Conditions
Qian Zhang, Shanqing Liu, Jerome Darbon, George Karniadakis
TL;DR
High-dimensional optimal control with collision and obstacle constraints makes real-time multi-agent path planning difficult as agent counts grow. OCFormer learns an inverse coordinate map from decoupled latent trajectories to interacting physical trajectories using physics-informed training. Experiments report collision-free navigation with up to 128 agents, while amortized inference and transfer adaptation address varying boundary conditions.
Problem
High-dimensional state spaces and non-convex interaction constraints make classical multi-agent optimal-control solvers computationally challenging as the number of agents grows.
Source: §1.1 · p. 2Method
OCFormer learns an inverse coordinate transformation from decoupled latent trajectories to interacting physical trajectories, using Hamiltonian ODE residuals and boundary matching for training.
Source: §1.2 · pp. 2–3Results
OCFormer produces collision-free trajectories on 2D and 3D benchmarks with up to 128 agents, with costs within a few percent of rigorous lower bounds.
Source: §6 · p. 17Takeaways & Limitations
A pretrained OCFormer can be adapted to rigid-body transformations and random boundary perturbations with seconds of L-BFGS fine-tuning rather than full retraining.
Source: §6 · p. 17Current amortized training is limited to rotated versions of a fixed configuration, and feasibility at higher densities remains to be improved.
Source: §6 · p. 17
Abstract
from arXiv · showhide
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.
1. Introduction
Multi-agent optimal control becomes difficult at scale because high-dimensional state spaces and non-convex interaction constraints challenge classical solvers. OCFormer learns an inverse coordinate map with physics-informed training and attention-based permutation equivariance.
1.1. Motivation and Context.
- Classical HJB and PMP approaches face severe computational challenges as agent count grows, compounded by collision constraints that create non-convexity and long-range coupling.The joint state dimension is Mdx; HJB grid complexity scales exponentially, while PMP shooting can be sensitive to co-state initialization.Source: §1.1 · pp. 1–2
- Prior symplectic-PINN architectures process agents in a fixed order and impose a symplectic constraint that may be unnecessary for these problems.These properties do not reflect the permutation symmetry of multi-agent systems.Source: §1.1 · p. 2
1.2. Contribution.
- OCFormer learns an inverse coordinate transformation from analytically tractable, decoupled latent trajectories to interacting physical trajectories.Its physics-informed loss combines Hamiltonian ODE residuals from PMP with boundary matching for prescribed initial and final configurations.Source: §1.2 · pp. 2–3
- Self-attention provides permutation equivariance, and amortized OCFormer predicts trajectories for unseen boundary conditions in a single forward pass of about 220 ms.The approach is validated on two- and three-dimensional navigation benchmarks and is reported to reduce inference time relative to existing methods.Source: §1.2 · p. 3
2. Multi-Agent Optimal Control Problem
The paper formulates multi-agent navigation with fixed endpoint constraints and collision or obstacle avoidance as an optimal-control problem. It represents the resulting PMP boundary-value system using a coordinate transformation to a simpler latent trajectory pair.
2.1. Problem setup.
- The problem seeks trajectories minimizing total action over a time horizon, with prescribed initial and final constraints and state constraints for collision and obstacle avoidance.The system comprises M interacting subsystems with concatenated state and control variables.Source: §2 · p. 3, §2.1 · p. 3
- A soft penalty converts state constraints into the Lagrangian, but its epsilon-penalized solution is biased away from the exact constrained optimum.The log barrier is not Lipschitz at the constraint boundary, and epsilon and l control the cost–feasibility trade-off.Source: §2.1 · pp. 3–4
2.2. From Maximum Principle to Hamiltonian ODE system.
- Pontryagin’s maximum principle yields a Hamiltonian boundary-value ODE system for the optimal state, control, and co-state under the endpoint constraints.The paper focuses on solving this system for multi-agent path planning.Source: §2.2 · p. 5
- The coordinate map sends the physical trajectory pair to a simpler latent pair associated with a decoupled Hamiltonian system; its inverse reconstructs interacting trajectories.The framework uses the inverse map to approximate the optimal trajectories.Source: §2 · p. 3, Figure 2 · p. 6
3. The OCFormer Framework
The framework represents coupled multi-agent trajectories through an inverse coordinate transformation from a decoupled latent system. OCFormer parameterizes that inverse and is trained with physics-informed dynamics and boundary losses.
3.1. Trajectory Representation by Coordinate Transformation in Latent Space.
- The latent coordinate transformation maps trajectories of the interacting system to a decoupled system whose low-dimensional subsystems can be solved separately.The transformation is motivated by interactions making the joint system non-convex in M × dx dimensions.Source: §3.1 · p. 6
3.2. Parameterize the Inverse Operator by Transformer Based Neural Network.
- OCFormer parameterizes the inverse transformation with a transformer; for the studied quadratic-kinetic problems, its residual ansatz starts from straight-line paths and learns collision-avoiding corrections.In per-instance training, the network sees only a one-dimensional input line segment, which explains why the fit is easy but does not directly generalize to new boundary conditions.Source: §3.2 · p. 7
- Self-attention makes OCFormer permutation equivariant over agents, while identical latent inputs produce identical outputs and cannot be separated without positional encoding.For role-differentiated targets, the paper uses PositionalOCFormer, which deliberately breaks permutation equivariance.Source: §3.2 · p. 8
3.3. The OCFormer Method and Training procedure.
- Training minimizes a physics-informed loss combining the Hamiltonian ODE residual, boundary matching, and auxiliary terms; 3D experiments add a velocity-bound penalty, and ball-3D adds obstacle-penetration penalties.The obstacle penalty supplements the log-barrier by penalizing penetration at collocation points.Source: §3.3 · p. 9
- With zero PINN and boundary losses on dense collocation points, a continuously differentiable ansatz satisfies the Hamiltonian ODE and is a normal extremal; lowering nonzero loss increasingly approximates an extremal.This result does not require the ansatz to be symplectic.Source: §3.3 · pp. 9–10
4. A Real Time Learning Framework for Perturbation on initial and Terminal Conditions
For small or structurally simple boundary perturbations, the framework adapts a pretrained reference model rather than resolving the full planning problem. It freezes that model and trains lightweight coordinate transformations selected according to the perturbation type.
4.1. Perturbation on Initial and Terminal Conditions.
- For small or structurally simple boundary perturbations, solving the full optimal control problem from scratch is computationally redundant because collision-avoidance logic remains largely consistent.The proposed alternative is transfer learning from a pretrained reference model.Source: §4.1 · p. 10
4.2. Transfer Learning Framework.
- The transfer model composes trainable coordinate transformations around a pretrained OCFormer whose parameters are frozen.The transformation modules are placed before and after the base model.Source: §4.2 · p. 10
- The global affine module applies a learnable linear transformation to position and momentum and a translation to position, but is not constrained to a rotation.Its residual form initializes at the identity, while the forward and inverse modules are trained independently without enforcing exact inverses.Source: §4.2 · p. 10
- Under 100 L-BFGS iterations are typically sufficient, and fine-tuning generally takes only seconds.The transfer parameters are optimized with the original physics-informed loss; the correction modules add 4Mdx trainable parameters.Source: §4.2 · pp. 10–11
- For rigid global rotations and translations, only the affine module is trained; unstructured boundary noise additionally activates per-agent bounded corrections.The corrections are time-independent parameters that perturb latent inputs and add residual adjustments at the output.Source: §4.2 · pp. 10–11
- Transfer training uses boundary data in a room twice the base model’s linear size, keeping adapted trajectories well within the feasible region during optimization.The specified transfer domain is [−1, 1]2.Source: §4.2 · p. 11
5. Numerical Experiments
The experiments evaluate OCFormer on symmetric and perturbed 2D drone configurations, amortized inference, and 3D navigation with room or spherical obstacles. Results include near-optimal costs and collision-free trajectories, while denser amortized cases expose feasibility limits.
5.1. Optimal Path Planning for Multiple Drones in a 2D Room.
- The 2D room task sends drones to target positions simultaneously without collision in a square room over a horizon T = 10.The drones have radius r = 0.02.Source: §5.1 · p. 11
5.1.1. Symmetry Setup.
- For M ≤8, OCFormer’s cost is within 1% of the true optimum; its gap stays below 10%, it reduces cost 13% versus SympOCNet at M = 32, and at M = 128 it remains feasible when SympOCNet fails.The fine-grid constraint minimum is positive, in [1.2, 1.5] × 10^-4, for every configuration.Source: §5.1.1 · p. 12, §5.1.2 · p. 12, Table 1 · p. 12
5.1.2. Symmetry Setup with Rigid Body Transformation.
- Rigid-body transfer recovers the exact transformed solution for four drones with trajectory L2 error below 10^-6.The experiment tests recovery under the rotation-and-translation symmetry of the reference configuration.Source: §5.1.2 · p. 13
5.1.3. Random Perturbation on Initial Conditions.
- Across 100 random perturbation trials, trajectories remain feasible with cost around 1.26 and positive constraint minimum around 1.5–4 × 10^-4.The initial-position perturbation has magnitude ∥δ0∥∞ = 0.05; fine-tuning reaches residual loss around 1–1.5 × 10^-4.Source: §5.1.3 · pp. 13–14
5.2. Amortized OCFormer: Training on a Distribution of Boundary Conditions.
- For M = 8, amortized inference is collision-free on all 20 held-out boundary pairs and stays within 1.3% of the analytic lower bound; for M = 16, feasibility is 75% and the cost gap is 5.0%.A single forward pass takes approximately 220 ms, versus about 20 minutes for per-instance Adam + L-BFGS training.Source: §5.2 · pp. 14–15, Table 2 · p. 14
5.3. Path Planning for Multiple Drones in a 3D Room.
- PositionalOCFormer coordinates 100 drones through a confined 3D room with two internal barriers while maintaining collision-free motion.Per-agent weights are used because the fixed geometry and role-differentiated positions make the agents non-interchangeable.Source: §5.3 · pp. 15–16, §5.2 · p. 15
5.4. Ball 3D Example.
- In the 3D ball-obstacle example, trajectories show agents avoiding both pairwise collisions and a spherical obstacle.The obstacle has radius 0.1, and the evaluated configurations include 16 and 128 drones.Source: §5.4 · pp. 16–17
6. Conclusion and Future Work
OCFormer maps analytically tractable, decoupled latent trajectories to interacting physical trajectories and is trained with Hamiltonian ODE residuals and boundary matching. Experiments report collision-free paths up to 128 agents near rigorous lower bounds, while amortized training and feasibility remain bounded by stated scope limitations.
6. Conclusion and Future Work
- OCFormer parameterizes an inverse coordinate transformation from a decoupled latent space to the interacting physical system, trained with Hamiltonian ODE residuals and boundary matching.It solves fixed-boundary problems without pre-computed trajectory data.Source: §6 · p. 17
- Transfer learning adapts a pretrained model to rigid-body transformations and random boundary-condition perturbations in seconds of L-BFGS fine-tuning rather than full retraining.Source: §6 · p. 17
- Across 2D and 3D benchmarks, OCFormer produces collision-free trajectories with up to 128 agents at costs within a few percent of rigorous lower bounds.The permutation-equivariant architecture is useful for symmetric problems, while a positional variant handles asymmetric settings.Source: §6 · p. 17
- Amortized zero-shot generalization is demonstrated only for rotated versions of a fixed configuration; broader boundary-condition distributions and improved feasibility at higher densities remain future work.Other directions include symplecticity preservation, general nonlinear dynamics, and feedback control for online replanning.Source: §6 · p. 17
Appendix A. General Pontryagin’s Maximum Principle with State Constraints
The appendix states assumptions for a finite-horizon deterministic control problem and gives PMP necessary conditions for optimal trajectories with initial/final constraints. It also explains why pure state constraints require a soft-penalty reformulation to use the presented absolutely continuous PMP.
Appendix A. General Pontryagin’s Maximum Principle with State Constraints
- The finite-horizon problem assumes Lipschitz-regular dynamics and running costs, a C1 initial/final constraint map with Lipschitz derivatives, and a nonempty closed convex constraint set.Under these assumptions, each admissible control has a unique continuous state solution.Source: Appendix A · p. 20
- An optimal trajectory must satisfy PMP conditions using a co-state, cost multiplier, and initial/final constraint multiplier.The pre-Hamiltonian is H(β, x, u, p) = p · f(x, u) − βℓ(x, u), and the initial/final Lagrangian incorporates the endpoint cost and constraint.Source: Appendix A · p. 20
- The PMP also requires the optimal control to maximize the pre-Hamiltonian over admissible controls at each time.Source: Appendix A · p. 20
- For endpoint constraints, the normal cone collects dual vectors whose pairing with every feasible displacement from the constrained point is nonpositive.The appendix uses this normal-cone condition in the endpoint multiplier formulation.Source: Appendix A · p. 20
- Pure state constraints can induce measure-valued PMP multipliers, which the presented absolutely continuous PMP does not directly cover.The main-text soft-penalty reformulation is used to make that PMP applicable.Source: Appendix A · pp. 20–21
Appendix B. Classical Indirect Shooting Method
The indirect shooting method replaces the initial/final PMP system with a root-finding problem over guessed initial co-state and endpoint multipliers. Its practical weakness is sensitivity to the shooting-parameter initialization, which can prevent convergence.
Appendix B. Classical Indirect Shooting Method
- Shooting converts the PMP boundary-value system into a root-finding problem for initial state, initial co-state, and endpoint constraint multiplier.The method assumes C2 data with Lipschitz second derivatives and equality endpoint constraints.Source: Appendix B · p. 21
- The shooting function returns endpoint residuals after integrating the PMP system from a guessed initial state and co-state, with the endpoint multiplier fixed.Source: Appendix B · p. 21
- The root is typically solved by a quasi-Newton method, but sensitivity to the initial shooting-parameter guess can cause non-convergence.The paper identifies this ill-conditioning as motivation for its learning-based approach, which avoids repeated integration and root-finding.Source: Appendix B · p. 21
Appendix C. Training Algorithm
The training procedure analytically solves each agent’s non-interacting latent trajectory, then trains OCFormer on sampled time points using physics-informed and boundary losses. Adam updates are followed by L-BFGS fine-tuning on a fixed uniform grid.
Appendix C. Training Algorithm
- Training takes boundary conditions, a soft-penalty Hamiltonian, boundary weight, Adam and L-BFGS iteration counts, and optional velocity or auxiliary penalty settings.It returns learned physical trajectories and co-states.Source: Appendix C · p. 22
- Each agent’s non-interacting latent trajectory is solved analytically as constant velocity between its prescribed endpoints.The algorithm samples collocation times uniformly over the time horizon and evaluates these latent trajectories in closed form.Source: Appendix C · p. 22
- OCFormer computes physical trajectories and time derivatives through Jacobian-vector products, minimizes the combined loss, takes Adam steps, then fine-tunes with L-BFGS on a fixed uniform grid.Source: Appendix C · p. 22