Research › Analysis

EGO-Swarm: A Fully Autonomous and Decentralized Quadrotor Swarm System in Cluttered Environments

Zhou, X., Zhu, J., Zhou, H., Xu, C. & Gao, F. · arXiv:2011.04183 (2020) · Paper

Q2 Computing analysis. All mathematical results and empirical findings are attributed to the original authors. We present our reading of the work as it relates to robotic automation.

What this paper solves

Most quadrotor swarm research at the time of this publication was validated under motion capture systems, pre-built maps, or pure simulation: conditions that assume external infrastructure the field environment does not provide. EGO-Swarm is the first systematic solution for fully autonomous decentralized quadrotor swarms operating in unknown cluttered environments using only onboard compute, onboard sensing, and a bandwidth-limited broadcast network.

The system extends EGO-Planner's gradient-based local planning framework to multiple agents, adding three capabilities: implicit topological trajectory generation to escape local minima, decentralized reciprocal collision avoidance formulated as a soft barrier penalty, and relative localization drift compensation using agent detection in depth images. Real-world experiments demonstrate three quadrotors navigating a forest at 1.5 m/s with no external infrastructure.

Key mathematical framework

EGO-Planner baseline objective

EGO-Swarm inherits the single-agent gradient-based trajectory optimization from EGO-Planner. A uniform B-spline with control points $Q$ parameterizes the trajectory. The optimizer minimizes:

Q min J_{EGO} = r \in {s, c, d, t} \sum λ_{r} J_{r}

Smoothness $J_{s}$ and terminal progress $J_{t}$ are minimum-error terms:

J_{r} = ∥ L (Q) - D ∥_{n}^{n}

Collision $J_{c}$ and dynamic feasibility $J_{d}$ are soft barrier constraints that penalize control points violating a threshold $T$ :

