Stigmergic Skeleton Fields: A Bio-Inspired Framework for Decentralized Multi-Robot Navigation via Localized Incremental Re-Skeletonization

Resumo Técnico: Campos de Esqueleto Estigmergicos (SSF)

Problema
A navegação de múltiplos robôs em ambientes dinâmicos requer uma representação que seja compacta o suficiente para um replanejamento rápido, mas rica o suficiente para suportar uma coordenação auto-organizada. As abordagens tradicionais enfrentam um compromisso: grades de ocupação de grão fino (usadas por A*, RRT*, D* Lite) oferecem alta fidelidade de trajetória, mas sofrem com altos custos computacionais e uso de memória, especialmente quando escaladas para sistemas multiagentes. Por outro lado, esqueletos topológicos (eixo medial ou diagramas de Voronoi) reduzem significativamente o espaço de busca, mas frequentemente carecem de mecanismos para reparo dinâmico ou coordenação consciente de congestionamento. Além disso, métodos bioinspirados existentes, como a Otimização por Colônia de Formigas (ACO) em grades, escalam mal com a resolução, enquanto algoritmos centralizados de Busca de Caminho Multiagente (MAPF), como a Busca Baseada em Conflitos (CBS), tornam-se computacionalmente intratáveis à medida que o número de agentes aumenta. O artigo aborda a necessidade de um framework descentralizado que combine a eficiência de grafos topológicos com a adaptabilidade da coordenação estigmergica, lidando especificamente com obstáculos dinâmicos sem a necessidade de recomputação total.

Metodologia
Os autores propõem o Campo de Esqueleto Estigmergico (SSF), um framework que acopla um grafo de esqueleto de eixo medial com um campo de feromônio no estilo colônia de formigas, aumentado pela Re-esqueletização Incremental Localizada (LIR).

1. Extração do Grafo de Esqueleto: O ambiente (grade de ocupação binária) é reduzido a um grafo de esqueleto de eixo medial 1D $G=(V, E)$. Os nós representam junções e extremidades, enquanto as arestas representam ramos do esqueleto que carregam comprimento euclidiano e folga mínima (clearance). Isso reduz o espaço de busca de $O(n)$ células de grade para $O(S)$ pixels do esqueleto, onde $S \ll n$.
2. Campo de Feromônio Estigmergico e Custo Consciente de Congestionamento: Os robôs interagem indiretamente através de um campo de feromônio compartilhado $\tau_{uv}$ nas arestas do grafo. O custo do caminho $w_{uv}$ para um robô é modulado por:
   • Níveis de feromônio: Incentivando caminhos utilizados por outros (feedback positivo).
   • Folga (Clearance): Recompensando corredores mais largos.
   • Penalidade de Congestionamento: Uma adição crítica onde o custo aumenta se o uso instantâneo $u_{uv}$ de uma aresta exceder um limiar $\kappa$. Isso evita que múltiplos robôs converjam para o mesmo gargalo estreito, um modo de falha comum no planejamento de caminho mais curto independente.
3. Re-esqueletização Incremental Localizada (LIR): Quando um obstáculo dinâmico aparece ou desaparece, a LIR evita a reconstrução de todo o grafo. Em vez disso, ela:
   • Identifica uma caixa delimitadora local ao redor da mudança (com uma margem de preenchimento $p$).
   • Recomputa o eixo medial e a topologia local apenas dentro desta caixa.
   • Emenda o novo subgrafo local no grafo global, preservando o estado de feromônio das regiões não afetadas.
   • A análise teórica (Teorema 1) garante que o esqueleto fora da caixa de preenchimento permanece idêntico a uma recomputação total, desde que o preenchimento exceda o raio de resposta do eixo medial máximo.

Principais Contribuições

