💻 computer science

RIT*: Riemannian Informed Trees for Cost-Adaptive Optimal Motion Planning

The paper presents RIT*, a motion planning framework that replaces Euclidean primitives with Riemannian counterparts and introduces a collision-adaptive metric refinement to achieve significantly lower-cost solutions in high-dimensional, spatially varying environments compared to existing baselines like BIT*.

Original authors: Muhayy Ud Din, Ahmed Nadar, Jan Rosell, Irfan Hussain

Published 2026-08-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhayy Ud Din, Ahmed Nadar, Jan Rosell, Irfan Hussain

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guide a robot through a maze. In the world of robotics, this is called "motion planning." For a long time, the smartest way to do this was to treat the robot's movement like a game of checkers on a flat board: every step forward, backward, or sideways costs the same amount of energy, and the shortest path is just a straight line. This works great in simple, empty rooms. But real life isn't a flat board. Think of a robot arm with many joints: twisting a heavy wrist might be easy, but lifting a heavy shoulder might be exhausting. Or imagine a robot trying to squeeze past a wall; getting too close is dangerous, so the "cost" of being near the wall should be high.

The problem is that most robot brains still use that old "flat board" math. They don't realize that some directions are harder than others, or that some areas are more dangerous. This paper introduces a new way of thinking called RIT* (Riemannian Informed Trees). Instead of assuming the world is flat and uniform, RIT* understands that the world is "curved" and "stretchy" depending on where you are and which way you are moving. It's like switching from a map that treats a mountain and a valley as the same distance, to a map that knows climbing a hill takes much more effort than walking across a field. By using this smarter math, the robot can find paths that are not just short, but actually the easiest and safest to travel.

The Problem: The "Flat Map" Mistake

For years, the best robot planners have used a trick called "informed sampling." Once a robot finds any way to get from point A to point B, it stops looking at the whole world and only looks inside a specific "search bubble" around that path. This makes finding a better path much faster.

However, these planners draw their search bubbles using standard, flat geometry (Euclidean distance). They assume that moving one meter to the left costs the same as moving one meter up. But in the real world, especially for complex robots with many moving parts, this is wrong.

The Anisotropy Problem: Imagine a robot arm. Moving a light, fast wrist joint is cheap. Moving a heavy, slow shoulder joint is expensive. A flat map treats them as equal.
The Obstacle Problem: If a robot bumps into a wall, it learns that area is bad. But standard planners don't automatically learn how bad it is or how to avoid it in future attempts without being explicitly programmed with a map of every obstacle beforehand.

The authors of this paper argue that relying on these flat, pre-set rules makes robots inefficient, especially in high-dimensional spaces (robots with many joints) or environments where the "cost" of moving changes depending on location.

The Solution: RIT* and the "Stretchy" Map

The paper presents RIT*, a new planning framework that replaces the flat math with Riemannian geometry. If you imagine the robot's world as a rubber sheet, Riemannian geometry allows that sheet to stretch and shrink.

Stretching the Map: In areas where movement is hard (like lifting a heavy arm), the map stretches out, making those areas look "farther" and more expensive. In easy areas, the map shrinks.
The New Search Bubble: Instead of drawing a perfect circle or oval for its search bubble, RIT* draws a shape that fits the "stretchy" map. It focuses its search only on the paths that actually look cheap on this new, curved map.
Smart Connections: When the robot considers connecting two points, it doesn't just check the straight line. It uses a "cascading" filter. It does a quick, rough check first. If the path looks expensive, it throws it away immediately. Only the promising paths get a full, detailed calculation. This saves a massive amount of computer time.

The Secret Weapon: CARM (Learning from Bumps)

The most exciting part of the paper is a feature called CARM (Collision-Adaptive Metric Refinement).

Usually, to make a robot avoid obstacles, engineers have to manually design a "cost field" (a map that says "stay away from here"). But what if the robot doesn't know the map yet?

The Learning Process: CARM lets the robot learn the map while it plans. Every time the robot tries a path and hits a wall (a collision), CARM takes note. It says, "Okay, that spot is dangerous."
The Feedback Loop: It uses these "bumps" to create a heat map of danger. It then inflates the cost of moving near those spots. The next time the robot plans, it naturally steers away from the places where it previously crashed.
No Prior Knowledge Needed: The robot doesn't need a perfect map of the room to start. It can start with a blank slate (or a basic idea of how its joints move) and learn the obstacles as it goes.

What the Experiments Showed

The researchers tested RIT* in a variety of simulated worlds, from simple 2-D mazes to complex 14-dimensional robot arms (like a two-armed robot).

In Simple Worlds: When the environment was uniform (no tricky costs), RIT* performed just as well as the best existing methods. It didn't break anything; it just matched the competition.
In Complex Worlds: This is where RIT* shined.
- In a 3-D environment with tricky, direction-dependent costs, RIT* found solutions that were 13.0% cheaper (more efficient) than the previous best method (BIT*).
- In a 6-D robot arm task, it improved the final path cost by 9.0%.
- In the hardest test, a 14-D two-armed robot, the improvement was massive: RIT* found paths that were 24.8% to 63.5% better than the other methods. In these high-dimensional cases, the old "flat map" methods actually got stuck or found terrible paths, while RIT* kept improving.
Real Robot Test: They even ran the algorithm on a real UR10e robot arm. The robot successfully planned and executed smooth, collision-free motions, proving the math works in the real world, not just in simulations.

The Bottom Line

The paper proves that by treating the robot's world as a flexible, curved landscape rather than a rigid, flat grid, we can find much better paths. RIT* doesn't just find a path; it finds the smartest path by understanding that some moves are harder than others and by learning from its own mistakes (collisions) to avoid danger.

