PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xin Zhou, Jiangchao Zhu, Hongyu Zhou, Chao Xu, Fei Gao

arXiv:2011.04183v3cs.RO

TL;DR

EGO-Swarm addresses multi-robot navigation in unknown cluttered environments using only onboard resources. It combines gradient-based local planning, lightweight topological trajectory generation, decentralized collision avoidance, and drift correction, and validates the system in simulation and real-world experiments.

  • Problem

    Quadrotor swarms must navigate unknown obstacle-rich environments despite limited sensing, unreliable communication, and inconsistent localization, while few real-world systems combine this with onboard processing.

  • Method

    The system combines EGO-Planner-based gradient planning with implicit topological planning, reciprocal collision penalties, unreliable trajectory sharing, and depth-image agent detection for drift correction.

  • Results

    Real-world experiments validate EGO-Swarm's robustness and efficiency, while benchmark comparisons demonstrate short computation time and high trajectory quality.

  • Takeaways & Limitations

    EGO-Swarm provides a fully autonomous decentralized quadrotor-swarm system for navigation in unknown cluttered environments using onboard resources.

Abstract

from arXiv · show

This paper presents a decentralized and asynchronous systematic solution for multi-robot autonomous navigation in unknown obstacle-rich scenes using merely onboard resources. The planning system is formulated under gradient-based local planning framework, where collision avoidance is achieved by formulating the collision risk as a penalty of a nonlinear optimization problem. In order to improve robustness and escape local minima, we incorporate a lightweight topological trajectory generation method. Then agents generate safe, smooth, and dynamically feasible trajectories in only several milliseconds using an unreliable trajectory sharing network. Relative localization drift among agents is corrected by using agent detection in depth images. Our method is demonstrated in both simulation and real-world experiments. The source code is released for the reference of the community.

I. INTRODUCTION

EGO-Swarm addresses autonomous quadrotor-swarm navigation in unknown cluttered environments using onboard resources despite sensing, communication, and localization challenges. It combines lightweight topological planning with decentralized reciprocal collision avoidance and validates the integrated system experimentally.

  • Motivation: Few real-world systems combine autonomous navigation and multi-agent control for quadrotor swarms sharing unknown space with only onboard processing.Deployment is complicated by obstacle parameterization, limited sensing range, unreliable bandwidth-limited communication, and localization drift.
  • System scope: EGO-Swarm extends EGO-Planner into a systematic solution requiring neither external localization and computation nor a pre-built map.The system targets high-performance travel by quadrotor swarms in cluttered environments.
  • Planning: Topological planning helps escape local minima, while a weighted swarm-collision penalty enables decentralized reciprocal collision avoidance.The penalty compares future agent distributions with the trajectory being optimized, and implicit front-end path search requires nearly no extra computation.
  • Validation: Real-world experiments validate the proposed swarm system, which integrates perception, planning, and control onboard.Comparisons with several state-of-the-art methods are reported for computation efficiency and robustness.
  • Robustness: The framework is decentralized and asynchronous, designed to remain effective despite unreliable communication and localization drift.Relative drift that can increase to half a meter is corrected by comparing witnessed-agent observations with trajectory-evaluation predictions.

II. RELATED WORKS

Prior work establishes gradient-based local planning, topological planning, and decentralized collision avoidance as separate components. The paper positions EGO-Swarm against methods that lack integrated sensing, mapping, planning, or full autonomy in field environments.

  • Gradient-based local planning: Gradient-based local planning formulates quadrotor navigation as unconstrained nonlinear optimization while accounting for smoothness, feasibility, and safety.EGO-Planner reduces computation time through a more compact environment representation and provides the basis for this work.
  • Topological planning: Topological planners commonly search for distinct-homotopy initial paths before back-end optimization, but three-dimensional homology is more difficult to exploit.Prior methods use Voronoi, sampling-based, or visibility-deformation front-ends.
  • Decentralized approaches: Decentralized approaches use velocity obstacles or related strategies for collision avoidance among point, holonomic, and non-holonomic agents.These methods address multi-agent planning but differ in system assumptions and deployment settings.
  • Gap: Existing algorithms were often validated in simulation without integrating sensing, mapping, and planning, while other methods lack full autonomy in field environments.Reported limitations include reliance on accurate high-frequency pose communication or ad hoc planning priority.

III. IMPLICIT TOPOLOGICAL TRAJECTORY GENERATION OF GRADIENT-BASED LOCAL PLANNING

The system extends EGO-Planner with implicit topological trajectory generation inside a gradient-based nonlinear optimizer. It uses obstacle-derived direction pairs to generate alternative local minima without explicit path search.

  • EGO-Planner formulates trajectory generation as nonlinear optimization balancing smoothness, collision, dynamic feasibility, and terminal progress.
  • The optimizer uses minimum-error terms and soft-barrier terms, with the latter penalizing decision variables that exceed specified thresholds.
  • Obstacle distance is estimated independently at each control point using anchor points p and safe outward directions v extracted from surrounding obstacles.
  • Topological alternatives are generated by reversing v to vnew := −v and selecting an opposite-side anchor pnew, yielding a different local minimum.
  • A colliding initial trajectory is paired with a searched bypass path, producing {p, v} constraints that guide optimization toward a safe trajectory.

B. Implicit Topological Trajectory Generation

The proposed implicit topological method addresses distinct local minima in 3-D trajectory optimization by constructing alternative distance fields from reversed obstacle directions. It avoids explicit path search while producing alternative trajectory constraints.

  • UVD classifies two trajectories as equivalent when corresponding points are connected by collision-free line segments.
  • Unlike conventional topological planners, the method inverts v to vnew := −v and searches for an opposite-side anchor pnew on the obstacle surface.
  • The new {pnew, vnew} pair creates a different local minimum without adopting an explicit path-search stage.

IV. DRONE SWARM NAVIGATION

The swarm navigation formulation defines each agent’s free state-space region while accounting for other agents and adds a soft collision-avoidance penalty to the trajectory objective. Trajectories remain compatible with the planner’s parameterization and timing framework.

  • Agent k’s free region excludes the states occupied by other agents, and valid trajectories must remain within that region throughout their domains.
  • Swarm collision avoidance is formulated as a soft-barrier penalty Jw,k added to each agent’s optimization objective.
  • The formulation evaluates agent positions over global trajectory start and end times, with pairwise distance penalties applied when distances become negative.
  • The clearance parameter C is user-defined, while E transforms Euclidean distance into ellipsoidal distance with a shorter z-axis to reduce downwash risk.
  • The collision-avoidance penalty can use any trajectory parameterization mapping decision variables to trajectory points; this paper uses a uniform B-spline.

B. Localization Drift Compensation

The system compensates localization drift by detecting an observed agent within an empirically sized depth-image trust region and comparing it with the predicted position. The resulting correction is designed to remain lightweight while tolerating imperfect observations.

  • Trust-region construction: The trust region is a sphere centered at the current evaluated position, with radius R representing an empirical upper bound on typical drift.Its projection into the depth image defines the region searched for the agent observation.
  • Trust-region construction: The exact projected region is an elliptical conic section, so the method uses an approximate axis-aligned ellipse to reduce computation.The approximation is acceptable because the trust region is empirical rather than precisely defined.
  • Agent observation: Projected depth points inside the approximate region are collected into a cluster, whose first raw moment provides the observed agent position.The cluster is formed by projecting candidate depth points into the world frame and retaining points within the spherical region.
  • Localization drift estimation: Drift compensation compares an agent’s predicted position from the received trajectory with its observed position in the depth image.The comparison is performed within a trust region around the evaluated current position.
  • Detection robustness: Detection robustness is improved with criteria including pixel count, the cluster’s second central moment, and deviation from previous measurements.Stricter criteria increase false negatives, but the authors state this is harmless because localization drift changes slowly.

C. Agent Removal from Depth Images

The system removes detected moving agents from depth and grayscale images so they do not corrupt static obstacle mapping or interfere with visual-inertial odometry.

  • Depth-image masking: Detected agents are masked and removed from depth images before map building to prevent moving objects from being recorded as static obstacles.The paper characterizes treating moving agents as map obstacles as unnecessary and potentially harmful.
  • Depth-image masking: The same mask is applied to grayscale images when moving objects cover most of the view and interfere with VIO.This extends agent removal beyond depth-based map fusion to visual-inertial localization inputs.

V. SYSTEM ARCHITECTURE

