Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

Resumo Técnico: Hiper-heurísticas de Bandido Conscientes da Paisagem para Seleção Online de Operadores em Roteamento de Inspeção por UAV

1. Definição do Problema

O artigo aborda o problema de roteamento de inspeção multi-local por UAV, abstraído como um Problema do Caixeiro Viajante Euclidiano (TSP). Neste contexto, um UAV deve visitar um conjunto de locais atribuídos e retornar a um depósito dentro de uma janela de voo limitada. A variável de decisão central é a ordem de visita desses locais, assumindo que preocupações de nível inferior (por exemplo, controle de altitude, evitamento de colisões, tempos de serviço) são tratadas separadamente por outros planejadores.

O desafio reside no fato de que diferentes paisagens de roteamento (por exemplo, uniformes, agrupadas, em corredor, em grade, de densidade mista) e diferentes estágios do processo de busca exigem estratégias de otimização distintas. Heurísticas clássicas frequentemente dependem de cronogramas fixos ou seleção aleatória de operadores, o que pode levar a ineficiências, como o uso excessivo de um operador que deixou de proporcionar melhorias ou o desperdício de avaliações em movimentos inadequados ao estado atual da busca.

2. Metodologia: LA-BHH

Os autores propõem o LA-BHH (Hiper-heurística de Bandido Consciente da Paisagem), um controlador online compacto projetado para aprender uma política de seleção de operadores durante uma única execução de otimização, sem treinamento offline.

• Framework de Hiper-heurística: O LA-BHH opera em um nível superior, selecionando de um portfólio de quatro operadores de baixo nível (braços):
  1. 2-opt: Inverte um segmento de tour para remover cruzamentos de arestas.
  2. Swap: Troca dois locais de inspeção.
  3. Relocate: Move um local para uma posição diferente.
  4. Or-opt-2: Realoca um bloco de dois locais.
• Controlador de Bandido Contextual: O mecanismo de seleção utiliza um algoritmo LinUCB (Limite Superior de Confiança Linear).
  • Vetor de Contexto ($z_t$): O controlador condiciona suas decisões a um vetor de características composto por:
    • Descritores Estáticos da Paisagem: Tamanho normalizado do problema, distância média ao vizinho mais próximo, dispersão, anisotropia de coordenadas, dispersão radial e peso da MST por nó.
    • Características Dinâmicas do Estado de Busca: Progresso do orçamento, comprimento do tour atual/melhor em relação ao inicial, melhoria recente, taxa de aceitação e indicadores de estagnação.
  • Sinal de Aprendizado: A recompensa ($r_t$) é a melhoria relativa truncada no comprimento do tour produzida pelo operador selecionado. Essa recompensa atualiza as estatísticas de regressão ridge ($A_a, b_a$) para o braço escolhido, permitindo que o controlador adapte sua atribuição de crédito em tempo real.
• Reparo Consciente de Estagnação: Uma característica de design específica viésa a seleção para movimentos 2-opt quando a busca detecta estagnação (falta de melhoria em uma janela curta). Isso aproveita a eficácia conhecida do 2-opt para reparo euclidiano sem introduzir novos tipos de movimento.
• Estratégia de Aceitação: O método emprega uma regra de melhor melhoria gananciosa. Embora a aceitação no estilo de recozimento tenha sido testada como ablação, constatou-se que ela degrada o desempenho nestas instâncias euclidianas específicas ao perturbar estruturas fortes de vizinhos mais próximos.

3. Contribuições Principais

• Aprendizado Online para Roteamento: O artigo demonstra que um controlador online compacto pode aprender efetivamente a selecionar operadores com base tanto em características estáticas da instância quanto no progresso dinâmico da busca, eliminando a necessidade de grandes conjuntos de dados offline ou arquiteturas neurais complexas.
• Atribuição de Crédito Contextual: Combina explicitamente descritores estáticos da paisagem com características de estado de busca online para guiar a seleção de operadores, mostrando que esse contexto é superior à seleção de bandidos não contextuais (UCB-HH) ou à seleção aleatória.
• Tratamento de Estagnação: A integração de um portão consciente de estagnação que viésa dinamicamente o controlador para movimentos de reparo 2-opt é identificada como um componente crítico para manter o progresso da busca.
• Análise de Ablação: O estudo isola sistematicamente as contribuições de componentes específicos (contexto, características estáticas, características dinâmicas, operadores específicos), esclarecendo que os ganhos de desempenho decorrem da interação entre reparo 2-opt, atribuição de crédito contextual e uso de estado consciente de estagnação.

4. Resultados Experimentais

O método foi avaliado em 45 instâncias de TSP euclidiano geradas em cinco famílias de paisagens (uniforme, agrupada, corredor, grade com jitter, densidade mista) e três tamanhos de instância (50, 100, 200 locais).

• Métricas de Desempenho: O LA-BHH alcançou a melhor lacuna final média (0,0223) e AUC de convergência (0,0389) entre todos os métodos comparados.
• Ganhos Comparativos:
  • Redução da lacuna final em 17,6% em comparação com o UCB-HH não contextual.
  • Redução da lacuna final em 22,6% em comparação com o Random-HH.
  • Redução da lacuna final em 68,2% em comparação com a construção por Vizinho Mais Próximo (NN).
• Robustez: O LA-BHH superou consistentemente as bases clássicas (incluindo Recozimento Simulado, Algoritmos Genéticos e Busca Local Iterada) em todas as famílias de paisagens, demonstrando estabilidade em diversos cenários de implantação.
• Uso de Operadores: A análise mostrou que, embora o 2-opt tenha sido o operador dominante (especialmente durante a estagnação), o controlador aprendido utilizou efetivamente swap, relocate e Or-opt-2 para corrigir erros de ordenação local que o 2-opt sozinho não poderia resolver.

5. Significado e Alegações

O artigo posiciona o LA-BHH como um estudo de caso prático para Design de Algoritmos Assistido por Aprendizado (LEAD) no domínio de roteamento. Seu significado é enquadrado em torno de várias alegações modestas, mas práticas:

• Interpretabilidade e Eficiência: Ao contrário de grandes modelos offline, o LA-BHH é um controlador leve e inspecionável que aprende durante uma única execução, tornando-o adequado para cenários onde apenas um pequeno número de instâncias relacionadas está disponível.
• Papel Complementar: Os autores afirmam explicitamente que o LA-BHH não tem a intenção de substituir solucionadores de TSP de última geração (como o LKH). Em vez disso, serve como uma camada de ordenação de roteamento que decide qual operador de busca reutilizável aplicar sob um orçamento fixo.
• Escalabilidade: O método é computacionalmente eficiente (apenas CPU, complexidade $O(Tn)$) e escala bem de 50 a 200 locais, mantendo competitividade onde as bases de busca local clássicas se tornam menos confiáveis.
• Aplicabilidade Futura: Os autores sugerem que o framework pode ser estendido para inspeção real por UAV substituindo distâncias euclidianas por distâncias de caminho mais curto em grafos de transitabilidade e lidando com obstáculos por meio de planejadores de nível inferior, embora observem que os experimentos atuais dependem de instâncias geradas controladas em vez de dados coletados em campo.