PaperlayerView exact revision on arXiv

Source-linked AI summary

Search and Rescue under the Forest Canopy using Multiple UAVs

Yulun Tian, Katherine Liu, Kyel Ok, Loc Tran, Danette Allen, Nicholas Roy, Jonathan P. How

arXiv:1908.10541v2cs.RO

TL;DR

Forest search and rescue requires collaborative mapping and exploration beneath a GPS-denied canopy despite perceptual aliasing and unreliable communication. The paper equips multiple UAVs with onboard autonomy, compressed tree-based communication, and centralized CSLAM using tree configurations and cycle-consistent matching. The resulting system improves data-association precision and recall over pairwise inputs and is validated in simulation and real forest flights.

  • Problem

    Forest canopy environments combine GPS denial, severe perceptual aliasing, noisy measurements, and unreliable communication, hindering collaborative exploration and map fusion.

  • Method

    Multiple UAVs perform onboard sensing, estimation, mapping, and planning while transmitting compressed tree-based submaps to a central ground station for CSLAM.

  • Results

    The system was validated through extensive experiments, including a real-world NASA LaRC flight demonstration, while cycle-consistent matching improved precision and recall over pairwise associations.

  • Takeaways & Limitations

    Tree-based representations and cycle-consistent multiway matching support collaborative multi-UAV exploration and mapping beneath the forest canopy.

  • Takeaways & Limitations

    The system does not explicitly address outliers in data association and loop closure, which become more likely under higher-noise conditions such as denser forests.

Abstract

from arXiv · show

We present a multi-robot system for GPS-denied search and rescue under the forest canopy. Forests are particularly challenging environments for collaborative exploration and mapping, in large part due to the existence of severe perceptual aliasing which hinders reliable loop closure detection for mutual localization and map fusion. Our proposed system features unmanned aerial vehicles (UAVs) that perform onboard sensing, estimation, and planning. When communication is available, each UAV transmits compressed tree-based submaps to a central ground station for collaborative simultaneous localization and mapping (CSLAM). To overcome high measurement noise and perceptual aliasing, we use the local configuration of a group of trees as a distinctive feature for robust loop closure detection. Furthermore, we propose a novel procedure based on cycle consistent multiway matching to recover from incorrect pairwise data associations. The returned global data association is guaranteed to be cycle consistent, and is shown to improve both precision and recall compared to the input pairwise associations. The proposed multi-UAV system is validated both in simulation and during real-world collaborative exploration missions at NASA Langley Research Center.

1. Introduction

The paper presents a multi-UAV system for GPS-denied forest search and rescue, addressing canopy-impaired visibility, perceptual aliasing, communication limits, and exploration efficiency.

  • Motivation: Forest canopy can hide lost hikers from manned aircraft, motivating rapidly deployable UAV teams for visibility and collaborative terrain exploration.The proposed vehicles are intended to operate beneath reasonably thick forest canopies.
  • Challenges: GPS denial, perceptual aliasing, and intermittent communication make independent flight, map fusion, and collaborative exploration technically challenging.Tree similarity complicates overlap detection, while attenuation and limited range constrain communication.
  • System: The system combines onboard autonomy with central-station CSLAM and uses dense occupancy grids alongside compact tree-based maps to manage planning and communication bandwidth.Onboard grids support trajectory planning, while compressed tree maps are transmitted when communication is available.
  • Contributions: Tree-group configurations support robust loop closure, while cycle-consistent multiway matching improves landmark-association reliability in forest environments.The method addresses noisy and visually ambiguous tree observations during collaborative mapping.
  • Contributions: A dynamics-aware frontier heuristic improves simulated exploration speed and time efficiency over standard frontier-based exploration.The comparison is reported in a high-fidelity simulation environment.
  • Evaluation: The system was evaluated through simulation and collaborative real-world exploration by two UAVs at NASA Langley Research Center.The real experiment assigned each UAV a search region for complete exploration.

2. Related Work

Prior work spans centralized and distributed multi-robot SLAM, lightweight object representations, forest-specific tree features, and pairwise or multiway association; this paper combines these directions for forest mapping.

  • Multi-robot SLAM: Existing multi-robot systems use centralized, distributed, or fully onboard SLAM architectures with different computation, scalability, and communication trade-offs.The surveyed systems transmit keyframes, relative poses, compressed maps, or boundary poses depending on architecture.
  • Multi-robot architectures: The paper adopts a centralized architecture because the ground station can handle computation and must provide the fused map to search-and-rescue responders.Distributed systems offer scalability, but centralized processing leverages ground-station resources.
  • Forest mapping: Forest mapping is difficult because moving vegetation adds noise and similar tree patterns create perceptual aliasing that disrupts standard scan matching.The paper therefore leverages prior environmental structure for loop closure and map fusion.
  • Representations: Object-level and semantic representations reduce the burden of feature-heavy tracking and loop-closure computation, though communication and real-time constraints remain relevant.The related work includes object detections, 3D point-cloud segments, and compact representations.
  • Novelty: The proposed work extends prior tree-feature approaches with a complete association procedure combining pairwise and cycle-consistent multiway matching.The system is demonstrated in a real-world multi-robot exploration task beneath the forest canopy.
  • Data association: Multiway association methods use multiple noisy pairwise matches to resolve inconsistencies, including spurious chains that conflict with same-robot landmark observations.Cycle consistency is also used in computer vision through spectral, semidefinite, consensus, and clustering approaches.

