GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance

arXiv:2607.04310 · cs.RO · Submitted 2026-07-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance".

Rosa: The proposed Polygonal Signed Distance Function (PSDF) is a geometry-exact signed distance function between a convex polygonal robot footprint and obstacles represented by their boundary edges,

Dev: First, who's behind it and why it matters.

Title and authors: Rosa: Looking at the title, "GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance," it immediately tells us that the core innovation is combining geometry precision with high computational speed for immediate collision avoidance in real-time control loops. It's about making sure a robot doesn't crash while it's moving through a space defined by polygonal obstacles, and doing all that calculation incredibly quickly.

Dev: From my perspective as a controls engineer, the focus on "GPU-Accelerated" suggests they are directly addressing the bottleneck of constraint evaluation speed within NMPC schemes. The authors are showing how to take geometrically precise information and process it using tensor operations on a GPU to meet strict timing requirements for low-level actuation.

Taro: The authors themselves are clearly targeting the performance gap that exists when moving from simplified geometric primitives, like just using circles or boxes, to needing true polygon fidelity in dynamic scenarios. They're addressing the fact that those simpler models often lead to overly conservative or inaccurate avoidance behaviors in dense settings.

Rosa: It seems the primary implication is moving away from methods where collision checking slows down the entire optimization process, which was a major issue before. Instead, they are proposing a structure where the geometric evaluation—the PSDF calculation—is massively parallelized on the GPU while keeping the subsequent optimization steps manageable on a standard CPU.

Dev: That separation of computation is key; it means if we need to increase the complexity of our environment, we don't necessarily have to drastically slow down our entire control loop because the bottleneck shifts from geometry evaluation to whatever fixed dimension your QP solver handles.

Taro: I think this points toward a future where autonomy systems can operate in environments with much richer, more detailed representations of obstacles without sacrificing the necessary control frequency for safe movement. It suggests we can afford to use more complex world models if the collision oracle is fast enough.

Rosa: Precisely; it’s about achieving a sweet spot between geometric accuracy and computational throughput that was previously considered impossible to reach within strict real-time constraints for complex polygonal setups. We are looking at how this impacts deployment outside of a clean lab setting, which I want to ask about next.

The paper's summary: Dev: The summary explains that the authors introduce the Polygonal Signed Distance Function, or PSDF, which is a geometry-exact function giving signed distances between a convex polygonal robot footprint and obstacles defined by their boundary edges. This function is implemented as a branch-free pipeline using tensor operations for batched GPU evaluation and automatic differentiation.

Rosa: The main implication of this formulation is that it provides not just the distance, but also the gradients, because it's piecewise-differentiable. This allows them to embed these safety constraints directly into an MPC framework by locally linearizing them around a nominal trajectory using those gradients.

Taro: I see how that differentiability feeds into the controller design; it allows for smooth transitions and convergence within the sequential quadratic programming–based real-time iteration scheme, which is essential for maintaining stability during iterative optimization. It’s about making sure the safety constraints are respected not just at a single point, but smoothly along a trajectory.

Dev: The paper highlights that they achieve this by separating CPU and GPU computation: the GPU handles batched PSDF values and gradients, while the CPU solves a sparse quadratic program whose dimension is fixed by system dimensions and horizon length. This architectural split is what allows for high-rate execution in practice.

Rosa: So, to summarize simply, this work delivers a tool that provides geometry-exact collision data at the speed needed for real-time planning, and it’s integrated into an MPC framework in a way that keeps the CPU workload predictable and fast regardless of how many obstacles are present.

Taro: The implications for autonomy are huge because it moves us closer to handling complex, unstructured environments where traditional methods would simply grind to a halt waiting for collision checks to finish. This capability should allow robots to operate reliably in crowded spaces that we currently treat as computationally prohibitive.

Dev: I agree; the fact that they achieved this with sub-one hundred millisecond optimization times, even with complex scenes, suggests a viable path toward high-density operational autonomy where safety isn't sacrificed for speed.

Rosa: It really feels like they’ve found a way to get the geometric rigor required for safe navigation without incurring the massive computational overhead that usually accompanies such rigorous checks in real-time systems. We need to see if this holds up when we push it outside of perfect simulation scenarios.

The paper's improvements: Rosa: The authors suggest several key architectural improvements, specifically focusing on how they structure their pipeline: they propose a branch-free pipeline that combines point–segment distance primitives with SAT-based overlap reasoning, all expressed as tensor operations for batched GPU evaluation and automatic differentiation.

Dev: That’s a major methodological improvement because it replaces potentially slower or less parallelizable branching logic with a more unified tensor approach. This shift simplifies the execution flow on the GPU, which directly contributes to achieving that high-speed, batched evaluation they report.

Taro: I'm also interested in the specific way they define their penetration depth using that smoothed max distance function involving a smoothing parameter eta > zero and an exponential sum; that mathematical definition is crucial for making the collision checking differentiable when it needs to be.

Rosa: That mathematical definition is what allows them to get a differentiable surrogate for the hard minimum of overlaps, which feeds directly into their final signed distance synthesis stage, giving them that continuous safety signal needed for gradient-based optimization.

Dev: The crucial improvement in the controller integration comes from how they linearize the stage-wise safety constraints around a nominal trajectory using a first-order Taylor expansion to get the Jacobian matrix J g. This ensures the QP subproblem is solvable in real time, and that this linearization doesn't rely on obstacle-dependent decision variables.

Taro: It’s interesting how they decouple the environment complexity from the QP solver dimension; they state that the CPU only needs to solve a sparse quadratic program whose size depends only on system dimensions and horizon length, not by how many obstacles are in the scene. That’s a massive structural improvement for scaling.

Rosa: So, these improvements boil down to making sure every piece of computation—from geometry calculation to constraint linearization—is highly parallelizable and structured so that the CPU side remains lightweight and fast. It’s about engineering the entire pipeline for maximum efficiency in a real-time setting.

Conclusion: Dev: To wrap up, this work with the "GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance" provides a concrete solution for high-rate collision avoidance by leveraging a heterogeneous CPU/GPU pipeline where geometry is offloaded to the GPU and optimization remains lightweight on the CPU. The key takeaway is that we can embed geometry-exact safety constraints into MPC without letting the complexity of the environment dictate the size of our core optimization problem.

Rosa: I think what really stands out is how they managed to maintain both geometric accuracy and real-time feasibility simultaneously, which is a tough balancing act in this field. It shows that a well-structured tensorized pipeline can be a powerful way to handle complex geometric constraints efficiently for practical applications.

Taro: If we look at the broader impact, this technique could significantly lower the barrier for deploying sophisticated autonomous systems into environments that are currently too dense or too unpredictable for existing optimization methods to handle effectively. It shifts the focus toward making perception and control tightly coupled in a way that is computationally feasible at high frequencies.

Dev: I’m keen to see how they translate this efficiency into longer operational durations; we need validation on how robust this system is when deployed outside of controlled simulation environments over extended periods without degradation of those sub-one hundred millisecond performance metrics.

Rosa: It sounds like a very promising direction for making sophisticated robots truly operate in the real world, and I'm looking forward to seeing the next steps where they tackle those deployment challenges head-on.

School of Mechanical Engineering, Yonsei University

cs.RO

Submitted: 2026-07-05

Updated: 2026-09-29

Comments: 10 pages, 5 figures, 3 tables

Code: https://github.com/Taek111/psdf

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: The proposed Polygonal Signed Distance Function (PSDF) is a geometry-exact signed distance function between a convex polygonal robot footprint and obstacles represented by their boundary edges,

Key concepts

Polygonal Signed Distance Function (PSDF)
A geometry-exact function that calculates signed distances between a robot's convex polygonal footprint and obstacles defined by their boundary edges. It is implemented using tensor operations for batched GPU evaluation, providing not just distance but also gradients.
GPU-Accelerated Pipeline
The method uses a branch-free pipeline combining point–segment distance primitives with SAT-based overlap reasoning, all expressed as tensor operations on a GPU. This structure replaces slower branching logic with a unified tensor approach for high-speed, batched evaluation.
MPC Constraint Linearization
The authors linearize stage-wise safety constraints around a nominal trajectory using a first-order Taylor expansion to obtain the Jacobian matrix J g. This ensures the sequential quadratic programming (QP) subproblem remains solvable in real time and avoids reliance on obstacle-dependent decision variables.

Terminology

Summary

The proposed Polygonal Signed Distance Function (PSDF) is a geometry-exact signed distance function between a convex polygonal robot footprint and obstacles represented by their boundary edges, designed for real-time collision avoidance in optimization-based local planning and control. It is implemented as a weight-free, branch-free tensorized geometric pipeline enabling batched GPU execution and automatic differentiation. The PSDF is embedded into model predictive control (MPC) by locally linearizing the stage-wise safety constraints within a sequential quadratic programming–based real-time iteration scheme, yielding the PSDF-embedded model predictive controller (PSDF-MPC).

The key features and contributions of the paper are:

  1. PSDF Formulation: An edge-based polygonal signed distance function for convex polygon footprints against polygonal obstacles, returning geometry-exact signed distances and state gradients.

  2. GPU-suitable Implementation: A branch-free pipeline combining point-to-segment distance primitives and SAT-based overlap and penetration reasoning, expressed as tensor operations enabling batched GPU evaluation and automatic differentiation.

  3. Controller Integration: Embedding PSDF-based safety constraints into SQP-RTI MPC via stage-wise local linearization with a clear CPU/GPU separation, yielding a real-time pipeline whose QP size is independent of obstacle feature count.

The architecture separates CPU/GPU computation so that the GPU evaluates batched PSDF values and gradients while the CPU solves a sparse quadratic program whose dimension is determined by system dimensions and horizon length, not by obstacle features. This design retains the structure exploited by real-time MPC solvers while enabling geometry-exact collision avoidance within the optimization loop.

The PSDF computes a signed distance between the robot footprint at state x and an environment represented directly by obstacle boundary edges, defined as:

ϕ(x, E):= min i=1,…,M sd(P 0(x), P i).

The safety constraint used in the finite-horizon optimal control problem is formulated as:

h(xk+s, Ek+s):= ϕ(xk+s, Ek+s) − dmin ≥ 0, which enforces that the robot remains at least a minimum clearance margin of dmin away from the obstacles.

The computational pipeline involves four sequential stages on the GPU:

  1. Coordinate transformation: Transforming world-frame obstacle segments into the robot-local frame.

  2. Branch-free point–segment distances: Computing distances from robot vertices to obstacle edges and vice versa using a branch-free primitive, yielding an obstacle-wise separation distance, and then combining these with a SAT stage to determine penetration depth.

  3. SAT-based collision checking: Using a tensorized Separating Axis Theorem (SAT) test on candidate axes derived from robot and obstacle edge normals to detect separation or overlap. A differentiable surrogate for the hard minimum of overlaps is used: "Let δ i+(n):= maxδ i(n), 0, and choose a smoothing parameter η > 0. The obstacle-wise penetration depth is defined as δ x, E i:= −1/η log Σ n∈Ni exp− η δ i+(n)!"

  4. Signed distance synthesis: Combining the separation distances and penetration depths to produce an obstacle-wise polygonal signed distance, and finally taking the minimum over all obstacles to obtain the global PSDF value ϕ(x, E).

The controller uses a Sequential Quadratic Programming–based real-time iteration (SQP-RTI) scheme. The safety constraint is linearized around a nominal predicted trajectory using a first-order Taylor expansion:

h(xk+s, Ek+s) ≈ h(¯xk+s, Ek+s) + ∇xh(¯xk+s, Ek+s)⊤∆xk+s.

This leads to the stage-wise linearized safety constraint: Jg(¯xk+s, Ek+s) ∆xk+s ≤ h(¯xk+s, Ek+s), where Jg is the stage-wise Jacobian matrix.

The implementation utilizes a CPU/GPU separation: The GPU evaluates batched PSDF values and gradients while the CPU solves a sparse quadratic program whose dimension is determined by system dimensions and horizon length, not by obstacle features. This decoupling confines environment complexity to the collision-oracle evaluation workload while keeping the CPU-side QP dimension and sparsity fixed.

Experimental results show that PSDF maintains real-time feasibility and robust collision avoidance in dense polygonal scenes, with per-step optimization times consistently below 100 ms, significantly outperforming optimization-based baselines like Optimization-Based Collision Avoidance (OBCA) and Discrete-time Control Barrier Function (DCBF), which require hundreds of milliseconds for larger obstacle feature counts. The method is also shown to be effective across different kinematic classes, including differential-drive and Ackermann dynamics.

Improvements for AI systems

Here are the specific improvements that can be made to existing AI systems, based on the proposed PSDF-MPC framework:

  1. Improve real-time collision avoidance in high-density, obstacle-rich environments by replacing conservative distance primitives (like simple circles or boxes) with a geometry-exact signed distance function (PSDF).

  2. Enable robust, fast trajectory optimization for mobile robots and autonomous vehicles by decoupling the computational cost of geometric constraint evaluation from the complexity of the environment.

  3. Enhance control loop frequency and stability in complex scenarios by implementing a heterogeneous CPU/GPU pipeline where:

  4. The GPU performs batched, branch-free evaluation of signed distances and their gradients using tensor operations, allowing for massive parallelization.

  5. The CPU solves a sparse Quadratic Program (QP) whose dimension and sparsity are determined only by system state dimensions and horizon length, making the optimization problem independent of the number of obstacles.

  6. Facilitate consistent local linearizations of collision constraints within Sequential Quadratic Programming–based Real-Time Iteration (SQP-RTI) schemes by using automatically differentiated gradients from the PSDF.

  7. Provide a real-time safety guarantee by embedding stage-wise, locally linearized safety constraints into the QP subproblem, ensuring that predicted states maintain a minimum clearance margin without requiring obstacle-dependent decision variables in the optimizer.

The improved AI system (PSDF-MPC) can:

  1. Navigate narrow passages and tight corridors with high fidelity, avoiding conservative behavior caused by coarse geometric surrogates or simple primitives.

  2. Maintain real-time feasibility and robust collision avoidance in unstructured, obstacle-dense environments where traditional optimization methods fail due to excessive computation time (e.g., achieving control frequencies below 10 Hz).

  3. Handle richer, polygonal obstacle descriptions (derived from high-resolution LiDAR point clouds) without increasing the size or complexity of the underlying Quadratic Program that the CPU must solve.

  4. Operate efficiently on embedded hardware (like NVIDIA Jetson) by leveraging GPU acceleration for geometry computation while keeping the optimization core on a standard CPU solver loop.

  5. Provide accurate, differentiable safety signals, which are crucial for reliable gradient-based optimization solvers like SQP and SQP-RTI to converge quickly toward collision-free trajectories.

Sources

Related papers