Self-driving vehicles, delivery drones, and urban robots all face the same brutal mathematical reality: the more of them you put on the road, the worse the standard tools for keeping them apart perform. Collision detection in dense multi-agent environments traditionally relies on exhaustive pairwise checks, meaning every agent must be compared with every other agent at every timestep, a burden that grows as O(N²) and quickly overwhelms real-time safety budgets. Researchers at the National Institute of Technology Raipur have now unveiled a framework that breaks this quadratic wall while keeping vehicle data private, and their results are turning heads in the autonomous systems community.

The new framework, called MAQDRL — short for Multi-Agent Federated Deep Q-Learning with QuadTree spatial partitioning — is described in an open-access paper published in the journal Cognitive Computation. Led by Aditya Kumar Raj, Anurag Sharma, and K. Jairam Naik, the team set out to solve two bottlenecks that have long plagued autonomous vehicle routing in complex urban settings: the latency and privacy problems of streaming raw sensor data to centralized servers, and the computational explosion of collision checking as fleets grow. Their answer combines three ideas that had rarely been fused together before — lightweight local reinforcement learning, federated averaging of model parameters, and a data structure borrowed from computational geometry.

At the heart of MAQDRL is a deceptively simple division of labor. Each agent, whether a simulated vehicle or a future delivery robot, trains its own compact Deep Q-Network using only local observations: its grid position, the elapsed timestep, its Euclidean distance to its goal, and the average distance to nearby agents within a defined collision boundary. No raw trajectories, sensor streams, or replay-buffer samples ever leave the agent. Instead, after every five episodes, each agent sends only its neural network parameters — a mere 2,629 trainable weights, roughly 10.27 kilobytes in 32-bit floating point — to a mobile edge computing aggregator, where they are blended through federated averaging into a shared global policy that is then redistributed to the fleet. In a ten-agent scenario, an entire synchronization round costs just over 0.20 megabytes of communication, and ten rounds of training consume approximately 2 megabytes in total — a figure the authors describe as modest enough to fit comfortably within the constraints of roadside mobile edge computing units.

The second pillar is the QuadTree, a classic spatial indexing structure that recursively subdivides a two-dimensional region into four quadrants whenever the number of agents in a cell exceeds a preset capacity. In MAQDRL’s simulated world — a 100 × 100 grid populated by ten agents with randomly assigned start positions and unique goals — the tree is rebuilt at every timestep to reflect the agents’ latest locations. A lazy merge policy collapses sibling nodes whose combined agent count falls below half the capacity threshold, preventing the structure from shattering into excessive fragments in sparse regions. The payoff is dramatic: querying which agents lie within a given collision boundary drops from quadratic cost to logarithmic time, O(log N), allowing each agent to check only its spatially relevant neighborhood rather than the entire population. The team’s complexity analysis puts the overall per-timestep cost at O(N(d + log N)), where d is the size of the local policy network — a far cry from the O(N²) dependence that plagues baseline methods such as MADDPG, MAPPO, and MARC, which rely on centralized critics, joint action spaces, or global replay buffers.

The training recipe itself is anchored in a compact neural architecture the authors call SAF-QNet. A five-dimensional state vector — x and y coordinates, goal distance, timestep, and local proximity — feeds into a fully connected hidden layer of 64 ReLU neurons, followed by a 32-neuron hidden layer and a five-output head producing Q-values for the discrete action set: up, down, left, right, or stay. Careful preprocessing underpins stability: state features are min-max normalized to the range [0, 1] so that no single variable dominates gradient calculations, actions are one-hot encoded so the network never mistakes “up” for being numerically adjacent to “down,” and rewards are standardized by subtracting the mean and dividing by the standard deviation of the reward vector. Gaussian noise augmentation with a variance of 0.01 is applied to state trajectories to harden policies against perturbation. The reward function blends a positive signal for reaching the goal, a penalty for collisions, and a proximity term that decays with distance to the target, nudging agents toward short, energy-efficient paths.

The evaluation environment was deliberately designed to be demanding. The benchmark is derived from CVRPTW-style routing instances — the Capacitated Vehicle Routing Problem with Time Windows — although the authors are careful to note that their setup addresses decentralized point-to-point spatial navigation rather than the full constraint-laden route feasibility problem. Because each agent starts from a different position, pursues a different goal, encounters different neighbors, and accumulates different collision and reward histories, the local training data are naturally non-IID, the heterogeneous setting that has historically been the Achilles’ heel of federated learning. Yet the federated averaging procedure appears to tame this heterogeneity: by aggregating parameters every five episodes, the framework reduces the variance of individual updates and preserves the contraction behavior of the Bellman operator, yielding learning curves as smooth as those of a single-agent DQN trained on stable data.

The headline numbers are striking. MAQDRL achieved a task success rate of 97.8 percent, comfortably ahead of MAPPO at 94.8 percent, MADDPG at 95.2 percent, and MARC at 92.2 percent. Collision frequency fell by 73.08 percent relative to MAPPO and 66.13 percent relative to MADDPG, while energy consumption — measured as the summed Euclidean distance traveled by all agents — dropped by 56.52 percent and 55.98 percent against the same two baselines. Over 100 training episodes, MAQDRL recorded just 21 total collisions, compared with 62 for MADDPG, 78 for MAPPO, 98 for MARC, and 192 for a random-policy control. Cumulative rewards told the same story: MAQDRL finished at approximately 125, against 85 for MADDPG, 68 for MAPPO, 60 for MARC, and barely 20 for the random policy. Average energy consumption per episode settled around 265.98 kilojoules for MAQDRL, well below the roughly 604 to 612 kilojoules consumed by MADDPG and MAPPO and the erratic 714.93 kilojoules of the random baseline.

