Stanford publica aula de Pavone sobre planejamento de movimento: RRT, PRM e FMT*

A Stanford Online publicou no YouTube a sétima aula do curso AA274A Principles of Robotic Autonomy, «Motion Planning II: Sampling-Based Methods». A gravação é do outono de 2019. A aula é de Marco Pavone, professor adjunto do Departamento de Aeronáutica e Astronáutica de Stanford e Senior Director de pesquisa em veículos autônomos na NVIDIA. Antes da universidade, ele trabalhou no Jet Propulsion Laboratory da NASA. Não se trata de um lançamento de produto, e sim de material didático, mas o tema define diretamente como robôs e veículos autônomos calculam trajetórias. A própria Stanford ressalva que a estrutura do curso, as tarefas e os materiais mudaram desde 2019, e que os links da descrição levam à versão atual.

Por que o planejador precisa de pontos aleatórios

A busca clássica em grafos (Dijkstra, A*) exige discretizar o espaço de configurações. Para um robô plano, isso é tolerável. Para um manipulador com sete juntas e uma grade de 100 valores por eixo, o resultado é 100 elevado à sétima potência, ou seja, cerca de 10^14 células. Armazenar e percorrer uma grade desse tamanho é inviável.

Os métodos baseados em amostragem contornam o problema de outra forma. O planejador sorteia configurações aleatórias, descarta as que resultam em colisão e conecta as restantes com segmentos curtos e admissíveis. Não é preciso um mapa explícito de obstáculos no espaço de configurações. Basta uma função que diga se determinado ponto ou segmento está livre.

Quais algoritmos fazem parte deste bloco

A descrição da aula usa um título genérico para o tema, mas o conjunto padrão do planejamento por amostragem é este:

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996): constrói uma só vez um grafo a partir de pontos aleatórios e responde a várias consultas. Serve para ambientes estáticos.
• RRT (LaValle, 1998): faz crescer uma árvore a partir do ponto de partida em direção a pontos aleatórios. Encontra caminhos rapidamente em espaços de muitas dimensões e, para uma única consulta, é mais prático que o PRM.
• RRT* (Karaman, Frazzoli, 2011): acrescenta a reconstrução da árvore e garante otimalidade assintótica. O custo do caminho converge para o ótimo à medida que o número de amostras cresce.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015): desenvolvido pelo grupo de Pavone. Percorre as amostras em uma ordem próxima à do fast marching method e, com frequência, chega a um bom caminho com menos verificações de colisão.
• Raio de conexão no PRM*: escala como (log n / n)^(1/d), onde d é a dimensão do espaço. Essa estimativa sustenta as provas de otimalidade.

O principal conceito teórico aqui é a completude probabilística. Se existe um caminho, a probabilidade de encontrá-lo tende a um conforme o número de pontos aumenta. Não há garantia de tempo, e essa é uma ressalva importante.

Por que as aulas de 2019 não ficaram obsoletas

Os planejadores por amostragem continuam em uso. A biblioteca OMPL, que o MoveIt usa por padrão para planejamento, traz implementações de PRM, RRT, RRT* e FMT. As abordagens mais recentes partem dessa base: distribuições aprendidas para escolher os pontos, verificação paralela de colisões em GPU, como no cuRobo da NVIDIA, e híbridos com otimização de trajetória. O gargalo de todas continua o mesmo: a verificação de colisões costuma consumir a maior parte do tempo de planejamento.

O curso tem um livro-texto gratuito, Principles of Robot Autonomy, em porabook.com, e um programa aberto em stanfordasl.github.io/PoRA-I. Para quem estuda por conta própria, é raro encontrar aulas, texto e exercícios reunidos em um só lugar.

Como usar o material na prática

Comece pelo livro-texto e depois assista à aula. Implemente um RRT no plano em cerca de cem linhas de código e conte quantas chamadas de verificação de colisão são necessárias para um único caminho. Em seguida, use a OMPL e compare RRT, RRT e FMT em uma mesma cena com uma passagem estreita. É ali que aparece a principal fraqueza desses métodos: a probabilidade de amostrar um ponto no corredor estreito é baixa, e o tempo de busca cresce rapidamente.

Há também duas limitações a considerar. Os caminhos do RRT saem em linhas quebradas e quase sempre precisam ser suavizados. Já para veículos com dinâmica, como carros, a geometria sozinha não basta: são necessárias variantes cinodinâmicas e a integração com o controlador. A aula de 2019 fornece a base, mas os detalhes ficam para a versão mais recente do curso.