The system architecture combines a single-agent onboard planner with multi-agent communication for decentralized swarm navigation. It includes topological planning, trajectory sharing, and mechanisms that limit computation as the swarm grows.

  • System overview: The architecture contains a detailed single-agent system and a multi-agent communication system.The architecture is depicted in Fig. 8.
  • Single-agent system: Each agent builds on EGO-Planner with modules for VIO-drift compensation and removal of witnessed agents from images.Planning activates when newly discovered obstacles collide with the current trajectory or when the trajectory nears its endpoint.
  • Communication system: A broadcast network shares trajectories, while a chain network synchronizes timestamps and manages sequential startup.These two networks provide separate communication functions within the decentralized architecture.
  • Scalability: Before planning, agents ignore received trajectories outside the planning range to control computational complexity as the number of agents increases.The position of each agent is compared with surrounding agents’ received trajectories before planning begins.

2) Chain Network:

The chain network synchronizes startup and timestamps, while trajectory broadcasting and immediate collision checks support decentralized operation despite communication imperfections. Experiments compare the planner’s front-end efficiency with Fast-Planner.

  • Chain Network: Agents start in a predefined order and generate initial trajectories only after receiving higher-priority agents’ trajectories through the chain network.This avoids simultaneous trajectory generation when agents initially lack information about one another.
  • Evaluation setting: Benchmark experiments use a 7.5m planning horizon, 0.1m map resolution, and replanning every second or when a collision is predicted.The same parameter setting is used in simulation and real-world experiments on an i7-9700KF CPU.
  • Topological-planning comparison: EGO-Swarm finds fewer candidate trajectories than Fast-Planner but performs front-end topological path search two orders of magnitude faster.The comparison concerns candidate trajectory count and computation time for front-end local-minima discovery.
  • Trajectory sharing: New collision-free trajectories are broadcast immediately and stored by other agents for generating safe trajectories when necessary.The closed-loop strategy works ideally with stable, low-latency communication, which is not guaranteed in practice.
  • Communication robustness: Each agent broadcasts one trajectory at a capacity-limited frequency and checks for collisions immediately after receiving another agent’s trajectory.If a potential collision is detected, the agent generates a new collision-free trajectory; typical trajectories are under 0.5KB.

1) In Empty Space:

In empty-space benchmarks, EGO-Swarm is compared with DMPC, ORCA, and RBP on trajectory quality, safety, collisions, and computation. The reported comparisons characterize EGO-Swarm as fast and nonconservative while maintaining collision-free trajectories and scalable computation.

  • Planner comparison: The benchmark compares DMPC, ORCA, RBP, and EGO-Swarm using flight distance, flight time, collision times per agent, and computation time.Eight agents perform swap transitions on a circle, and results are averaged across agents.
  • Planner comparison: In obstacle-free scenarios, eight agents perform circle-swap transitions for comparison across swarm planners.The evaluated planners are DMPC, ORCA, RBP, and EGO-Swarm.
  • Planner comparison: EGO-Swarm generates the shortest collision-free, nonconservative trajectories with fast computation, supporting real-time quadrotor applications.RBP is described as safe but conservative, while DMPC depends on accurate high-frequency pose communication and ORCA is incompatible with third-order quadrotor systems.
  • Obstacle-rich comparison: Ten drones in a 0.42 obstacles/m2 simulation plan smooth and safe trajectories while flying between opposite sides of the map.The speed limit is 2m/s and the quadrotor radius is 0.2 meters.
  • Scalability analysis: Computation time gradually flattens as the number of agents increases in a 50-meter random-target scenario.The reported behavior is attributed to on-demand collision checking.

VII. REAL-WORLD EXPERIMENTS

Real-world experiments evaluate autonomous quadrotor navigation in indoor clutter and a forest. The experiments report reciprocal collision avoidance, narrow-door passage, and successful traversal of cluttered environments by three quadrotors.

  • Indoor: Three quadrotors perform a circle swap with reciprocal collision avoidance at a 1.5m/s speed limit.This is the top indoor experiment shown in Fig.12.
  • Indoor: Quadrotors pass through a narrow door one after another in the indoor experiments.The experiment is presented as the middle scenario in Fig.12.
  • Indoor: Three quadrotors navigate across a more cluttered indoor environment.This is the bottom scenario in Fig.12.
  • Outdoor: Three quadrotors start together in a forest with trees spaced about 2 meters apart and reach a target outside the forest.The velocity limit is 1.5m/s, and the goal ordering makes reciprocal avoidance unavoidable.
  • Conclusion: Benchmark comparisons and real-world experiments validate EGO-Swarm's reported computation efficiency and robustness.The conclusion describes the system as using only onboard resources for multi-robot navigation in unknown cluttered environments.
Loading 2011.04183v3…