Introdução à Engenharia de Controle: Planejamento de Trajetória — A*, Dijkstra, RRT, RRT* e PRM

Mover um robô do ponto inicial ao ponto final raramente significa traçar uma linha reta. Um plano viável deve levar em conta paredes, largura da passagem, área ocupada pelo robô, limites de giro, incerteza de localização, mapas desatualizados, pessoas em movimento e distância de parada. O planejamento de trajetória escolhe para onde ir; a geração e o controle de trajetória decidem como seguir essa rota sob condições dinâmicas. Uma pilha de segurança mantém essas responsabilidades distintas, embora compartilhe seus limites.

Este guia compara os algoritmos Dijkstra e A em grade com os algoritmos RRT, RRT e PRM em espaço contínuo. Ele explica a inflação de obstáculos, heurísticas, amostragem, complexidade, integração SLAM/Nav2, verificações de implementação e comportamento de segurança independente. Consulte Visual SLAM Primer, ROS 2 Primer e Sensor Fusion Primer para camadas adjacentes.

Conclusão prática

• O algoritmo de Dijkstra garante o caminho mais curto em um grafo ponderado não negativo, mas se expande em direções não relacionadas ao objetivo. O algoritmo A* direciona a expansão com uma heurística admissível, mantendo a mesma otimalidade.

• O algoritmo RRT tende a encontrar um caminho viável rapidamente em espaços contínuos de alta dimensionalidade. O algoritmo RRT* se aproxima de um caminho ótimo à medida que as amostras aumentam, com custos adicionais de vizinhança e reconexão. O algoritmo PRM amortiza a construção do mapa de rotas em várias consultas em um espaço suficientemente estático.

• O caminho mais curto em um mapa não inflado é um caminho de colisão para um robô com raio, erro de localização e distância de parada.

• Uma rota retornada não é prova de segurança. A atualização do mapa, a detecção local, o erro de rastreamento, os obstáculos dinâmicos, a latência de replanejamento e a parada de emergência precisam de tratamento independente.

Defina o espaço livre antes de selecionar um algoritmo

Considere o espaço de estados como \mathcal X, o espaço de obstáculos como \mathcal X_{obs} e o espaço livre como \mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}. Um caminho \sigma:[0,1]\to\mathcal X_{free} conecta x_s a x_g, com \sigma(0)=x_s,\sigma(1)=x_g. Um robô pontual em 2D usa x=(x,y); um veículo adiciona a direção \theta, a velocidade e o controle; um manipulador inclui todos os ângulos das juntas. Simplificar o estado reduz o custo da busca, mas pode produzir curvas que o veículo subsequente não consegue realizar.

A inflação de obstáculos transforma um robô finito em uma busca pontual, expandindo os obstáculos. Aqui, r_{loc} deve ser um termo de incerteza especificado, como um raio escolhido para um nível de confiança definido, em vez de um erro médio não especificado. Um mínimo conceitual é

onde r_{robot} é o raio do corpo, a incerteza de localização é representada pelo termo anterior e r_{safe} é a margem de rastreamento/parada. Na realidade, a margem varia com a resolução do mapa, os pontos cegos do sensor, a velocidade do objeto em aproximação e a capacidade de frenagem. Uma margem muito pequena causa colisões; uma margem muito grande torna as passagens viáveis impossíveis.

Diagrama: Duskcoil, conceitual em vez de medido. O tamanho da célula e a inflação devem ser derivados de uma pegada real do robô, incerteza e envelope operacional.

Busca em grade: Dijkstra e A*

Para o grafo G=(V,E) com custo de aresta não negativo c(u,v)\ge0 , o Dijkstra se estabiliza repetidamente O nó instável com o menor custo inicial conhecido é g(n) e relaxa os vizinhos. Uma vez estabilizado, seu valor g é o menor. Com um heap binário, uma complexidade representativa é O((|V|+|E|)\log|V|). Isso garante a menor distância no grafo, mas, sem conhecimento do objetivo, tende a se expandir amplamente.

O A* ordena os nós por

onde h(n) é um limite inferior para o custo restante. Uma heurística admissível nunca superestima o custo restante real; então o A* permanece ótimo. A distância de Manhattan é adequada para grades 4-conectadas, enquanto a distância euclidiana ou relacionada a Chebyshev pode ser adequada para movimentos 8-conectados. Uma heurística consistente também satisfaz h(n)\le c(n,n')+h(n') e reduz a reexpansão.

O A* ponderado escala a heurística por w>1 busca uma rota viável mais rapidamente, ao custo da otimalidade. Isso pode ser uma troca operacional sólida se for explícita. O custo da aresta pode codificar não apenas o comprimento, mas também o risco de obstáculos inflados, a folga, a curva, a energia ou o terreno. A saída é então o custo mínimo definido, não necessariamente o comprimento geométrico mínimo.

Espaços contínuos e de alta dimensão: RRT, RRT*, PRM

Grades finas explodem em um espaço de configuração de braço de seis juntas ou espaço de pose de veículo. O RRT amostra x_{rand} do espaço livre, encontra o nó da árvore mais próximo x_{near}, direciona-se a uma distância limitada em direção a ele, verifica colisões e adiciona x_{new}. É probabilisticamente completo: com amostras suficientes, a probabilidade de encontrar uma rota viável se aproxima de um quando ela existe. Não garante uma primeira rota curta.

O RRT* escolhe o pai de menor custo entre os vértices próximos e reconecta os vizinhos por meio de um Novo vértice quando mais barato. É assintoticamente ótimo, não ótimo em tempo finito; busca de vizinhos, testes de colisão e reconfiguração consomem computação. Meça a qualidade no prazo operacional em vez de prometer "ótimo".

O PRM amostra configurações livres e conecta pares próximos sem colisões em um mapa reutilizável. É atraente em um ambiente de fábrica estática ou em um cenário de consulta repetida de braço, pois o pré-processamento pode ser amortizado. Obstáculos dinâmicos invalidam as arestas. Passagens estreitas dificultam a amostragem uniforme, portanto, amostras com base em limites de obstáculos, com viés de caminho ou informadas pela tarefa podem ser necessárias.

Diagrama: Duskcoil, simplificado. Amostragem, verificação de colisão e conectividade não são uma medida de desempenho ou uma rota de produção final.

SLAM, Nav2 e planejamento local

O SLAM fornece um mapa e uma estimativa de pose, mas um planejador precisa de transformações alinhadas com o timestamp e um significado claro de ocupação/custo. O fechamento de loops ou a relocalização podem alterar a pose no mapa; continuar seguindo uma rota antiga pode ser perigoso. Incorpore eventos de incerteza, reinicialização de localização e atualização do mapa nas regras de replanejamento; veja Visual SLAM Primer.

Em uma arquitetura ROS 2 semelhante ao Nav2, um mapa de custos global e um planejador escolhem uma rota em grande escala, enquanto um mapa de custos local e um controlador lidam com obstáculos próximos e velocidade. Um algoritmo A* global pode selecionar um corredor; a camada local deve ceder, parar ou desviar de uma pessoa. Uma camada puramente local pode ficar presa em um beco sem saída. Defina explicitamente o planejador, o controlador, a recuperação, as taxas de atualização do mapa, os prazos e as prioridades. O transporte ROS 2 descrito em ROS 2 Primer não garante tempo real nem segurança.

Antes da implantação, meça a área ocupada, incluindo a carga útil, o campo de visão dos sensores, a velocidade/desaceleração máxima, o erro de localização e a resolução do mapa. Teste a folga real em passagens estreitas. Verifique a ocorrência de colisões nos caminhos planejados em relação ao movimento contínuo e à cinemática: uma rota em grade pode fazer curvas entre células de maneiras que um veículo com tração diferencial, um carro ou um braço mecânico não conseguem.

Para obstáculos dinâmicos, meça a atualização da detecção, a velocidade relativa, a distância de frenagem e o tempo de replanejamento; nunca continue se movendo porque o planejador está atrasado. Trate pessoas desconhecidas, buracos, obstáculos transparentes e falhas de sensores como casos de segurança, não como liberação automática de células. Diminua a velocidade, pare ou transfira o controle quando não houver rota, o caminho local for inseguro, a covariância for muito grande, o mapa estiver desatualizado ou o erro de rastreamento exceder o limite. A parada de emergência deve operar independentemente da saída do planejador.

Lista de verificação de implementação e segurança

1. Defina o espaço de estados, a área de cobertura, os quadros, a resolução do mapa e o significado das células desconhecidas.

2. Inclua na inflação o erro de localização, a velocidade e a distância de parada; teste em passagens estreitas reais.

3. Verifique a admissibilidade da heurística ou documente a garantia deliberadamente relaxada.

4. Registre a resolução da verificação de colisões, a semente aleatória, o prazo e o comportamento de ausência de solução para os planejadores de amostragem.

5. Injete relocalização, alterações no mapa, perda de sensores, obstáculos dinâmicos e atraso de comunicação.

6. Verifique uma parada segura e um caminho de registro diagnosticável para eventos de ausência de rota, mapa desatualizado e desvio de rastreamento.

Referências

• Hart, Nilsson, Raphael, 1968: Uma Base Formal para A*
• LaValle: Árvores Aleatórias de Exploração Rápida
• Karaman e Frazzoli, 2011: RRT*
• Documentação do Nav2