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

1. Declaração do Problema

O Problema de Agendamento de Satélites de Observação da Terra (EOSSP) é um desafio crítico de otimização combinatória NP-difícil. À medida que as constelações de satélites evoluem de plataformas únicas para frotas grandes e ágeis, a complexidade do agendamento de tarefas de imageamento aumenta significativamente devido a:

• Agilidade: Satélites de próxima geração podem manobrar (rolagem, arfagem, guinada) para observar alvos fora do nadir, expandindo as oportunidades viáveis, mas introduzindo restrições complexas de transição dependentes do tempo.
• Restrições de Recursos: Energia a bordo limitada, armazenamento e janelas de visibilidade.
• Falta de Padronização: O campo carece de um benchmark unificado e de código aberto. Estudos existentes dependem de instâncias privadas e específicas de problemas, tornando impossível comparar consistentemente algoritmos (Exatos, Heurísticos, Meta-heurísticos e Aprendizado por Reforço Profundo) ou interpretar diferenças de desempenho.
• Métricas Superficiais: Os benchmarks atuais frequentemente dependem apenas de escalas nominais (número de satélites/tarefas) em vez da dificuldade estrutural intrínseca (por exemplo, densidade de oportunidades, intensidade de conflito).

2. Metodologia: O Framework EOS-Bench

O EOS-Bench é um framework unificado e de código aberto projetado para gerar, caracterizar e avaliar cenários de agendamento sistematicamente.

A. Espaço de Cenários e Geração

O framework define um espaço de cenários multidimensional ($\Sigma$) baseado em:

• Tipo de Plataforma: Ágil (manobrável em 3 eixos) vs. Não ágil (fixa no nadir).
• Horizonte de Planejamento: Variando de 1 hora a 7 dias.
• Escala da Constelação: De 1 a 1.000 satélites (usando dados TLE reais para escalas pequenas e constelações sintéticas Walker-Delta para escalas grandes).
• Carga de Missão: 10 a 10.000 tarefas com distribuições variadas (Global-Aleatória, Agrupada por Região, Cidades do Mundo Real).

A biblioteca compreende 1.390 cenários e 13.900 instâncias, divididos em:

• Cenários Padrão (1.104): Variam sistematicamente a escala e a carga para testar a escalabilidade.
• Cenários Específicos (286): Projetados para análise de sensibilidade na capacidade de recursos, manobrabilidade, arquitetura orbital e alvos realistas.

B. Componentes de Modelagem

• Dinâmica de Satélites: Utiliza SGP4 para propagação orbital. Para satélites ágeis, emprega uma função de tempo de transição linear por partes baseada em mudanças angulares (rolagem, arfagem, guinada). Satélites não ágeis usam tempos de transição fixos.
• Visibilidade: Gera janelas de acesso baseadas em linha de visada, campo de visão e restrições de atitude.
• Modelagem de Tarefas: Suporta alvos pontuais com prioridade, lucro e duração. (Versões futuras suportarão alvos de área/faixa).
• Recursos: Unidades normalizadas para consumo de energia e armazenamento.

C. Caracterização de Cenários (Pré-Otimização)

Uma inovação chave é o Esquema de Caracterização de Cenários, que quantifica a dificuldade estrutural intrínseca antes da resolução. Ele agrega descritores em nível de instância em duas perspectivas:

1. Orientado a Tarefas: Oportunidades disponíveis médias, proporção de tarefas restritas, interferência de tarefas e elasticidade.
2. Orientado a Satélites: Concorrência de observação, proporção de satélites em conflito, sobrecarga de cronograma e demanda excedente.
   Isso permite que os pesquisadores entendam por que um cenário é difícil (por exemplo, é devido a oportunidades esparsas ou alta congestão temporal?).

D. Protocolo de Avaliação

O EOS-Bench utiliza um sistema de métricas de cinco dimensões para evitar viés de pontuação única:

1. Lucro da Tarefa (TP): Valor total das tarefas concluídas.
2. Taxa de Conclusão de Tarefas (TCR): Fração de tarefas concluídas.
3. Grau de Equilíbrio (BD): Justiça na distribuição da carga de trabalho entre os satélites.
4. Pontualidade (TM): Quão cedo as tarefas são executadas.
5. Tempo de Execução (RT): Tempo computacional (tempo real).

