Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM
Seungyeop Lee, Jong-Han Kim · 2026
Read Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM by Seungyeop Lee, Jong-Han Kim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21913.txt.
Introduction
Lee and Kim schedule speeds for many agents on fixed routes without collisions. Since paths cannot change, they optimize when each agent passes its waypoints. A smooth surrogate model turns those timings into position curves and captures tracking lag. Safety comes from distance penalties checked on a dense time grid. An ADMM solver with inexact projections alternates timing updates with gradient steps that push agents apart. In random-crossing, bottleneck, and network tests, it found feasible schedules and beat a hierarchical baseline on bottleneck finish times.
Catalog record
| CREATOR | Seungyeop Lee, Jong-Han Kim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33901 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21913
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM Seungyeop Lee, Jong-Han Kim 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. I INTRODUCTION Safe coordination is a fundamental requirement in multi-agent transportation systems such as urban air mobility (UAM), automated warehouse logistics, and corridor-based robotic operations. In many practical settings, agents are constrained to predefined routes due to infrastructure or operational requirements. Under such conditions, collision avoidance cannot rely on spatial rerouting and must instead be achieved by coordinating the timing of motion along the routes. Existing approaches to multi-agent collision avoidance can be broadly categorized into reactive local methods and planning-based global methods. Reactive schemes, including reciprocal collision avoidance, safety-critical control, and model predictive control, provide fast responses with low computational overhead [ 6 , 5 , 7 , 8 , 2 , 18 , 4 , 12 ] . However, their reliance on local information often leads to conservatism or deadlocks in dense environments. Global coordination methods, such as priority-based planning, conflict-based search, sequential convex programming, and mixed-integer formulations, leverage global information to produce more consistent solutions [ 11 , 17 , 1 , 13 , 3 , 14 ] . Nevertheless, these approaches primarily resolve conflicts through spatial path modification, which is incompatible with route-constrained systems. Temporal scheduling offers a natural alternative by adjusting agent velocities while preserving fixed paths. A representative framework determines passing orders at conflict regions via mixed-integer programming and subsequently generates dynamically feasible trajectories through convex optimization [ 20 ] . While effective for moderate problem sizes, such hierarchical methods suffer from poor scalability due to the combinatorial growth of discrete sequencing variables, and may exhibit numerical sensitivity in dense scenarios. To alleviate these limitations, recent approaches attempt to avoid explicit sequencing. For instance, [ 16 ] formulates collision avoidance through projection onto nonconvex constraints at intersection points. Although this reduces combinatorial complexity, its event-based formulation is limited in handling shallow-angle crossings or prolonged proximity between agents. Motivated by these challenges, this paper proposes a distance-based velocity scheduling framework for multi-agent systems on predefined routes. Waypoint passage times are treated as optimization variables, and a differentiable surrogate trajectory model maps these timings to continuous position profiles while capturing first-order tracking dynamics. Based on this representation, pairwise safety is enforced through distance-based penalties evaluated over the mission horizon. The resulting nonlinear and nonconvex problem is solved using an inexact-projection Alternating Direction Method of Multipliers (ADMM) framework that combines structured timing updates with gradient-based collision correction, thereby avoiding explicit integer sequencing variables. The main contributions of this paper are threefold. First, we formulate route-constrained multi-agent coordination as a waypoint-time optimization problem with distance-based safety constraints defined over the mission horizon. Second, we develop a differentiable surrogate trajectory model and an inexact-projection ADMM solver tailored to the resulting nonconvex structure. Third, we validate the proposed approach in random-crossing, bottleneck, and graph-based network scenarios, and compare it with a representative hierarchical temporal-scheduling baseline [ 20 ] . The results demonstrate that the proposed method achieves feasible and time-efficient coordination across a range of congestion conditions without requiring explicit priority assignment. Fig. 1 : Illustration of the piecewise linear segment trajectory and associated notations. II PROBLEM STATEMENT II-A Notations Throughout this paper, scalars are denoted by non-bold symbols, vectors by lowercase bold symbols, and matrices by uppercase bold symbols. The set of integers \left\{1,2,\dots,N\right\} is abbreviated as [N] . For a vector \mathbf{x}\in\mathbb{R}^{N} , the difference operator \Delta is defined as \Delta\mathbf{x}:=\mathbf{x}_{2:N}-\mathbf{x}_{1:N-1} , where \mathbf{x}_{i:j} represents the subvector of \mathbf{x} from the i -th to the j -th element. The vertical concatenation of vectors or matrices is denoted by [\mathbf{x}_{1};\mathbf{x}_{2};\dots;\mathbf{x}_{N}]:=[\mathbf{x}_{1}^{T},\mathbf{x}_{2}^{T},\dots,\mathbf{x}_{N}^{T}]^{T} . Furthermore, the indicator function associated with a set \mathcal{C} , denoted by I_{\mathcal{C}}(\mathbf{x}) , is defined as I_{\mathcal{C}}(\mathbf{x})=0 if \mathbf{x}\in\mathcal{C} , and I_{\mathcal{C}}(\mathbf{x})=+\infty otherwise. II-B Assumptions We consider a system consisting of K agents. Agent i is assigned a sequence of N_{i} waypoints \{\mathbf{p}^{(i)}_{n}\}_{n=1}^{N_{i}} together with the corresponding waypoint passage times \mathbf{t}^{(i)}:=[t^{(i)}_{1},\dots,t^{(i)}_{N_{i}}]^{T}\in\mathbb{R}^{N_{i}} . The agent motion is modeled using a segment-wise constant-velocity assumption. Specifically, the agent moves along the straight-line segment connecting \mathbf{p}^{(i)}_{n} and \mathbf{p}^{(i)}_{n+1} with constant velocity. Let the segment duration and length be defined as \Delta t^{(i)}_{n}:=t^{(i)}_{n+1}-t^{(i)}_{n} and d^{(i)}_{n}:=\|\mathbf{p}^{(i)}_{n+1}-\mathbf{p}^{(i)}_{n}\|_{2} , respectively. The velocity along segment n is therefore given by \mathbf{v}^{(i)}_{n}(\mathbf{t}^{(i)})=\frac{\mathbf{p}^{(i)}_{n+1}-\mathbf{p}^{(i)}_{n}}{\Delta t^{(i)}_{n}},\qquad n=1,\dots,N_{i}-1. (1) Fig. 1 illustrates the waypoint-based path representation. To facilitate stable gradient-based collision handling, we later introduce a smooth trajectory approximation while preserving the same timing variables. II-C Problem Formulation The decision variables are the waypoint passage times \{\mathbf{t}^{(i)}\}_{i=1}^{K} . For agents with prescribed terminal times, define \mathcal{K}_{f}\subseteq\{1,\dots,K\} and let \mathcal{K}_{u}:=\{1,\dots,K\}\setminus\mathcal{K}_{f} denote the remaining agents. Let \mathcal{P}:=\{(i,j)\mid 1\leq i<j\leq K\} be the set of unordered agent pairs. The objective is to minimize the sum of completion time of agents without fixed arrival constraints. This promotes early task completion while allowing agents with prescribed terminal times to satisfy their deadlines. The optimization is subject to the following constraints: (i) fixed departure times, (ii) optional fixed arrival times, (iii) speed bounds expressed as linear constraints on segment durations, and (iv) continuous-time collision avoidance throughout the mission horizon. The mission time horizon is defined as \mathcal{T}:=\Big[\min_{i}t^{(i)}_{1},\;\max_{i}t^{(i)}_{N_{i}}\Big]. (2) The resulting optimization problem is formulated as \displaystyle\minimize_{\{\mathbf{t}^{(i)}\}_{i=1}^{K}}\;\; \displaystyle\sum_{i\in\mathcal{K}_{u}}t^{(i)}_{N_{i}} (3) \displaystyle\subjectto \displaystyle t^{(i)}_{1}=t^{(i)}_{s},\quad\forall i\in[K], \displaystyle t^{(i)}_{N_{i}}=t^{(i)}_{f},\quad\forall i\in\mathcal{K}_{f}, \displaystyle\frac{\mathbf{d}^{(i)}}{v_{\max}}\leq\Delta\mathbf{t}^{(i)}\leq\frac{\mathbf{d}^{(i)}}{v_{\min}},\quad\forall i\in[K], \displaystyle\big\|\mathbf{p}^{(i)}(\mathbf{t}^{(i)},\tau)-\mathbf{p}^{(j)}(\mathbf{t}^{(j)},\tau)\big\|_{2}\geq d_{\rm safe}, \displaystyle\forall(i,j)\in\mathcal{P},\ \forall\tau\in\mathcal{T}. where \mathbf{d}^{(i)}:=[d^{(i)}_{1},\dots,d^{(i)}_{N_{i}-1}]^{T} and \Delta\mathbf{t}^{(i)}:=[\Delta t^{(i)}_{1},\dots,\Delta t^{(i)}_{N_{i}-1}]^{T} . The \mathbf{p}^{(i)}(\mathbf{t}^{(i)},\tau) denotes the position of agent i at time \tau when the agent traverses its waypoint sequence according to the waypoint passage times \mathbf{t}^{(i)} . II-D Piecewise Trajectory Approximation The segment-wise constant-velocity model produces discontinuous switching at waypoint times, which makes the inter-agent distance function non-smooth and sensitive to tracking latency. To obtain a differentiable mapping from waypoint times to continuous-time positions, we replace the hard segment activation with smooth sigmoid transitions. Specifically, the velocity of agent i at time \tau is approximated as \mathbf{\tilde{v}}^{(i)}(\mathbf{t}^{(i)},\tau)=\sum_{n=1}^{N_{i}-1}\mathbf{v}^{(i)}_{n}(\mathbf{t}^{(i)})\Big(\sigma\!\big(\beta(\tau-\hat{t}^{(i)}_{n})\big)-\sigma\!\big(\beta(\tau-\hat{t}^{(i)}_{n+1})\big)\Big), (4) where \sigma(x)=1/(1+e^{-x}) , \beta>0 controls the transition sharpness, and \hat{t}^{(i)}_{n}:=t^{(i)}_{n}+b introduces a time bias b to account for tracking delay. Integrating ( 4 ) yields a closed-form position model. Let \zeta(x):=\log(1+e^{x}) denote the softplus function. The position of agent i is then given by \displaystyle\mathbf{\tilde{p}}^{(i)}(\mathbf{t}^{(i)},\tau)=\mathbf{p}^{(i)}_{1}+\sum_{n=1}^{N_{i}-1}\frac{\mathbf{v}^{(i)}_{n}(\mathbf{t}^{(i)})}{\beta}\Big(\zeta\!\big(\beta(\tau-\hat{t}^{(i)}_{n})\big) (5) \displaystyle-\zeta\!\big(\beta(\tau-\hat{t}^{(i)}_{n+1})\big).\Big), which satisfies \mathbf{\tilde{p}}^{(i)}(\mathbf{t}^{(i)},t^{(i)}_{1})=\mathbf{p}^{(i)}_{1} and is differentiable with respect to both \tau and \mathbf{t}^{(i)} . For sufficiently large \beta , the approximation closely matches the original piecewise trajectory while remaining differentiable. Fig. 2 : Comparison of an ideal