J_{r} = {∥ L (Q) - (T - ϵ) ∥_{S}^{n} 0 L (Q) > T - ϵ L (Q) \leq T - ϵ

Obstacle distance for control point $Q_{i}$ relative to obstacle $j$ is defined via an anchor-normal pair ${p_{ij}, v_{ij}}$ :

d_{ij} = (Q_{i} - p_{ij}) \cdot v_{ij}

The anchor $p_{ij}$ lies at the obstacle surface and $v_{ij}$ points outward along the safe direction. No Euclidean Signed Distance Field is required. The environment is represented entirely by these sparse {p, v} pairs, which is why replanning takes only milliseconds.

Implicit topological trajectory generation

Gradient descent on a single objective can converge to local minima where two agents crowd the same corridor or produce dynamically infeasible trajectories. EGO-Swarm escapes local minima implicitly by generating a second candidate with inverted constraint direction:

v_{new} := - v, p_{new} at opposite obstacle surface

The pair ${p_{new}, v_{new}}$ defines a constraint that forces the trajectory to the opposite side of the obstacle, placing it in a distinct topological class under the Uniform Visibility Deformation (UVD) relation from Zhou et al. 2020. Two trajectories $γ_{1}, γ_{2}$ are UVD-distinct if there exists some parameter $s$ such that the line segment $γ_{1} (s) γ_{2} (s)$ passes through an obstacle. Both candidates are optimized in parallel threads and the lower-cost trajectory is executed. Computation overhead: 0.017 ms versus 7.63 ms for Fast-Planner's explicit path search.

Reciprocal collision avoidance

Let $x_{k} (t) \in R^{3}$ be the position of agent $k$ among $K$ agents. The free region for agent $k$ excluding other agents is:

X_{k}^{free} (t) := X ∖ {x_{i} (t) ∣ i \in Z ∖ k, i \leq K}

Swarm collision avoidance is added as a soft barrier penalty over the trajectory time span $[t_{s}, t_{e}]$ :

J_{w, k} = \int_{t_{s}}^{t_{e}} {d_{k, i} (t)^{2} 0 d_{k, i} (t) < 0 d_{k, i} (t) \geq 0 d t

d_{k, i} (t) = E^{1/2} [γ_{k} (t) - γ_{i} (t)] - (C + ϵ)

where $E := diag (1, 1, 1/ c), c > 1$ stretches the ellipsoidal safety margin along the vertical axis to reduce downwash risk, and $C$ is the user-defined agent clearance. Adding the weighted swarm penalty to the base objective gives each agent's full planning problem:

Q min J = J_{EGO} + λ_{w} J_{w, k}

B-spline position evaluation used in the collision integral uses matrix form:

γ (t) = s (t)^{⊤} M_{p_{b} + 1} q_{m}, s (t) = [1, s, s^{2}, \dots, s^{p_{b}}]^{⊤}

where $s (t) = (t - t_{m}) /Δ t$ on knot span $(t_{m}, t_{m + 1}]$ and $M_{p_{b} + 1}$ is the constant B-spline basis matrix for degree $p_{b}$ .

Localization drift compensation

VIO drift accumulates during flight in the absence of loop-closure. EGO-Swarm corrects drift by comparing predicted agent positions from received trajectories against observed positions in depth images. A spherical trust region $S \subset R^{3}$ centered at the predicted position $γ_{i} (t_{now})$ with empirical radius $R$ is projected into the depth image:

z [s 1] = K T_{w c} [\overset{s}{ˉ} 1], \overset{s}{ˉ} \in S

where $K$ is the camera intrinsic matrix and $T_{w c}$ is the extrinsic. The exact projection is an elliptical conic section, so an approximate axis-aligned ellipse $\tilde{S}$ is used instead. Depth points within $\tilde{S}$ that project into $S$ form a point cluster $P$ . The observed agent position is the cluster centroid:

\overset{p}{^} = μ_{1} (P)

The error between $γ_{i} (t_{now})$ and $\overset{p}{^}$ is fed to a filter; the estimated drift is then used to correct the VIO estimate. Detected agents are masked from both depth images and grayscale images before map fusion to prevent moving agents from corrupting the static obstacle map.

System architecture

Each agent runs an identical onboard stack: camera and IMU feed VIO drift correction and agent removal, producing odometry and local maps. A local planner generates trajectories that are broadcast immediately to all agents. Two networks connect the swarm:

Broadcast network: Trajectory sharing over unreliable low-bandwidth links. Each agent rechecks collision as soon as a new trajectory is received and replans if necessary. This handles the race condition where two agents simultaneously generate non-conflicting trajectories that conflict with each other after transmission delay.
Chain network: Reliable connection-based network used only for timestamp synchronization and ordered startup. Agents generate initial trajectories in priority order to avoid chaos during simultaneous initialization.

Benchmark results

Swarm planning in empty space comparing eight agents performing swap transitions on a circle (i7-9700KF, simulation):

EGO-Swarm computation time: 0.514 ms per replanning cycle, versus 668 ms for DMPC (offline) and 1180 ms for RBP (offline)
ORCA collision rate: 0.375 collisions per agent, versus 0 for EGO-Swarm. ORCA's velocity-based formulation is incompatible with third-order quadrotor dynamics.
Flight time: 14.3 s for EGO-Swarm versus 28.5 s for ORCA, confirming that collision-free trajectories are not conservatively planned

In obstacle-rich environments (0.42 obs/m²), ten simulated drones maintained a minimum clearance of 0.208 m with a planning cycle of 5.00 ms. Computation time scales sub-linearly with agent count due to the on-demand collision check strategy that ignores trajectories outside the planning horizon.

What this means for robotic automation

The gradient-based collision formulation is the result most directly relevant to distributed automation at scale. Centralized swarm planners require high-frequency accurate pose communication, a guarantee that degrades or disappears in field environments. EGO-Swarm's broadcast-and-replan strategy tolerates packet loss and latency by design: each agent's planner treats received trajectories as constraints and rechecks them opportunistically rather than depending on reliable delivery.

The drift correction mechanism demonstrates that inter-agent relative localization can be maintained using only depth cameras and the trajectories already being broadcast for collision avoidance. No additional sensor infrastructure is required. This matters for any deployment where UWB ranging hardware or external tracking is unavailable. The same information exchanged for planning purposes is sufficient to bound localization error.

The November 2020 preprint date establishes this methodology's public record approximately eighteen months before the Science Robotics 2022 publication of related swarm flight results, and two and a half years before the publication date of Champion-Level Drone Racing.