⚡ electrical engineering

From Distances to Trajectories: Real-Time Signed Distance Function Mapping and Distance-Accelerated Motion Planning for UAVs

This paper presents an integrated onboard system for UAVs that co-designs mapping and planning using a neural network-based Signed Distance Function (OREN) and a distance-accelerated search planner (Bubble $^\star$ ) to enable real-time, safe navigation in cluttered environments with significantly improved accuracy and speed compared to conventional methods.

Original authors: Jason Stanley (UC San Diego, La Jolla, USA), Zhirui Dai (UC San Diego, La Jolla, USA), Qihao Qian (UC San Diego, La Jolla, USA), Tzu-Chin Ho (UC San Diego, La Jolla, USA), Tianxing Fan (UC San Diego

Published 2026-07-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jason Stanley (UC San Diego, La Jolla, USA), Zhirui Dai (UC San Diego, La Jolla, USA), Qihao Qian (UC San Diego, La Jolla, USA), Tzu-Chin Ho (UC San Diego, La Jolla, USA), Tianxing Fan (UC San Diego, La Jolla, USA), Siddharth Saha (Shield AI, San Diego, USA), Christopher Barngrover (Shield AI, San Diego, USA), Ki Myung Brian Lee (UC San Diego, La Jolla, USA), Nikolay Atanasov (UC San Diego, La Jolla, USA)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to fly through a messy, cluttered room without crashing. To do this, the robot needs two superpowers. First, it needs mapping: the ability to look at the world and build a mental picture of where the walls, tables, and chairs are. Second, it needs planning: the ability to look at that picture and figure out a safe path to fly from point A to point B. For a long time, engineers treated these as two separate jobs. The robot would build a simple "yes/no" map (is this spot empty or full?) and then try to plan a path through it. But this is like trying to navigate a city using only a list of blocked streets, without knowing how wide the open roads are or how far you are from the next traffic light. It's slow, clumsy, and often leads to dead ends.

This paper tackles the problem of making drones smarter and faster at flying in unknown, messy places. The authors argue that instead of treating mapping and planning as separate steps, they should be best friends that share a single, super-detailed mental model called a Signed Distance Function (SDF). Think of an SDF not just as a map of where things are, but as a map that tells you exactly how far you are from the nearest wall at every single point in the air. If you are one meter away from a wall, the map says "1.0"; if you are touching it, it says "0"; if you are inside a wall, it says "-1". By using this rich, distance-filled map, the robot can make decisions much faster and safer than if it only knew "wall" or "no wall."

The researchers, a team from UC San Diego and Shield AI, developed a new system that combines a clever neural network with a search algorithm to make this happen in real-time. They call their mapping tool OREN (Octree Residual Network) and their planning tool Bubble⋆.

Here is how their system works, using a few playful analogies:

The Mapper: OREN (The Artist with a Sketchbook)
Imagine the drone is flying through a dark cave. It needs to draw the cave as it goes. Old methods tried to draw the cave using a giant grid of tiny boxes, filling them in one by one. This is slow and the drawing looks blocky. Other methods tried to use a super-smart AI artist to draw the whole cave perfectly, but that artist was too slow and needed too much memory to run on a small drone.

OREN is like a hybrid artist. It starts with a quick, rough sketch of the cave using a "skeleton" of boxes (an octree) to get the big picture right. Then, it uses a neural network (a type of AI) to add the fine details, like the texture of the rock or the curve of a stalactite, on top of that sketch. This allows the drone to build a smooth, accurate, and continuous map of the distance to every wall, even while flying fast and using very little computer power. In their tests, this method improved the accuracy of the distance map by 22% compared to older techniques.

The Planner: Bubble⋆ (The Inflating Balloon)
Once the drone has this detailed map, it needs to find a path. Traditional planners, like the famous A⋆ algorithm, work like a mouse in a maze. They check one tiny square at a time: "Can I move left? No. Can I move right? Yes." They have to check thousands of these tiny squares to find a way through, which takes a long time.

Bubble⋆ is different. Instead of checking tiny squares, it uses the distance information from the map to blow up giant, invisible bubbles of safety. If the drone is standing in a wide-open hallway, the bubble grows huge, covering the whole hallway. If it's in a narrow corridor, the bubble stays small. The planner then jumps from the center of one giant bubble to the next, skipping over all the empty space in between. It's like skipping stones across a pond instead of walking step-by-step along the shore.

Because the bubbles are guaranteed to be free of obstacles (thanks to the accurate map), the planner doesn't need to check for collisions inside them. This makes the planning process incredibly fast. In the paper's experiments, while older methods took up to 10 seconds to find a path through a cluttered environment, Bubble⋆ found a path spanning about 90 meters in just 1 to 3 seconds.

The Real-World Test
The team didn't just run these ideas on a computer; they put them on a real drone equipped with a Jetson Orin NX computer (a powerful but small chip). They flew the drone through unseen indoor environments, building the map and planning the path entirely on the drone itself, in real-time. The drone successfully navigated complex loops and tight spaces, maintaining a safe distance from obstacles.

The results show that by combining a smart, distance-aware map (OREN) with a planner that uses that distance to "inflate" safe zones (Bubble⋆), drones can fly faster and safer than ever before. The system reduced the number of collision checks needed by 91–99% compared to standard grid-based planners. This proves that with the right tools, even small, resource-limited robots can handle the complex task of autonomous flight in the real world.

Technical Summary: From Distances to Trajectories

Problem Statement
Autonomous flight in unknown, cluttered environments requires Unmanned Aerial Vehicles (UAVs) to simultaneously build a geometric map of their surroundings and plan safe, dynamically feasible trajectories. These operations must occur onboard and in real-time from streaming sensor data. Conventional approaches treat mapping and planning as separate stages, typically relying on binary occupancy maps for collision checking. This separation discards valuable distance and gradient information that could accelerate planning and improve trajectory optimization. Furthermore, existing Signed Distance Function (SDF) methods often fail to meet the conflicting requirements of aerial autonomy: they are either accurate but computationally expensive (neural methods), efficient but discrete and non-differentiable (volumetric methods), or unable to extrapolate well beyond observed surfaces (Gaussian Process methods). The challenge is to develop a unified system that reconstructs accurate, non-truncated SDFs in real-time and leverages this continuous distance information to plan efficiently under tight onboard computational constraints.

Methodology
The authors propose an integrated approach consisting of two core components: OREN (Octree REsidual Network) for mapping and Bubble⋆ for motion planning.

OREN (Mapping):
- Architecture: OREN is a hybrid model that combines an explicit geometric prior with an implicit neural residual. It utilizes a semi-sparse octree where the first $M$ layers are semi-sparse (creating all siblings of occupied nodes) and subsequent layers are sparse.
- SDF Prior: Each octant vertex stores learnable estimates of the SDF value ( $d_k$ ) and its gradient ( $g_k$ ). A coarse SDF prior, $d_{ga}(v)$ , is computed via gradient-augmented trilinear interpolation. This method uses stored gradients to extrapolate values from vertices, providing a more accurate prior than standard interpolation, especially away from the surface.
- Neural Residual: To recover fine geometric details lost due to octree resolution limits, implicit neural features are stored at octant vertices. A Multi-Layer Perceptron (MLP) decoder predicts a residual correction, $\delta d(v)$ , based on these features.
- Occupancy & Training: A second MLP decoder predicts occupancy log-odds directly from features. This occupancy prediction is used as a regularization term to supervise the SDF sign during online training, improving robustness to sensor noise. The final SDF is $\hat{d}(v) = d_{ga}(v) + \delta d(v)$ .
- Output: The system produces a continuous, differentiable, non-truncated SDF map with low memory footprint, suitable for real-time updates from streaming point clouds.
Bubble⋆ (Planning):
- Concept: Instead of treating path search and safe corridor construction as separate stages, Bubble⋆ unifies them. It exploits the SDF value at any point to define a maximal collision-free ball (a "bubble") around that point.
- Algorithm: Bubble⋆ is a search-based planner that constructs a graph of bubbles on a grid. It expands nodes by growing bubbles from SDF clearance values. The algorithm connects nodes within a bubble to the nodes on the bubble's boundary.
- Search: Using a heuristic similar to A⋆, the planner expands the most promising node, adding boundary nodes as successors. Because the bubble represents a collision-free region, the planner can skip intermediate grid checks, effectively performing "any-angle" pathfinding within the bubbles.
- Guarantees: The authors provide formal proofs for termination, completeness (under a mild clearance assumption of $1.5\Delta$ ), and failure detection.
- Trajectory Optimization: The sequence of overlapping bubbles forms a safe corridor. The authors use MINCO (Minimum Control) to optimize a dynamically feasible trajectory within this corridor. The optimization is unconstrained in its parameterization, mapping unconstrained variables to waypoints within the bubble overlap regions, ensuring the trajectory respects the safety constraints while minimizing snap and duration.

Key Contributions

OREN: A mapping approach that reconstructs accurate, differentiable, non-truncated SDFs in real-time by pairing an explicit octree prior with implicit neural corrections. It achieves the accuracy of neural methods with the memory and runtime efficiency of volumetric methods.
Bubble⋆: A search-based motion planner that unifies path search and safe-corridor construction. It constructs a graph of collision-free spheres (bubbles) directly from SDF queries, providing formal guarantees of termination, completeness, and failure detection.
Integrated System: A demonstration of the complete OREN-Bubble⋆ pipeline running fully onboard a quadrotor (Jetson Orin NX) in real-time, navigating unseen indoor environments.

Results

Mapping Performance: In comparison to baselines (H2-Mapping, PIN-SLAM, HIO-SDF, Voxblox), OREN improved SDF estimation by 22% on average. On the Newer College dataset, it improved mesh reconstruction metrics by an average of 43.1% over the best baselines.
Planning Efficiency: Bubble⋆ significantly outperformed grid-based A⋆ and sampling-based RRT/RRT⋆ planners.
- Collision Checks: Bubble⋆ performed 91–99% fewer collision checks than A⋆ in 2D tests.
- Planning Time: In 3D industrial environments, Bubble⋆ found trajectories spanning ~90 m in 1–3 seconds (total time ~1.0s), whereas A⋆ took up to 1.2s and RRT⋆ took up to 10s. In forest environments, Bubble⋆ completed planning in 3.8s, compared to 4.2s for A⋆ and over 10s for RRT⋆.
- Trajectory Quality: Bubble⋆ produced paths comparable in length to the shortest paths found by RRT⋆ but with lower tracking errors (0.291 m vs 0.314 m for RRT⋆ in industrial settings).
Real-World Flight: The system successfully executed multi-segment, looping trajectories onboard a quadrotor in an indoor environment, maintaining safe clearance from obstacles while running at real-time frequencies (OREN at ~7 Hz, planning in <220 ms).

Significance
The paper argues that mapping and planning should be co-designed around a single representation: the Signed Distance Function. By encoding the distance to the nearest obstacle, the SDF provides richer information than binary occupancy, allowing the planner to grow maximal collision-free regions (bubbles) rather than checking grid cells individually. This approach reduces the computational burden of collision checking, accelerates the planning process, and provides smooth constraints for trajectory optimization. The authors demonstrate that this integrated approach makes safe, autonomous flight tractable even under the tight compute and memory budgets of onboard UAV hardware, bridging the gap between high-fidelity implicit mapping and efficient, real-time motion planning.

More like this