QTree-RRT: Improving RRT Through Quadtree-Guided Sampling for Path Planning - Bianor, Jhorlen Souza; Dias, Lucas Matos de Abreu; Drews-Jr, Paulo L. J.; Gamarra, Daniel Fernando Tello; Cukla, Anselmo Rafael; Oliveira, Felipe Gomes de (Anais do Simpósio Brasileiro de Robótica e Simpósio Latino Americano de Robótica (SBR/LARS), 2025)
Path planning plays a crucial role for autonomous vehicles operating in complex environments, where efficient and reliable navigation is of paramount importance. Traditional path planning algorithms, such as the Rapidly-Exploring Random Tree (RRT) and its variants, are widely used but often suffer from inefficient exploration and suboptimal path generation, particularly in cluttered environments. This work introduces QTree-RRT, a hybrid approach designed to improve path planning by guiding the exploration process through a hierarchical spatial decomposition. The method first decomposes the environment using a Quadtree representation, then computes an initial coarse path through the free regions using a graph search algorithm (e.g., Dijkstra or A*). This preliminary path defines the relevant regions in which RRT sampling is then concentrated, leading to a more focused and efficient exploration. Experimental evaluations in simulated environments with varying obstacle densities show that QTree-RRT consistently outperforms classical RRT and its variants RRT* and RRT-Connect. The proposed approach achieves lower execution times (1.6s), reduces the number of required samples (295), and generates paths with better cost (475.39) and quality, demonstrating its effectiveness as a path planning solution for mobile robots.