Zonal RL-RRT: Integrated RL-RRT Path Planning with Collision Probability and Zone Connectivity

AmirMohammad Tahmasbi, MohammadSaleh Faghfoorian, Saeed Khodaygan, Aniket BeraarXiv 2024 · DOI · arXiv

Abstract

Path planning in complex, high-dimensional spaces remains a significant challenge for autonomous systems. Traditional sampling-based algorithms like Rapidly-exploring Random Trees (RRT) often suffer from high computational costs in cluttered environments. This paper presents Zonal RL-RRT, a hybrid hierarchical approach that integrates spatial partitioning, Reinforcement Learning (RL), and local RRT planning. By dividing the environment into adaptive zones and using Q-learning to navigate the global structure, Zonal RL-RRT achieves significant speedups and improved success rates compared to standard methods.

Introduction

Navigating through dense environments—such as a drone traversing a forest or a robotic arm moving through a crowded workspace—requires balancing global strategy with local obstacle avoidance. Standard RRT-based planners explore the space blindly, leading to inefficiencies. Zonal RL-RRT addresses this by introducing a "divide and conquer" strategy that understands the global structure of an environment before committing to local paths.

Methodology: A Three-Tiered Approach

The Zonal RL-RRT framework operates through three distinct stages to optimize path discovery:

The three-stage Zonal RL-RRT pipeline: zone partitioning, RL-based subgoal selection, and local RRT planning.
  1. Spatial Partitioning via kd-trees: The environment is recursively divided into "zones" using a kd-tree. Unlike uniform grids, this partitioning is adaptive: zones are smaller in high-density areas and larger in open spaces, effectively mapping the environment's complexity.
  2. High-Level Strategy with Q-Learning: The algorithm treats these zones as states in an RL framework. A Q-learning agent identifies the optimal sequence of zones to reach the goal. The reward function considers distance to the goal ($R_d$), collision probability ($R_\rho$), and zone connectivity, ensuring the selected path is both efficient and traversable.
  3. Low-Level Local Planning: Once the high-level "highway" of zones is established, standard RRT is employed as a local planner to find the final collision-free trajectory within the selected zones.

Experimental Evaluation

The authors evaluated Zonal RL-RRT across three distinct types of environments to test its versatility:

  • 2D Forest Maps: Grids populated with up to 1,000 circular obstacles.
  • 3D Environments: Spaces with randomly distributed box-shaped obstacles.
  • 6D Robotic Simulation: A UR10e robotic arm manipulator simulated in the MuJoCo physics environment, testing the algorithm's ability to handle high-dimensional configuration spaces.

Key Results and Insights

Zonal RL-RRT demonstrated superior performance across all metrics, particularly in high-density environments.

Comparative performance of ZRL-RRT against state-of-the-art planners across three different map configurations.
  • Computational Efficiency: In 2D maps with 1,000 obstacles, the algorithm was 3x faster than basic RRT and significantly outperformed BIT and Informed RRT. In 3D environments, it showed a 38% average improvement in runtime.
  • Robustness: The system maintained a success rate of 98-100%, even in complex scenarios where other planners' success rates dropped to 85%.
  • Strategic Flexibility: By adjusting reward weights, the robot's behavior can be tuned from "greedy" (shortest path) to "conservative" (safest path), allowing for mission-specific optimization.

Conclusion and Future Work

Zonal RL-RRT offers a scalable solution for complex path planning by combining global spatial reasoning with local efficiency. Unlike many deep-learning planners, it generalizes to new maps without extensive re-training. Future research will focus on adapting the framework for dynamic obstacle handling and multi-agent coordination in shared spaces.

Summary updated

BibTeX
@misc{tahmasbi2024zonal,
  author = {AmirMohammad Tahmasbi and MohammadSaleh Faghfoorian and Saeed Khodaygan and Aniket Bera},
  title = {{Zonal RL-RRT: Integrated RL-RRT Path Planning with Collision Probability and Zone Connectivity}},
  year = {2024},
  eprint = {2410.24205},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.24205},
}
Figure