Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach

Cet article propose une approche d'acquisition active de contraintes, nommée CCA et intégrée au cadre « Learn & Optimize », pour optimiser les calendriers de satellites d'observation de la Terre en apprenant interactivement des contraintes opérationnelles inconnues via un oracle binaire, surpassant ainsi les méthodes baselines en termes de qualité de solution et d'efficacité des requêtes.

L'essentiel

🌍 Le Défi : Prendre des photos depuis l'espace sans connaître les règles du jeu

Imaginez que vous êtes le chef d'orchestre d'un satellite qui tourne autour de la Terre. Votre mission est de prendre des photos de villes, de forêts ou d'océans. Chaque photo a une "valeur" (une ville importante vaut plus qu'un champ vide). Votre but est simple : prendre le maximum de photos valables possibles.

Mais il y a un gros problème : vous ne connaissez pas toutes les règles de sécurité du satellite.

Dans les méthodes classiques, on suppose que l'on a un manuel d'instructions parfait qui dit : "Pour aller de Paris à Tokyo, il faut 3 minutes de rotation" ou "La batterie ne peut supporter que 5 photos par heure".

La réalité est différente :

• Ces règles sont cachées dans des logiciels complexes, des schémas d'ingénieurs ou des simulateurs physiques.
• Elles changent avec le temps (la batterie vieillit, le logiciel se met à jour).
• Parfois, personne n'a même écrit ces règles sous forme de mathématiques.

Si vous demandez au satellite : "Peut-on prendre la photo A puis la photo B ?", le satellite ne vous dira pas "Non, parce que la règle X est violée". Il vous dira juste un simple "Non" (ou "Oui"). C'est comme si vous essayiez de cuisiner un plat sans recette, en goûtant à chaque fois et en vous disant "Ah, c'est trop salé", sans savoir exactement combien de sel vous avez mis.