3. Contribuições Principais

1. Benchmark Unificado e Aberto: O primeiro framework abrangente e de código aberto que suporta plataformas ágeis e não ágeis em escalas de 1 a 1.000 satélites.
2. Caracterização Estrutural: Introduz um framework matemático para quantificar a dificuldade do cenário além do tamanho nominal, distinguindo entre problemas "esparsos em oportunidades" e "pesados em congestionamento".
3. Avaliação Multidimensional: Estabelece um protocolo padronizado usando cinco métricas complementares, permitindo uma análise transparente de trade-offs entre qualidade da solução, equidade, pontualidade e velocidade.
4. Avaliação Exaustiva de Baselines: Fornece uma análise comparativa de 17 algoritmos, incluindo:
   • Exatos: Programação Inteira Mista (MIP).
   • Construtivos: Heurísticas gananciosas.
   • Meta-heurísticas: Algoritmos Genéticos (GA), Recozimento Simulado (SA), Otimização por Colônia de Formigas (ACO).
   • Baseados em Aprendizado: Aprendizado por Reforço Profundo (PPO).
5. Visualização: Inclui um motor de visualização 3D interativo (CesiumJS) para análise espaço-temporal de agendamentos.

4. Resultados Experimentais

Os autores avaliaram o framework em um subconjunto de 2.500 instâncias (96 Padrão, 154 Específicas). As principais descobertas incluem:

• Escalabilidade e Comportamento do Solucionador:

  • Escala Pequena: Solucionadores MIP fornecem baselines ótimas; meta-heurísticas (SA, ACO) performam competitivamente.
  • Escala Grande: Métodos exatos tornam-se intratáveis. Meta-heurísticas mantêm alta qualidade de solução, mas sofrem com alto tempo de execução. O Aprendizado por Reforço (RL) oferece um trade-off equilibrado, fornecendo qualidade quase ótima com tempo de inferência significativamente menor comparado a métodos de busca iterativa.
  • Heurísticas Gananciosas: Rápidas, mas lutam com cenários complexos e de alto conflito, frequentemente falhando em equilibrar a carga de trabalho ou maximizar o lucro.

• Sensibilidade Estrutural:

  • Agilidade: Maior manobrabilidade melhora as taxas de conclusão de tarefas para algoritmos gananciosos, mas mostra retornos decrescentes para o lucro global em clusters densos.
  • Arquitetura Orbital: Constelações "Poucos Planos" (densas) aumentam o congestionamento local e a sobrecarga de cronograma, enquanto "Muitos Planos" (esparso) melhoram a pontualidade ao reduzir tempos de espera.
  • Distribuição de Alvos: Alvos agrupados por região criam proporções de conflito e congestionamento de cronograma significativamente maiores em comparação com distribuições globais-aleatórias, reduzindo drasticamente o desempenho do solucionador.

• Restrições de Recursos: Capacidades de recursos heterogêneas (gerações mistas de satélites) favorecem métodos adaptativos (SA, RL) sobre abordagens gananciosas, que tendem a comprometer-se excessivamente com nós de alta capacidade.

5. Significado

O EOS-Bench aborda uma lacuna crítica na comunidade do EOSSP, afastando-se de benchmarks fragmentados e privados em direção a um ecossistema reprodutível e padronizado.

• Para Pesquisadores: Fornece um campo de testes rigoroso para validar novos algoritmos contra cenários diversos e estruturalmente caracterizados, garantindo que os ganhos de desempenho sejam genuínos e não artefatos da construção de instâncias específicas.
• Para Praticantes: A avaliação multi-métrica ajuda a identificar algoritmos adequados para necessidades operacionais específicas (por exemplo, velocidade vs. optimalidade).
• Impacto Futuro: O framework é extensível para incluir alvos de área regional, cargas úteis diversas (SAR, LiDAR), constelações heterogêneas e autonomia a bordo sob incerteza, abrindo caminho para o planejamento de missões espaciais de próxima geração.

O código e os dados estão disponíveis publicamente em https://github.com/Ethan19YQ/EOS-Bench.