3. Overview

Each UAV independently senses, estimates state, maps, and plans in GPS-denied forests, while a ground station fuses compressed tree-based observations into a global map when communication is available.

  • Onboard autonomy: Onboard autonomy performs sensing, vehicle-state estimation, local mapping, and exploration planning for independent GPS-denied operation.The vehicles use filtering-based state estimation and occupancy grids for real-time obstacle avoidance and planning.
  • Map communication: Local observations are compressed into lightweight tree-object submaps before transmission to reduce communication bandwidth.The transmitted representation retains detected tree objects rather than full dense local maps.
  • Centralized CSLAM: The ground station performs CSLAM by recovering cross-submap tree correspondences and jointly optimizing submap origins and global landmark positions.Global data association precedes landmark SLAM in the two-stage fusion process.

4. Onboard Autonomy

Each UAV performs autonomous sensing, state estimation, local mapping, and frontier-based exploration without GPS. Submap-based mapping and dynamics-aware frontier costs address onboard estimation drift and inefficient heading changes.

  • 4.1. State Estimation and Local Mapping: Submap-based occupancy grids let CSLAM optimize relative submap transformations, correcting accumulated onboard estimation errors while retaining explored-area information.Each submap remains locally rigid, while the union supports onboard motion and exploration planning.
  • 4.2. Frontier-based Planning: Frontier selection avoids the closest-frontier failure mode in which a target behind the vehicle falls within the LIDAR blindspot and causes poor progress.The planner uses A* search on a projected 2D occupancy map after selecting a frontier.
  • 4.2. Frontier-based Planning: Frontier planning combines Euclidean distance with required heading change, discouraging excessive turns and enabling continuous replacement of the selected frontier.The cost is J(a) = Jθ(a) + λJt(a), with λ = 0.5 observed at 2.0 m/sec in outdoor experiments.
  • 4.3. Tree-based Map Compression: Tree compression approximates trunks as cylinders in 3D or circles in 2D, but performance degrades in denser forests with branches and leaves.The method works well when most trunks are clearly visible at the vehicle’s flight altitude.

5. Offboard Collaborative SLAM

The ground station performs collaborative SLAM by detecting candidate submap overlaps, verifying tree correspondences, enforcing cycle consistency, and optimizing the fused map. This pipeline addresses noisy associations and perceptual aliasing in forest environments.

  • 5. Offboard Collaborative SLAM: The CSLAM pipeline detects loop closures, verifies pairwise tree correspondences, enforces global cycle consistency, and then performs landmark SLAM.Landmark SLAM jointly optimizes submap origins and tree positions in the global map.
  • 5.1. Fast Loop Closure Candidate Detection: GLARE encodes relative tree distances and orientations into a 2D histogram, while GLAROT compares descriptors using a rotation-invariant shifted L1 distance.A distance below threshold ϵGLAROT filters submap pairs into loop-closure candidates for further verification.
  • 5.2. Loop Closure Verification: Correspondence graph matching finds a maximum clique of geometrically compatible tree matches, producing a partial permutation for two submaps without requiring a shared reference frame.Relative landmark distances must be preserved within tolerance ϵCG.
  • 5.3. Globally Consistent Loop Closures: Cycle consistency requires compositions around every submap cycle to equal the identity and prevents transitive associations from merging distinct trees within one submap.Violating associations can create same-submap conflicts through chains of spurious matches.
  • 5.3. Globally Consistent Loop Closures: CLEAR recovers global tree associations by assigning data-association-graph cliques to unique objects in the universe, yielding cycle-consistent pairwise matches.The graph representation makes globally consistent association recovery explicit through disjoint cliques.

6. Simulation Experiments

