Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios

Título: Benchmarking de Heurísticas Clássicas de Planejamento de Trajetória de Cobertura em Grades Hexagonais Irregulares para Cenários Marítimos

1. Problema e Motivação

O Planejamento de Trajetória de Cobertura (CPP) visa gerar trajetórias que observem todos os pontos de uma Área de Interesse (AOI) minimizando esforço de viagem, redundância e complexidade de manobra. No contexto marítimo (vigilância, busca e resgate, monitoramento ambiental), as AOIs raramente são convexas; elas contêm costas, ilhas e zonas de exclusão que criam passagens estreitas e gargalos.

• Desafio Específico: A maioria dos estudos compara métodos em grades retangulares ou em exemplos pequenos e ad hoc. As grades hexagonais são preferidas no sensoriamento marítimo por oferecerem conectividade quase isotrópica e uma aproximação natural de "pegadas" de sensores circulares.
• Lacuna: Não existia um benchmark reprodutível e em larga escala que avaliasse heurísticas determinísticas clássicas em grafos hexagonais esparsos e irregulares, focando tanto na cobertura relaxada (revisitas permitidas) quanto na cobertura Hamiltoniana (visita exata a cada célula, sem revisitas).

2. Metodologia

A. Geração do Dataset (O Benchmark)
Os autores criaram um conjunto de dados controlado com 10.000 instâncias de grafos hexagonais irregulares:

• Morfologias: As instâncias foram geradas em três famílias: Compactas (zonas de patrulha abertas), Alongadas (faixas costeiras, canais) e Irregulares (formas côncavas com gargalos).
• Escala: Os grafos possuem entre 28 e 46 células visitáveis, um tamanho escolhido para permitir auditoria exata de viabilidade Hamiltoniana via busca em profundidade (DFS) exaustiva.
• Validação: Todas as instâncias foram auditadas offline para garantir que uma solução Hamiltoniana (caminho sem revisitas) é teoricamente possível. Instâncias inviáveis foram descartadas.

B. Heurísticas Avaliadas
O estudo comparou 17 heurísticas determinísticas agrupadas em 7 famílias:

1. Varredura Linear (3 métodos): Padrões de "boustrophedon" e variações.
2. Varredura Intercalada (2 métodos): Para reduzir curvas locais.
3. Contorno/Espirais (3 métodos): Varredura de dentro para fora ou vice-versa.
4. Cobertura por Árvore Geradora (STC) (2 métodos): Baseadas em DFS em árvores geradoras.
5. Busca Local Baseada em Grafos (5 métodos):
   • Variações de Warnsdorff: Regra que escolhe o vizinho não visitado com menor grau residual. O estudo focou em duas variáveis críticas: Tie-breaking (empate por índice vs. distância) e Política de Grau Residual (Endpoint-Aware vs. Terminal-Inclusive).
   • DFS com Backtracking: Permite revisitas para recuperar conectividade.
6. Wavefront/Brushfire (1 método): Campo de distância estático.
7. Curvas de Preenchimento de Espaço (1 método): Curva de Morton (Z-order).

C. Protocolo de Avaliação
As métricas incluíram:

• Taxa de Sucesso Hamiltoniano (HSR): Sucesso em encontrar um caminho sem revisitas.
• Taxa de Conclusão de Cobertura (CCR): Sucesso em cobrir todas as células (revisitas permitidas).
• Qualidade do Caminho: Número de revisitas, comprimento da trajetória, mudanças de rumo e latência de CPU.

3. Principais Contribuições

1. Dataset Público e Auditado: Disponibilização de 10.000 instâncias de grafos hexagonais irregulares com viabilidade Hamiltoniana verificada.
2. Protocolo Comum: Avaliação de 17 algoritmos sob as mesmas condições de grafos, pontos de partida e retorno.
3. Análise de Sensibilidade de Implementação: Evidência de que detalhes de implementação frequentemente omitidos (especificamente a definição do grau residual quando o nó terminal é reservado) impactam drasticamente o desempenho.
4. Liberdade de Código: Disponibilização do gerador de benchmark, implementações e scripts de avaliação para reprodutibilidade.

4. Resultados Chave

• Cobertura Relaxada vs. Hamiltoniana: Existe uma dicotomia clara. Métodos que garantem cobertura relaxada (como varreduras lineares e STC) têm 0% de sucesso Hamiltoniano na maioria dos casos. Eles falham em evitar revisitas em grafos com gargalos.
• Desempenho Hamiltoniano:
  • A melhor linha de base clássica foi uma variante da regra de Warnsdorff com política Terminal-Inclusive (TI) e desempate por Índice, alcançando 79,0% de sucesso Hamiltoniano.
  • A variante Endpoint-Aware (EP) (que ignora o terminal no cálculo do grau) teve desempenho significativamente pior (47,5% com desempate por índice).
  • O DFS com Backtracking garantiu 100% de cobertura, mas apenas 34,7% de sucesso Hamiltoniano, com alto custo de revisitas.
• Fator Crítico: Política de Grau Residual: O estudo descobriu que a forma como o nó de retorno (terminal) é tratado no cálculo do "grau residual" é o fator dominante.
  • Terminal-Inclusive (TI): Contar o terminal no grau residual (mesmo que não seja um candidato válido) atua como um sinal estrutural latente, evitando que o algoritmo consuma células de corredores críticos adjacentes ao terminal prematuramente.
  • Endpoint-Aware (EP): Ignorar o terminal leva ao consumo prematuro de corredores, resultando em falhas de conectividade.
• Tie-Breaking: O desempate por índice (ordem de construção da grade) superou o desempate por distância euclidiana, sugerindo que a proximidade euclidiana pode tornar a busca excessivamente míope em grafos irregulares.

5. Significado e Conclusão

O artigo demonstra que, em grafos geométricos esparsos e irregulares (comuns em cenários marítimos), detalhes de implementação não reportados podem alterar materialmente o desempenho.

• Para Planejamento Operacional: Se a missão tolera revisitas, métodos de varredura estruturada são superiores em eficiência de caminho. Se a missão exige zero revisitas (ex.: restrições de combustível ou detecção), heurísticas baseadas em grau residual (como Warnsdorff) são necessárias, mas devem ser configuradas com políticas de "Terminal-Inclusive".
• Para Pesquisa Futura: O benchmark serve como um "chão de prova" controlado para analisar falhas qualitativas de heurísticas, separando a inviabilidade do problema da fraqueza do algoritmo.
• Limitação: O estudo foca em agentes estáticos e sintéticos em grafos pequenos (28-46 células). Resultados podem variar em escalas maiores ou com dinâmicas ambientais (correntes, obstáculos móveis).

Em suma, o trabalho estabelece que a definição precisa de como o destino final é considerado durante a exploração local é mais crítica do que a estratégia de desempate para garantir trajetórias Hamiltonianas em grades hexagonais irregulares.