PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Latency Mapless ESDF Queries for MAV Reactive Collision Avoidance

Leonard Freißmuth, Cedric Le Gentil, Helen Oleynikova, Stefan Leutenegger

arXiv:2610.13158v1cs.RO

TL;DR

Reactive collision avoidance needs obstacle perception and motion correction within milliseconds, while map preprocessing can outweigh its query savings at the low query counts of short-horizon planning. The paper queries posed depth images directly on a GPU; in forest simulations its MPC runs had a 0.4% branch-collision rate, and the system flew at two forest sites.

  • Problem

    Reactive avoidance needs collision answers within milliseconds, but map preprocessing may not pay off when short-horizon planners make only hundreds of queries per measurement.

    Source: §I · p. 1

  • Method

    A GPU-accelerated mapless ESDF query evaluates posed depth images directly, with pooling-controlled resolution and a covariance-based pose-uncertainty margin.

    Source: §I · pp. 1–2, B. Representation · p. 3

  • Results

    In forest simulations, branch collisions were 0.4% with the method versus 5.9% with FIESTA; at full resolution it was more accurate and faster in total latency than every measured voxel grid.

    Source: B. Accuracy, Total Latency, and Memory · p. 5, §V · p. 7

  • Takeaways & Limitations

    At two forest sites, all ten flights at commanded speeds up to 4 m/s were collision-free.

    Source: §V · p. 8

Abstract

from arXiv · show

Reactive collision avoidance in unknown, cluttered environments must perceive obstacles and correct motion within milliseconds. Existing methods rely on maps for high-rate collision queries, but their acceleration structures require pre- processing. That cost is amortized in long-horizon planning, where a map serves millions of queries; reactive planning, however, is a near-field, short-horizon problem with potentially only hundreds of queries per measurement, where building a map may not pay off. We propose a mapless, Graphics Processing Unit (GPU)-accelerated Euclidean Signed Distance Field (ESDF) query with negligible pre-processing that operates directly on posed depth images, with resolution set by pooling the image rather than by a voxel size. On an embedded GPU it is simultaneously more accurate and lower in total latency than every voxel-grid configuration we measured between 2 cm and 20 cm, at one to two orders of magnitude less memory at matched resolution. With our query integrated into a Model Predictive Controller (MPC), simulated runs in laser-scanned forests at up to 9 m/s collide in 0.4 % through dense branches, against 5.9 % with the best voxel grid and 5.5 % with the best mapless baseline at our resolution, whose failures we attribute to voxel resolution and total latency respectively. We deploy the system onboard at two forest sites and fly at commanded speeds of up to 4 m/s.

I. INTRODUCTION

Reactive collision avoidance has little time and relatively few queries per sensor update to amortize map-building costs. The paper presents a mapless GPU query on posed depth images and evaluates its accuracy, latency, memory use, and flight performance.

I. INTRODUCTION

  • Reactive planning makes about 10^2 queries per sensor update, so map preprocessing can dominate total latency despite a map’s lower per-query cost.A map’s preprocessing cost can pay off in long-horizon planning, where measurements may be reused for millions of queries.Source: §I · p. 1
  • At full resolution, the query is more accurate and faster in total latency than every measured voxel-grid configuration, while using the least memory at matched resolution.It answers 400 planner queries in 6.2 ms on a Jetson Orin NX; ten forest flights were conducted at commanded speeds up to 4 m/s.Source: §I · p. 1
  • The proposed GPU query fuses posed depth views with pooling-controlled resolution, supports optimistic or conservative unknown-space handling, and adds a covariance-based pose-uncertainty margin.The evaluation compares voxel grids, KD-trees, meshes, and the proposed representation in a forest MPC simulation, and includes ten real-world forest flights.Source: §I · p. 2

A. Reactive Collision Avoidance

The paper frames its query as a reactive layer for planners and assumes static geometry over the buffered horizon. It contrasts this role with corridor-based, predictive, and learned approaches.

A. Reactive Collision Avoidance

1) Corridor-Based Methods:

  • Corridor-based planners optimize trajectories within overlapping convex free-space regions, but without a prior map they can be trapped in local minima.The query targets the reactive layer beneath a global planner and can also serve optimizers that query the neighborhood sparingly.Source: 1) Corridor-Based Methods · p. 2

2) Predictive Methods:

  • Predictive methods use collision constraints from maps, learned representations, or control barrier functions; map updates can bound their total latency.The paper adopts an MPC to demonstrate the query, which could also be consumed by the other described methods.Source: 2) Predictive Methods · p. 2

3) Learning-Based Methods:

  • Learned policies avoid maps at fixed inference latency but require training data and sim-to-real transfer, and are tied to their domain and vehicle.The query is training-free and returns distances and gradients usable as hard constraints, a safety filter, or supervision.Source: 3) Learning-Based Methods · p. 2

1) Point Cloud Integrations:

The related work contrasts map-based acceleration structures with direct sensor-space queries. The formulation seeks signed distance to the free-space boundary while minimizing preprocessing and pruning the search.

1) Point Cloud Integrations:

  • Point-cloud methods query KD-trees or continuous fields, but maintaining their structures can dominate total latency at low query counts, and unknown space must be recovered separately.Source: 1) Point Cloud Integrations · p. 2

2) Voxel Grids:

  • Voxel grids model occlusion and can use octrees, hashing, or incremental ESDF updates, but fixed cell sizes consume memory at high resolution and integration can dominate latency.Source: 2) Voxel Grids · p. 2

3) Mapless Methods:

  • Prior mapless methods use an occlusion-aware pyramid for binary collision tests or per-frame KD-trees; the proposed direct pixel query returns signed distances and gradients with either unknown-space policy.Source: 3) Mapless Methods · p. 2

A. Problem Formulation

  • The ESDF’s magnitude is distance to the free-space boundary, while its sign distinguishes free from unknown space; low latency calls for minimal preprocessing and truncation-based pruning.Source: A. Problem Formulation · p. 2

B. Representation

The representation buffers posed depth images and queries them individually before merging results and accounting for pose uncertainty. Its spatial resolution follows the depth image and can be coarsened by min-pooling.

B. Representation

  • The representation buffers a latest frame and keyframes, treating the slots identically for querying, merging per-frame distances, and accounting for pose uncertainty.Images are divided into 32×16-pixel blocks; new keyframes replace the oldest when pose or time differs sufficiently.Source: B. Representation · pp. 2–3
  • Min-pooling with a p×p kernel coarsens the depth image while retaining the nearest depth, conservatively trading accuracy for latency.Source: B. Representation · p. 3

C. Single-Frame Query

  • A query treats unknown space as occupied and seeks the largest sphere around q containing neither observed surfaces nor occlusion boundaries, searching active blocks and pixels in parallel.The search is clipped at a truncation radius; active blocks are restricted to those that may contain a candidate point.Source: C. Single-Frame Query · p. 3

1) Truncation Mechanism:

The query prunes depth-image pixels using per-block depth ranges, then finds the nearest observed surface and optionally accounts for occlusion boundaries. It can return either an optimistic distance that treats unknown space as free or a conservative one that treats it as occupied.

1) Truncation Mechanism:

  • A block is active only when its projected footprint intersects the query sphere and its depth range intersects [q_z − rmax, q_z + rmax].Per-block minimum and maximum depths are recorded on image arrival; this is the only source of preprocessing latency besides memory management.Source: 1) Truncation Mechanism · p. 3

2) Nearest Observed Surface:

  • Within active blocks, atomicMin over 64-bit distance-and-pixel keys selects the nearest back-projected surface point, whose distance is clipped at rmax.The key stores squared distance in its upper 32 bits and pixel coordinates in its lower bits.Source: 2) Nearest Observed Surface · p. 3

3) Occlusion Boundaries:

  • Occlusion segments yield a conservative distance, while reporting the surface distance alone treats unknown space as free and saves nearly half the query time.The signed distance is positive in free space F and negative in unknown space U.Source: 3) Occlusion Boundaries · p. 3

D. Merging Multiple Views

The method merges signed distances across buffered views by selecting the maximum, so a free-space observation in any frame can override an occluded one. It accounts for relative pose uncertainty by reducing distances from older frames before merging.

D. Merging Multiple Views

  • Fig. 4b reports that every pooling level has lower total latency than the fastest grid for 400 queries.The figure measures from the start of the last integration to the last query answer.Source: Figure 4 · p. 4
  • Max-pooling signed distances selects the winning frame and its closest point, leaving q free if any frame observes it as free.The maximum also selects the larger clearance when both frames report positive distances.Source: D. Merging Multiple Views · pp. 3–4

E. Handling Pose Uncertainty

  • Pose uncertainty can make reported distances exceed the true distance and erode obstacles, so the method grows each frame’s truncation radius and subtracts its uncertainty margin before max-pooling.Because uncertainty is relative to the latest pose, the margin grows with frame age and reduces the contribution of older observations.Source: E. Handling Pose Uncertainty · p. 4

F. Example Application: Reactive MPC

The paper integrates its distance query into a flatness-based path-tracking and collision-avoiding MPC. Each SQP iteration batches distance and gradient queries across the horizon and enforces a linearized robot-clearance constraint.

F. Example Application: Reactive MPC

  • The MPC uses a triple-integrator position model with jerk input, discretized at 0.1 s over a 2 s horizon, and a PD controller tracks its result.The cost includes velocity along the reference tangent and lateral deviation; yaw follows the direction of motion.Source: F. Example Application: Reactive MPC · p. 4
  • SQP runs up to 20 iterations per loop, with five HPIPM interior-point iterations per quadratic program.Each iteration queries distance and gradient at all 20 stages in one batch, for up to 400 queries per update.Source: F. Example Application: Reactive MPC · p. 4
  • At each prior iterate, the MPC enforces the linearized half-space constraint ϕ( q̄ ) + ∇ϕ( q̄ )⊤(q − q̄) ≥ r_robot.The paper notes that the same queries could also feed corridor-based planners.Source: F. Example Application: Reactive MPC · p. 4

IV. EXPERIMENTAL EVALUATION

On an embedded GPU, the proposed query is more accurate and lower-latency than the tested voxel grids, while using less memory at matched resolution. The evaluation benchmarks alternative representations and reports accuracy, total latency, and memory.

A. Setup and Baselines

  • The benchmark compares a per-frame FLANN KD-tree, CPU and GPU voxel ESDFs, and a back-projected-pixel mesh on an Orin NX with 16 GB shared memory.Depth sequences come from a RealSense D455 posed by OKVIS2-X; voxel sizes and pooling levels are matched approximately at 2.85 m.Source: A. Setup and Baselines · pp. 4–5

B. Accuracy, Total Latency, and Memory

  • At the finest setting, the proposed query is more accurate and faster than every tested voxel configuration; at coarser pooling, it matches the finest grids’ accuracy with lower latency.The comparison uses voxel sizes from 2 cm to 20 cm and image pooling levels matched approximately by pixel footprint.Source: B. Accuracy, Total Latency, and Memory · p. 5, A. Setup and Baselines · p. 5
  • The proposed query takes 3.3–6.2 ms for 400 queries, with median preprocessing of 0.26–0.37 ms per frame.NVBlox latency ranges from 199 ms at 2 cm to 11 ms at 20 cm; the mapless baselines are slower than the proposed query at every measured pooling level.Source: B. Accuracy, Total Latency, and Memory · p. 5
  • The five-frame buffer uses 5.9 MiB, compared with 66 MiB for NVBlox at 2 cm; at the 10 cm pairing, the memory gap is a factor of 44.FIESTA uses 1.4 GiB and its dense-volume allocation rules out 2 cm on the Orin NX in this experiment.Source: B. Accuracy, Total Latency, and Memory · p. 5

IV. EXPERIMENTAL EVALUATION

  • Fig. 5a plots collision rate against commanded speed and reports the proposed method at no more than 2%.The evaluation includes forest scenes with laser-scanned branches and trunks.Source: Figure 5 · p. 5

C. Closed-Loop Simulation in Laser-Scanned Forests

The laser-scanned-forest MPC evaluation compares representations under measured onboard costs, then separates geometry from latency. Our full-resolution query rarely collides through branches, while voxel grids and slower mapless baselines show different failure patterns.