While the method requires more computer power to do the complex math, the results show that for complex robots in tricky environments, this extra effort pays off with significantly better, safer, and more efficient movements. The authors suggest that as robots get more complex and enter more unpredictable environments, this kind of "curved map" thinking will become essential.

Technical Summary: RIT: Riemannian Informed Trees for Cost-Adaptive Optimal Motion Planning*

Problem Statement
Sampling-based motion planning algorithms, particularly those that are asymptotically optimal (AO) such as RRT* and BIT*, traditionally rely on Euclidean distance metrics to define informed sets, nearest-neighbor searches, and edge costs. While effective in isotropic environments, these Euclidean primitives fail to reflect the true cost structure in anisotropic environments where traversal costs vary by direction and location (e.g., due to joint-space inertia or obstacle proximity). Furthermore, existing planners typically depend on predetermined cost structures, lacking the ability to learn cost fields online from planning experience, which limits their effectiveness in unknown or complex environments.

Methodology
The authors propose RIT* (Riemannian Informed Trees), a planning framework that replaces Euclidean primitives in batch-informed search with Riemannian counterparts. The core methodology involves:

Riemannian Formulation: The configuration space is equipped with a smooth, positive-definite metric tensor field $G(x)$ . The cost of a path is defined as its Riemannian arc length.
- Riemannian Informed Set: Instead of a prolate hyperspheroid defined by Euclidean distance, RIT* constructs a tighter, cost-consistent informed set ( $I_R$ ) based on Riemannian geodesic distances.
- Anisotropic Nearest-Neighbor Search: The connection radius is defined by a Riemannian ball, which expands along low-cost directions and contracts along high-cost ones, aligning the search with the underlying cost structure.
- Cascading Edge Evaluation: To handle the computational cost of numerical integration required for Riemannian edge costs, RIT* employs a three-level cascade (Midpoint check, Simpson's rule, and full Gauss-Legendre quadrature). This filters out unpromising edges early, reserving expensive full-precision evaluations and collision checks for a small fraction of candidates.
Collision-Adaptive Metric Refinement (CARM): To address the lack of prior knowledge in practical settings, RIT* introduces CARM. This component learns an obstacle-proximity cost field online from collision feedback.
- CARM collects collision points from failed edge checks and generates a density field using Gaussian Kernel Density Estimation (KDE).
- This density field is applied as a conformal scaling factor to a base metric (which defaults to the identity matrix if no prior metric is known).
- The refined metric is updated periodically, tightening the informed set and guiding the planner away from obstacles without requiring prior obstacle geometry.
Theoretical Guarantees: The paper establishes that RIT* preserves the probabilistic completeness and asymptotic optimality of BIT*. Theoretical analysis confirms that the Riemannian informed set and connection radii satisfy the necessary conditions for convergence, even with the online metric updates provided by CARM.

Key Contributions

Riemannian Informed Planning: RIT* is the first to integrate Riemannian geometry into the global informed sampling pipeline of a batch-informed planner. It replaces the informed set, nearest-neighbor search, and edge cost evaluation with Riemannian equivalents, focusing sampling on relevant regions and improving efficiency in anisotropic spaces.
Online Metric Learning (CARM): The introduction of CARM allows the planner to learn a collision-induced cost field online. It requires no prior obstacle knowledge, adapting the metric based solely on collision feedback to refine the cost landscape.
Experimental Validation: The framework is validated across a comprehensive suite of benchmarks ranging from 2-D to 14-D configuration spaces, including real-world UR10e robot execution.

Experimental Results
Experiments were conducted in 2-D, 3-D, 6-D (UR10 manipulation), and 14-D (Tiago bimanual) environments against five asymptotically optimal baselines (Informed RRT*, BIT*, AIT*, EIT*, APT*).

Low-Dimensional Isotropic (2-D): RIT* performs competitively, achieving results comparable to Euclidean baselines, as the Riemannian and Euclidean informed sets converge under isotropic metrics.
Low-Dimensional Anisotropic (3-D): In a 3-D environment with a diagonal anisotropic metric, RIT* produced solutions with 13.0% lower median initial cost and 9.0% lower median final cost compared to BIT*.
High-Dimensional (6-D and 14-D): The performance gains scale significantly with dimensionality and anisotropy.
- In the 6-D UR10 task, RIT* achieved a 9.0% improvement in median final cost over BIT*.
- In the 14-D bimanual task, RIT* outperformed Euclidean-informed baselines by 24.8% to 63.5% in median final cost.
CARM Effectiveness: In low-dimensional settings where the base metric was the identity matrix, CARM learned the obstacle-proximity cost field from collisions alone, resulting in path costs within 1.0% of the oracle (ground-truth) metric.
Real-Robot Execution: Trajectories planned by RIT* were successfully executed on a UR10e robot, demonstrating smooth, collision-free motions that transferred from simulation to hardware.

Significance and Claims
The paper claims that RIT* addresses the fundamental limitation of Euclidean-based planners in anisotropic environments by aligning the search structure with the true cost geometry. The significance of the work lies in its ability to produce substantially lower-cost solutions in high-dimensional, anisotropic configuration spaces where Euclidean-informed baselines degrade.

The authors emphasize that while RIT* incurs a computational overhead due to metric evaluations and a smaller connection radius (which can delay the first solution in very high dimensions), this is offset by the superior quality of the final solution. The framework demonstrates that replacing Euclidean primitives with Riemannian ones, combined with online metric learning via CARM, enables robust, cost-adaptive planning without requiring prior environmental knowledge. The gains are shown to scale with both the degree of anisotropy and the dimensionality of the problem.

The Problem: The "Flat Map" Mistake

The Solution: RIT* and the "Stretchy" Map

The Secret Weapon: CARM (Learning from Bumps)

What the Experiments Showed

The Bottom Line

More like this