KIN · Robotics & Autonomy — Mathematical IP
Kinematics Core — 3D Differentiable ORCA IP
A C++20 source library that resolves, once per tick, a collision-avoiding velocity for every agent of a three-dimensional cohort using Optimal Reciprocal Collision Avoidance, with three extensions: analytic Jacobians, hierarchical time horizons, and the two combined.
Overview
The asset implements the standard two-case ORCA algorithm from the published description (no third-party ORCA code is used or derived from) and adds three extensions: a differentiable mode returning closed-form analytic Jacobians of each resolved velocity with respect to every input of the agent and its neighbours; hierarchical multi-horizon planning, where each neighbour pair chooses its time horizon from its closing speed inside the half-space kernel, so there is still exactly one linear programme per agent per tick; and a combined differentiable-hierarchical mode whose Jacobians include the horizon selector's derivative.
Without derivatives, a pipeline that differentiates through ORCA has to fall back on finite differences, with their noise floor and extra solves. Here a Jacobian costs one small KKT solve per agent, step() performs no heap allocation, and the solver in the production planner is the same code that returns the gradients at training time.
Verification on the delivered code: 12,016 of 12,016 feasible linear programmes and 2,500 of 2,500 infeasible (minimax) cases agree with a separately written long-double reference solver; analytic Jacobians agree with finite differences at 640 of 640 random configurations; 17 of 17 test targets pass on GCC and Clang (18 of 18 with the Python binding), and 17 of 17 under ASan+UBSan and TSan; 1.37 million fuzz executions found no crash. The code is written to MISRA C++:2023 guidance, not certified.
The problem
Differentiable robotics pipelines need gradients through the collision-avoidance layer. The widely used ORCA implementations, such as RVO2-3D, provide no derivatives, so teams wrap them in finite differences — adding a numerical noise floor to training, multiplying the solves per tick, and letting the training-time model drift from the production planner.
What it does
- Standard two-case ORCA velocity-obstacle resolution in three dimensions, with an infeasible-LP (minimax) fallback.
- Differentiable mode with closed-form analytic Jacobians; degenerate points (constraint kinks) are detected and flagged.
- Hierarchical multi-horizon planning inside the half-space kernel: still one LP per agent per tick, with no measurable extra cost.
- Combined differentiable-hierarchical mode, with gradients chaining through the per-pair horizon selector (documented convention at its two kinks).
- AVX2 kernels with a scalar fallback and runtime CPUID/XGETBV dispatch, bit-identical to scalar; an AVX-512F path is compiled but has never been executed, so it is opt-in and not auto-selected.
- Exact K-nearest-neighbour search on a uniform grid and an OpenMP driver, with results bit-identical for any thread count.
- C++20 API, a C99 ABI (opaque handle, status codes, single header), and an optional zero-copy pybind11/NumPy module; a numerical-analysis document is included.
- Defensive interface: a step() that overlaps another on the same solver returns Busy (lock-free guard), and output buffers that alias inputs are rejected.
Performance
Measured 2026-10-09| Metric | Figure | Basis |
|---|---|---|
| Tick latency at 1,024 agents (AVX2, grid, 4 threads) | 685 µs median with no avoidance active (counterflow); 1,083 µs with about 960 agents deflected per tick (swap) | Measured by Vlaander |
| Speed-up over single-thread scalar brute force | 4.98× (counterflow); 6.56× (swap) | Measured by Vlaander |
| Versus RVO2-3D on the same machine | 1.2–3.7× faster across both scenarios at 1 and 4 threads (2.2–3.7× in two quiet-window runs from the delivered archive; 1.2–2.2× in the run recorded in the source's docs/bench-2026-10-08.txt); per-agent velocities within 0.0009 m/s, 0 agents over 1 cm/s | Measured by Vlaander |
| LP oracle agreement | 18,000 generated cases: all 12,016 feasible ones agree with a separately written long-double reference solver (worst error 8e-8) and all 5,984 infeasible ones are detected; 2,500/2,500 minimax fallbacks optimal | Measured by Vlaander |
| Jacobian vs finite differences | 640/640 random configurations agree (320 single-horizon, 320 hierarchical); every mismatch at constructed boundary points is a genuine kink and is flagged | Measured by Vlaander |
| Test and sanitizer gate | 17/17 on GCC 14.3 and Clang 16 (Release; GCC also Debug), warnings as errors; 18/18 with the Python binding; 17/17 under ASan+UBSan and TSan (GCC 14.3 and Clang 16) | Measured by Vlaander |
| Fuzzing | 1,374,779 executions on the delivered code (two harnesses, 5 minutes each, ASan+UBSan), 0 crashes | Measured by Vlaander |
- Date
- 2026-10-09
- Hardware
- AMD EPYC 7763, GitHub Codespace (shared Azure VM), 4 vCPU (2 cores), 15 GiB
- Toolchain
- GCC 14.3, -O3, CMake Release, library flags as shipped (-ffp-contract=off; AVX2 unit -mavx2 -mno-fma), OpenMP (libgomp), Debian 12 container; tests also built with Clang 16
- Source archive SHA-256
- 0b89c03cdf51ca0d15c6c57457fc34e306c9270a0a3b86f216cbe969e9452d60
- Method
- Built from the delivered source archive. kin-bench: 1,024 agents, 300 timed ticks after 30 warm-up ticks, steady_clock around each step(), median reported. Two scenarios: counterflow, interleaved lanes that never conflict, so no agent is deflected and it measures the fixed per-tick cost (neighbour search, half-space construction, LP check); and swap, every agent crossing the centre to its mirror position, so about 960 of 1,024 agents are deflected and the minimax fallback runs about 400 times per tick. kin-vs-rvo2: RVO2-3D fetched at a pinned commit and compiled with the same compiler, -O3 and OpenMP; KIN step plus position update timed against RVO2-3D's doStep(); agreement checked by feeding identical float-rounded state into both at seven ticks.
- The catalogue's figures (257 µs per tick and 17.6× over single-thread scalar) predate this build and were not reproduced; they came from the counterflow scenario only, in which no agent is ever deflected. The engine Vlaander delivers is the one measured here.
- The VM was shared (1-minute load average 0.6–2.7 during these runs) and has 2 physical cores, on which 4 threads scale about 2.6× over 1; a machine with more physical cores has not been measured.
- Differentiable mode costs 1.7× (counterflow) to 3.3× (swap) the plain solve.
- In the swap run KIN ended with about 7% more overlapping agent pairs than RVO2-3D (120,188 vs 112,404 summed over 300 ticks; deepest 0.102 m vs 0.106 m). Both are ORCA in a fully jammed centre at dt 0.1 s; the trajectories diverge only by round-off, and neither library is safer.
- The RVO2-3D ratio spans 1.2–3.7× because RVO2-3D's own timing varied between runs from identical builds (single-thread counterflow 3,125 µs in the run recorded in docs/bench-2026-10-08.txt, about 5,000 µs in the 2026-10-09 runs), while KIN's times agreed within about 10%; the cause was not established, so treat the ratio as indicative.
- RVO2-3D computes in single precision and KIN in double; the residual velocity differences are float round-off.
- The AVX-512 path was not measured: this CPU has no AVX-512.
Value in your own metrics
- Gradient accuracy in training
- Closed-form analytic Jacobians in place of finite-difference wrappers; they agree with central differences at 640 of 640 random configurations, and non-differentiable points are flagged rather than hidden.
- Production / training code reuse
- One solver: the production planner and the differentiable training-time primitive are the same implementation, switched by a configuration flag.
- Tick latency
- 685–1,083 µs per tick at 1,024 agents (AVX2, grid, 4 threads) and 4.98–6.56× over single-thread scalar, measured by Vlaander on the hardware above; 1.2–3.7× faster than RVO2-3D on the same machine; the spread comes from RVO2-3D's own timing varying between runs, not from KIN.
- Correctness assurance
- 12,016/12,016 feasible and 2,500/2,500 infeasible LP cases agree with a separately written long-double reference solver; 1.37 million fuzz executions on the delivered code, zero crashes.
- Framework integration
- A C++ API, a C ABI that binds from any C-FFI language, and an optional zero-copy pybind11/NumPy module that returns the Jacobians as arrays. There is no PyTorch or JAX operator; wrapping one is the acquirer's work.
Assurance and build
- Language
- C++20; core and public surface written to MISRA C++:2023 guidance, not certified (no MISRA checker has been run; deviations listed in MISRA.md)
- Build
- CMake · Conan recipe · GitHub Actions workflow provided, not yet run on GitHub
- Warnings
- 0 warnings with the strict -Werror set on GCC 14.3 and Clang 16, Release and Debug (checked by Vlaander)
- SIMD dispatch
- AVX2 · scalar fallback · runtime CPUID/XGETBV · AVX-512F compiled, opt-in, never executed
- Sanitizers
- 17/17 test targets passing under ASan+UBSan (GCC 14.3 and Clang 16) and under TSan (Clang 16; GCC 14.3 with LLVM libomp), no reports
- Fuzzing
- libFuzzer + ASan+UBSan, 2 harnesses (solver, C ABI) seeded from fuzz/corpus: 1,374,779 executions on the delivered code in two 5-minute runs, zero crashes
- Oracle agreement
- 12,016/12,016 feasible and 2,500/2,500 minimax cases against a separately written long-double reference solver — passing
- Tests
- 16 property/unit sections, a C99 ABI program and a Python binding test: 18/18 passing
- Determinism
- Bit-identical outputs across thread counts, grid vs brute force, and scalar vs AVX2 (memcmp-tested); AVX-512 untested
- Source archive SHA-256
- 0b89c03cdf51ca0d15c6c57457fc34e306c9270a0a3b86f216cbe969e9452d60
- Dependencies
- No third-party code in the core; toolchain C++ standard library, libm and (optionally) OpenMP. Optional Python module: pybind11 (BSD-3-Clause) and NumPy
Releases are not yet cryptographically signed, and no release manifests or external audit summaries are published. Check the source tarball you receive against its SHA-256 in Schedule 1 of your Sale and Assignment Agreement, which you see before you sign.
Scope and maturity
What is real today, what is deliberately excluded, and what is pending — published unprompted.
Included today
- The two-case ORCA solver with three extensions: differentiable mode, hierarchical multi-horizon planning, and the combined differentiable-hierarchical mode.
- AVX2 kernels with scalar fallback and runtime dispatch, an exact uniform-grid K-nearest-neighbour search, and an OpenMP driver, all bit-identical to the scalar single-thread result.
- The verification surface: 16 test sections plus C ABI and Python tests, a separately written long-double reference LP solver, two fuzz harnesses with seed corpora, and sanitizer builds.
- A C99 ABI, an optional zero-copy pybind11/NumPy module, the kin-bench and RVO2-3D head-to-head harnesses, and a numerical-analysis document.
Explicitly scoped out
- Three-dimensional ORCA velocity-obstacle resolution — not a full motion-planning stack. No global planner, perception, vehicle dynamics beyond a speed limit, or position integration; the caller supplies preferred velocities and integrates positions.
- Jacobians are exact on each smooth piece; at constraint-boundary kinks the derivative is not unique, so the solver flags the point and returns the Jacobian of an adjacent smooth piece or a documented convention.
- A Solver is not re-entrant: use one per thread or serialise calls (an overlapping call returns Busy).
- No PyTorch or JAX operator; the Python module is NumPy only.
Pending
- The AVX-512F path is compiled and reviewed but has never been executed; it stays opt-in until kin_tests simd_bit_identity passes on AVX-512 hardware.
- The GitHub Actions workflow mirrors the commands run locally but has not been run on GitHub.
Who it's for
- Autonomous mobile robot and warehouse-fleet companies operating dense multi-agent cohorts.
- Drone and UAS swarm operators requiring true three-dimensional reciprocal avoidance.
- Robotics research and RL platform groups building differentiable control stacks.
- Simulation and digital-twin vendors requiring a single kernel across training and deployment.
- Defence autonomy programmes that want MISRA C++ guidance followed; certified conformance would need the buyer's own checker run.
Before you buy
- No patents or patent applications come with this asset; value it as source code and know-how only.
- Test the differentiable mode inside your training loop, including how your pipeline treats Jacobians flagged as degenerate at constraint kinks.
- The source ships with build/kin-bench and scripts/bench_rvo2.sh, so after delivery you can rerun the latency figures at your own agent count and density in a few minutes; the figures above hold for the machine above only.
- If you deploy on AVX-512 hardware, run kin_tests simd_bit_identity there before enabling the AVX-512 path.
- Confirm the absence of a global planner, perception layer and dynamics integration against your stack — this is mathematical IP, not an autonomy platform.
What transfers
- The asset's sourceSubject to the Sale and Assignment Agreement, Vlaander assigns to the verified Buyer the transferable right, title and interest that Vlaander owns in the specified Asset. The assignment excludes Third Party Materials, open-source components, Vlaander’s pre-existing tools, generic know-how, development methods, trademarks, confidential information and any rights that cannot lawfully be assigned.
- Its testsThe test suite the published assurance claims rest on, as delivered in the source archive.
- Its audit artefactsSpecifications, model-checking output, reviews and the software bill of materials, where the asset has them.
- Not includedThird-party and open-source materials are not sold or assigned by Vlaander. They remain under their own licences, listed in each asset’s software bill of materials (SBOM.md in the archive), and the Buyer is responsible for complying with those licences.
First described in: VLA-GEN catalogue, 3 August 2026, §3.7. Revised by Vlaander against the delivered source; every figure is labelled with its basis.
From test to source
- 01
Check
Read the engine's page: what Vlaander measured and on which hardware, what it has not measured, and the open review findings. Nothing runs before purchase.
- 02
Buy
Verified businesses only. Place the order, give your company's details, have your authorised signatory sign the Sale and Assignment Agreement, then pay the invoice in naira by bank transfer, or in USDC on Polygon. Once the payment is verified, your account shows Paid.
- 03
Receive
We confirm the funds and release the source tarball to you. Delivering, then Download ready. Check it against the SHA-256 in Schedule 1, then rerun the tests and benchmarks yourself.