Simulation experiments evaluated tree detection, loop-closure candidate detection, frontier-based exploration, and submap-based SLAM under varying forest conditions. The proposed methods improved exploration efficiency and corrected accumulated localization drift, while tree-detection precision degraded in denser forests.

  • Simulation Setup: The experiments used random-forest and Unity-based simulations with parameters largely matched to the real-world missions, while adjusting some settings for effects such as wind.The tree-detection simulator modeled noisy 2D laser measurements, whereas the high-fidelity environment simulated vehicle dynamics, IMU readings, and laser scans.
  • Tree Detection Results in Simulation: Tree-detection precision decreased as forest density increased, with dense-forest failures often caused by clustering points from nearby trees into one tree.Precision was evaluated over 500 random simulations for each noise and density level.
  • Loop Closure Candidates Detection Results in Simulation: GLAROT distances were consistently lower for overlapping scan pairs than for nonoverlapping pairs, with a larger separation in sparser forests.The study averaged results over 100 random simulations; densities above 0.6/m2 were omitted because the margin stayed relatively constant.
  • Exploration Results in Simulation: The proposed planner outperformed the baseline in all three simulated search areas, completing exploration faster while maintaining higher flight speed.Table 1 reports average completion time and flight speed across repeated trials in three areas.
  • SLAM Results in Simulation: SLAM bounded absolute trajectory error below 0.03 m, whereas EKF drift eventually exceeded 0.25 m.Optimizing submap origins produced a trajectory that mostly matched ground truth.

7. Flight Experiments

Real-flight experiments evaluated two-UAV coverage, CSLAM map fusion, runtime, communication, and data association, while simulation assessed planning and estimation. The system supported real-time operation and produced consistent fused maps, but duplicate landmarks and evaluation limitations remained.

  • Simulation Results: At t = 250 sec, the proposed planner nearly completed simulation, whereas the baseline had only partially explored its assigned search area.The proposed trajectory was also smoother and more time-efficient than the baseline trajectory.
  • Real-time Planning and CSLAM Results: Vehicle 1 completed exploration in 122 seconds at 2.66 m/sec, and vehicle 2 in 135 seconds at 2.65 m/sec during outdoor tests.The reported average speeds exceeded the 2.0 m/sec maximum because of measurement noise.
  • Real-time Planning and CSLAM Results: The first inter-trajectory loop closure occurred at t = 45 sec, after which newly received submaps were consistently fused into the global map.At t = 30 sec, the trajectories were arbitrarily aligned because no inter-trajectory loop closure had yet been detected.
  • Real-time Planning and CSLAM Results: The fused global map was geometrically consistent but contained duplicate trees because conservative association thresholds favored precision over recall.Missing associations did not prevent correct loop-closure transformations when enough correct landmark matches remained.
  • Real-time Planning and CSLAM Results: GLAROT and iSAM ran efficiently in real time, while CG matching took at most 0.015 sec per outdoor submap match and CLEAR exceeded 0.5 sec as submaps increased.Object-level representations and aggressive culling reduced CG matching inputs, which typically contained fewer than 30 tree landmarks.
  • Real-time Planning and CSLAM Results: At most 8kB with 48 submaps, the tree-based representation kept communication payloads minimal for low-bandwidth, real-time CSLAM.Payload growth was not exactly linear because submaps contained different numbers of trees; protocol overhead was excluded.
  • Data Association Results: The reported estimation evaluation was limited by accumulated EKF drift and should be replaced by more accurate or uncertainty-aware metrics in future work.Suggested alternatives include GPS-based information and Mahalanobis-distance metrics.
  • Data Association Results: CLEAR improved precision and recall over initial pairwise associations by rejecting false matches and suggesting correct ones, while guaranteeing cycle consistency.The evaluation compared tree landmarks with stabilized FLIRT features and found tree detection superior in the forest data.

8. Conclusions and Future Work

The system combines onboard UAV autonomy, compressed tree-based maps, and CSLAM with tree-group loop closures and cycle-consistent multiway matching for forest search and rescue. Future work targets outlier rejection, higher-level exploration coordination, and extending the predominantly 2D system to denser 3D environments.

  • Conclusions: The system compresses dense onboard occupancy grids into sparse tree-based maps before transmission to support CSLAM under limited communication bandwidth.This compression scheme enables lightweight communication with the central ground station.
  • Conclusions: The system validated collaborative multi-UAV exploration and mapping for forest search and rescue, including a real-world flight demonstration at NASA LaRC.Experiments covered the proposed system and included a forest deployment at NASA Langley Research Center.
  • Conclusions: Cycle-consistent multiway matching improved data-association precision and recall, while tree-group signatures supported loop-closure detection under perceptual aliasing.The method uses relative positions and orientations among multiple trees as a distinctive signature during CSLAM.
  • Future Work: Outlier rejection remains unaddressed, and higher noise in denser forests may increase data-association and loop-closure errors.The authors suggest adding outlier-rejection schemes for both inner-trajectory and inter-trajectory loop closures.
  • Future Work: Independent frontier-based exploration can miss small unobserved patches, motivating higher-level coordination for flexible reassignment of vehicles across search areas.The current system assigns vehicles to non-overlapping regions with limited interaction outside collaborative SLAM.
  • Future Work: The predominantly 2D mapping and planning assumption is generally sufficient for sparse forests but may become restrictive in denser environments where feasible 2D paths disappear.Extending modules to 3D is possible but increases computational costs.
Loading 1908.10541v2…