QTree-RRT: Improving RRT Through Quadtree-Guided Sampling for Path Planning

• Jhorlen Souza Bianor UFAM
• Lucas Matos de Abreu Dias UFAM
• Paulo L. J. Drews-Jr FURG
• Daniel Fernando Tello Gamarra UFSM
• Anselmo Rafael Cukla UFSM
• Felipe Gomes de Oliveira UFAM

Resumo

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.

Palavras-chave: Costs, Navigation, Trees (botanical), Conferences, Education, Focusing, Path planning, Mobile robots, Reliability, Autonomous vehicles, Path Planning, RRT, Quadtree, Autonomous Navigation, Mobile Robotics