Planejamento de caminhos e mapeamento: do flood fill ao SLAM
Você pode planejar uma rota em uma grade conhecida, replanejar quando surgem obstáculos e explicar como um robô constrói o mapa usado no planejamento.
A navegação reativa permite que um robô se desloque por uma sala sem nunca saber onde está. Essa abordagem deixa de funcionar rapidamente: não é possível dizer a um robô puramente reativo vá até a cozinha, e ele pode ficar em um laço para sempre em uma sala com formato de ferradura. O planejamento é a resposta e exige algo que o controle reativo nunca oferece — um mapa.
Esta trilha começa onde o mapa é gratuito. Em um labirinto, o flood fill propaga distâncias para fora do objetivo e o robô simplesmente segue o gradiente para baixo, replanejando no instante em que descobre uma parede que supunha estar livre. Depois, o mundo fica mais complexo: A* planeja em uma grade de ocupação em que as células têm custos, os obstáculos precisam ser inflados e a heurística decide se o planejador é rápido ou apenas correto.
O último nó é o mais honesto. Todos os planejadores anteriores pressupõem que você tem um mapa, mas um robô real precisa construí-lo enquanto se movimenta sobre rodas que mentem para ele. SLAM acontece quando o mapeamento e a localização deixam de poder ser separados, e o fechamento de loop impede que o mapa se deforme com a deriva da odometria. Uma IMU também se justifica aqui pelo mesmo motivo: mede a rotação diretamente, algo que rodas que patinam não conseguem.
Antes de começar
Você precisa se sentir à vontade com matrizes bidimensionais e raciocínio algorítmico básico — filas e a ideia de visitar células em uma determinada ordem. A trilha de controle de motores vale a pena fazer primeiro, porque todos os planejadores aqui pressupõem que o robô consegue executar um movimento comandado e informar aproximadamente quanto percorreu.
O que você será capaz de fazer
- Propagar distâncias a partir de um objetivo em uma grade e seguir o gradiente até ele.
- Executar A* com uma heurística que você possa demonstrar que nunca superestima e explicar por que essa propriedade produz o caminho mais curto.
- Transformar leituras de distância em uma grade de ocupação com ray casting, atualizando separadamente as células livres e ocupadas.
- Explicar por que a odometria, sozinha, não produz um mapa utilizável em uma longa operação e o que SLAM acrescenta.
Onde as pessoas costumam travar
Uma heurística que superestima. A* só garante o caminho mais curto quando a heurística nunca declara uma distância maior do que o custo restante real. Usar a distância euclidiana em uma grade conectada em 4 direções ou aumentar a heurística para acelerar a busca retorna silenciosamente caminhos que não são os mais curtos.
Planejamento para um robô representado por um ponto. O caminho é calculado na grade, mas o robô tem largura. Uma rota que roça um canto é geometricamente válida e fisicamente resulta em uma colisão. Infle os obstáculos pelo raio do robô antes de planejar, e o problema desaparece.
Tratar o desconhecido como livre. Uma célula que não foi observada não está vazia — está sem medição. Se planejar através dela como espaço livre, o robô avança com confiança para onde nunca viu. O desconhecido é um terceiro estado e precisa continuar assim.
Passos diagonais com custo um. Em uma grade conectada em 8 direções, um passo diagonal cobre √2 células, não uma. Cobrar por ele o mesmo valor de uma célula produz caminhos que preferem escadas e distâncias simplesmente erradas.
Supor que o robô esteja onde a odometria indica. Todos os planejadores aqui operam sobre uma pose. A odometria das rodas deriva sem limite, então um plano perfeito é executado a partir de uma posição cada vez menos realista. Essa diferença é a motivação completa para o último nó desta trilha.
O que você precisa
| Item | Por que esta trilha precisa dele | Observações |
|---|---|---|
| Familiaridade com matrizes 2D e filas | Todos os algoritmos aqui percorrem uma grade em um laço | Sem matemática avançada; uma fila e um laço aninhado bastam |
| Um robô que execute movimentos comandados | Um plano não vale nada se o robô não puder executá-lo | A trilha de controle de motores chega a este ponto |
| Um giroscópio ou uma IMU | As rodas não conseguem medir uma rotação causada por patinação | MPU-6050; os nós de mapeamento dependem do rumo |
| Um sensor de distância, de preferência com varredura | As células só se tornam conhecidas quando são medidas | Um sonar varrido por um servo basta para construir uma grade básica |
| Um lugar para visualizar uma grade | Depurar um planejador observando um robô é quase impossível | Envie caracteres ASCII pela porta serial ou use os laboratórios desta trilha |
Os dois laboratórios funcionam inteiramente no navegador, então você pode concluir os nós de flood fill e cobertura sem nenhum equipamento físico.
Por que a trilha segue esta ordem
O labirinto vem primeiro porque o mapa é gratuito. Em um labirinto de micromouse, o mundo é uma grade por construção — as células têm tamanho conhecido, as paredes ficam nos limites das células e a posição do robô é sempre um índice de célula. Isso elimina de uma vez todos os problemas de percepção e deixa apenas o planejamento, que é o que você veio aprender. O flood fill em uma grade conhecida é a introdução mais direta a “calcule um campo de distância e siga o gradiente”.
A* vem em segundo porque elimina as comodidades do labirinto uma de cada vez. Agora as células têm custos, não apenas paredes. A grade é maior, então expandir tudo desperdiça trabalho e a heurística passa a valer. O robô tem largura, então os obstáculos precisam ser inflados. E as células podem ser desconhecidas, uma ideia genuinamente nova que o labirinto nunca exigiu.
As grades de ocupação vêm em terceiro porque são o ponto em que o mapa deixa de ser fornecido. O ray casting transforma uma leitura de distância em evidências sobre várias células ao mesmo tempo — tudo ao longo do raio tem maior probabilidade de estar livre, e o ponto final, de estar ocupado —. Atualizar esses dois estados separadamente é toda a técnica.
A IMU fica aqui de propósito. Ela chega exatamente no nó em que o erro de rumo começa a ser gravado no mapa, porque um giroscópio mede a rotação diretamente e rodas que patinam não conseguem.
SLAM vem por último porque representa o reconhecimento de que os nós anteriores pressupunham algo falso. Todos os planejadores operam sobre uma pose, e cada pose veio de uma odometria que deriva sem limite. SLAM acontece quando você para de fingir que é possível resolver o mapeamento e a localização separadamente.
A cobertura encerra a trilha porque é o problema que mais claramente precisa de um mapa e menos claramente pode ser resolvido de forma reativa. “Já visitei todo lugar?” é uma pergunta que somente a memória pode responder.
Pontos de verificação: como saber que uma etapa foi dominada
| Etapa | Verificação | Como é um resultado aprovado |
|---|---|---|
| Flood fill | Exiba o campo de distância de um pequeno labirinto | O objetivo vale 0, os valores aumentam para fora e as paredes criam os desvios esperados |
| Replanejamento | Revele uma parede que o robô supunha estar livre | O campo é atualizado e o próximo movimento muda — sem reexplorar |
| Validação de A* | Execute em uma grade cujo resultado você conhece manualmente | O comprimento é igual ao do caminho mais curto calculado à mão, sempre |
| Admissibilidade | Aumente deliberadamente sua heurística em 2× | A busca fica mais rápida e o caminho fica mais longo — agora você viu a troca |
| Custo diagonal | Planeje pelo espaço livre em uma grade conectada em 8 direções | O caminho é uma diagonal reta, não uma escada; diagonais custam √2 |
| Inflação de obstáculos | Planeje próximo a um canto com a inflação desligada e depois ligada | Desligada, o caminho roça o canto; ligada, ele mantém uma folga equivalente ao raio do robô |
| Grade de ocupação | Varrer um sensor diante de uma porta e renderizar a grade | O espaço livre aparece ao longo dos raios, as células ocupadas nas pontas e o desconhecido atrás das paredes |
| Tratamento do desconhecido | Peça ao planejador uma rota para um espaço sem mapa | Ele recusa ou assume conscientemente — ambas opções servem; adivinhar não |
| Deriva | Percorra um loop fechado e compare o início e o fim do mapa | O mapa não fecha — essa diferença é exatamente o que o fechamento de loop corrige |
| Cobertura | Execute uma varredura planejada e uma caminhada aleatória pelo mesmo tempo | A varredura planejada cobre muito mais, e você pode informar as duas porcentagens |
Onde esta trilha termina
Esta trilha plana em um mundo estático, bidimensional e de tamanho conhecido. Cada uma dessas palavras representa uma limitação que vale nomear.
Estático. Nada aqui lida com uma pessoa atravessando o plano. Obstáculos dinâmicos exigem um planejador local executando sob o planejador global, capaz de replanejar muito mais rápido do que A* sobre uma grade inteira.
Bidimensional. Uma grade de células livres e ocupadas representa uma planta baixa. Ela não representa uma mesa sob a qual o robô pode passar, mas através da qual não pode atravessar. Por isso, robôs sofisticados usam representações 3D ou mapas de custo em camadas.
Baseado em grade. Planejadores por amostragem, como RRT e RRT*, lidam com espaços de alta dimensão, como o espaço das juntas de um braço robótico, nos quais uma grade é inútil. Eles trocam a garantia do caminho mais curto pela possibilidade de funcionar.
A trilha também não cobre filtros de partícula ou localização de Monte Carlo, que permitem que um robô se localize em um mapa que recebeu, em vez de um que está construindo. Esse é um problema mais simples e muito mais comum, e vale conhecer sua existência antes de recorrer ao SLAM completo.
Roteiro de aprendizagem
O caminho
Siga os nós em ordem — cada um desbloqueia o próximo depois que você o conclui. Seu progresso fica salvo neste dispositivo.
0 / 9 concluídos
Dúvidas comuns
Perguntas frequentes
Qual é a diferença entre flood fill e A* no planejamento de caminhos de robôs?
O flood fill calcula a distância do objetivo a todas as células da grade, para que o robô possa então seguir o gradiente a partir de qualquer posição em que estiver. O A* pesquisa a partir de um único início em direção a um único objetivo e expande somente as células que a heurística sugere serem promissoras. O flood fill é a escolha certa em um labirinto de micromouse, porque o robô está constantemente descobrindo novas paredes e precisa replanejar a cada poucas células; como a distância de todas as células já está calculada, isso não tem custo adicional. O A* é a escolha certa em uma grade grande, quando você planeja uma vez a partir de um início conhecido e expandir o mapa inteiro seria desperdício.
Por que meu caminho A* corta os cantos dos obstáculos?
Porque você planejou para um ponto, mas o robô tem largura. O caminho é geometricamente válido na grade, mas fisicamente resulta em uma colisão, porque o planejador nunca soube que o robô ocupa mais de uma célula. A correção padrão é inflar cada obstáculo pelo raio do robô antes de planejar, expandindo as células ocupadas para fora, de modo que qualquer caminho encontrado tenha folga para o robô real. Isso é muito mais simples e confiável do que tentar verificar a folga durante a busca.
O que torna a heurística do A* admissível e por que isso importa?
Uma heurística admissível nunca superestima o custo real restante até o objetivo. Essa única propriedade garante que o A* retorne o caminho mais curto; superestimar em qualquer ponto pode fazer a busca se comprometer com uma rota que deveria rejeitar. As formas mais comuns de violá-la são usar a distância euclidiana em uma grade conectada em 4 direções, em que o custo real é o de Manhattan e é sempre pelo menos igual, e aumentar deliberadamente a heurística para acelerar a busca. A segunda é uma técnica válida, mas troca a garantia do caminho mais curto, e você deve saber que está fazendo essa troca.
Preciso de SLAM para um robô de projeto?
Somente quando o robô precisa saber onde está durante uma longa operação em um espaço do qual não recebeu um mapa. Se você pode fornecer um mapa, a localização, sozinha, é muito mais simples. Se o espaço for pequeno o bastante para que a deriva da odometria permaneça tolerável — um labirinto, uma sala, alguns minutos de operação; você também não precisa de SLAM. A complexidade do SLAM se justifica quando as duas condições falham ao mesmo tempo. Esse é um limite real, não um selo: muitos robôs realmente capazes nunca precisam dele.
Por que meu mapa de grade de ocupação se deforma conforme o robô se desloca?
Porque a deriva da odometria está sendo gravada no mapa. Cada varredura é posicionada conforme a pose em que o robô acreditava estar, de modo que uma estimativa de rumo que girou lentamente insere um corredor reto no mapa como uma curva. Nada está errado com o mapeamento: ele registra fielmente uma pose fictícia. É exatamente isso que o fechamento de loop corrige, reconhecendo que o robô retornou a um lugar já visitado e ajustando toda a trajetória para que as duas observações concordem.
Por que não tratar células desconhecidas como espaço livre?
Porque uma célula que não foi observada não está vazia; ela não foi medida. A diferença decide se o robô entra em objetos que nunca viu. Se tratar o desconhecido como livre, o planejador traçará uma rota por uma região que nenhum sensor cobriu, normalmente onde os móveis estão, pois espaços ocultados e ocupados têm correlação forte. Mantenha o desconhecido como um terceiro estado distinto, ao lado de livre e ocupado, e decida conscientemente se um planejador pode atravessá-lo.