Quadtree-Based Free-Space Cell-Decomposition for Pathplanning With RRT* Implementation
Noah D. Otte, Sumeet Gajanan Satpute, Avijit Banerjee, George Nikolakopoulos · 2025
This paper introduces a novel, computationally efficient, random-search based path-planning algorithm specifically designed to enhance the dexterous accessibility of autonomous lunar rovers operating on highly cluttered obstacle-dense planetary surfaces. The proposed path-planning framework employs a Quadtree-based cell decomposition to enhance the performance of sampling-based path-planning algorithms, specifically those in the category of Rapidly-exploring Random Trees (RRT) and its optimized variant, RRT*. In the process of generating the path through an occupancy grid map, the obstacle-free cells are utilized as discrete sampling points for the RRT* algorithm. A unique non-uniform sampling approach is employed to favor larger cells with a higher degree of safety, thereby enabling seamless navigation through the obstacle-dense map. Additionally, the non-uniform sampling approach enhances the overall computational efficiency of the framework, making it suitable for fast, lightweight onboard implementation. The efficacy of the proposed planning framework is demonstrated through numerous simulation scenarios.