Por que o RRT às vezes não acha um caminho onde A* acha?

Corredores estreitos pedem que o ponto aleatório caia **dentro** da fresta antes de a árvore «entrar»; com orçamento baixo de iterações ou passo grande, a probabilidade é pequena. Baixe o **passo**, suba o máximo de nós ou o **viés** rumo à meta quando a árvore já está perto: o mesmo gargalo de «passagem estreita» que motivou **RRT*** e **Informed RRT**.

O caminho amarelo do RRT é ótimo?

Não: o RRT básico devolve **qualquer** caminho geométrico admissível. O **A*** na grade é ótimo **para esse modelo discreto**, mas não corta células à vontade, então os custos não se comparam de frente.

Como é feita a verificação de colisões?

O segmento é discretizado com passo menor que uma célula; cada ponto cai numa célula pela parte inteira inferior das coordenadas; se toca uma **parede**, a aresta é rejeitada. É um teste rápido de aula, não um motor com obstáculos «inflados».

O A* se atualiza ao mover S/G?

A comparação toma o estado **atual** do mapa e das pontas. Depois de mover os marcadores, lance de novo a comparação com **A***.

Planejador RRT

O mesmo mapa de paredes 40×28: amostras ao acaso, nó mais próximo, passo com verificação de colisões, viés de amostragem rumo à meta; botão para comparar com A*.

Planejador RRT

Ferramenta

Passo de avanço (células)0.85

Viés de amostragem rumo à meta0.08

Raio de captura da meta0.42

Máx. de nós da árvore4500

Iterações RRT por quadro220

Semente da amostragem1

Predefinição do mapa

Tamanho da árvore1

Meta alcançadanão

Comprimento do caminho RRT—cells

A* (4-vizinhança, o mesmo mapa)—

O RRT explora direções ao acaso; A* nas mesmas paredes minimiza o custo acumulado por células (×5 em células «caras», se as houver na grade — aqui por omissão só há paredes).

Atalhos de teclado

Clique: parede / borracha; Move S / G — mover as pontas.
Compare A* — A* Manhattan no mesmo mapa; o jogo completo de heurísticas está na página **engineering/astar-dijkstra-grid**.

Grandezas medidas

Crescimentonão

Sobre o modelo

O planejador RRT (árvore aleatória de exploração rápida) cresce um caminho em passos aleatórios no espaço livre. O RRT de aula constrói-se na mesma grade de paredes 40×28 que engineering/astar-dijkstra-grid, mas com coordenadas de nós contínuas em unidades de «célula»: o caminho pode cortar cantos entre nós da grade. Em cada iteração toma-se um ponto livre ao acaso (com viés de amostragem rumo à meta), busca-se o nó mais próximo da árvore, dá-se um passo de comprimento limitado ao longo da corda e a aresta só é aceita se uma verificação densa do segmento não cruzar células-parede. Um vértice novo dentro do raio de captura da meta em torno do centro de G encerra a busca; a linha amarela é o retorno pelos pais até S. O RRT tem completude probabilística, mas não é ótimo: o comprimento do caminho costuma ser maior que o do **A* discreto com heurística de Manhattan sobre as mesmas paredes; o botão de comparação lança esse A* (4-vizinhança, células caras ×5 se as houver na grade). Ajuste o passo, o viés e as iterações por quadro** para ver o compromisso entre sondar o espaço e passar por corredores estreitos.

Para quem: Depois de A* numa grade: planejamento por amostragem, antes de RRT*, PRM e das versões cinodinâmicas.

Conceitos-chave

RRT
planejamento por amostragem
vizinho mais próximo
função de avanço
verificação de colisões
completude probabilística
viés rumo à meta
obstáculos na grade

Como funciona

RRT: ponto ao acaso → nó mais próximo da árvore → passo até ele com verificação das paredes da grade; o viés rumo à meta acelera o fim; A* no mesmo mapa é a referência discreta de custo e de número de expansões.

Perguntas frequentes

Por que o RRT às vezes não acha um caminho onde A* acha?: Corredores estreitos pedem que o ponto aleatório caia dentro da fresta antes de a árvore «entrar»; com orçamento baixo de iterações ou passo grande, a probabilidade é pequena. Baixe o passo, suba o máximo de nós ou o viés rumo à meta quando a árvore já está perto: o mesmo gargalo de «passagem estreita» que motivou RRT* e Informed RRT.
O caminho amarelo do RRT é ótimo?: Não: o RRT básico devolve qualquer caminho geométrico admissível. O A* na grade é ótimo para esse modelo discreto, mas não corta células à vontade, então os custos não se comparam de frente.
Como é feita a verificação de colisões?: O segmento é discretizado com passo menor que uma célula; cada ponto cai numa célula pela parte inteira inferior das coordenadas; se toca uma parede, a aresta é rejeitada. É um teste rápido de aula, não um motor com obstáculos «inflados».
O A* se atualiza ao mover S/G?: A comparação toma o estado atual do mapa e das pontas. Depois de mover os marcadores, lance de novo a comparação com A*.

Continue com temas próximos desta categoria — ou todos os 48 em «Engenharia».

Toda a categoria →

NovoUniversidade / pesquisa

MPC: veículo holonômico 2D

Abrir o simulador

Integrador duplo no plano com limite ‖u‖₂: MPPI por amostragem leva a uma meta que se arrasta e penaliza com suavidade obstáculos circulares — leque de previsões e melhor caminho.

NovoEscola

Labirintos e A*

Abrir o simulador

Labirintos perfeitos numa grade 40×28: percurso recursivo, Wilson, Eller ou Prim aleatório; resolve-se com A* (Manhattan, 4-vizinhança). Dá para desenhar paredes e mover o início e a meta.

NovoUniversidade / pesquisa

ADC e DAC

Abrir o simulador

Um seno contínuo vira amostras e é quantizado; o DAC reconstrói uma tensão em degraus (retenção de ordem zero). Veem-se o critério de Nyquist e a sobreposição de espectros.

NovoEscola

A* e Dijkstra

Abrir o simulador

Grade 40×28: A*, Dijkstra ou busca gulosa; heurísticas, 4- e 8-vizinhança, paredes e células caras; coloração do conjunto aberto e do fechado.

NovoEscola

Recipiente de paredes finas sob pressão

Abrir o simulador

Tensões de membrana em cilindro e esfera: circunferencial σθ, longitudinal σz, equivalente de von Mises, verificação de r/t e fator de segurança ao escoamento.

NovoEscola

Árvore geradora mínima (Prim e Kruskal)

Abrir o simulador

Pontos ao acaso no plano, grafo completo com pesos euclidianos: Prim passo a passo a partir da raiz ou Kruskal com conjuntos disjuntos; compara-se o peso total.

Planejador RRT

Sobre o modelo

Como funciona

Perguntas frequentes

Simuladores relacionados

MPC: veículo holonômico 2D

Labirintos e A*

ADC e DAC

A* e Dijkstra

Recipiente de paredes finas sob pressão

Árvore geradora mínima (Prim e Kruskal)

Planejador RRT

Sobre o modelo

Como funciona

Perguntas frequentes