🔍 La Solution : Apprendre en faisant (L'approche "Apprendre & Optimiser")

Les chercheurs (Mohamed-Bachir Belaid et son équipe) ont proposé une nouvelle méthode appelée L&O (Learn & Optimize). Au lieu d'attendre d'avoir écrit tout le manuel d'instructions avant de commencer, ils apprennent les règles pendant qu'ils essaient de faire le meilleur emploi du temps possible.

Voici comment cela fonctionne, avec une analogie simple :

1. Le Jeu de l'Échec et du "Non"

Imaginez que vous jouez aux échecs contre un adversaire qui ne vous dit jamais pourquoi il gagne, juste "Échec".

• L'ancienne méthode (FAO) : Vous passez 100 coups à essayer de deviner toutes les règles du jeu, puis vous jouez votre meilleure partie.
• La nouvelle méthode (L&O) : Vous jouez une partie. Si vous perdez, vous demandez : "Pourquoi ?". L'adversaire dit "Non". Vous déduisez une petite règle (ex: "Ah, les cavaliers ne peuvent pas sauter par-dessus les tours ici"). Vous ajustez votre stratégie immédiatement et vous rejouez.

2. L'Acquisition Conservatrice (CCA) : Le détective prudent

Le papier introduit une technique spéciale appelée CCA. C'est comme un détective très prudent.
Quand le satellite dit "Non" à un plan, le détective ne devine pas n'importe quoi. Il pose des questions ciblées pour trouver la règle la plus stricte qui explique le refus.

• Exemple : Si le satellite refuse de prendre deux photos trop proches, le détective teste : "Est-ce qu'il faut 2 minutes de pause ? Non. 3 minutes ? Non. 4 minutes ? Non."
• Il apprend alors : "Bon, il faut au moins 4 minutes".
• Le piège (et la sécurité) : Parfois, le détective se trompe et pense qu'il faut 4 minutes alors qu'en réalité, c'était juste la batterie qui était pleine. Il va donc apprendre une règle un peu trop stricte ("4 minutes"). Ce n'est pas grave ! Cela rend le satellite plus prudent, mais il ne risque pas de casser. C'est ce qu'ils appellent une approche "conservatrice".

🚀 Les Résultats : Plus rapide et presque aussi bon

Les chercheurs ont testé cela sur des simulations avec jusqu'à 50 tâches (photos). Voici ce qu'ils ont découvert :

1. Moins de questions, plus de résultats : La méthode traditionnelle posait 100 questions pour apprendre les règles, puis essayait de résoudre le problème. La nouvelle méthode (L&O) trouve souvent une très bonne solution après seulement 5 à 20 questions.
2. Gain de temps énorme : Parce qu'ils n'attendent pas la fin de l'apprentissage pour agir, ils sont 5 fois plus rapides. C'est comme si vous aviez trouvé un bon itinéraire de voyage en 10 minutes au lieu de passer une heure à étudier la carte routière complète.
3. On n'a pas besoin de tout savoir : Le résultat le plus surprenant ? Pour avoir un excellent emploi du temps, il n'est pas nécessaire de connaître toutes les règles cachées. Il suffit d'apprendre les quelques règles qui empêchent les "mauvaises" combinaisons. Même si le détective se trompe sur certains détails (en étant trop prudent), il réussit quand même à trouver la meilleure solution possible.

🎯 En résumé

Ce papier nous dit que pour gérer des satellites complexes dont on ne connaît pas toutes les limites techniques, il ne faut pas essayer de tout comprendre avant d'agir.

Il faut agir, tester, apprendre des erreurs, et recommencer. C'est une méthode interactive qui apprend les règles "sur le tas", comme un apprenti pilote qui apprend à piloter en vol plutôt qu'en lisant uniquement le manuel théorique.

L'analogie finale :
C'est la différence entre un cuisinier qui passe 2 heures à lire un livre de cuisine parfait avant de toucher une casserole (méthode ancienne), et un chef étoilé qui goûte sa sauce, ajuste le sel, goûte encore, et ajuste le poivre, tout en cuisinant, pour obtenir le plat parfait beaucoup plus vite (méthode L&O).

Résumé technique

1. Problématique : Planification de Satellites d'Observation de la Terre (EO) sous Contraintes Inconnues

Contexte :
La planification des satellites d'observation de la Terre (EO) consiste à décider quels objectifs photographier et à quel moment, afin de maximiser la priorité totale des tâches observées. Ce problème est un problème d'optimisation combinatoire classique.

Le Défi :
Les méthodes existantes supposent que le modèle de contraintes opérationnelles (temps de séparation entre observations, budgets énergétiques, limites thermiques) est entièrement spécifié à l'avance sous forme mathématique. Cependant, en pratique :

• Ces contraintes sont souvent intégrées dans des artefacts d'ingénierie, des firmwares ou des simulateurs haute fidélité, et non dans des modèles explicites.
• Elles évoluent au cours de la mission (dégradation des batteries, mises à jour logicielles).
• Pour les nouvelles missions, aucun modèle validé n'existe encore.

L'Approche Proposée :
Les auteurs considèrent un scénario où le modèle de contraintes est inconnu. L'objectif est connu, mais la faisabilité d'un planning doit être apprise de manière interactive via un oracle binaire. Cet oracle (généralement un simulateur de satellite) renvoie uniquement « OUI » (faisable) ou « NON » (non faisable) pour un planning proposé, sans indiquer quelle contrainte spécifique a été violée ni pourquoi.

2. Méthodologie

Le papier propose un cadre combinant l'apprentissage de contraintes et l'optimisation, basé sur le framework Learn&Optimize (L&O).

A. Modélisation Simplifiée (EOSP-UC)

Pour rendre le problème traitable, les auteurs se concentrent sur deux familles de contraintes dominantes :

1. Séparation (sep) : Contrainte de temps minimale entre deux tâches $i$ et $j$ si elles sont toutes deux planifiées ($|x_i - x_j| \ge \delta$).
2. Capacité (cap) : Limite globale sur le nombre de tâches planifiables dans une fenêtre glissante de $w$ slots ($k$ tâches max).

Le langage de contraintes $L$ est connu, mais les paramètres exacts (les valeurs de $\delta$, $k$, $w$) sont cachés dans un ensemble de candidats $B$.

B. Acquisition Conservatrice de Contraintes (CCA)

C'est le cœur de la contribution méthodologique. Contrairement aux algorithmes génériques d'acquisition (comme QuAcq), la CCA est une procédure spécifique au domaine conçue pour la structure de séparation/capacité.

• Principe de conservatisme : Lorsqu'un planning est rejeté par l'oracle, la CCA ne tente pas de reconstruire le modèle exact immédiatement. Elle utilise des requêtes partielles (sous-ensembles de tâches) pour identifier la contrainte la plus forte justifiée par le rejet.
• Stratégie :
  1. Pour les paires de tâches en conflit, elle effectue une recherche binaire sur les valeurs de séparation possibles pour trouver le $\delta$ maximal justifié.
  2. Si aucune séparation n'est justifiée, elle tombe sur une contrainte de capacité (la plus faible violée).
  3. Elle ajoute cette contrainte au modèle appris $L$ et élimine les candidats dominés de la base $B$.
• Note importante : La CCA peut apprendre des contraintes « trop serrées » (over-tightened). Par exemple, si un rejet est dû à une contrainte de capacité mais que l'algorithme l'attribue à la séparation, il apprendra une séparation plus stricte que la réalité. Cela rend le modèle appris plus restrictif, mais garantit souvent la faisabilité.

C. Framework Learn&Optimize (L&O)

L'algorithme alterne itérativement entre :

1. Optimisation : Résolution du problème de planification sous le modèle de contraintes appris actuel $L$ (via un solveur CP-SAT).
2. Vérification : Interrogation de l'oracle sur le planning obtenu.
3. Apprentissage : Si l'oracle rejette le planning, la CCA met à jour $L$ et réduit $B$.
4. Arrêt : Le processus s'arrête dès qu'un planning proposé par le solveur est accepté par l'oracle, ou si la base de candidats est épuisée.

3. Contributions Clés

1. Formulation EOSP-UC : Introduction d'un nouveau problème de planification EO où les contraintes sont cachées derrière un oracle binaire.
2. Algorithme CCA : Développement d'une procédure d'acquisition spécifique au domaine, exploitant la structure ordonnée des contraintes de séparation et de capacité, plus efficace que les méthodes génériques pour ce contexte.
3. Intégration L&O : Démonstration que l'interleaving (entrelacement) de l'acquisition et de l'optimisation permet de trouver de bonnes solutions sans attendre l'acquisition complète du modèle.
4. Évaluation Empirique : Premiers résultats sur des instances synthétiques montrant que l'on peut obtenir des solutions quasi-optimales avec très peu de contraintes exactement identifiées.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances synthétiques avec $n \in \{10, 20, 30, 40, 50\}$ tâches et des réseaux de contraintes denses.

Comparaison des Méthodes :

• PG (Priorité Greedy) : Base de référence sans connaissance des contraintes (Gap moyen de 65-73%).
• FAO (Full Acquire-then-Optimise) : Acquisition complète (100 requêtes) suivie d'une optimisation.
• L&O (Learn&Optimize) : Approche proposée.

Résultats Principaux :

• Qualité de la solution : Pour $n \le 30$, L&O réduit l'écart (gap) par rapport à l'optimum de 65-68% (Greedy) à 17,7% - 35,8%. Pour $n=50$, L&O surpasse FAO avec un écart moyen de 17,9% contre 20,3% pour FAO.
• Efficacité des requêtes : L&O trouve sa meilleure solution en moyenne après seulement 5 à 21 requêtes principales (selon la taille $n$), tandis que FAO utilise systématiquement 100 requêtes avant de résoudre.
• Temps d'exécution : L&O est considérablement plus rapide. À $n=50$, L&O est environ 5 fois plus rapide que FAO (130s vs 695s).
• Apprentissage partiel : Un résultat frappant est que la meilleure solution est souvent trouvée alors que seulement 4% à 10% des contraintes cachées ont été exactement identifiées. Cela démontre qu'il n'est pas nécessaire de reconstruire le modèle complet pour obtenir une solution de haute qualité ; il suffit d'identifier les contraintes qui éliminent les candidats les plus prometteurs mais non réalisables.

5. Signification et Conclusion

Ce travail représente la première application de l'acquisition active de contraintes à la planification de satellites EO.

Implications majeures :

• Pragmatisme opérationnel : Il est possible de planifier efficacement des missions complexes même sans modèle de contraintes explicite, en utilisant simplement un simulateur comme oracle.
• Efficacité du temps réel : L'approche « anytime » (L&O) permet d'arrêter le processus dès qu'une solution acceptable est trouvée, évitant le gaspillage de temps de calcul et de ressources de simulation (requêtes oracle) nécessaire pour un apprentissage exhaustif.
• Robustesse : La méthode tolère l'apprentissage de contraintes « sur-estimées » (conservatrices), ce qui, bien que pouvant exclure certaines solutions théoriques, garantit la faisabilité opérationnelle et guide le solveur vers des solutions robustes.

Limites et Perspectives :
L'étude se limite actuellement à un modèle simplifié (séparation et capacité) et suppose un oracle parfait et stationnaire. Les travaux futurs visent à intégrer des familles de contraintes plus riches, à gérer le bruit et la dérive des contraintes, et à valider la méthode sur des jeux de données réels de satellites.