EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling

Aquí se presenta un resumen técnico detallado del artículo "EOS-Bench: Un Benchmark Integral para la Programación de Satélites de Observación Terrestre."

1. Planteamiento del Problema

El Problema de Programación de Satélites de Observación Terrestre (EOSSP) es un desafío crítico de optimización combinatoria NP-difícil. A medida que las constelaciones de satélites evolucionan desde plataformas individuales hasta flotas grandes y ágiles, la complejidad de la programación de tareas de imagen aumenta significativamente debido a:

• Agilidad: Los satélites de próxima generación pueden maniobrar (rodar, cabecear, alabeo) para observar objetivos fuera del nadir, expandiendo las oportunidades factibles pero introduciendo complejas restricciones de transición dependientes del tiempo.
• Restricciones de Recursos: Energía, almacenamiento y ventanas de visibilidad limitadas a bordo.
• Falta de Estandarización: El campo carece de un benchmark unificado y de código abierto. Los estudios existentes dependen de instancias privadas y específicas del problema, lo que hace imposible comparar consistentemente los algoritmos (Exactos, Heurísticos, Metaheurísticos y Aprendizaje por Refuerzo Profundo) o interpretar las diferencias de rendimiento.
• Métricas Superficiales: Los benchmarks actuales a menudo dependen únicamente de escalas nominales (número de satélites/tareas) en lugar de la dificultad estructural intrínseca (por ejemplo, densidad de oportunidades, intensidad de conflictos).

2. Metodología: El Marco EOS-Bench

EOS-Bench es un marco unificado y de código abierto diseñado para generar, caracterizar y evaluar escenarios de programación de manera sistemática.

A. Espacio de Escenarios y Generación

El marco define un espacio de escenarios multidimensional ($\Sigma$) basado en:

• Tipo de Plataforma: Ágil (maniobrable en 3 ejes) vs. No ágil (fija al nadir).
• Horizonte de Planificación: Desde 1 hora hasta 7 días.
• Escala de Constelación: Desde 1 hasta 1,000 satélites (utilizando datos TLE reales para escalas pequeñas y constelaciones sintéticas Walker-Delta para escalas grandes).
• Carga de Misión: 10 a 10,000 tareas con distribuciones variables (Global-Aleatoria, Agrupada por Región, Ciudades del Mundo Real).

La biblioteca comprende 1,390 escenarios y 13,900 instancias, divididas en:

• Escenarios Estándar (1,104): Varían sistemáticamente la escala y la carga para probar la escalabilidad.
• Escenarios Específicos (286): Diseñados para el análisis de sensibilidad sobre la capacidad de recursos, maniobrabilidad, arquitectura orbital y objetivos realistas.

B. Componentes de Modelado

• Dinámica de Satélites: Utiliza SGP4 para la propagación orbital. Para satélites ágiles, emplea una función de tiempo de transición lineal por tramos basada en cambios angulares (rodar, cabecear, alabeo). Los satélites no ágiles utilizan tiempos de transición fijos.
• Visibilidad: Genera ventanas de acceso basadas en la línea de visión, campo de visión y restricciones de actitud.
• Modelado de Tareas: Soporta objetivos puntuales con prioridad, beneficio y duración. (Las versiones futuras soportarán objetivos de área/tira).
• Recursos: Unidades normalizadas para el consumo de energía y almacenamiento.

C. Caracterización de Escenarios (Pre-Optimización)

Una innovación clave es el Esquema de Caracterización de Escenarios, que cuantifica la dificultad estructural intrínseca antes de resolverlo. Agrega descriptores a nivel de instancia en dos perspectivas:

1. Orientado a Tareas: Promedio de oportunidades disponibles, ratio de tareas restringidas, interferencia de tareas y elasticidad.
2. Orientado a Satélites: Contención de observación, ratio de satélites en conflicto, sobrecarga de línea temporal y demanda excesiva.
   Esto permite a los investigadores comprender por qué un escenario es difícil (por ejemplo, ¿se debe a oportunidades escasas o a una alta congestión temporal?).

D. Protocolo de Evaluación

EOS-Bench utiliza un sistema de métricas de cinco dimensiones para evitar el sesgo de una sola puntuación:

1. Beneficio de Tarea (TP): Valor total de las tareas completadas.
2. Tasa de Completación de Tareas (TCR): Fracción de tareas completadas.
3. Grado de Equilibrio (BD): Equidad en la distribución de la carga de trabajo entre satélites.
4. Oportunidad (TM): Qué tan temprano se ejecutan las tareas.
5. Tiempo de Ejecución (RT): Tiempo computacional (reloj de pared).

3. Contribuciones Clave

1. Benchmark Unificado de Código Abierto: El primer marco integral y de código abierto que soporta tanto plataformas ágiles como no ágiles en escalas desde 1 hasta 1,000 satélites.
2. Caracterización Estructural: Introduce un marco matemático para cuantificar la dificultad de los escenarios más allá del tamaño nominal, distinguiendo entre problemas "con oportunidades escasas" y "con alta congestión".
3. Evaluación Multidimensional: Establece un protocolo estandarizado utilizando cinco métricas complementarias, permitiendo un análisis transparente de compensaciones entre calidad de la solución, equidad, oportunidad y velocidad.
4. Evaluación de Línea Base Extensa: Proporciona un análisis comparativo de 17 algoritmos, incluyendo:
   • Exactos: Programación Entera Mixta (MIP).
   • Constructivos: Heurísticas voraces.
   • Metaheurísticas: Algoritmos Genéticos (GA), Recocido Simulado (SA), Optimización por Colonia de Hormigas (ACO).
   • Basados en Aprendizaje: Aprendizaje por Refuerzo Profundo (PPO).
5. Visualización: Incluye un motor de visualización 3D interactivo (CesiumJS) para el análisis espacio-temporal de las programaciones.

4. Resultados Experimentales

Los autores evaluaron el marco en un subconjunto de 2,500 instancias (96 Estándar, 154 Específicas). Los hallazgos clave incluyen:

• Escalabilidad y Comportamiento del Solucionador:

  • Escala Pequeña: Los solucionadores MIP proporcionan líneas base óptimas; las metaheurísticas (SA, ACO) se desempeñan de manera competitiva.
  • Escala Grande: Los métodos exactos se vuelven intratables. Las metaheurísticas mantienen una alta calidad de solución pero sufren de un tiempo de ejecución alto. El Aprendizaje por Refuerzo (RL) ofrece un equilibrio compensado, proporcionando calidad casi óptima con un tiempo de inferencia significativamente menor en comparación con los métodos de búsqueda iterativa.
  • Heurísticas Voraces: Rápidas pero luchan con escenarios complejos y de alto conflicto, a menudo fallando en equilibrar la carga de trabajo o maximizar el beneficio.

• Sensibilidad Estructural:

  • Agilidad: Una mayor maniobrabilidad mejora las tasas de completación de tareas para algoritmos voraces, pero muestra rendimientos decrecientes para el beneficio global en grupos densos.
  • Arquitectura Orbital: Las constelaciones "Pocos Planos" (densas) aumentan la congestión local y la sobrecarga de la línea temporal, mientras que las "Muchos Planos" (escasas) mejoran la oportunidad al reducir los tiempos de espera.
  • Distribución de Objetivos: Los objetivos agrupados por región crean ratios de conflicto y congestión de línea temporal significativamente más altos en comparación con las distribuciones globales aleatorias, reduciendo drásticamente el rendimiento del solucionador.

• Restricciones de Recursos: Las capacidades de recursos heterogéneas (mezcla de generaciones de satélites) favorecen métodos adaptativos (SA, RL) sobre enfoques voraces, que tienden a comprometerse en exceso con nodos de alta capacidad.

5. Significado

EOS-Bench aborda una brecha crítica en la comunidad del EOSSP al alejarse de benchmarks fragmentados y privados hacia un ecosistema reproducible y estandarizado.

• Para Investigadores: Proporciona un banco de pruebas riguroso para validar nuevos algoritmos frente a escenarios diversos y estructuralmente caracterizados, asegurando que las ganancias de rendimiento sean genuinas y no artefactos de la construcción específica de instancias.
• Para Practicantes: La evaluación de múltiples métricas ayuda a identificar algoritmos adecuados para necesidades operativas específicas (por ejemplo, velocidad vs. optimalidad).
• Impacto Futuro: El marco es extensible para incluir objetivos de área regionales, cargas útiles diversas (SAR, LiDAR), constelaciones heterogéneas y autonomía a bordo bajo incertidumbre, allanando el camino para la planificación de misiones espaciales de próxima generación.

El código y los datos están disponibles públicamente en https://github.com/Ethan19YQ/EOS-Bench.