• Integração de Estigmia e Topologia: Ao contrário de trabalhos anteriores que aplicam ACO a partições de Voronoi fixas (ex: Xiong et al. para amostragem marinha), o SSF acopla a dinâmica de feromônios com um esqueleto de eixo medial dinâmico.
• Algoritmo LIR: Um procedimento formal para reparar a estrutura topológica no local, garantindo validade sob mudanças ambientais sem recomputação global.
• Roteamento Consciente de Congestionamento: Uma função de custo específica (Eq. 1) projetada para penalizar a saturação de arestas, permitindo coordenação descentralizada sem comunicação explícita entre robôs.
• Comparação Rigorosa com Baselines: O artigo avalia o SSF contra sete baselines: Dijkstra de esqueleto estático, ACO de grade bruta, RRT*, A*, Theta*, PRM* e um CBS restrito ao esqueleto. Também inclui um experimento controlado comparando LIR com D* Lite em grades simplificadas para isolar o efeito do tamanho do grafo da velocidade algorítmica.

Resultos

• Qualidade do Caminho vs. Eficiência: O SSF iguala o desempenho de um baseline Dijkstra de esqueleto estático dentro de 3–8% em comprimento de caminho (estatisticamente significativo em ambientes de escritório e obstruídos) ao adicionar a prevenção de congestionamento.
• Velocidade de Replanejamento Dinâmico:
  • A LIR é até uma ordem de magnitude mais rápida que a re-esqueletização total para mapas de até 1000x1000 células.
  • A LIR é 30–200 vezes mais rápida que o D* Lite em grades de resolução total.
  • Nuance Crucial: Um experimento controlado usando grades simplificadas mostrou que o D* Lite em um grafo com um número de nós semelhante ao do esqueleto é mais rápido (~3ms vs. ~35ms para LIR). No entanto, a grade simplificada produziu caminhos quase o dobro do comprimento do caminho do esqueleto devido ao bloqueio conservador de corredores estreitos. O artigo conclui que a vantagem da LIR não é apenas o tamanho do grafo, mas a capacidade do esqueleto de alcançar um grafo pequeno sem sacrificar a fidelidade do caminho.
• Escalabilidade:
  • Contagem de Robôs: O tempo de planejamento por robô aumenta apenas por um fator de 1,4 ao escalar de 5 para 100 robôs.
  • Memória: O grafo de esqueleto reduz a pegada de memória (RSS de pico) em aproximadamente 14x em comparação com um grafo de grade 8-conectada equivalente.
  • Obstáculos Dinâmicos: A LIR lida com obstáculos simultâneos e remoção de obstáculos com custo quase linear e simétrico.
• Desempenho Multiagente: Para pequenos números de agentes ($N \le 4$), um CBS restrito ao esqueleto encontra soluções ótimas que coincidem com o SSF. Para $N$ maiores, o CBS falha em terminar dentro dos limites de tempo, enquanto o SSF resolve todas as instâncias em menos de 5ms.
• Etapa de Validação de Hardware: Os autores implementaram um controlador diferencial contínuo com sensores locais para executar os caminhos SSF em simulação, demonstrando um passo em direção à validação física, embora nenhuma implantação em hardware físico tenha sido realizada.

Significância e Alegações
O artigo alega modestamente que o SSF não é uma solução universal para caminhos mais curtos (A*/Theta* baseados em grade encontram caminhos mais curtos) nem para coordenação de pequena equipe provadamente ótima (CBS é superior para $N \le 4$). Em vez disso, sua significância reside em fornecer um framework prático e descentralizado para coordenação multirobô em tempo real e consciente de congestionamento em ambientes dinâmicos.

Os autores enfatizam que a contribuição central é a combinação de um campo de feromônio consciente de congestionamento e um mecanismo de reparo localizado (LIR). Eles declaram explicitamente que a vantagem de velocidade sobre o D* Lite é parcialmente um artefato do menor tamanho do grafo do esqueleto, mas o valor único é que o esqueleto alcança esse tamanho pequeno de forma adaptativa (preservando a conectividade dos corredores) sem a degradação da qualidade do caminho inerente ao simplificar manualmente uma grade. O trabalho é apresentado como baseado em simulação, com um pacote ROS 2 fornecido para implantação futura, reconhecendo que a validação física em relação ao ruído do sensor, erro de localização e comunicação distribuída permanece uma etapa necessária.