borglab / borglab/GTDynamics

Share an immutable compiled kinematic traversal across forward kinematics and obstacle queries

Open
#435 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
65
Forks
15
Avg merge
8d 8h
Merged PRs (30d)
2

Description

## Context

PR #433 adds obstacle-aware planning through `RobotQueryPoints`, which maps a selected joint configuration to world-frame query points and, when requested, their analytic Jacobians. This is evaluated repeatedly by the obstacle factors, so the implementation precomputes the robot topology/traversal once and replays a compact traversal in the optimizer's hot loop.

GTDynamics already has a general robot-tree traversal in `Robot::forwardKinematics()`. The simulator's forward-dynamics path calls that routine before solving for accelerations. However, the existing routine has a different interface and purpose: it operates on `gtsam::Values`, computes poses and twists for the reachable links, rebuilds a breadth-first traversal per call, and does not directly produce the query-point Jacobians required by the obstacle factors.

Consequently, #433 contains a second implementation of robot-tree traversal. Calling forward dynamics from obstacle evaluation would be incorrect and unnecessarily expensive; calling the current general forward-kinematics routine would still leave the Jacobian propagation problem and would likely add overhead in the optimization loop. Nevertheless, maintaining two independent implementations of the topology and joint-propagation rules creates a long-term risk of behavioral drift.

> **Timing:** This issue is intentionally a follow-up to #433. It is relevant only after #433 has been merged, and should not block or expand that PR.

## Proposal

Introduce an immutable, precompiled kinematic traversal abstraction that can be constructed once from a `Robot` and reused by clients that need to propagate state through the robot tree.

The shared layer should own only the common structural information and traversal rules, for example:

- validated root and parent/child relationships;
- deterministic traversal order;
- references or indices for links and joints;
- the mapping needed to propagate a child pose from its parent and joint value;
- optional filtering to a selected set of joints, links, or descendant subtrees.

Clients would remain responsible for choosing which quantities they compute:

- `Robot::forwardKinematics()` can use the traversal to produce its existing poses and twists in `gtsam::Values`;
- `RobotQueryPoints` can use it to compute only the required link poses, query-point positions, and analytic Jacobians;
- dynamics code can continue to use the general forward-kinematics API and its subsequent acceleration solve.

This should be a reusable kinematics primitive, not an attempt to route collision checking through forward dynamics.

## Performance requirements

The refactor must preserve the reason `RobotQueryPoints` has a specialized implementation:

- no topology search or BFS construction during factor evaluation;
- no `gtsam::Values` assembly in the obstacle-factor hot path;
- no pose/twist/dynamics quantities computed unless requested;
- no additional heap allocation proportional to the robot size per evaluation, where practical;
- analytic query-point Jacobians remain available;
- the compiled traversal is immutable after construction and safe for concurrent read-only evaluation.

A benchmark should compare the implementation from #433 with the shared-traversal version for representative robot sizes, numbers of query points, and Jacobian-on/Jacobian-off evaluations. The goal should be no meaningful regression in obstacle-factor evaluation time.

## Suggested implementation sequence

1. Add tests that compare the existing `Robot::forwardKinematics()` and `RobotQueryPoints` pose results for the same configurations.
2. Extract the immutable traversal description without changing public behavior.
3. Migrate `RobotQueryPoints` to the shared representation while retaining its specialized evaluation buffers and outputs.
4. Migrate `Robot::forwardKinematics()` to the same traversal if doing so keeps its API and behavior clear.
5. Add equivalence, branched-tree, fixed-link, selected-joint, Jacobian, concurrency, and performance tests.

## Acceptance criteria

- There is one canonical implementation of robot-tree topology and traversal ordering.
- Existing forward-kinematics and obstacle-factor APIs retain their behavior.
- Query-point Jacobians pass numerical derivative checks.
- Branched robots, fixed links, nontrivial roots, and selected joint subsets are covered.
- A single compiled traversal can be evaluated concurrently without mutation or shared scratch state.
- Benchmarks demonstrate that the obstacle-query hot path remains approximately as fast as the implementation introduced by #433.

Contributor guide

No contributing guide indexed for this repository

Research direction

Begin after PR #433 is merged by reading Robot::forwardKinematics() and the RobotQueryPoints implementation, then run the existing pose and Jacobian tests for matching configurations. Extract one immutable traversal while preserving both APIs and specialized obstacle evaluation. Add equivalence, branched-tree, fixed-link, selected-joint, concurrency, derivative, and performance coverage; done means acceptance criteria pass without hot-path regression.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
robotics
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.