Scheduling Telescope Observations for the European Southern Observatory

The European Southern Observatory (ESO) provides a state-of-the-art facility at its site on Paranal, Chile, hosting a variety of instruments (see Figure 1). Astronomers submit proposals for sets of observations on instruments – these proposals are then ranked based on their scientific merit. A schedule is constructed to accommodate the observations from as many proposals as possible, respecting the ranking. This scheduling task is particularly challenging for the Very Large Telescope Interferometer (VLTI). The VLTI combines light from four 8.2 metre Unit Telescopes (UTs) and four movable 1.8 metre Auxiliary Telescopes (ATs) to create a virtual telescope equivalent to the distance between the individual telescopes (called the baseline distance). When scheduling observations on the VLTI, the time taken to reconfigure the baseline must be considered, as well as the need to run various maintenance tasks on individual telescopes making up the array.

ESO uses Savile Row [8] and several of its backends to create a prototype schedule for half a year of observing time using a ranked list of science proposals as input. For each proposal, we try to allocate time on the used telescope taking into account the observability of the targets and any time constraints from the astronomer and also trying to take into account probabilistic observing conditions (e.g. weather) and deterministic conditions, e.g. moon illumination. Only proposals which can fit into the schedule will get observing time. From around 900 proposals per half-year semester, roughly a quarter are accepted and scheduled.

ESO has two sites in Chile hosting various optical telescopes, and jointly operates a radio telescope array at a third site. Of the optical telescope sites, the older site is La Silla (in operation since the late sixties) with the 3.6m telescope and the NTT. The newer site is Paranal with the Very Large Telescope (VLT) consisting of four 8.2m Unit Telescopes (UTs) and four 1.8m Auxiliary Telescopes (ATs). The UTs can work either independently or work together to form an interferometric array (VLTI). When the UTs operate independently, the ATs can be used as VLTI, too. A telescope has several instruments. Each instrument has specific, unique capabilities and cannot easily be moved to another telescope.

VLTI scheduling is the most difficult case (illustrated in Figure 2). Here, all observations carry a grouping tag, specifying the size of the baseline: small, medium, large, extended (all of these use only the ATs; VLTI-AT) or UTs (only the UTs; VLTI-UT). The baseline is the set of physical locations of the ATs. Changing the baseline takes 1 or 2 nights (depending on the two baselines) so observations are grouped accordingly and there must be sufficient time between them. The VLTI schedule must also take all the TTRs into account that need one of the UTs, because during these times one cannot have VLTI-UT observations.

Once the VLTI has been set up with a baseline, it remains in that configuration for a set of nights (named a stretch). Stretches have a minimum length because it is not practical to spend one or two nights setting up a new baseline then using it for a single night. Stretches also have an upper limit designed to avoid making the UTs unavailable for long periods of time and thus blocking other observations (that are not in the VLTI schedule) on the UTs.

There are two periods called imaging slots (given as input) when no VLTI-UT observations occur, and which contain at least one set of nights of each of the VLTI-AT baselines. To find the baseline stretches, we attempt to put all observations somewhere on the calendar.

In this section we describe the most important aspects of each of the constraint models. Full models and all benchmark instances are provided in the experimental repository [10].

We carry out experiments to compare performance across different combinations of the models presented and backend solvers. The models are written in the Essence Prime language [7] which are read by the modelling assistant tool Savile Row [8]. Savile Row is able to tailor models to a variety of back-end solvers, including OR-Tools and SAT. We chose OR-Tools CP-SAT [9] 9.11.4210 as it has been the best all-rounder in recent constraint solving competitions [13] and it implements the DiffN global constraint. We also solve the problem with Savile Row’s SAT output, using Kissat [3] 3.1.1, because in preliminary experiments this approach was usually the fastest in a single-threaded context. We provide the models, instances and software in an online repository [10].

As described in Section 2.1, each solver call is independent, solving the entire instance (i.e. scheduling a concrete set of runs, or finding that no such schedule exists). The approach may seem inefficient but it has two advantages: we do not need to represent all the proposed runs in one constraint optimisation problem (which would be very large and difficult to handle); and each instance can be optimised prior to solving by Savile Row (with a concrete set of runs, i.e. without complications such as optional tasks or reification of constraints between tasks that might hinder pre-solving). Throughout this section we use instance to mean one CSP instance, corresponding to one solver call and one point on the plots below (Figure 3). The instances in the repository represent the progression towards the final schedule, with instances containing incrementally more requested runs to schedule.

The experiments are run on a server with Dual AMD EPYC 7501 2.6GHz processors with 2 $\times$ 64 threads and 2TB RAM, running Ubuntu Linux 22.04.5. To account for randomness in the solvers, each instance is solved 5 times with different random seeds and the median total runtime recorded. We run 231 real half-year instances from ESO with these setups:

• $\mathrm{■}$

  DiffN Model 1 as described in Section 4.2, solved with OR-Tools CP-SAT single-threaded with free search;

• $\mathrm{■}$

  DiffN Model 2 as described in Section 4.2, solved with OR-Tools (as above);

• $\mathrm{■}$

  The basic constraint model, solved with OR-Tools (as above); and

• $\mathrm{■}$

  The basic constraint model encoded by Savile Row into SAT, solved with Kissat.

We also solve 110 synthetic full-year instances (including real science runs and TTRs from two successive half-years, preprocessed as a full year), using the best performing model and solver combinations for the half-year experiment, namely DiffN 1 and SAT. With the full-year instances we found that the relative performance of OR-Tools (single-threaded, free search) was poor for the most challenging instances so we also ran OR-Tools with 16 threads and without free search (because the free search flag causes it to ignore the specified number of threads). In this case we report the total CPU time across all threads.

The experimental results are plotted in Figure 3. We observe that the DiffN 1 model is slightly faster than DiffN 2 on the majority of instances, with an overall geometric mean speedup of 1.38. DiffN 1 also does marginally better than SAT, with an overall speed-up of 1.08; the advantage is more marked in the harder instances, whereas SAT is solving the easy and medium difficulty instances more quickly. The third plot shows that the global constraint model does outperform the one with decomposed non-overlap constraints, being over twice as fast on average. In terms of the full-year instances, single-threaded OR-Tools is struggling to solve the harder instances, with SAT being 1.52 times faster on average. When running OR-Tools with 16 threads, the trend with the most challenging instances is curving away from the $x=y$ line, so it appears that SAT is scaling better overall.

There is a larger proportion of unsatisfiable instances in the half-year schedule; this is explained in part by the fact that some requested targets are barely visible during the half-year period, but there must be a set of nights when they are visible during the full year.

ESO provides state-of-the-art large telescope facilities which astronomers bid to use. They are significantly over-subscribed, leading to scheduling problems where the goal is to make the fullest possible use of the facilities while respecting priority order (based on scientific merit) on the bids. The most challenging scheduling problems arise with the VLTI facility on Paranal, Chile, where there are complex constraints between observation tasks and other tasks, and hundreds of tasks to schedule per half-year. We have presented CP models of the VLTI problem and evaluated their performance with a CP solver and a SAT solver.

The new scheduling approach replaces a laborious and partially manual process with a largely automated one, saving significant time and potentially also allowing more observations to be packed into the schedule. The new system has been in production use since the end of 2023, during which time the CP models have evolved to their current state. Future work includes refining the CP models and SAT encoding, moving to full-year scheduling, and a feasibility study of scheduling more types of observations in one model (for example, individual UT observations combined with VLTI).