PaperlayerView exact revision on arXiv

Source-linked AI summary

RACER: Rapid Collaborative Exploration with a Decentralized Multi-UAV System

Boyu Zhou, Hao Xu, Shaojie Shen

arXiv:2209.08533v1cs.RO

TL;DR

Multi-UAV exploration has been less studied despite its potential for faster autonomous mapping. RACER uses decentralized hgrid coordination, CVRP workload and path optimization, and hierarchical trajectory planning; evaluations report efficient, scalable, communication-robust exploration and fully decentralized real-world operation.

  • Problem

    Most exploration research focuses on single UAVs, despite multi-UAV systems’ potential for faster exploration and greater fault tolerance.

  • Method

    RACER distributes online hgrid regions through pairwise asynchronous coordination, balances workloads with CVRP, and plans hierarchical safe trajectories independently on each UAV.

  • Results

    The approach achieves fully autonomous collaborative exploration in complex real-world environments, completing one experiment in 23 s with quadrotor movement distances of 13.4 m and 14.4 m.

  • Takeaways & Limitations

    RACER demonstrates decentralized multi-UAV exploration with high efficiency, scalability, and robustness to limited communication.

Abstract

from arXiv · show

Although the use of multiple Unmanned Aerial Vehicles (UAVs) has great potential for fast autonomous exploration, it has received far too little attention. In this paper, we present RACER, a RApid Collaborative ExploRation approach using a fleet of decentralized UAVs. To effectively dispatch the UAVs, a pairwise interaction based on an online hgrid space decomposition is used. It ensures that all UAVs simultaneously explore distinct regions, using only asynchronous and limited communication. Further, we optimize the coverage paths of unknown space and balance the workloads partitioned to each UAV with a Capacitated Vehicle Routing Problem(CVRP) formulation. Given the task allocation, each UAV constantly updates the coverage path and incrementally extracts crucial information to support the exploration planning. A hierarchical planner finds exploration paths, refines local viewpoints and generates minimum-time trajectories in sequence to explore the unknown space agilely and safely. The proposed approach is evaluated extensively, showing high exploration efficiency, scalability and robustness to limited communication. Furthermore, for the first time, we achieve fully decentralized collaborative exploration with multiple UAVs in real world. We will release our implementation as an open-source package.

I. INTRODUCTION

RACER addresses the limited attention to multi-UAV exploration with decentralized coordination, workload-aware coverage planning, and hierarchical safe trajectory generation. Simulations and real-world experiments report faster, scalable, communication-robust exploration and fully autonomous collaborative flight.

  • Multi-UAV exploration can complete missions faster and tolerate individual failures, but most prior work focuses on single-UAV systems.
  • Simulations and real-world experiments report faster exploration than centralized and decentralized baselines, consistent performance under restricted communication, and scalable computation.The system also integrates decentralized state estimation for fully autonomous exploration in complex real-world environments.
  • RACER coordinates decentralized UAVs by distributing online hgrid task units through pairwise interactions using asynchronous, restricted communication.The approach is designed to support simultaneous exploration of distinct regions without interference.
  • A CVRP formulation minimizes global coverage-path lengths while balancing workloads assigned to each quadrotor.
  • A hierarchical planner guides efficient and safe exploration, incorporating coverage paths and multi-robot collision avoidance.

B. Coordinating Multiple Robots

The paper situates multi-robot exploration between centralized allocation and decentralized alternatives, then presents hgrid-based pairwise coordination with workload-aware routing and independent local planning. Its system combines decentralized estimation, mapping, coordination, and safe trajectory generation for communication-limited exploration.

  • Coordination paradigms: Centralized coordination can fail when robots lose contact with a server, whereas decentralized agents can continue operating independently under communication loss.
  • Coordination paradigms: Existing decentralized methods may send multiple robots to the same place or require several communication rounds, limiting coordination effectiveness.
  • RACER coordination: RACER uses hgrid cells as disjoint elementary task units and improves pairwise allocation by minimizing exact traveling distance with request-response scheduling.The request-response scheme addresses inequitable interaction opportunities and conflicting interactions.
  • Exploration planning: Each quadrotor independently computes coverage paths, updates frontier information, and generates minimum-time trajectories while avoiding obstacles and other quadrotors.Periodic trajectory exchange and replanning maintain collision avoidance under communication latency or packet losses.

