# Planification d'observations sur télescope avec nuits incertaines

Thomas Rahab Lacroix, Pierre Lemaire

► To cite this version:

Thomas Rahab Lacroix, Pierre Lemaire. Planification d'observations sur télescope avec nuits incertaines. Roadef, Feb 2025, Paris, France. hal-04995561

HAL Id: hal-04995561

https://hal.science/hal-04995561v1

Submitted on 18 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Planification d'observations sur télescope avec nuits incertaines

Thomas Rahab Lacroix, Pierre Lemaire

Univ. Grenoble Alpes, CNRS, Grenoble INP, G-SCOP, 38000 Grenoble, France
{thomas.rahab-lacroix, pierre.lemaire}@grenoble-inp.fr

**Mots-clés** : Astronomie, optimisation stochastique, horizon glissant, exoplanètes

## 1 Le problème des astronomers

Nous proposons un problème d'ordonnancement original issu d'une collaboration avec des astronomers de l'Institut de Planétologie et d'Astronomie de Grenoble. Pour faire de l'imagerie directe d'exoplanètes, les télescopes sont rares ; ainsi le VLT (Very Large Telescope) est un des seuls télescopes européens adapté. Cette ressource rare et les très nombreuses cibles célestes intéressantes obligent à calculer un ordonnancement optimisé.

Concrètement, on dispose de *m* nuits pour observer un ensemble de cibles. Chaque cible *j* est qualifiée par un intérêt à priori ($w_j$), une durée d'observation (processing time $p_j$) ainsi qu'une fenêtre de visibilité (release date $r_j$, due date $d_j$). Toutes les nuits sont identiques et il faut maximiser l'intérêt global, le gain. On a donc un problème $P_m|r_j| \sum w_j U_j$.

Ce problème d'ordonnancement déterministe, fortement NP-complet, a déjà été bien étudié (par exemple [2] encore récemment) tandis qu'une version spécifique aux astronomers avec des nuits distinctes a été étudiée dans [3].

Ici, nous considérons un élément nouveau : la météo. La formulation choisie est une simplification de la réalité où l'on considère qu'une nuit est soit parfaite (toutes les observations sont faisables), soit le télescope est fermé. On a alors un problème $P_m|r_j| \sum w_j U_j$ avec *m* incertain. C'est seulement au début de chaque nuit que l'on sait si elle est parfaite ou non.

Nous proposons et discutons différentes approches qui correspondent à autant de visions différentes pour gérer cette incertitude.

## 2 Approches de planifications avec nuits incertaines

Pour toutes les approches, l'ordonnancement est calculé sur les *m* nuits potentielles. Si seulement *k* nuits sont parfaites, alors la fin de la planification n'est pas utilisée. La Figure 1 illustre une instance théorique sur quatre nuits. Chaque marche correspond à une nuit de plus d'observation et sa longueur est la probabilité que cela arrive (obtenue via des prévisions météo). Ainsi, comme le gain est en ordonnées, l'aire sous une courbe est l'espérance, le gain réalisé en moyenne.

**Approche 1** : Glouton. Cela ressemble à ce que les astronomers font actuellement. On planifie chaque nuit comme si c'était la dernière, avec ce qu'il y a de mieux dans ce qui reste à faire. Cette heuristique peut facilement se faire piéger, comme l'illustre la Figure 2 où Glouton met trois nuits à planifier toutes les observations alors que la solution alternative n'en a besoin que de deux. Ainsi si la probabilité que deux nuits soient observables est très élevée, la Figure 2 montre que Glouton a des limites et l'améliorer est bénéfique pour les astronomers.

**Approche 2** : Stochastique. Via un solveur (MILP ou CP), on cherche la solution qui maximise l'espérance. Sur la Figure 1, on observe la courbe Stochastique majoritairement au dessus de Glouton ainsi que son espérance supérieure. Cela prouve l'intérêt de cette approche.

**Approche 3** : Omniscient. Contrairement aux deux autres, sa courbe sur la Figure 1 ne représente pas une solution. Omniscient n'a plus de notion d'incertitude et chaque marche est
la solution optimale pour chaque nombre de nuits possibles. L'écart entre la courbe Omniscient et Stochastique illustre donc le coût de l'incertitude.

<figure><img src="image_2.png" /><figcaption>FIG. 1 – Comparaison des trois approches</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>FIG. 2 – Limite de Glouton</figcaption></figure>

## 3 Version réactive du problème

Il semble pertinent de s'adapter entre les nuits en fonction de leurs observabilités via une méthode d'horizon glissant [1]. A chaque nuit se révélant observable, les probabilités sont mises à jour, l'optimum stochastique est recalculé et la première nuit du nouveau planning est exécutée et ce ainsi de suite. On calcule alors l'espérance réactive de l'ensemble de cette simulation. Cette espérance est toujours supérieure à celle de Stochastique, preuve de l'intérêt d'une approche réactive. La Table 1 montre ce que fait gagner la méthode Réactive par rapport à la méthode Stochastique pour des instances de quatre nuits. Actuellement de l'ordre du pourcent, cette amélioration pourrait devenir bien plus conséquente sur de grandes instances.

<table><caption>TAB. 1 – Comparaison des espérances Réactive et Stochastique</caption><thead><tr><td>Instance</td><td>Espérance Réactive</td><td>Espérance Stochastique</td><td>Amélioration</td></tr></thead><tbody><tr><td>1</td><td>70.81</td><td>70.56</td><td>0.35%</td></tr><tr><td>2</td><td>74.60</td><td>74.35</td><td>0.33%</td></tr><tr><td>3</td><td>78.36</td><td>78.11</td><td>0.32%</td></tr></tbody></table>

## 4 Conclusions et perspectives

Cette étude présente un problème neuf et des techniques pour l'aborder. On découvre l'intérêt d'utiliser des méthodes élaborées, une mesure de l'incertitude et l'amélioration par le réactif. Les perspectives sont de complexifier le modèle pour se rapprocher du problème réel des astronomers.

## Références

[1] Addis B, Carello G, Grosso A et al. *Operating room scheduling and rescheduling: a rolling horizon approach*. Flex Serv Manuf J 28, 206–232 (2016).

[2] Angel E, Bampis E, Chau V, Nguyen KT. *Throughput maximization in multiprocessor speed-scaling*, Theoretical Computer Science, Volume 630, 2016, ISSN 0304-3975.

[3] Catusse et al. *A Branch-and-Price Algorithm for Scheduling Observations on a Telescope*. International Joint Conference on Artificial Intelligence (IJCAI-16), 2016.