C. Closed-Loop Simulation in Laser-Scanned Forests

  • The benchmark uses 50 laser-scanned trees per world, five speeds up to 9 m/s, and references that intersect geometry, making safe stops a valid outcome.Runs use 200 trials per configuration at each speed; twigs below 1 cm are removed.Source: C. Closed-Loop Simulation in… · p. 5

1) Representations in the Loop:

  • 0.4 % of branch runs with our query collide, versus 5.9 % with FIESTA and 44 % to 81 % with NVBlox under onboard costs.FIESTA reaches more goals because unobserved space is free and its map covers the whole scene; its collision rate is fifteen times ours.Source: Figure 6 · p. 6, 1) Representations in the Loop · p. 6
  • At 9 m/s in branches, collisions reach 11 % with the KD-tree and 19 % with the mesh, while ours stay at or below 2 % at every speed.The authors attribute the speed-related degradation of delayed plans to reduced reaction time.Source: 1) Representations in the Loop · p. 6
  • Without compute charged, KD-tree runs match ours at every pooling level and mesh runs match through p = 9, while voxel-grid collisions persist.The authors interpret the mapless gap under onboard costs as latency-related and the voxel-grid failures as resolution-related.Source: Figure 7 · p. 6, 1) Representations in the Loop · p. 6
  • In the delayed-query sweep, stops rise from 50 ms onward, isolating how added plan delay changes outcomes.The onboard model charges measured query and integration costs; the instant model charges neither.Source: C. Closed-Loop Simulation in… · p. 5, Figure 8 · p. 6

2) Separating the Effect of Resolution:

The experiments separate representation geometry from compute delay, then test the uncertainty margin under noisy poses. No-compute runs distinguish persistent voxel-grid collisions from latency effects, while the margin reduces branch collisions at higher odometry noise.

2) Separating the Effect of Resolution:

  • In the instant model, KD-tree runs match ours at every pooling level and mesh runs through p = 9, but voxel-grid collisions remain at 5–20 cm.At 2 cm, NVBlox integration cannot cover a frame, leaving an incomplete field; coarser pooling can turn goals into stops through inflated obstacles.Source: 2) Separating the Effect of Resolution · p. 6

3) Separating the Effect of Total Latency:

  • With compute removed, mapless baselines match our geometry while voxel-grid collisions persist; added delay explains much of the onboard loss for the mesh and less than half for the KD-tree.The delayed sweep reaches 7.2 % collisions at 300 ms, while runs at 100–200 ms retain about 70 % trunk goals with under 1 % collisions.Source: 3) Separating the Effect of Total… · pp. 6–7

D. Ablation of Uncertainty Handling

  • At k = 4, the uncertainty margin lowers branch collision rate from 38.2 % to 21.1 %, but collisions still rise with k because odometry also feeds the planner.In open trunks, the margin pays off only above k = 6; below k = 2, the margin vanishes with covariance and both settings are about equally safe.Source: D. Ablation of Uncertainty Handling · p. 7, Figure 9 · p. 7

E. Real-World Forest Flights

The system was flown at two forest sites, where all ten runs reached their goals without collision or operator intervention. The conclusion reports collision-free flights up to 4 m/s and identifies longer-range LiDAR queries as future work.

E. Real-World Forest Flights

  • All ten forest flights reached the goal without collision or operator intervention, at a median speed of 2.5 m/s.Five runs were flown at each of two sites, through bare trunks and through bushes and fine branches, at commanded speeds up to 4 m/s.Source: E. Real-World Forest Flights · p. 7, Figure 10 · p. 7
  • Onboard integration and planning took median times of 14.8 ms in trunks and 34.1 ms in branches, within the 66.7 ms camera period.The branch scenes required a median of 20 SQP linearizations versus 6 in trunks, while the query remained 53 and 55 µs per point, respectively.Source: E. Real-World Forest Flights · p. 7, Figure 11 · p. 7

V. Conclusion

  • All ten flights at commanded speeds up to 4 m/s were collision-free; extending the query to longer-range sensors such as LiDAR is future work.The proposed extension treats a LiDAR scan as a range image.Source: §V · pp. 7–8
Loading 2610.13158v1…