IV. HGRID-BASED PAIRWISE INTERACTION

RACER represents unexplored space with an online hierarchical grid and distributes its disjoint regions through pairwise interactions between nearby quadrotors. The grid is updated as maps are shared, refining partially unknown cells and removing fully covered cells.

  • Hgrid decomposition: Online hgrid decomposition represents the unknown space as disjoint task regions allocated among quadrotors.Hgrid cells span coarse-to-fine resolutions, with each cell subdividing into eight sub-cells in 3D.
  • Hgrid decomposition: Each quadrotor maintains the hgrid in a common world frame and records unknown-voxel counts and centroids for its cells.
  • Hgrid decomposition: The array-based hgrid provides O(1) cell retrieval and improved data locality compared with an equivalent geometric octree representation.
  • Online updates: Map updates recompute overlapping cells and subdivide them when partially unknown, while completely covered cells are removed from the active list.
  • Pairwise interaction: Pairwise interaction allocates hgrid cells between two quadrotors by minimizing the exact coverage-path length for their combined assignments.

4 UpdateCellInfo(sk)

RACER coordinates task allocation through asynchronous pairwise interactions among nearby quadrotors. Its CVRP formulation minimizes coverage-path length while balancing the unknown-space workload assigned to each vehicle.

  • Interaction protocol: A request-response scheme resolves uneven interaction timing and records recent successful interactions to distribute negotiation opportunities.
  • Interaction protocol: Only nearby quadrotors with communication participate in an interaction, while a short exclusion interval prevents simultaneous conflicting negotiations.
  • Interaction protocol: The pairwise method simplifies communication to two-quadrotor negotiations, improving resilience to unstable communication without necessarily reducing communication events.
  • Interaction protocol: Pairwise allocation can be suboptimal relative to centralized allocation, but one interaction round quickly reaches a promising assignment.
  • CVRP allocation: CVRP minimizes total coverage-path length and balances the unknown-space workload assigned to the interacting quadrotors.

2 Tn ←TimeNow()

The section introduces a function named RespondInteraction with inputs beginning T′ᵢ and T′.

  • RespondInteraction is presented as a function.
  • The visible function signature begins with T′ᵢ and T′ as inputs.
  • The passage identifies this material as implementation content.

24 UpdatePartitioning(T ′

RACER reduces open coverage-path allocation for two quadrotors to an Asymmetric VRP using a virtual depot and path-based connection costs. Capacity constraints further balance the unknown-space workloads assigned to the routes.

  • Asymmetric VRP: The Asymmetric VRP uses nodes for the virtual depot, both quadrotors, and the hgrid cells to produce two minimum-cost routes.
  • Workload balancing: Capacity constraints assign cell demands from unknown-voxel counts to make the two quadrotors’ workloads more equitable.
  • Cost matrix: Connection costs between hgrid cells are based on collision-free path lengths between their unknown-voxel centroids.
  • Cost matrix: Quadrotor-to-cell costs combine travel from the quadrotor position with a consistency term for the existing coverage path.
  • Cost matrix: The consistency term discourages frequent changes between comparable route patterns that could cause inconsistent movements and slow exploration.
  • Asymmetric VRP: A large negative virtual-depot cost connects the depot directly to both quadrotors, leaving the desired open coverage paths after depot edges are removed.

2) Capacity Constraints:

