TL;DR
Finding optimal paths (geodesics) on complex manifolds is central to robot motion planning, but standard sequential reinforcement learning struggles with sparse rewards and long horizons. This paper introduces midpoint trees, a hierarchical divide-and-conquer approach where an actor-critic model recursively predicts the exact metric midpoint between two points. The authors prove that minimizing the sum of squared segment costs converges to true geodesics and demonstrate robust performance on challenging non-holonomic and high-degree-of-freedom robotic planning tasks.
What Problem Does This Paper Address?
Many real-world path-planning tasks—such as navigating sloped terrain or steering a non-holonomic vehicle—can be mathematically formulated as finding geodesics (curves of minimal length) on Riemannian or Finsler manifolds.
In practice, the global distance metric between two distant states is unknown beforehand; we only have access to local, infinitesimal approximations of distance. Using standard goal-conditioned reinforcement learning (RL) to generate paths sequentially (step-by-step) suffers from severe reward sparsity, tricky reward shaping, and optimization instability over long horizons. Previous hierarchical alternatives, such as sub-goal trees, predict arbitrary intermediate waypoints. However, when distances are only accurate locally, picking sub-goals that are not evenly spaced can cause steps to land far apart, breaking the validity of local metric approximations.
Methods
The paper introduces an Actor-Critic Midpoint Learning framework:
- Midpoint Trees: Instead of generating waypoints sequentially or picking arbitrary intermediate states, the model recursively predicts the exact midpoint—the intermediate state equidistant from the start and goal.
-
Sum-of-Squares Objective: To enforce that the sub-goal is an exact midpoint, the actor minimizes: $$\mathcal{L}_{\text{actor}}(\pi, V, s, g) = V(s, \pi(s, g))^2 + V(\pi(s, g), g)^2$$ Because $a^2 + b^2 = \frac{1}{2}(a+b)^2 + \frac{1}{2}(a-b)^2 \ge \frac{1}{2}(a+b)^2$, minimizing the sum of squared distances strictly penalizes imbalance ($a \neq b$), guaranteeing that the predicted point bisects the path length.
-
Actor-Critic Setup:
- Critic ($V_\phi$): Predicts geodesic distances between pairs of states, trained via Monte Carlo returns from paths generated by the actor.
- Actor ($\pi_\theta$): Outputs a Gaussian distribution over the coordinate space using the reparameterization trick to predict midpoints.
- Theoretical Guarantee: The authors formally prove that on compact, weakly symmetric pseudo-quasi-metric spaces, if the learning converges at the limit of infinite recursion depth, the critic converges to the true distance function $d$, and the actor generates exact midpoints.
Datasets
The framework is evaluated across three simulated benchmark environments:
- Matsumoto Metric: An asymmetric Finsler surface modeling travel time across a 2D unit disk with a mountain at the center.
- Unidirectional Car-Like Constraints: A 3D configuration space ($x, y, \theta$) modeling forward-only car navigation with curvature constraints (penalizing lateral slip and sharp turns).
- 7-DoF Robotic Arm: Motion planning for a 7-degree-of-freedom Franka Panda robotic arm navigating around a columnar obstacle, where configuration space geometry is warped based on workspace obstacle proximity.
Key Insights and Ideas
- Why Midpoints Matter: When path cost can only be approximated between nearby points, uniform recursive bisection ensures all adjacent pairs across the tree shrink at identical rates, preventing waypoints from clustering irregularly near the endpoints.
- The Pitfall of Linear Sums: Optimizing $\min_z [V(s, z) + V(z, g)]$ allows degenerate or biased intermediate points (e.g., $z = s$), preventing convergence to the true distance function. The squared formulation eliminates this degeneracy.
- Inherent Parallelism: Recursive midpoint trees divide a horizon of length $2^D$ into independent sub-problems of depth $D$, offering natural parallelization compared to sequential generation.
Key Results
- Matsumoto Metric: Both the proposed method (Ours) and sequential RL achieved ~75% success rates, but Ours showed significantly smaller variance across random seeds and produced smooth, uniformly spaced waypoints matching the ground-truth geodesic. Policy gradient without a critic (PG) failed completely (~0%).
- Car-Like Constraints: Ours and an intermediate-point variant reached ~40% success and continued to improve, while sequential RL and PG remained near 0%.
- 7-DoF Robotic Arm: Ours and its variants exceeded an 80% success rate within $2 \times 10^7$ environment steps. In contrast, PG plateaued around ~20%, and sequential PPO failed entirely (0%).
Limitations and Future Work
- Environment Specificity: The policy currently needs to be trained from scratch for each specific manifold/environment. Incorporating environment geometry or obstacle representations as inputs is an open next step.
- Theoretical Assumptions: The proof relies on a continuous midpoint property across the space, which may only hold locally in environments with discrete obstacles (e.g., choosing to pass left vs. right around an obstacle creates a discontinuity).
- Collision Checking Detail: In the 7-DoF arm task, collisions occasionally occurred because the cost metric only evaluated distance from robot joints rather than the full volumetric links between joints.
- Algorithmic Extensions: The current algorithm is on-policy; incorporating off-policy RL and dedicated quasi-metric learning architectures could further improve sample efficiency.
Summary updated