Rapidly-exploring random tree

• Também chamado: RRT
• Categoria: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

Um planejador de movimento baseado em amostragem que faz crescer uma árvore a partir do estado inicial amostrando repetidamente um estado aleatório e estendendo em sua direção o nó mais próximo da árvore, explorando rapidamente espaços grandes.

Definição

A árvore aleatória de exploração rápida (RRT) (rapidly-exploring random tree) é um algoritmo baseado em amostragem para encontrar um caminho viável de um estado inicial até uma região objetivo. Foi introduzida por Steven LaValle em 1998. O algoritmo faz crescer uma árvore com raiz no início: a cada iteração ele amostra um estado aleatório no espaço de configurações ou de estados, encontra o nó mais próximo da árvore e estende a partir desse nó uma distância curta em direção à amostra. Se a extensão estiver livre de colisões, o novo estado é adicionado à árvore. A busca termina quando a árvore alcança a região objetivo, e o caminho é recuperado de trás para frente pelo pai de cada nó.

A propriedade-chave é o viés de Voronoi. Os nós na fronteira da árvore têm as maiores regiões de Voronoi, então são os mais propensos a ser os mais próximos de uma amostra aleatória, e a árvore é puxada para o espaço inexplorado em vez de preencher regiões que já cobriu. Isso torna o RRT eficaz em espaços de alta dimensão, como o espaço das juntas de um braço robótico. O RRT é probabilisticamente completo: se existe uma solução, a probabilidade de encontrá-la tende a um à medida que o número de amostras cresce. As melhorias comuns incluem o viés para o objetivo (goal biasing), em que uma fração das amostras é tirada no objetivo, e o RRT-Connect, que faz crescer árvores tanto a partir do início quanto do objetivo e tenta uni-las de forma gulosa.

Como o passo de extensão só precisa de uma forma de ir de um estado em direção a outro, o RRT também lida com planejamento cinodinâmico, em que o robô não pode se mover em linhas retas pelo seu espaço de estados. O passo de extensão então aplica controles amostrados ou otimizados e simula a dinâmica para frente, como no RRT cinodinâmico de LaValle e Kuffner, ou encadeia primitivas de movimento pré-calculadas. Isso o torna útil para veículos, robôs com pernas e manipulação rica em contatos, em que a métrica de distância e o passo de extensão precisam ser projetados em torno da dinâmica. Os caminhos do RRT costumam ser irregulares e não ótimos, e adicionar mais amostras não melhora um caminho depois de encontrado. O RRT\ adiciona um passo de escolha do pai e um passo de religação que reconecta nós próximos sempre que existe uma rota mais barata, o que o torna assintoticamente ótimo ao custo de mais computação por amostra. Quando um caminho viável é necessário rapidamente, o RRT simples ou o RRT-Connect seguido de atalhos e suavização continua sendo uma escolha comum.

Por que importa

O RRT tornou o planejamento de movimento prático para robôs com muitos graus de liberdade e para sistemas com dinâmica, e continua sendo um planejador padrão em bibliotecas como OMPL e MoveIt. Muitos planejadores posteriores, incluindo o RRT*, são construídos sobre sua estrutura.

Principais aplicações

• Planejamento de movimento de braços robóticos em espaços de trabalho congestionados
• Planejamento cinodinâmico para carros, drones e robôs com pernas
• Planejamento de manipulação rica em contatos com métricas de distância personalizadas
• Planejamento sobre grafos de primitivas de movimento para locomoção
• Exploração de ambientes desconhecidos

Na prática

Uma equipe que configura o MoveIt para um braço de sete eixos que pega itens de prateleiras usa o RRT-Connect do OMPL como planejador padrão. A verificação de colisões usa o modelo do robô e uma octree construída a partir de uma câmera de profundidade. A equipe define o limite de tempo de planejamento e o tamanho do passo de extensão em relação à folga das aberturas das prateleiras e depois pós-processa cada caminho com atalhos e parametrização temporal para que o braço se mova suavemente. Quando o planejamento tem dificuldade para chegar ao fundo de nichos estreitos, ela aumenta o viés para o objetivo ou testa um planejador com melhor comportamento em passagens estreitas, e para consultas repetidas em uma célula estática considera usar um mapa de rotas probabilístico.

Equívocos comuns

• O RRT encontra o caminho mais curto — ele encontra um caminho viável; para uma boa qualidade de caminho é preciso o RRT* ou um pós-processamento
• O RRT garante encontrar um caminho dentro de um tempo definido — ele é probabilisticamente completo, então encontra um caminho com probabilidade que tende a um à medida que a amostragem continua, e passagens estreitas podem levar muito tempo
• O RRT* é sempre a melhor escolha — ele melhora os caminhos com o tempo, mas é mais lento até uma primeira solução; o RRT-Connect com suavização costuma ser preferido quando a velocidade importa

Quem deve saber

• Engenheiros de planejamento de movimento
• Desenvolvedores de manipulação e de robôs móveis que usam MoveIt ou OMPL
• Engenheiros de planejamento de veículos autônomos e drones
• Estudantes de robótica

Tecnologias relacionadas

• OMPL
• MoveIt
• RRT-Connect
• RRT cinodinâmico (Kinodynamic RRT)
• Informed RRT*
• Atalhos de caminho (Path Shortcutting)

Termos relacionados

• Configuration Space
• Motion Planning
• Obstacle Avoidance
• RRT*
• Probabilistic Roadmap
• Motion Primitive

Projetos relacionados

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

Vídeos

• Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering