Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM

1. Problem Statement

The paper addresses the challenge of coordinating multiple agents (e.g., drones, warehouse robots) in structured transportation systems where agents are constrained to predefined routes.

• Constraints: Agents cannot perform spatial rerouting (changing paths) due to infrastructure or operational limits. Collision avoidance must be achieved solely by adjusting the timing of motion (velocity scheduling) along fixed paths.
• Objective: Minimize the total mission completion time (sum of arrival times for agents without fixed deadlines) while satisfying:
  • Fixed departure and optional fixed arrival times.
  • Velocity bounds (min/max speed).
  • Continuous-time collision avoidance: Maintaining a safe distance ($d_{safe}$) between any pair of agents throughout the entire mission horizon.
• Challenge: The problem is nonlinear and nonconvex due to the collision avoidance constraints. Traditional global methods often rely on Mixed-Integer Programming (MIP) to determine passing orders, which leads to combinatorial explosion and poor scalability in dense environments.

2. Methodology

The authors propose a framework that avoids explicit integer sequencing variables (which determine who passes first) by formulating the problem as a continuous optimization over waypoint passage times.

A. Differentiable Surrogate Trajectory Model

To enable gradient-based optimization, the authors replace the standard piecewise-constant velocity model (which creates discontinuous position functions) with a smooth, differentiable approximation:

• Mechanism: They use sigmoid functions to model the transition between waypoints, capturing first-order tracking lag and smooth velocity transitions.
• Benefit: This creates a differentiable mapping from waypoint passage times ($t$) to continuous position profiles ($p$), allowing the use of gradient-based solvers for collision handling.

B. Optimization Formulation

The problem is cast as minimizing the sum of completion times subject to:

1. Linear constraints: Fixed times and velocity bounds.
2. Nonconvex constraints: Pairwise distance $\ge d_{safe}$ for all time steps.

C. Inexact-Projection ADMM Solver

To solve the resulting nonconvex problem efficiently, the authors employ an Alternating Direction Method of Multipliers (ADMM) with an inexact projection strategy:

• Variable Splitting: The problem is decomposed into three variables:
  • $t$: Waypoint passage times.
  • $x$: Segment durations (handling velocity bounds).
  • $z$: A copy of timing variables used specifically for collision evaluation.
• Update Steps:
  1. $t$-update: Solves a sparse linear system (quadratic subproblem) to update timing variables while respecting linear constraints.
  2. $x$-update: Performs a simple projection onto the convex set of velocity limits.
  3. $z$-update (Inexact Projection): Instead of projecting onto the nonconvex collision-free set (which is computationally intractable), the algorithm minimizes a penalty function measuring safety violations over a dense temporal grid. This is done using a Polyak-type gradient step with adaptive momentum to escape numerical stagnation.
• Termination: The algorithm stops when primal residuals are small and safety violations are negligible.

3. Key Contributions

1. Formulation: A novel route-constrained coordination problem formulated as a waypoint-time optimization with distance-based safety constraints defined over the continuous mission horizon, avoiding discrete sequencing variables.
2. Modeling: Development of a differentiable surrogate trajectory model that maps discrete waypoint timings to smooth, continuous position profiles, enabling gradient-based collision correction.
3. Algorithm: An Inexact-Projection ADMM solver that combines structured timing updates with gradient-based collision correction, offering scalability and avoiding the combinatorial complexity of MIP-based approaches.
4. Validation: Comprehensive numerical experiments demonstrating feasibility and efficiency across diverse scenarios.

4. Experimental Results

The method was tested in three distinct scenarios: Random Crossing, Bottleneck, and Graph-Based Networks.

• Random Crossing (Co-directional & Counter-directional):
  • The method successfully resolved overtaking and head-on conflicts.
  • Convergence: Typically converged within 400 iterations.
  • Robustness: Achieved near-perfect success rates (SR) for low-to-moderate congestion. For high congestion ($K=11$, density 10%), success rates dropped slightly due to physical infeasibility (velocity limits), but the algorithm remained robust.
• Bottleneck Scenario:
  • Agents were forced through a narrow corridor, requiring strict sequential passing.
  • The method handled high congestion ($K=11$, density 10%) with a time overhead of only ~27% compared to the theoretical minimum, demonstrating efficient queue management without spatial deviation.
• Graph-Based Network (UAM/Logistics style):
  • Tested on a Delaunay triangulation network.
  • The algorithm achieved 100% success rate when the safety distance was within the geometric limits of the network topology ($d_{safe} < \bar{d}_{safe}$).
  • Performance degraded gracefully as safety distance exceeded geometric feasibility limits.
• Comparison with Baseline:
  • Compared against a hierarchical MIP-SOCP baseline [15].
  • Result: The proposed method consistently produced shorter mission completion times and remained feasible in high-density cases (10% occupancy) where the baseline failed to find a solution.

5. Significance

• Scalability: By eliminating explicit integer sequencing variables, the method avoids the combinatorial explosion associated with traditional global planners, making it suitable for dense multi-agent systems.
• Practicality: It is specifically designed for systems where spatial rerouting is impossible (e.g., air corridors, fixed rail/track systems), a common constraint in real-world logistics and Urban Air Mobility (UAM).
• Efficiency: The use of a differentiable surrogate model allows for the application of efficient gradient-based optimization techniques to a problem that is traditionally non-differentiable and nonconvex.
• Performance: The method outperforms hierarchical baselines in terms of solution quality (mission time) and feasibility in high-congestion scenarios, offering a viable solution for large-scale, route-constrained multi-agent coordination.