Introduction
Finding the shortest path between two points—a geodesic—is a fundamental challenge in robotics, physics, and computer graphics. While conceptually simple in Euclidean space, the problem becomes significantly more complex when navigating high-dimensional manifolds with non-trivial constraints, such as a 7-jointed robotic arm avoiding obstacles or a non-holonomic vehicle that cannot move laterally.
Traditional path planning often relies on Goal-Conditioned Reinforcement Learning (GCRL), which typically generates trajectories sequentially. However, sequential planning suffers from the "long horizon problem," where agents struggle to associate early actions with distant rewards. In this work, the Midpoint Tree (MT) framework is introduced, leveraging recursive sub-goal generation and an actor-critic reinforcement learning approach to "hallucinate" the exact midpoints of a shortest path.
The Midpoint Tree Framework
The core innovation of the MT framework is its recursive approach to trajectory generation. Instead of planning a path as a sequence of small steps ($A \to B \to C \dots$), the model predicts the midpoint $M$ between the start and the goal. It then recursively predicts midpoints between the start and $M$, and between $M$ and the goal.
This recursive structure offers a significant advantage: a path of length $N$ can be generated in $\log(N)$ steps. This logarithmic complexity effectively mitigates the long-horizon problem that plagues sequential RL methods.
Actor-Critic Implementation
To solve the functional equations of a geodesic, the authors employ an Actor-Critic architecture:
- The Critic ($V$): Learns to estimate the distance between any two points on the manifold.
- The Actor ($\pi$): Learns to predict the midpoint between two given states.
A critical challenge in sub-goal generation is ensuring the predicted point is exactly in the middle. While standard methods might minimize $V(start, mid) + V(mid, goal)$, any point on the shortest path satisfies this condition. To force the actor to select the equidistant midpoint, the authors introduce a "sum of squares" loss function: $$V(start, mid)^2 + V(mid, goal)^2$$ Mathematically, this expression is minimized only when the two distances are equal, ensuring the predicted sub-goal is the true midpoint.
Comparison with Existing Methods
The MT framework addresses several limitations of existing Goal-Conditioned RL and Sub-goal Tree (SGT) methods. Unlike GCRL, which requires a fixed step length and faces linear horizon scaling, MT utilizes variable step lengths and scales logarithmically. Furthermore, while previous sub-goal methods often required a global upper bound on distances—which is computationally expensive to verify—MT operates using only local metric information.
Evaluation and Results
The framework was evaluated across five diverse simulated environments, including a 2D disk with asymmetric terrain (Matsumoto metric), a non-holonomic car-like system, and a 7-DoF Franka Panda robotic arm.
Key findings include:
- High-Dimensional Success: In the 7-DoF robotic arm and multi-agent coordination tasks, MT achieved nearly 100% success rates, whereas sequential methods like PPO struggled to exceed 50%.
- Handling Asymmetry: MT successfully learned smooth paths for non-holonomic vehicles, including the "looping" maneuvers required to reach goals located directly behind the starting position.
- Sample Efficiency: By bootstrapping from local metric knowledge (distances between very close points), the model learned global distances more efficiently than sequential baselines.
Conclusion and Future Work
The Midpoint Tree framework provides a theoretically sound and computationally efficient method for generating geodesics on complex manifolds. By transforming the sequential planning problem into a recursive midpoint prediction task, it overcomes the hurdles of long horizons and sparse rewards. Future research may focus on automating the "depth scheduling" of the tree during training and incorporating environment-specific features to create more generalized geodesic generators.
Summary updated