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

May 5, 2026

ARMATA: Auto-Regressive Multi-Agent Task Assignment

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.

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

Ask PDF

May 15, 2026

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

Multi-robot systems are integral to modern logistics, but their capabilities are often limited to tasks executable by individual agents. This paper addresses a critical gap in existing frameworks like Multi-Agent Path Finding (MAPF) and Task Allocation and Path Finding (TAPF), which lack true cooperation for transporting large items that require multiple agents. To this end, we formalise the Cooperative Transportation Task Allocation and Path Finding (CT-TAPF) problem, which integrates team formation, task assignment, and collision-free pathfinding. We present an optimal solver, Cooperative Transportation Task Conflict-Based Search (CT-TCBS), which features a novel Incremental Expansion strategy to tackle the combinatorial explosion inherent in team formation. Recognising the computational cost of optimality, we also develop a family of sub-optimal solvers that employ a global, task-centric perspective, selecting the next task to assign based on a global difficulty metric (Best Task or Worst Task). Our comprehensive empirical evaluation demonstrates three key findings: (1) the incremental expansion strategy significantly outperforms the naive combinatorial approach by successfully pruning the dominant task-allocation search space; (2) we identify a task-conflict expansion dilemma, where sophisticated conflict resolvers effective for large-agent pathfinding subproblems can be detrimental in the integrated CT-TAPF setting; and (3) our proposed sub-optimal solvers establish a new, more efficient frontier on the solution quality-runtime spectrum compared to "nn-" agent-centric baselines. This work provides a foundational framework and a set of effective algorithms for a new, practical class of cooperative multi-agent problems.

Ning Zhou, Nikolai W. F. Bode, Edmund R. Hunt

University of Bristol

Multi-Agent System Optimization Multi-Robot Coordination Conflict-Based Search Multi-Robot Task Allocation Multi-Agent Path Finding

Ask PDF

Jun 22, 2026

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

Multi-Agent Path Finding (MAPF) is a problem that requires computing collision-free paths for a set of agents from their start locations to designated goal locations. The problem has broad applications in domains where teams of robots must operate in a coordinated manner. ORCA* is a real time MAPF solver that assigns for each timestep a velocity for each agent. Due to its real time nature, it is myopic to future deadlocks that result from current decisions. ORCA*-MAPF attempts to remedy this limitation by introducing fallback mechanisms when deadlocks are detected. However, post hoc interventions often introduce significant flowtime overhead. In this paper, we introduce C-ORCA* and C-ORCA*-MAPF, continuous space MAPF algorithms that incorporate agents' entire spatial trajectory and their spatial dependencies to proactively prevent deadlocks from occurring, thus avoiding the high flowtime overhead associated with post hoc corrections in ORCA*-MAPF. The C-ORCA* family of algorithms significantly outperform previous state-of-the-art in terms of solve rate, runtime, and flowtime.

Junfeng Wu, Jiaqi Chen, Hongkun Lyu +2

Monash University

Multi-Robot Motion Planning Robust MAPF Multi-Agent Path Finding

Ask PDF