Signed Distance Field (SDF)

Unlike discrete occupancy grids, an SDF stores the exact Euclidean distance to the nearest surface at every point in space. This allows a planner to instantly know how far a robot link is from a collision, not just whether a collision exists. The sign convention—negative inside, positive outside—provides immediate penetration depth information, which is critical for gradient-based trajectory optimization that needs to push configurations out of collision.

Because SDFs are differentiable almost everywhere, they provide smooth gradient vectors pointing directly toward the nearest surface. Optimization-based planners like Trajectory Optimization and CHOMP leverage these gradients as collision cost terms, guiding the solver away from obstacles. The gradient magnitude equals 1 for valid SDFs, ensuring consistent step sizes during numerical optimization without the vanishing-gradient problems that plague other representations.

SDFs enable O(1) collision queries by simply evaluating the signed distance at a query point. A negative value indicates penetration, while a positive value below a safety threshold triggers a proximity warning. This constant-time lookup replaces expensive mesh-mesh intersection tests like the Gilbert-Johnson-Keerthi (GJK) algorithm during online planning. For articulated robots, the SDF of each link can be queried against the environment SDF without iterative pairwise checks.

SDFs are stored in several forms depending on the application:

• Voxel Grids: A dense 3D array where each cell stores the signed distance, offering fast random access at the cost of high memory usage
• Octrees: A hierarchical sparse structure that subdivides space only where detail is needed, dramatically reducing memory for large environments
• Neural Implicit Representations: Networks like Neural Radiance Fields (NeRF) variants learn a continuous SDF from images, enabling high-fidelity reconstruction from partial sensor data

For Continuous Collision Detection (CCD), SDFs can represent the swept volume of a moving robot link. By taking the minimum distance over the motion trajectory, the SDF captures the entire space occupied during a timestep. This prevents tunneling artifacts where fast-moving robots pass through thin obstacles between discrete collision checks. The swept-volume SDF can be precomputed for known trajectories or approximated using conservative advancement techniques.

Modern motion planning libraries natively support SDF-based collision environments:

• MoveIt uses SDFs through its planning scene to accelerate collision checking for manipulators
• OMPL planners can query SDF-based validity checkers for sampling-based methods like RRT* and PRM
• TrajOpt and STOMP directly consume SDF gradients for trajectory smoothing
• GPU-accelerated SDF computation enables real-time replanning at kilohertz rates for reactive control loops

The mathematical space representing all possible positions and orientations of a robot. In this space, the robot is treated as a point, and obstacles are inflated by the robot's geometry. SDFs are often queried directly in C-Space to compute the distance from a configuration to the nearest obstacle boundary, enabling efficient collision checking during sampling-based planning.

An iterative algorithm that efficiently computes the minimum distance between two convex shapes. GJK serves as the foundational narrow-phase collision detection routine that SDFs approximate. While GJK computes exact distances on-the-fly for explicit geometry, SDFs precompute and store these distances in a grid for constant-time lookup, trading memory for speed.

A method that checks for collisions along the entire continuous motion between two discrete timesteps, preventing tunneling artifacts where fast-moving objects pass through thin obstacles. SDFs enable efficient CCD by allowing linear interpolation of distance values along a path segment; if the signed distance crosses zero, a collision has occurred.

A numerical optimization approach that refines an initial path into a dynamically feasible trajectory by minimizing a cost function subject to constraints. SDFs provide smooth, differentiable collision costs that can be directly incorporated into gradient-based optimizers:

• Obstacle cost: Penalizes configurations with negative or small positive distances
• Gradient: The SDF gradient points away from the nearest obstacle, providing a natural repulsive force

A grid-based data structure used in ROS navigation that aggregates sensor information into occupancy probabilities and inflated obstacle representations. Each cell stores a cost value derived from its distance to the nearest obstacle, making it a discrete 2D analog of an SDF. Mobile robots use costmaps for local path planning, where higher costs repel trajectories from obstacles with a safety margin.