The HJCD-IK algorithm#

HJCD-IK three-phase pipeline — initialization, polishing, collision filter

Fig. 1 The HJCD-IK pipeline: orientation-aware greedy coordinate-descent initialization (PO-CCD), parallel Jacobian-based polishing (PJ-IK), and a parallel collision filter.#

Hybrid Jacobian Coordinate Descent is a three-phase, sampling-based solver that combines cheap per-joint coordinate updates with Jacobian-based refinement and a GPU collision filter:

  1. Coarse search (PO-CCD). From hundreds-to-thousands of random restarts, an orientation-aware greedy coordinate-descent sweep picks the per-joint moves that most reduce position and orientation error. Cheap, fast, and good at escaping poor initializations — it produces a diverse set of coarse seeds.

  2. Levenberg–Marquardt refine (PJ-IK). The best coarse candidates are polished: build the 6×N geometric Jacobian from the world-frame joint transforms (cross-products), form the normal equations (JᵀJ + λ·diag)Δq = Jᵀr, and solve them with a warp Cholesky. A trust region + backtracking line search (with dogleg / single-coordinate fallbacks) adapts λ to sub-millimetre, sub-degree accuracy.

  3. Collision filter. The refined batch is filtered for feasibility (see below).

The end-effector error is computed as a quaternion orientation error plus a Euclidean position error. See arXiv:2510.07514 for the full method and evaluation.

Batched execution & warp-locality#

Each call solves one target, exploring a batch of candidate configurations. Coarse search assigns one candidate per CUDA block; its warps cooperate on coordinate-pair trials. Refinement assigns one candidate per warp, optionally packing several independent candidates into a block (warp_id = threadIdx.x >> 5, lane = threadIdx.x & 31).

  • LM forward kinematics, Jacobian construction, reductions, and the normal-equations solve stay warp-scoped. LM’s SYNC() is a warp barrier even in multi-warp blocks: independent candidates may diverge or finish at different times.

  • Coarse-search state shared across warps uses block barriers. Per-warp scratch reuse also needs warp fences; register shuffles alone do not order shared-memory reads/writes.

  • Larger batches and different GPU scheduling can change the candidate pool. A seeded target sequence does not promise bitwise-identical returned configurations across launches.

When refactoring math onto GRiD/GLASS, keep it warp-scoped: use grid::ee_pose_inner_warp and the glass::warp:: primitives — not block-scoped (glass::), cooperative-groups (glass::cgrps::), or vendor (glass::nvidia::) paths, which lose parallelism or add overhead at these tiny, warp-dispatched sizes.

Collision avoidance#

With collision_free=True, the refined candidates are scored against the environment after optimization (never on the hot solver loop) using GRiD’s URDF-driven grid_collision. The robot is approximated by covering spheres baked into grid.cuh at codegen (--collision); obstacles (spheres / cuboids / cylinders) come from the problem set. hard mode (default) filters colliding candidates with grid_collision::config_free (self and environment), so a request can return fewer solutions than requested, including zero. soft adds a penetration cost for ranking experiments but does not guarantee collision freedom; both combines the two. Select the policy with the Python collision_mode argument; the benchmark also accepts --collision-mode.

Collision geometry is generated from URDF shapes or supplied pre-spherized geometry and bound to the kinematic robot’s frames. Adding a supported robot needs no hand-written collision code — see Custom robot (GRiD codegen workflow). Python rejects collision_free=True when grid.cuh was built without --collision instead of silently running open-world.