Ablation experiments confirmed that neither of the two innovations alone accounts for the gains. A DQN paired with QuadTree indexing but no federated synchronization showed fast early rewards but plateaued prematurely, unable to propagate successful strategies across agents. A Federated DQN without the QuadTree produced smooth, steady improvement but lacked the spatial awareness needed to respond quickly to proximity conflicts. Only the full integration — local DQN learning, periodic federated averaging, QuadTree-based spatial indexing, and reward shaping — delivered the best trade-off across stability, safety, and energy efficiency, maintaining energy levels roughly 20 to 30 percent below its ablated counterparts. Hyperparameter sweeps reinforced the picture: a conservative learning rate of 0.001 yielded the highest total reward of 4,736 with only 21 collisions, while faster rates of 0.1 and 0.01 triggered aggressive overcorrection, collision spikes of up to four per episode, and energy peaks above 300 kilojoules. Similarly, a slow exploration decay of 0.995 — which preserves exploration longer before committing to exploitation — consistently produced better rewards, fewer collisions, and lower energy use than decay rates of 0.8 or 0.9.

The implications extend well beyond simulation. The authors argue that the framework’s small model footprint, low synchronization overhead, and linear aggregation complexity make it a natural fit for MEC-assisted edge deployments, where roadside units must aggregate updates from many vehicles within tight bandwidth and compute budgets. Keeping raw sensor streams local also sidesteps regional data-privacy regulations and the sub-100-millisecond latency thresholds that centralized LiDAR and V2X transmission can violate. The theoretical analysis offers an intuitive explanation for why the combination works: by confining each agent’s interactions to a small, logarithmically sized spatial neighborhood, the QuadTree dampens the non-stationarity that other agents introduce into the environment, producing smoother temporal-difference targets and a tighter effective contraction factor for the Bellman operator — the mathematical engine that underpins stable reinforcement learning.

The team is candid about the limits. The current experiments ran in a simplified obstacle-free grid with ten agents, and the communication and aggregation analysis is analytical rather than a hardware-level benchmark of inference latency, memory footprint, or energy draw on constrained edge devices. Extreme local density, adversarial agents, noisy localization, and obstacle-rich environments may all demand additional mechanisms, from robust aggregation to asynchronous synchronization and personalized federated learning. Future work will extend the framework toward full CVRPTW-aware routing, test it on realistic traffic simulators such as SUMO and CityFlow, scale the agent population beyond fifty, and deploy the trained policies on single-board computers to validate real-world feasibility. Still, as urban fleets of autonomous vehicles edge closer to reality, the message of this study is clear: the fastest way for machines to avoid crashing into each other may be to learn separately, share sparingly, and always know exactly where to look.

Subject of Research: Multi-agent reinforcement learning for autonomous vehicle routing, combining federated deep Q-learning with QuadTree spatial indexing for collision avoidance and energy-efficient navigation

Subject of Research: Technology and Engineering

Article Title: MAQDRL: QuadTree-Based Multi-Agent Federated Deep Q-Learning for Collision Avoidance and Routing Optimization with MEC-Aware Communication Analysis

Article References: Raj, A. K., Sharma, A., & Naik, K. J. (2026). MAQDRL: QuadTree-Based Multi-Agent Federated Deep Q-Learning for Collision Avoidance and Routing Optimization with MEC-Aware Communication Analysis. Cognitive Computation, 18(1), Article 107. https://doi.org/10.1007/s12559-026-10647-x

Image Credits: AI Generated

DOI: 10.1007/s12559-026-10647-x

Keywords: Autonomous vehicle routing, Multi-agent reinforcement learning, Federated deep Q-learning, QuadTree spatial partitioning, Collision avoidance, Energy consumption, Mobile edge computing, Decentralized decision-making, Federated averaging, Collision frequency, Deep Q-Network, Cumulative rewards

Cite Scienmag News

APA
MLA
Chicago

Denise Maddox. (September 3, 2026). QuadTree-Based Federated Deep Q-Learning Optimizes Routing and Collision Avoidance. Scienmag. https://scienmag.com/quadtree-based-federated-deep-q-learning-optimizes-routing-and-collision-avoidance/

Copy citation
Download RIS

Tags: Autonomous vehicle collision avoidancecollision avoidance in dense environmentsdecentralized autonomous vehicle coordinationdeep reinforcement learning for autonomous systemsDeep reinforcement learning for drone delivery optimizationEfficient multi-agent collision checking techniquesefficient multi-agent system algorithmsfederated deep Q-learningFederated Deep Q-Learning for urban robot routingmulti-agent autonomous vehicle routingMulti-agent deep Q-learning with spatial data structuresmulti-agent traffic managementOptimization of collision avoidance in autonomous systemsPrivacy-aware autonomous vehicle coordinationprivacy-preserving federated learningPrivacy-preserving multi-agent reinforcement learningQuadTree spatial partitioningQuadTree spatial partitioning in multi-agent systemsReal-time collision detection in dense autonomous fleetsreal-time urban robot navigationscalable multi-agent collision detectionScalable multi-agent routing algorithmsspatial data partitioning in roboticsUrban traffic management with federated learning