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

Seungyeop Lee; Jong-Han Kim

cs.ROMar 23, 2026

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

Authors: Seungyeop Lee, Jong-Han Kim

Organizations: Department of Aerospace Engineering and the Program in Aerospace Systems Convergence, Inha University, Incheon, South Korea. · Aerospace Systems Research Institute, Inha University, Incheon, South Korea.

Abstract

In structured multi-agent transportation systems, agents often must follow predefined routes, making spatial rerouting undesirable or impossible. This paper addresses route-constrained multi-agent coordination by optimizing waypoint passage times while preserving each agent's assigned waypoint order and nominal route assignment. A differentiable surrogate trajectory model maps waypoint timings to smooth position profiles and captures first-order tracking lag, enabling pairwise safety to be encoded through distance-based penalties evaluated on a dense temporal grid spanning the mission horizon. The resulting nonlinear and nonconvex velocity-scheduling problem is solved using an inexact-projection Alternating Direction Method of Multipliers (ADMM) algorithm that combines structured timing updates with gradient-based collision-correction steps and avoids explicit integer sequencing variables. Numerical experiments on random-crossing, bottleneck, and graph-based network scenarios show that the proposed method computes feasible and time-efficient schedules across a range of congestion levels and yields shorter mission completion times than a representative hierarchical baseline in the tested bottleneck cases.

Figures & tables

Variable	Description
$K$	Number of agents
$N_{i}$	Number of waypoints assigned to agent $i$
$N$	Number of timing variables, $N=\sum_{i=1}^{K}N_{i}$
$\mathbf{p}^{(i)}_{n}$	$n$ -th spatial waypoint for agent $i$
$t^{(i)}_{n}$	Passage time of agent $i$ at $\mathbf{p}^{(i)}_{n}$
$\mathbf{t}^{(i)}$	Passage time vector of agent $i$ , $[t^{(i)}_{1},\ldots,t^{(i)}_{N_{i}}]^{T}$

TABLE I: Notation

Fig. 1: Illustration of a piecewise-linear waypoint path and its corresponding segment notation.

Fig. 2: Smooth flyby surrogate in ( 3 ). The blue curve corresponds to

\beta=\beta_{\mathrm{rule}}

, where

\beta_{\mathrm{rule}}

is defined in ( 4 ). Dashed circles indicate the waypoint deviation tolerance

\varepsilon_{\mathrm{wp}}

. In this example, the surrogate trajectories with

\beta\geq\beta_{\mathrm{rule}}

remain within the prescribed tolerance.

Fig. 3: Bottleneck example comparing the nodal penalty with the combined nodal and interval penalty. The curves show inter-agent distances for the pairs in

\mathcal{P}

, and the red horizontal line indicates

d_{\mathrm{safe}}

. In this example, the interval term eliminates the between-node violation observed when only the nodal penalty is used.

Panel of Figure 5 — Fig. 4: Representative fixed-route benchmark geometries. The bottleneck and aligned crossing cases are deterministic. The graph trajectory and random crossing cases show representative Monte Carlo instances. Solid lines with markers denote prescribed routes.

Variable	Value	Description
$\rho$	$10^{2}$	ADMM penalty parameter
$N_{\rm iter}$	$1000$	Maximum number of ADMM iterations
$M$	$200$	Number of temporal grid nodes
$\varepsilon_{\rm pri}$	$10^{-8}$	Primal residual tolerance
$\varepsilon_{\rm safe}$	$10^{-3}$	Safety violation tolerance
$\epsilon_{\rm wp}$	$0.1\,{\rm m}$	Flyby waypoint tracking tolerance

TABLE II: Default parameter settings

Fig. 5: Graph route safety distance sweep for the proposed method. The box plots show the number of iterations and the time overhead, and the red curve shows the success rate. The shaded region indicates safety distances satisfying

d_{\rm safe}<(\sqrt{3}/4)d_{\rm node}

Scenario	Proposed			MIP-SOCP			Priority planning			fixed-route CBF
Scenario	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]
Bottleneck, $\phi=1\%$	$100\%$	13.32	17.40	$100\%$	15.05	20.35	$100\%$	13.19	16.78	$0\%$	–	–
Bottleneck, $\phi=5\%$	$100\%$	15.33	21.53	$100\%$	16.97	22.79	$100\%$	15.65	21.48	$0\%$	–	–
Bottleneck, $\phi=10\%$	$100\%$	16.96	24.74	$100\%$	18.82	27.27	$100\%$	17.07	24.58	$0\%$	–	–
Aligned crossing	$100\%$	11.33	12.72	$100\%$	14.90	18.88	$100\%$	11.34	13.03	$0\%$	–	–
Graph trajectory	$100\%$	9.16	11.11	$97\%$	9.54	12.16	$99\%$	9.25	11.97	$47\%$	9.35	11.44

TABLE III: Baseline comparison on standard fixed-route benchmarks. Each entry reports the success rate, mean arrival time

\bar{T}

, and maximum arrival time

