RRT*

• Também chamado: RRT star, RRT-star, optimal RRT
• Categoria: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Uma versão assintoticamente ótima do planejador Rapidly-exploring Random Tree que reconecta sua árvore à medida que ela cresce, de modo que o caminho que ele retorna continua melhorando em direção ao de menor custo.

Definição

RRT\ (pronuncia-se “RRT star”) é um algoritmo de planejamento de movimento baseado em amostragem que encontra caminhos livres de colisão e, com amostras suficientes, converge para um ótimo. Foi apresentado por Sertac Karaman e Emilio Frazzoli em 2011 como uma extensão do algoritmo Rapidly-exploring Random Tree (RRT), proposto por Steven LaValle em 1998.

O RRT original faz crescer uma árvore a partir da configuração de início amostrando repetidamente um ponto aleatório no espaço de configurações, encontrando o nó mais próximo na árvore e estendendo um passo curto em direção à amostra se esse movimento estiver livre de colisão. O RRT encontra caminhos viáveis rapidamente, mesmo em espaços de alta dimensão como o espaço das juntas de um braço robótico, mas seus caminhos costumam ser irregulares e longe do mais curto, e não melhoram à medida que mais amostras são adicionadas.

O RRT* muda duas coisas. Quando um novo nó é adicionado, ele examina todos os nós da árvore dentro de um raio de vizinhança e se conecta ao que dá o menor custo a partir do início, e não simplesmente ao mais próximo. Em seguida, ele reconecta: para cada vizinho, se passar pelo novo nó gera um caminho mais barato, o pai desse vizinho é trocado. Karaman e Frazzoli mostraram que, com um raio de vizinhança que diminui de forma adequada à medida que a árvore cresce, o custo da solução converge para o ótimo quando o número de amostras tende ao infinito, uma propriedade chamada otimalidade assintótica.

O preço é computação extra por amostra, por isso o RRT é mais lento que o RRT para encontrar uma primeira solução. Variantes como Informed RRT e BIT* concentram a amostragem para acelerar a convergência.

Por que importa

Muitos robôs não precisam de um caminho qualquer, mas de um bom: mais curto, mais suave ou mais barato em energia. O RRT* dá aos planejadores baseados em amostragem, que escalam para espaços de configurações de alta dimensão, um caminho fundamentado para a qualidade do caminho, e é uma referência padrão em pesquisa e software de planejamento de movimento.

Principais aplicações

• Planejamento de movimento livre de colisão para braços robóticos em espaços de trabalho congestionados
• Planejamento global de caminhos para robôs móveis e drones
• Planejamento em espaços de configurações de alta dimensão em que a busca em grade é impraticável
• Geração de caminhos de referência para otimização de trajetória

Na prática

As equipes de robótica geralmente chegam ao RRT por meio de uma biblioteca de planejamento em vez de implementá-lo elas mesmas. A Open Motion Planning Library (OMPL), que o MoveIt usa para braços robóticos, inclui o RRT e várias de suas variantes ao lado de RRT, RRT-Connect e PRM. Um padrão comum é rodar o RRT com um orçamento de tempo fixo, pegar o melhor caminho encontrado quando o tempo acaba e depois encurtá-lo e suavizá-lo antes de convertê-lo em uma trajetória parametrizada no tempo. Para robôs móveis e drones, as equipes também usam o RRT sobre um mapa de ocupação 2D ou 3D como planejador global, escolhendo o tempo de planejamento e o tamanho do passo para equilibrar a qualidade do caminho e o tempo de resposta.

Equívocos comuns

• O RRT* retorna o caminho ótimo — ele é assintoticamente ótimo, então o custo do caminho se aproxima do ótimo apenas à medida que o número de amostras cresce sem limite
• Os caminhos do RRT* são suaves — eles são lineares por partes e geralmente precisam de atalhos e suavização antes da execução
• O RRT* é sempre melhor que o RRT — quando só é preciso um caminho viável rapidamente, o RRT simples ou o RRT-Connect costuma ser a melhor escolha

Quem deve saber

• Engenheiros de planejamento de movimento
• Desenvolvedores de software para braços robóticos e manipulação
• Desenvolvedores de drones autônomos e robôs móveis
• Estudantes de robótica que estudam algoritmos de planejamento

Tecnologias relacionadas

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• Verificação de colisão (Collision Checking)

Termos relacionados

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

Projetos relacionados

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

Vídeos

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB