Generation of Geodesics with Actor-Critic Reinforcement Learning to Predict Midpoints

Kazumi Kasaura

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.

The recursive process of the Midpoint Tree framework, showing the evolution from a single midpoint to a dense trajectory.

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.

Comparison of the Midpoint Tree (MT) framework against standard GCRL and SGT methods.

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

Abstract

Various tasks in the real world, such as path planning, can be reduced to the generation of geodesics on manifolds. For reinforcement learning to generate geodesics sequentially, we need to define rewards appropriately. To generate geodesics without any adjustment of rewards, we propose to use a modified version of sub-goal trees, called midpoint trees. While sub-goal trees consist of arbitrary intermediate points, midpoint trees consist of midpoints. In addition, we propose an actor-critic method to learn to predict midpoints and theoretically prove that, under mild assumptions, when the learning converges at the limit of infinite tree depth, the resulting policy generates exact midpoints. We show experimentally that our proposed method outperforms existing methods in a certain path planning task.
BibTeX
@misc{kasaura2024generation,
  author = {Kazumi Kasaura},
  title = {{Generation of Geodesics with Actor-Critic Reinforcement Learning to Predict Midpoints}},
  year = {2024},
  eprint = {2407.01991},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.01991},
}
Figure