Resumo Técnico: SE(2) Navigation Mesh

Definição do Problema

A navegação global para robôs terrestres em ambientes complexos e de múltiplos níveis (ex: instalações industriais com escadas, saliências e passagens estreitas) requer representações que capturem com precisão as regiões transitáveis, ao mesmo tempo em que permitem o planejamento de trajetória eficiente. As abordagens existentes enfrentam limitações significativas:

• Nuvens de pontos e mapas volumétricos (ex: grades de ocupação, TSDFs) carecem de estrutura de superfície explícita, tornando a estimativa de transitabilidade detalhada computacionalmente dispendiosa e exigindo inferência geométrica adicional.
• O planejamento de trajetória direto em malhas de triângulos densas é computacionalmente proibitivo para o planejamento em tempo real.
• As Navigation Meshes (NavMeshes) clássicas abstraem regiões transitáveis em polígonos convexos, mas assumem uma transitabilidade invariante ao yaw (guinada). Ao aproximar os robôs como cilindros e exigir viabilidade para todos os sentidos, elas falham em capturar as restrições específicas de robôs não circulares (ex: robôs quadrúpedes retangulares) em espaços estreitos, muitas vezes descartando caminhos válidos ou falhando em representar estruturas de múltiplos níveis de forma eficaz.

Metodologia

Os autores propõem a SE(2) Navigation Mesh (SE(2) NavMesh), uma representação poligonal que codifica explicitamente a transitabilidade dependente do yaw. O sistema opera em dois modos: geração offline a partir de mapas pré-construídos e geração incremental online a partir de nuvens de pontos em fluxo (streaming).

1. Representação: SE(2) NavMesh

O método estende a NavMesh clássica incorporando o yaw ($\psi$) do robô na construção da malha, criando um espaço de estados $X = M \times S^1$ (superfície $\times$ orientação).

• Modelo do Robô: Diferente da aproximação cilíndrica das NavMeshes clássicas, este método utiliza uma aproximação de bloco (cuboide) (comprimento, largura, altura) para representar melhor a geometria de robôs quadrúpedes.
• Canais de Yaw: O intervalo contínuo de yaw $[0, 2\pi)$ é discretizado em $N_\Psi$ canais.
• Máscaras de Pegada (Footprint Masks): A transitabilidade é avaliada usando máscaras de pegada de yaw contínuo. Estas máscaras representam a união das áreas ocupadas varridas pela pegada do robô sobre um intervalo de yaw, garantindo a rotação segura entre cabeçamentos adjacentes.
• Estrutura em Camadas: O espaço transitável é particionado em camadas de transitabilidade específicas de yaw ($L_i$). Cada camada contém regiões onde o robô pode transitar com um cabeçamento específico.
  • Regiões Seguras: Viáveis para todos os ângulos de yaw discretizados.
  • Regiões Restritas: Viáveis apenas para um subconjunto de ângulos de yaw.
• Conectividade: O grafo de navegação inclui dois tipos de arestas:
  • Conectividade Translacional: Entre regiões dentro da mesma camada de yaw (movimento sem alteração de cabeamento).
  • Conectividade Rotacional: Entre regiões de camadas de yaw diferentes, mas de mesma localização espacial (rotação sobre o próprio eixo).

2. Pipeline de Geração

• Offline: O ambiente (malha de triângulos) é voxelizado. Um mapa de distância é computado para classificar os voxels como seguros, restritos ou inacessíveis com base na pegada do robô e nas restrições de trajeto (altura de degrau, inclinação). Um algoritmo de watershed particiona esses voxels em polígonos convexos, que são então fundidos entre blocos (tiles) para formar a malha global.
• Online: O sistema utiliza o Voxblox para reconstrução geométrica incremental a partir de nuvens de pontos. Para manter o desempenho em tempo real, as atualizações são locais. O mapa é dividido em lajes (slabs) verticais; apenas as lajes afetadas por nova geometria e seus vizinhos imediatos são reprocessadas. Isso evita o crescimento da latência linear associado à regeneração global.

3. Estratégia de Planejamento de Trajetória: ASA

Os autores introduzem uma estratégia de três estágios A-String Pulling-A (ASA)** para otimizar tanto a posição quanto o cabeamento:

1. Busca Inicial: Uma busca A* no grafo de navegação encontra uma sequência viável de regiões e estados específicos de camada.
2. Retificação de Caminho (String Pulling): Um algoritmo de string-pulling refina geometricamente o caminho para remover o efeito de zigue-zague, produzindo um caminho retificado dentro do corredor definido pela sequência de regiões.
3. Refinamento de Yaw: Uma segunda busca A* otimiza o cabeamento do robô ao longo do caminho retificado, garantindo que a trajetória final respeite as restrições de transitabilidade dependentes do yaw.

Principais Contribuições

1. Representação SE(2) NavMesh: Uma representação poligonal inovadora que codifica a viabilidade dependente do yaw usando máscaras de pegada e uma estrutura de grafo em camadas. Ela captura significativamente mais área transitável (especialmente em passagens estreitas) do que as NavMeshes clássicas.
2. Estratégia de Planejamento ASA: Uma abordagem de planejamento hierárquico que desacopla a retificação geométrica do caminho da otimização do cabeamento, reduzindo o comprimento do caminho geométrico em 6,2% e o custo final do caminho para 87% do custo da busca inicial.
3. Framework de Geração Online: Um método eficiente para construir e atualizar incrementalmente SE(2) NavMeshes a partir de nuvens de pontos em fluxo usando atualizações locais baseadas em lajes, permitindo o uso em tempo real em hardware embarcado.

Resultados Experimentais

• Simulação (Transitabilidade): Em seis ambientes internos diversos (incluindo cenas de múltiplos níveis), a SE(2) NavMesh capturou mais de 50% de área transitável adicional do que as NavMeshes clássicas. Ela conseguiu unir regiões seguras anteriormente desconectadas ao utilizar regiões restritas.
• Simulação (Planejamento): O pipeline ASA superou consistentemente as bases baseadas em amostragem (RRT, RRT*, PRM) em ambientes restritos, alcançando maior Sucesso Ponderado pelo Custo do Caminho (SPC) e menores tempos de planejamento. Em espaços abertos, os métodos baseados em amostragem foram mais rápidos, mas produziram caminhos de maior custo.
• Implantação no Mundo Real: Experimentos em um robô quadrúpede ANYmal demonstraram a geração online e navegação bem-sucedidas em cenários complexos, incluindo:
  • Ambientes de múltiplos níveis com travessia de escadas.
  • Corredores estreitos (0,8m de largura, apenas 0,27m mais largos que o robô).
  • Navegação sob obstáculos suspensos (overhangs).
  • O sistema manteve uma taxa de atualização de 4 Hz usando atualizações locais, enquanto as atualizações globais falharam em sustentar o desempenho em tempo real conforme o mapa crescia.

Significância e Alegações

O artigo afirma que a SE(2) NavMesh aborda uma lacuna crítica na navegação de robôs terrestres ao modelar explicitamente a relação entre o cabeamento do robô e a transitabilidade. Ao ir além da suposição de "pegada circular" das NavMeshes clássicas, o método permite a navegação confiável para robôs não circulares em ambientes restritos e de múltiplos níveis, onde as abordagens tradicionais falham ou são excessivamente conservadoras. A integração de um pipeline de geração online estabelece ainda a viabilidade do uso desta representação para exploração autônoma em ambientes desconhecidos e dinâmicos sem mapas prévios. O trabalho é apresentado como um passo para uma navegação global mais robusta para robôs quadrúpedes em tarefas de inspeção industrial e de infraestrutura.