Uma extensão do algoritmo RRT para a representação compacta do espaço de configurações em alta dimensionalidade

Abstract

Path planning in high-dimensional spaces is one of the main challenges in modern robotics, due to the complexity of the con guration space (Cspace) and the high computational cost associated with its exploration. Sampling-based probabilistic methods, such as the Rapidly-exploring Random Tree (RRT), stand out for their ability to handle these scenarios. However, when employed with the objective of extensively exploring the space, they tend to exhibit a loss of e ciency due to the excessive generation of redundant nodes, which entails higher computational and storage costs. Unlike the classical RRT approach, essentially focused on nding paths between speci c con gurations, this work investigates the use of the algorithm as a tool to build a compact representation of the free con guration space, focusing on maximizing coverage and computational e ciency. In this context, this dissertation proposes an extension of the RRT-Edge algorithm through an n-dimensional continuous polarization mechanism strictly independent of discretization. The approach introduces a strategy based on the analytical de nition of an exploration region around nodes and edges, coupled with a polarized sampling process guided by an exponential distribution. It guides sample generation toward promising regions of the space, reducing the incidence of redundant expansions and promoting a more e cient and structurally organized exploration of the environment. Additionally, an evaluation metric based on the Monte Carlo method is proposed to quantify the space exploration rate, allowing consistent comparative analyses across di erent dimensions. The developed method, referred to as RRT-Edge Continuous Polarization (RRT-EdgeCP), presents a generalized formulation of the polarization strategy for n-dimensional con guration spaces. The approach is validated in this research through experiments in d e two- and three-dimensional environments, used as a proof of concept. These scenarios allow the exploratory behavior of the tree to be analyzed, its structural dispersion and redundancy to be evaluated, and the proposed approach to be compared with di erent RRT variants. The experimental results demonstrated that the proposed approach achieved greater coverage of the explored space, particularly during the initial stages of exploration. A reduction in structural redundancy was also observed, associated with directing expansions toward regions not yet represented by the tree. Thus, the proposed approach contributes to the development of strategies for the exploration and representation of n-dimensional con guration spaces, providing a continuous polarization approach that is independent of spatial discretization. The results indicate the potential of the strategy for constructing compact representations of the free space while maintaining the exibility required for its application across di erent dimensions and robotic exploration scenarios.