Capacity constraints convert workload allocation into a CVRP that balances unknown-space workloads across quadrotors. A sparse hgrid graph reduces path-search computation while preserving comparable CVRP solutions.

  • Capacity Constraints: CVRP capacity constraints use unknown-voxel counts to balance workloads assigned to quadrotors.Each vehicle’s capacity is restricted to a percentage of the total unknown voxels.
  • Capacity Constraints: The CVRP is solved with an extended Lin-Kernighan-Helsgaun solver using penalty functions for capacity constraints.Although the problem is NP-hard, the small problem scale often permits optimal solutions.
  • Sparse Graph for Path Searching: A sparse graph embedded in the hgrid supports global path searches between adjacent collision-free cells.Each hgrid cell has a graph node, and weighted edges connect adjacent cells when collision-free paths exist.
  • Sparse Graph for Path Searching: Approximated sparse-graph costs produce comparable CVRP solutions while substantially reducing computation time.For distant cells, the estimate combines the quadrotor-to-cell path with the sparse-graph path between cells.
  • Exploration Planning: The exploration planner extends prior hierarchical planning with coverage-path guidance and multi-robot collision avoidance.It incrementally extracts frontier information structures while adapting computation for shared regions and additional clusters.

5 Fnew ←DetectNewFrontierCluster(Bm)

The multi-UAV frontier-information update expands beyond each quadrotor’s locally updated map region to maintain frontier information across shared nearby regions. Coverage paths then reduce repeated visits by ordering exploration across different regions.

  • Frontier Information Structure: Shared regions tracked by AABBs are included in frontier updates to maintain a complete frontier list across nearby quadrotors.This multi-UAV adaptation incrementally updates shared regions rather than processing only each quadrotor’s locally changed map.
  • Coverage-Path Guidance: Global coverage paths guide quadrotors to visit different regions in a more sensible order and reduce repeated exploration of the same regions.The prior hierarchical planner did not account for global coverage routes.

1) CP-guided exploration path planning:

CP-guided planning uses CVRP-generated coverage paths to order frontier-cluster visits through subdivided unknown space. It then refines viewpoints and computes a path with fixed current-start and cell-end constraints.

  • CP-guided exploration path planning: The CVRP produces a coverage path through assigned hgrid cells, and the next NCP cells guide local frontier-cluster selection.The local path starts at the quadrotor’s current viewpoint, visits selected clusters, and ends at the next hgrid-cell centroid.
  • CP-guided exploration path planning: The local planning problem is formulated as a TSP variant with fixed start and end points.The fixed endpoints are the current quadrotor viewpoint and the subsequent hgrid-cell centroid.
  • CP-guided exploration path planning: A virtual depot and a large negative depot-edge cost transform the fixed-endpoint problem into a standard TSP.Removing the depot and its two connected edges yields the desired path.
  • CP-guided exploration path planning: The cost matrix combines cluster-to-cluster, current-viewpoint-to-cluster, and cluster-to-hgrid-cell connection costs.Cluster connection costs account for translational distance and yaw-angle change.
  • Local viewpoint refinement: Graph-based viewpoint refinement evaluates alternative viewpoints for each frontier cluster to improve the initial CP-guided path.The refinement graph includes the current viewpoint, cluster viewpoints, and the hgrid cell on the initial path.

3) Minimum-time B-spline Trajectory Generation:

RACER converts discrete exploration viewpoints into smooth, safe, dynamically feasible B-spline trajectories while accounting for obstacle and inter-quadrotor collisions. Decentralized trajectory sharing and immediate map-chunk exchange support replanning under multi-UAV operation.

  • Minimum-time B-spline Trajectory Generation: The trajectory generator produces continuous-time B-spline trajectories that are smooth, safe, and dynamically feasible.It extends prior trajectory generation to include collision avoidance among quadrotors.
  • Minimum-time B-spline Trajectory Generation: Each trajectory minimizes smoothness cost and total time subject to safety, dynamic-feasibility, and boundary-state constraints.The optimization uses control points and a knot span to define each uniform B-spline.
  • Collision Avoidance: The objective penalizes collisions with obstacles and other quadrotors alongside smoothness, duration, dynamics, and boundary-state terms.The inter-quadrotor term uses nearby quadrotor trajectories and enforces a minimum distance adjusted for downwash.
  • Decentralized Trajectory Generation: Trajectory generation is decentralized, runs at higher frequency than the prior method, and uses periodic trajectory broadcasts.Each quadrotor replans after obtaining a new exploration path and shares its latest trajectory over the broadcast network.
  • Mapping Support: The mapping framework builds an occupancy grid from depth measurements and supports probabilistic updates of occupied, free, and unknown space.An incremental ESDF is maintained to facilitate gradient-based trajectory planning.
  • Map Sharing: Newly observed voxels are grouped into chunks and immediately broadcast to nearby quadrotors using UDP.The exchange is intended to update map information promptly during exploration.