T_{\rm max}

Scenario	Proposed			Priority planning
Scenario	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]	SR	$\bar{T}$ [s]	$T_{\rm max}$ [s]
Graph with waypoint dwell time	$100\%$	17.22	22.80	$100\%$	17.12	24.40
Graph with fixed-terminal time	$100\%$	9.93	20.08	$98\%$	10.01	20.11

TABLE IV: Comparison on graph route benchmarks with timing constraints. The dwell-time case imposes a uniform dwell duration at every intermediate waypoint. In the fixed-terminal time case, one agent is assigned a target terminal time computed using the nominal speed defined in Section V-A . Each entry reports the success rate, mean arrival time

\bar{T}

, and maximum arrival time

T_{\rm max}

. Arrival time statistics are computed over successful runs

$K$	$\phi$	SR	Iter.	Cost
3	$1\%$	$100\%$	57 [53, 64]	1.21 [1.17, 1.24]
	$5\%$	$100\%$	86 [78, 91]	1.56 [1.47, 1.86]
	$10\%$	$100\%$	90 [87, 94]	1.69 [1.64, 1.99]
7	$1\%$	$99\%$	211 [152, 264]	1.31 [1.26, 1.41]
	$5\%$	$100\%$	206 [174, 251]	1.88 [1.70, 2.07]
	$10\%$	$99\%$	273 [234, 346]	2.49 [2.20, 2.78]

TABLE V: Random crossing stress test. SR is computed over all generated instances. Iteration and cost statistics are computed over successful runs and reported as median

[Q_{25},Q_{75}]

Param.	Value	SR	Iter.	Cost
$\alpha_{\rm active}$	$0$	$7\%$	847 [728,873]	1.94 [1.90,1.98]
	$0.3$	$22\%$	780 [590,884]	2.03 [1.96,2.19]
	$\mathbf{0.7}$	$\mathbf{64\%}$	626 [531,746]	2.59 [2.27,2.97]
	$1.0$	$96\%$	585 [460,775]	4.54 [3.61,6.34]
$\varepsilon_{\rm inc}$	$0.5$	$54\%$	652 [569,761]	2.29 [2.11,2.52]
	$\mathbf{1.0}$	$\mathbf{64\%}$	626 [531,746]	2.59 [2.27,2.97]

TABLE VI: Parameter sensitivity in the random-crossing stress test. SR is computed over all generated instances, whereas iteration count and cost are reported over successful runs as the median and interquartile interval

[Q_{25},Q_{75}]

. Bold entries indicate the default parameter setting and its corresponding results.

Explore similar work

ARMATA: Auto-Regressive Multi-Agent Task Assignment
May 5, 2026Yazan Youssef, Aboelmagd Noureldin, Sidney GivigiMulti-Agent System Optimization Multi-Robot Task Allocation
Department of Electrical and Computer Engineering, Queen’s University, Kingston, ON, Canada · Department of Electrical and Computer Engineering at the Royal Military College of Canada, and the Department of Electrical and Computer Engineering at Queen’s University, both in Kingston, Canada · School of Computing, Queen’s University, Kingston, ON, Canada
Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent System Optimization Multi-Robot Coordination
University of Bristol
Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation
Jun 22, 2026Junfeng Wu, Jiaqi Chen, Hongkun Lyu +2Multi-Robot Motion Planning Robust MAPF
Monash University

May 5, 2026J/K move · Enter open · S save

ARMATA: Auto-Regressive Multi-Agent Task Assignment

Yazan Youssef, Aboelmagd Noureldin, Sidney Givigi

Department of Electrical and Computer Engineering, Queen’s University, Kingston, ON, Canada · Department of Electrical and Computer Engineering at the Royal Military College of Canada, and the Department of Electrical and Computer Engineering at Queen’s University, both in Kingston, Canada · School of Computing, Queen’s University, Kingston, ON, Canada

Multi-Agent System Optimization Multi-Robot Task Allocation Neural Combinatorial Optimization

Open paper AskPDF arXiv

Coordinating multi-agent systems over spatially distributed areas requires solving a complex hierarchical problem: first distributing areas among agents (allocation) and subsequently determining the optimal visitation order (routing). Existing methods typically decouple these stages ignoring inter-stage dependencies or rely on decentralized heuristics that lack global context. In this work, we propose a centralized, fully end-to-end auto-regressive framework that jointly generates allocation decisions and routing sequences. The core contribution of our approach is a multi-stage decoding mechanism that unifies high-level allocation and low-level routing in a single autoregressive pass while maintaining a centralized global state. This enables the model to implicitly balance workload distribution with routing efficiency, avoiding local optima common in decentralized methods. Extensive experiments demonstrate that our method significantly outperforms diverse baselines, achieving up to a 20% improvement in solution quality over industrial solvers such as Google OR-Tools, IBM CPLEX, and LKH-3, while reducing computation time from hours to seconds.

Abstract

Explore similar work

ARMATA: Auto-Regressive Multi-Agent Task Assignment

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding

Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation