Pith. sign in

REVIEW 2 major objections 6 minor 27 references

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

T0 review · 2 major / 6 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A GPU signed-distance function for polygons keeps exact robot-obstacle geometry while the MPC quadratic program stays fixed-size no matter how many obstacles appear.

desk verdict Solid systems paper: geometry-exact edge SDF + fixed-size QP via GPU/CPU split; usable now, scope limited to convex static polygons. read the letter →

arxiv 2607.04310 v1 pith:LBSHHWF2 submitted 2026-07-05 cs.RO

Taekwon Ga , Jongeun Choi This is my paper
classification cs.RO
keywords CollisionAvoidanceSignedDistanceFunctionGPUAccelerationReal-TimeOptimizationModelPredictiveControlPolygonalGeometrySQP-RTI
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Optimization-based robot controllers need fast, accurate collision checks over a prediction horizon. In cluttered scenes those checks often dominate runtime, and coarse shapes (circles, boxes) waste free space. This paper introduces the Polygonal Signed Distance Function (PSDF): a branch-free, tensorized signed-distance computation between a convex polygonal robot footprint and obstacle boundary edges that runs in batches on a GPU and yields gradients by automatic differentiation. PSDF values and Jacobians are turned into stage-wise linear safety inequalities and fed to a real-time sequential quadratic program on the CPU. Because the QP dimension depends only on the robot’s state size, input size, and horizon length—not on the number of edges—the controller can keep exact polygonal geometry without enlarging the optimizer. Micro-benchmarks and closed-loop tests (simulation and real robot) show that the resulting PSDF-MPC stays real-time and collision-free in dense polygonal environments where duality-based and soft-constraint baselines slow down or fail.

What carries the argument

Polygonal Signed Distance Function (PSDF): a weight-free pipeline of robot-local edge transforms, branch-free point-to-segment distances, SAT-based soft-min penetration, and min-reduction that returns signed distances and state gradients for any batch of poses against a padded edge tensor.

What would settle it

In a dense static polygonal scene with a convex robot footprint, measure whether per-step solve time remains essentially constant as obstacle edge count grows while the robot still tracks a tight reference without collision; if either the QP dimension grows with edges or clearance is lost under the reported linearizations, the central claim fails.

Watch

Extended reading notes

Core claim

A geometry-exact polygonal signed-distance oracle can be written as a fully tensorized, branch-free GPU pipeline whose outputs linearize into stage-wise safety constraints for SQP-RTI model predictive control; the resulting QP size and sparsity are independent of obstacle feature count, so environment complexity is confined to the parallel collision-oracle workload while the optimizer remains a fixed, sparse real-time problem.

Load-bearing premise

The robot footprint and every obstacle must be convex (or already split into convex pieces) and the obstacle edge set is treated as fixed for the whole prediction horizon.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes the Polygonal Signed Distance Function (PSDF), a branch-free, tensorized, GPU-executable signed-distance oracle between a convex polygonal robot footprint and obstacle boundary edges, together with its embedding into SQP-RTI model predictive control (PSDF-MPC). The architecture evaluates batched PSDF values and state gradients on the GPU and injects stage-wise affine safety linearizations into a CPU-side sparse QP whose size depends only on (n_x, n_u, N), not on obstacle feature count. Micro-benchmarks (Table I) compare query latency against GJK+EPA and NPField; closed-loop results in 2D mazes, Gazebo corridors, CARLA parking, and a Jetson+LiDAR Scout Mini deployment (Tables II–III, Figs. 2–5) report real-time feasibility and competitive success/navigation times versus OBCA, DCBF, TEB, and RDA under the paper’s convex, static-horizon setting.

Significance. If the reported scaling and closed-loop behavior hold, the work offers a practical systems-level answer to a recurring bottleneck in optimization-based local planning: geometry-exact polygonal collision constraints without dual variables or obstacle-dependent QP growth. The CPU/GPU separation (Sec. V, Alg. 1) is a clear engineering contribution, and the public ROS/PyTorch release strengthens reproducibility. The evaluation spans micro-benchmarks, multiple simulators, and onboard LiDAR deployment, which is stronger evidence than many related MPC-collision papers. Scope is appropriately limited to convex (or pre-decomposed) polygons and static edge sets over the horizon; within that scope the result is useful for dense planar navigation and parking-style maneuvers.

major comments (2)
  1. [Abstract; Sec. IV-C, Eq. (31); Sec. IV-D] Abstract and Contribution 1 call PSDF “geometry-exact,” but Sec. IV-C Eq. (31) replaces the hard min penetration depth with a log-sum-exp soft-min controlled by η. Separation distances from the point-to-segment stage are exact for convex polygons; penetration is intentionally smoothed. The exactness claim should be qualified in the abstract, contributions, and Sec. IV-D (e.g., exact when separated; smooth surrogate when penetrating), and the sensitivity of closed-loop behavior to η should be stated or briefly ablated so readers know the approximation is not load-bearing for the reported timings.
  2. [Sec. VI-D; Fig. 4; Table III] Sec. VI-D and Fig. 4 present real-robot deployment only qualitatively (trajectory and top-down views). Table III quantifies success, navigation time, and mean computation time only in Gazebo. Given the paper’s claim of “real-world navigation experiments” and onboard Jetson execution, at least mean per-step optimization time and a success/failure summary on the physical platform (even without TEB/RDA on-robot) are needed to support the deployability claim at the same standard as the simulation tables.
minor comments (6)
  1. [Assumption 1; Sec. V-B; Note to Practitioners] Assumption 1 and Sec. V-B correctly state convexity and static-horizon edge sets; the Note to Practitioners and Conclusion already flag dynamic obstacles and perception noise. A short explicit failure-mode paragraph (e.g., incomplete line fits, nonconvex leftovers after decomposition) would help practitioners without changing scope.
  2. [Sec. IV-D, Eq. (32)] Eq. (32) uses a hard separated_i switch. Values match at contact if d_sep and δ both approach zero, but gradients can jump. A one-sentence note on how the tensorized mask is implemented and that SQP-RTI re-linearizes every cycle would clarify nondifferentiability at the contact boundary.
  3. [Sec. VI-B; Table I] Table I compares GPU PSDF/NPField to CPU GJK+EPA. The text already notes the platform difference; stating explicitly that GJK+EPA is a sequential CPU baseline (not a GPU-optimized competitor) would prevent misreading of the large-M, large-B gap.
  4. [Fig. 1; Sec. V-A] Fig. 1 caption and Alg. 1 refer to stage-wise parameters {[h_s; J_g,s^T]}; notation for J_g is introduced later in Eqs. (39)–(40). Align symbol order so the figure is self-contained.
  5. [Introduction; front matter] Minor typography: “an collision oracle” (p. 1), “the authors are with the School…” affiliation line breaks, and occasional missing spaces before citations. A pass for grammar and IEEE style would help.
  6. [Sec. II-B; Ref. [11]] Related work cites OBCA, duality-CBF, RDA, NeuPAN, and SDF-NMPC appropriately. A brief contrast with recent GPU-accelerated OBCA (ref. [11]) on whether dual variables still grow with features would sharpen the QP-size-independence claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: PSDF is a constructive geometric pipeline and PSDF-MPC is an engineering integration evaluated against external baselines.

full rationale

The paper’s load-bearing chain is constructive, not predictive. PSDF is defined from first-order geometric primitives (branch-free point-to-segment distances, SAT projections, soft-min penetration, min over obstacles; Sec. IV, Eqs. 17–33) and implemented as a weight-free tensor graph; nothing in that definition is fitted to the navigation outcomes later reported. Embedding into SQP-RTI (Sec. V, Alg. 1) uses standard local linearization of the safety constraint and a CPU/GPU split so QP size depends only on (nx, nu, N); that architectural claim is checked by microbenchmarks (Table I vs GJK+EPA and NPField) and closed-loop timings against independent baselines (OBCA, DCBF, TEB, RDA; Tables II–III), not by re-labeling fitted parameters as predictions. Free knobs (N, d_min, soft-min η) are controller settings, not claimed discoveries. Self-citations are limited to tooling (SQP-RTI, RealTime L4CasADi) and prior NMPC context; none supply a uniqueness theorem or ansatz that forces the central result. Scope assumptions (convex footprints/obstacles, static edges over the horizon) are stated as limits, not smuggled conclusions. No step reduces a claimed prediction to its own inputs by construction.

Assumptions & free parameters 4 free parameters · 4 assumptions · 1 invented entities

The central claim rests on standard convex geometry and SQP-RTI machinery plus a small set of domain assumptions (convexity, static horizon, perfect edge encoding) and a few controller hyperparameters. No new physical entities are postulated; the PSDF itself is an algorithmic construction, not an invented ontological object.

free parameters (4)
  • prediction horizon N = 15
    Fixed to 15 steps in all closed-loop experiments; affects both feasibility and timing.
  • safety margin d_min = 0.01 m
    Clearance offset in the safety constraint; set to 0.01 m.
  • soft-min smoothing η
    Controls differentiability of the SAT penetration depth; chosen for numerical stability but not systematically ablated.
  • padding bounds M-bar, m-bar
    Upper bounds on obstacles and edges per obstacle that fix GPU tensor shapes; scenario-dependent.
assumptions (4)
  • domain assumption Robot footprint and every obstacle are convex bounded polygons (or pre-decomposed into convex pieces); distance checks are applied componentwise.
    Assumption 1; required for the SAT and point-to-segment reductions to be exact.
  • domain assumption Environment edge set is static over the entire MPC prediction horizon.
    Sec. V-B; simplifies batched evaluation and is used in all reported experiments.
  • domain assumption First-order Taylor linearization of the PSDF safety constraint around the nominal trajectory yields a sufficiently accurate local model for one SQP-RTI step.
    Sec. V-A; standard RTI premise whose quality depends on trajectory smoothness and replan rate.
  • standard math Standard SQP-RTI convergence and real-time iteration theory apply to the resulting sparse QP.
    Cited from Diehl et al.; used without re-derivation.
invented entities (1)
  • Polygonal Signed Distance Function (PSDF) independent evidence
    purpose: Geometry-exact, differentiable, branch-free signed-distance oracle between a convex robot polygon and an edge-set environment.
    Algorithmic construction assembled from known primitives (point-to-segment, SAT); independent evidence is the released code and empirical timings, not a new physical object.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance." pith.science (2026). https://pith.science/paper/LBSHHWF2

@misc{pith2026260704310,
  author       = {Pith},
  title        = {Pith review of: GPU-Accelerated Polygonal Signed Distance Functions for Real-Time Collision Avoidance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LBSHHWF2}},
  note         = {Machine review of arXiv:2607.04310}
}
read the original abstract

Optimization-based local planning and control require high-rate collision-avoidance constraint evaluation over a prediction horizon. In obstacle-dense environments, where feasible space is limited and the constraints become increasingly complex, the computational workload often dominates the control-cycle runtime. The resulting bottleneck motivates collision-avoidance constraints that combine computational efficiency with geometric fidelity. 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. 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 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 design 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. Microbenchmarks show that PSDF scales favorably against signed-distance query baselines. Closed-loop simulated and real-world navigation experiments, including comparisons with optimization-based baselines, demonstrate that PSDF-MPC maintains real-time feasibility and robust collision avoidance in dense polygonal environments.

Figures

Figures reproduced from arXiv: 2607.04310 by the authors.

Figure 1
Figure 1. Overall PSDF-MPC architecture with heterogeneous CPU/GPU execution. The robot system provides the measured state [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Closed-loop trajectories in the 2D Maze environments. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Gazebo corridor navigation benchmark and representative executed trajectories. (a) Gazebo test environment comprising [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Real robot deployment: trajectories and top-down views. (a) Real-world driving environment and the trajectory executed [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Autonomous parking in a cluttered parking-lot scenario. The maneuver is executed in two stages: straight driving to the [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 1 linked inside Pith

  1. [1]

    Nonaffine helicopter control design and implementation based on a robust explicit nonlinear model predictive control,

    J. Seo, S. Lee, J. Lee, and J. Choi, “Nonaffine helicopter control design and implementation based on a robust explicit nonlinear model predictive control,”IEEE Transactions on Control Systems Technology, vol. 30, no. 2, pp. 811–818, 2021

    2021

  2. [2]

    A linear time algorithm for computing exact euclidean distance transforms of binary images in arbitrary dimensions,

    C. R. Maurer, R. Qi, and V . Raghavan, “A linear time algorithm for computing exact euclidean distance transforms of binary images in arbitrary dimensions,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 2, pp. 265–270, 2003

    2003

  3. [3]

    Distance transforms of sampled functions,

    P. F. Felzenszwalb and D. P. Huttenlocher, “Distance transforms of sampled functions,”Theory of computing, vol. 8, no. 1, pp. 415–428, 2012

    2012

  4. [4]

    V oxblox: Incremental 3d euclidean signed distance fields for on-board mav planning,

    H. Oleynikova, Z. Taylor, M. Fehr, R. Siegwart, and J. Nieto, “V oxblox: Incremental 3d euclidean signed distance fields for on-board mav planning,” in2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2017, pp. 1366–1373

    2017

  5. [5]

    Fiesta: Fast incremental euclidean distance fields for online motion planning of aerial robots,

    L. Han, F. Gao, B. Zhou, and S. Shen, “Fiesta: Fast incremental euclidean distance fields for online motion planning of aerial robots,” in2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2019, pp. 4423–4430

    2019

  6. [6]

    Autonomous parking using optimization-based collision avoidance,

    X. Zhang, A. Liniger, A. Sakai, and F. Borrelli, “Autonomous parking using optimization-based collision avoidance,” in2018 IEEE Conference on Decision and Control (CDC). IEEE, 2018, pp. 4327–4332

    2018

  7. [7]

    Optimization-based collision avoidance,

    X. Zhang, A. Liniger, and F. Borrelli, “Optimization-based collision avoidance,”IEEE Transactions on Control Systems Technology, vol. 29, no. 3, pp. 972–983, 2020

    2020

  8. [8]

    Duality-based convex optimization for real-time obstacle avoidance between polytopes with control barrier functions,

    A. Thirugnanam, J. Zeng, and K. Sreenath, “Duality-based convex optimization for real-time obstacle avoidance between polytopes with control barrier functions,” in2022 American Control Conference (ACC). IEEE, 2022, pp. 2239–2246

    2022

Show all 27 references
  1. [9]

    Safety-critical control and planning for obstacle avoidance be- tween polytopes with control barrier functions,

    ——, “Safety-critical control and planning for obstacle avoidance be- tween polytopes with control barrier functions,” in2022 International Conference on Robotics and Automation (ICRA). IEEE, 2022, pp. 286– 292

    2022

  2. [10]

    Rda: An accelerated collision free motion planner for autonomous navigation in cluttered environments,

    R. Han, S. Wang, S. Wang, Z. Zhang, Q. Zhang, Y . C. Eldar, Q. Hao, and J. Pan, “Rda: An accelerated collision free motion planner for autonomous navigation in cluttered environments,”IEEE Robotics and Automation Letters, vol. 8, no. 3, pp. 1715–1722, 2023

    2023

  3. [11]

    Gpu-accelerated optimization- based collision avoidance,

    Z. Wu, Z. Wang, and H. Zhang, “Gpu-accelerated optimization- based collision avoidance,” in2024 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2024, pp. 7561–7567

    2024

  4. [12]

    Sequential quadratic programming,

    P. T. Boggs and J. W. Tolle, “Sequential quadratic programming,”Acta numerica, vol. 4, pp. 1–51, 1995

    1995

  5. [13]

    A real-time iteration scheme for nonlinear optimization in optimal feedback control,

    M. Diehl, H. G. Bock, and J. P. Schl ¨oder, “A real-time iteration scheme for nonlinear optimization in optimal feedback control,”SIAM Journal on control and optimization, vol. 43, no. 5, pp. 1714–1736, 2005

    2005

  6. [14]

    Integrated online trajec- tory planning and optimization in distinctive topologies,

    C. R ¨osmann, F. Hoffmann, and T. Bertram, “Integrated online trajec- tory planning and optimization in distinctive topologies,”Robotics and Autonomous Systems, vol. 88, pp. 142–153, 2017

    2017

  7. [15]

    Nonlinear model predictive control for wheeled mobile robot in dynamic environment,

    C.-H. Hsieh and J.-S. Liu, “Nonlinear model predictive control for wheeled mobile robot in dynamic environment,” in2012 IEEE/ASME international conference on advanced intelligent mechatronics (AIM). IEEE, 2012, pp. 363–368

    2012

  8. [16]

    Autonomous vehicle con- trol: A nonconvex approach for obstacle avoidance,

    U. Rosolia, S. De Bruyne, and A. G. Alleyne, “Autonomous vehicle con- trol: A nonconvex approach for obstacle avoidance,”IEEE Transactions on Control Systems Technology, vol. 25, no. 2, pp. 469–484, 2016

    2016

  9. [17]

    Finding locally optimal, collision-free trajectories with sequential con- vex optimization

    J. Schulman, J. Ho, A. X. Lee, I. Awwal, H. Bradlow, and P. Abbeel, “Finding locally optimal, collision-free trajectories with sequential con- vex optimization.” inRobotics: science and systems, vol. 9, no. 1. Berlin, Germany, 2013, pp. 1–10

    2013

  10. [18]

    A fast procedure for computing the distance between complex objects in three-dimensional space,

    E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, “A fast procedure for computing the distance between complex objects in three-dimensional space,”IEEE Journal on Robotics and Automation, vol. 4, no. 2, pp. 193–203, 2002

    2002

  11. [19]

    Proximity queries and penetration depth compu- tation on 3d game objects,

    G. Van Den Bergen, “Proximity queries and penetration depth compu- tation on 3d game objects,” inGame developers conference, vol. 170, 2001, p. 209

    2001

  12. [20]

    Reachability-based trajectory design via exact formulation of implicit neural signed distance functions,

    J. Michaux, Q. Chen, C. E. Adu, J. Liu, and R. Vasudevan, “Reachability-based trajectory design via exact formulation of implicit neural signed distance functions,”arXiv preprint arXiv:2403.12280, 2024

    2024 arXiv

  13. [21]

    Neural nmpc through signed distance field encoding for collision avoidance,

    M. Jacquet, M. Harms, and K. Alexis, “Neural nmpc through signed distance field encoding for collision avoidance,”The International Journal of Robotics Research, p. 02783649251401223, 2025

    2025

  14. [22]

    Neupan: Direct point robot navigation with end- to-end model-based learning,

    R. Han, S. Wang, S. Wang, Z. Zhang, J. Chen, S. Lin, C. Li, C. Xu, Y . C. Eldar, Q. Haoet al., “Neupan: Direct point robot navigation with end- to-end model-based learning,”IEEE Transactions on Robotics, 2025

    2025

  15. [23]

    Neural potential field for obstacle-aware local motion planning,

    M. Alhaddad, K. Mironov, A. Staroverov, and A. Panov, “Neural potential field for obstacle-aware local motion planning,” in2024 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2024, pp. 9313–9320

    2024

  16. [24]

    Learning for casadi: Data-driven models in numerical optimization,

    T. Salzmann, J. Arrizabalaga, J. Andersson, M. Pavone, and M. Ryll, “Learning for casadi: Data-driven models in numerical optimization,” in6th Annual Learning for Dynamics & Control Conference. PMLR, 2024, pp. 541–553

    2024

  17. [25]

    Real-time neural mpc: Deep learning model predictive control for quadrotors and agile robotic platforms,

    T. Salzmann, E. Kaufmann, J. Arrizabalaga, M. Pavone, D. Scaramuzza, and M. Ryll, “Real-time neural mpc: Deep learning model predictive control for quadrotors and agile robotic platforms,”IEEE Robotics and Automation Letters, vol. 8, no. 4, pp. 2397–2404, 2023

    2023

  18. [26]

    Carla: An open urban driving simulator,

    A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V . Koltun, “Carla: An open urban driving simulator,” inConference on robot learning. PMLR, 2017, pp. 1–16

    2017

  19. [27]

    Practical search techniques in path planning for autonomous driving,

    D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving,”ann arbor, vol. 1001, no. 48105, pp. 18–80, 2008

    2008

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.