C. System Setup

The system combines onboard sensing and planning with hgrid-based coordination, CVRP task allocation, and coverage-path planning. Ablations show that subdivided regions, CVRP allocation, and global coverage paths improve exploration efficiency.

  • System implementation: All state estimation, mapping, planning, and control algorithms run onboard, with quadrotors exchanging information through a wireless ad hoc network.
  • Evaluation design: The evaluation uses ablations, coordination comparisons, team-size studies, and indoor and outdoor real-world experiments.
  • Coordination ablation: H+mTSP outperforms NoHgrid in both scenes because subdivided regions represent workloads and disjoint cells reduce interference.
  • Coordination ablation: CVRP-based partitioning further improves efficiency, while H+BFS is limited because it does not explicitly optimize coverage-path length.
  • Path-planning ablation: Global coverage paths produce a more sensible exploration pattern, significantly shorter exploration time, and shorter overall path length than NoCP.

B. Coordination of Multi-robot Exploration

RACER coordinates quadrotors by assigning distinct regions under limited communication and scales to larger teams. It improves exploration efficiency and maintains more consistent performance as communication range decreases.

  • Benchmark comparison: Under ideal communication, jointly allocating all targets performs better than assigning one target at a time, while mTSP is marginally more efficient than Pair.
  • Benchmark comparison: RACER significantly outperforms centralized and decentralized baselines in exploration time and total movement distance by dispatching quadrotors to distinct regions.
  • Communication robustness: As communication range decreases, all approaches take longer and travel farther, but RACER maintains more consistent performance across scenes.
  • Scalability: Exploration rate consistently improves with team size, while even large teams experience only minor interference.
  • Computation and communication: Partitioning and trajectory messages use less than 50 kB/s, while total bandwidth remains much lower than the wireless network’s > 3 MB/s capacity.

D. Study on Suboptimality

The study evaluates pairwise coordination’s suboptimality and demonstrates RACER in large-scale, indoor, and natural environments. Pairwise paths are only marginally longer than centralized VRP paths, while real-world tests achieve autonomous multi-quadrotor exploration.

  • Suboptimality study: Across 100 tests for each target-and-robot count, pairwise interaction produces paths only marginally longer than centralized VRP.
  • Large-scale exploration: The simulated large-scale test covers a 20 × 100 × 3 m3 scene with three quadrotors exploring for 153 seconds.
  • Real-world validation: Real-world experiments use no external localization or central flight-control server, with estimation, mapping, coordination, and planning performed onboard.
  • Indoor experiments: Two quadrotors completely explore a 10 × 6 × 2 m3 indoor scene in 23 s, traveling 13.4 m and 14.4 m.
  • Indoor experiments: Three quadrotors finish exploration of a 15 × 9 × 2 m3 indoor scene in 33 s, with path lengths of 22.3, 23.0 and 25.7 m.
  • Outdoor experiments: In a 15 × 12 × 2 m3 forest area, three quadrotors complete exploration in 33 s with path lengths of 33.3, 25.2 and 34.1 m.
  • Overall findings: The experiments demonstrate applicability under limited communication, restricted computation resources, and considerable perception noise.
Loading 2209.08533v1…