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

Resumen Técnico: Hiperheurísticas de Bandido Conscientes del Paisaje para la Selección de Operadores en Línea en la Ruteo de Inspección con UAV

1. Definición del Problema

El artículo aborda el problema de ruteo de inspección multi-sitio con UAV, abstraído como un Problema del Viajante de Comercio Euclidiano (TSP). En este contexto, un UAV debe visitar un conjunto de sitios asignados y regresar a un depósito dentro de una ventana de vuelo limitada. La variable de decisión central es el orden de visita de estos sitios, asumiendo que las preocupaciones de nivel inferior (por ejemplo, control de altitud, evitación de colisiones, tiempos de servicio) se gestionan por separado mediante otros planificadores.

El desafío radica en el hecho de que diferentes paisajes de ruteo (por ejemplo, uniformes, agrupados, tipo corredor, tipo cuadrícula, de densidad mixta) y diferentes etapas del proceso de búsqueda requieren estrategias de optimización distintas. Las heurísticas clásicas a menudo dependen de horarios fijos o selección aleatoria de operadores, lo que puede conducir a ineficiencias como el uso excesivo de un operador que ha dejado de proporcionar mejoras o el desperdicio de evaluaciones en movimientos inadecuados para el estado actual de la búsqueda.

2. Metodología: LA-BHH

Los autores proponen LA-BHH (Hiperheurística de Bandido Consciente del Paisaje), un controlador en línea compacto diseñado para aprender una política de selección de operadores durante una sola ejecución de optimización sin entrenamiento fuera de línea.

• Marco de Hiperheurística: LA-BHH opera a un nivel alto, seleccionando de un portafolio de cuatro operadores de bajo nivel (brazos):
  1. 2-opt: Invierte un segmento del recorrido para eliminar cruces de aristas.
  2. Intercambio (Swap): Intercambia dos sitios de inspección.
  3. Reubicación (Relocate): Mueve un sitio a una posición diferente.
  4. Or-opt-2: Reubica un bloque de dos sitios.
• Controlador de Bandido Contextual: El mecanismo de selección utiliza un algoritmo LinUCB (Límite Superior de Confianza Lineal).
  • Vector de Contexto ($z_t$): El controlador condiciona sus decisiones en un vector de características que comprende:
    • Descriptores Estáticos del Paisaje: Tamaño normalizado del problema, distancia media al vecino más cercano, dispersión, anisotropía de coordenadas, dispersión radial y peso del MST por nodo.
    • Características Dinámicas del Estado de Búsqueda: Progreso del presupuesto, longitud del recorrido actual/mejor en relación con la inicial, mejora reciente, tasa de aceptación e indicadores de estancamiento.
  • Señal de Aprendizaje: La recompensa ($r_t$) es la mejora relativa recortada en la longitud del recorrido producida por el operador seleccionado. Esta recompensa actualiza las estadísticas de regresión de cresta ($A_a, b_a$) para el brazo elegido, permitiendo que el controlador adapte su asignación de crédito en tiempo real.
• Reparación Consciente del Estancamiento: Una característica de diseño específica sesga la selección hacia movimientos 2-opt cuando la búsqueda detecta estancamiento (falta de mejora en una ventana corta). Esto aprovecha la eficacia conocida de 2-opt para la reparación euclidiana sin introducir nuevos tipos de movimientos.
• Estrategia de Aceptación: El método emplea una regla de mejora mejorada codiciosa (greedy best-improvement). Aunque se probó una aceptación estilo recocido simulado como ablación, se encontró que degradaba el rendimiento en estas instancias euclidianas específicas al interrumpir fuertes estructuras de vecino más cercano.

3. Contribuciones Clave

• Aprendizaje en Línea para Ruteo: El artículo demuestra que un controlador en línea compacto puede aprender eficazmente a seleccionar operadores basándose tanto en características estáticas de la instancia como en el progreso dinámico de la búsqueda, eliminando la necesidad de grandes conjuntos de datos fuera de línea o arquitecturas neuronales complejas.
• Asignación de Crédito Contextual: Combina explícitamente descriptores estáticos del paisaje con características de estado de búsqueda en línea para guiar la selección de operadores, mostrando que este contexto es superior a la selección de bandidos no contextuales (UCB-HH) o a la selección aleatoria.
• Manejo del Estancamiento: La integración de una puerta consciente del estancamiento que sesga dinámicamente al controlador hacia movimientos de reparación 2-opt se identifica como un componente crítico para mantener el progreso de la búsqueda.
• Análisis de Ablación: El estudio aísla sistemáticamente las contribuciones de componentes específicos (contexto, características estáticas, características dinámicas, operadores específicos), aclarando que las ganancias de rendimiento provienen de la interacción entre la reparación 2-opt, la asignación de crédito contextual y el uso de estados conscientes del estancamiento.

4. Resultados Experimentales

El método fue evaluado en 45 instancias de TSP euclidianas generadas a través de cinco familias de paisajes (uniforme, agrupado, corredor, cuadrícula con jitter, densidad mixta) y tres tamaños de instancia (50, 100, 200 sitios).

• Métricas de Rendimiento: LA-BHH logró la mejor brecha final media (0.0223) y AUC de convergencia (0.0389) entre todos los métodos comparados.
• Ganancias Comparativas:
  • Redujo la brecha final en un 17.6% en comparación con UCB-HH no contextual.
  • Redujo la brecha final en un 22.6% en comparación con Random-HH.
  • Redujo la brecha final en un 68.2% en comparación con la construcción por Vecino Más Cercano (NN).
• Robustez: LA-BHH superó consistentemente a las líneas base clásicas (incluyendo Recocido Simulado, Algoritmos Genéticos y Búsqueda Local Iterada) en todas las familias de paisajes, demostrando estabilidad en diversos escenarios de despliegue.
• Uso de Operadores: El análisis mostró que, aunque 2-opt fue el operador dominante (especialmente durante el estancamiento), el controlador aprendido utilizó eficazmente intercambio, reubicación y Or-opt-2 para corregir errores de ordenamiento local que 2-opt por sí solo no podía abordar.

5. Significado y Afirmaciones

El artículo presenta a LA-BHH como un estudio de caso práctico para el Diseño de Algoritmos Asistido por Aprendizaje (LEAD) en el dominio del ruteo. Su significado se enmarca en torno a varias afirmaciones modestas pero prácticas:

• Interpretabilidad y Eficiencia: A diferencia de los grandes modelos fuera de línea, LA-BHH es un controlador ligero e inspeccionable que aprende durante una sola ejecución, lo que lo hace adecuado para escenarios donde solo está disponible un pequeño número de instancias relacionadas.
• Rol Complementario: Los autores declaran explícitamente que LA-BHH no pretende reemplazar a los solucionadores de TSP más avanzados (como LKH). En cambio, sirve como una capa de ordenamiento de ruteo que decide cuál operador de búsqueda reutilizable aplicar bajo un presupuesto fijo.
• Escalabilidad: El método es computacionalmente eficiente (solo CPU, complejidad $O(Tn)$) y escala bien desde 50 hasta 200 sitios, manteniendo la competitividad donde las líneas base de búsqueda local clásicas se vuelven menos fiables.
• Aplicabilidad Futura: Los autores sugieren que el marco puede extenderse a la inspección con UAV en el mundo real reemplazando las distancias euclidianas por distancias de camino más corto en grafos de transitabilidad y manejando obstáculos mediante planificadores de nivel inferior, aunque señalan que los experimentos actuales dependen de instancias generadas controladas en lugar de datos recopilados en campo.