Resilient and Efficient Allocation for Large-Scale Autonomous Fleets via Decentralized Coordination
Ashish Kumar Perukari 1 , Polina Khoroshevskaya 1 · 2025
Read Resilient and Efficient Allocation for Large-Scale Autonomous Fleets via Decentralized Coordination by Ashish Kumar Perukari 1 , Polina Khoroshevskaya 1 (2025) 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-2511-12879.txt.
Introduction
Ashish Kumar Perukari and Polina Khoroshevskaya coordinate resources for large fleets of autonomous vehicles and satellites. Fleets must share scarce things: energy, charger access, maintenance slots, time windows, and bandwidth, all under uncertainty about future consumption. Their approach gives each agent a risk model shaped by local side information, links the agents with chance constraints on failures. Lets them agree through a lightweight decentralized routine run over a sparse communication network, avoiding any single point of failure.
Tests used real urban road networks with autonomous vehicles and a representative satellite constellation, against greedy, uninformed, and all-knowing central baselines. The method cut failure rates by roughly a third to a half at the same cost. It scaled to thousands of agents with near-linear running time while keeping plans feasible with high probability. The work targets operators who need near-central quality without a fragile central controller.
Catalog record
| CREATOR | Ashish Kumar Perukari 1 , Polina Khoroshevskaya 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-12879
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Resilient and Efficient Allocation for Large-Scale Autonomous Fleets via Decentralized Coordination Contact: [email protected] , [email protected] . Ashish Kumar Perukari 1 , Polina Khoroshevskaya 1 Abstract Operating large autonomous fleets demands fast, resilient allocation of scarce resources—such as energy and fuel, charger access and maintenance slots, time windows, and communication bandwidth—under uncertainty. We propose a side-information–aware approach for resource allocation at scale that combines distributional predictions with decentralized coordination. Local side information shapes per-agent risk models for consumption, which are coupled through chance constraints on failures. A lightweight consensus-ADMM routine coordinates agents over a sparse communication graph, enabling near-centralized performance while avoiding single points of failure. We validate the framework on real urban road networks with autonomous vehicles and on a representative satellite constellation, comparing against greedy, no-side-information, and oracle central baselines. Our method reduces failure rates by 30–55% at matched cost and scales to thousands of agents with near-linear runtime, while preserving feasibility with high probability. I Introduction Autonomous fleets—from electric vehicles to satellite constellations—face the challenge of allocating scarce resources (energy, charging capacity, bandwidth) among distributed agents under stochastic consumption and capacity constraints. Centralized optimization achieves high-quality solutions but suffers from communication overhead, computational bottlenecks, and single points of failure [ 4 , 10 ] . Conversely, decentralized heuristics offer computational scalability and fault tolerance [ 29 ] but lack coordination mechanisms, typically yielding high constraint violation rates or inefficient resource utilization when capacity is limited. An underutilized opportunity in fleet resource allocation lies in exploiting side information—contextual features correlated with but not deterministically specifying resource consumption. For electric vehicles, energy consumption depends on route topology, elevation profiles, traffic conditions, and ambient temperature [ 17 ] ; similar principles apply to transit planning [ 39 ] and stochastic routing with reliability constraints [ 46 ] . For satellite constellations, power and thermal loads vary with orbital position, sun angle, payload activity, and communication link utilization [ 44 ] . Analogous resource management challenges arise in agricultural logistics [ 37 ] and other domains. Recent advances suggest that conditioning resource models on such features can significantly tighten uncertainty estimates [ 1 , 18 ] , enabling more efficient allocation without sacrificing safety. However, integrating feature-based consumption models into large-scale distributed coordination algorithms remains an open challenge, particularly when predictive models must be calibrated online and safety guarantees preserved under model misspecification. This paper presents DESIRA (Decentralized Side-Information Resource Allocation), a framework combining side-information–conditioned risk shaping with scalable consensus-based coordination. The approach models uncertain resource consumption via distributional predictions conditioned on local contextual features, translating these predictions into risk-adjusted allocation requirements through chance constraints and Conditional Value-at-Risk (CVaR) penalties [ 31 ] . To achieve coordination without centralized control, the framework employs a consensus-ADMM algorithm [ 9 ] that decomposes capacity constraints across a sparse communication graph, enabling agents to reach near-globally-optimal allocations through local message passing. While resource-constrained MDPs [ 7 , 6 ] provide guarantees for single-agent planning with consumption constraints, our approach addresses decentralized multi-agent coordination where capacity is shared and coupling constraints arise from global resource limits. Experiments on real-world urban road networks extracted from OpenStreetMap [ 8 ] with 200–2000 agents and satellite constellation scenarios demonstrate that incorporating side information reduces failure rates by 30–55% compared to methods ignoring contextual features, while maintaining costs within 5–10% of centralized oracles. The decentralized algorithm exhibits near-linear computational scaling and requires only 10–20 iterations to converge across all tested scales. The key technical contributions are: (i) a tractable reformulation of chance-constrained resource allocation via side-information–conditioned risk quantiles, enabling distributed agents to compute local safety buffers without centralized coordination; (ii) a consensus-ADMM decomposition that separates local consumption modeling from global capacity enforcement through efficient projection operators; (iii) online calibration mechanisms based on conformal prediction that maintain probabilistic safety guarantees under model drift; and (iv) empirical validation demonstrating scalability to thousands of agents and cross-domain applicability from urban transportation to orbital systems. II Related Work Fleet coordination and stochastic optimization. Classical vehicle routing problems [ 42 , 25 ] and recent EV charging coordination work [ 19 , 16 ] typically assume deterministic or stationary consumption models. Multi-robot task allocation [ 23 , 20 ] and satellite resource management [ 44 , 22 ] face similar challenges but do not systematically leverage contextual side information. Stochastic programming [ 5 , 34 ] and chance-constrained optimization [ 12 , 28 , 30 ] provide frameworks for handling uncertainty, with scenario-based methods [ 11 ] offering distribution-free guarantees. CVaR and coherent risk measures [ 31 , 32 , 2 ] enable tractable tail risk management, with applications to risk-sensitive MDPs [ 13 ] . Distributed optimization. ADMM [ 9 ] decomposes problems via augmented Lagrangian relaxations. Consensus algorithms [ 29 , 45 ] and distributed subgradient methods [ 27 , 26 ] enable coordination over communication graphs. However, integration with online prediction and side-information–based risk shaping has received limited attention. Learning from side information. Contextual bandits [ 24 , 1 , 18 ] and conformal prediction [ 43 , 33 ] leverage features to improve prediction, but typically focus on single-agent settings. Foundational work on efficient learning with spatial side information in MDPs [ 41 ] demonstrated how local structure reduces sample complexity. Subsequent advances enabled expedited online learning [ 38 ] with convergence guarantees and safety-certified exploration [ 40 , 3 ] under probabilistic constraints. This work extends these principles to distributed multi-agent resource allocation, integrating side-information–conditioned risk models with decentralized coordination under capacity coupling. III Problem Formulation This section formalizes the decentralized resource allocation problem under stochastic consumption and capacity constraints, introducing the chance-constrained formulation and its consensus-based decomposition for distributed coordination. Consider N agents on network \mathcal{G}=(\mathcal{V},\mathcal{E}) with initial endowment E_{i}^{0} and stochastic consumption X_{i} conditioned on side information \phi_{i}\in\mathbb{R}^{d} . For electric vehicles, \phi_{i} includes route characteristics, traffic conditions, and ambient temperature [ 17 ] ; for satellites, orbital position, sun angle, and payload activity [ 44 ] . Agents access S resource stations with capacities c_{s} . Let a_{i,s}\geq 0 denote allocation of agent i at station s . The optimization problem minimizes total cost plus conditional value-at-risk (CVaR) penalty on resource shortfall: \displaystyle\min_{\{a_{i}\}}\; \displaystyle\sum_{i=1}^{N}\Big(J_{i}(a_{i})+\lambda\,\text{CVaR}_{\alpha}\big[\text{shortfall}_{i}(a_{i})\big]\Big) (1) s.t. \displaystyle\sum_{i=1}^{N}a_{i,s}\leq c_{s},\;\forall s,\quad a_{i,s}\geq 0, (2) \displaystyle\mathbb{P}\big(X_{i}>E_{i}^{0}+\textstyle\sum_{s}a_{i,s}\mid\phi_{i}\big)\leq\varepsilon,\;\forall i, (3) where \text{shortfall}_{i}(a_{i})=\max(0,X_{i}-E_{i}^{0}-\sum_{s}a_{i,s}) represents resource deficit, J_{i} is a convex separable cost function (e.g., quadratic deviation from desired allocation), and \lambda,\alpha control risk aversion. The chance constraint ( 3 ) ensures each agent’s probability of shortfall remains below threshold \varepsilon . Under Gaussian assumption X_{i}\mid\phi_{i}\sim\mathcal{N}(\mu_{i}(\phi_{i}),\sigma_{i}^{2}(\phi_{i})) , the chance constraint becomes deterministic: \sum_{s}a_{i,s}\geq\mu_{i}(\phi_{i})+\Phi^{-1}(1-\varepsilon)\sigma_{i}(\phi_{i})-E_{i}^{0} , where \Phi^{-1} is the inverse standard normal CDF. For decentralized coordination, introduce consensus variables z_{i} and communication graph \mathcal{C} with neighbors \mathcal{N}(i) . The consensus formulation enforces a_{i}=z_{i} and global capacity constraints via ADMM: \displaystyle\min_{\{a_{i},z_{i}\}}\; \displaystyle\sum_{i}\big(J_{i}(a_{i})+\lambda\,\text{CVaR}_{\alpha}[\text{shortfall}_{i}]\big) (4a) s.t. \displaystyle\sum_{i}z_{i,s}\leq c_{s}\;\forall s,\quad a_{i}=z_{i}\;\forall i. (4b) This decomposition allows agents to solve local subproblems while coordinating through message passing over \mathcal{C} . IV Methodology This section develops the decentralized allocation algorithm, beginning with side-information–conditioned risk modeling, continuing with the consensus-ADMM iteration structure, and concluding with complexity analysis and calibration procedures for maintaining safety guarantees. IV-A Side-Information–Aware Risk Shaping Each agent i estimates consumption from historical telemetry via a heteroscedastic Gaussian model: X_{i}\mid\phi_{i}\sim\mathcal{N}(\mu_{i}(\phi_{i}),\sigma_{i}^{2}(\phi_{i}))