About this Article

The SPIKE system is a software tool kit for planning and scheduling astronomical observations that was built at the Institute for Hubble long-range planning and is in the final stages of preparation for use with JWST. This article reviews Artificial Intelligence (AI)-based techniques that SPIKE incorporates to produce plans and schedules for these missions.

During World War Ⅱ the field of Operations Research developed techniques, such as integer programming, for solving logistical optimization problems like managing supply chains and scheduling. AI search algorithms were born out of the shortcomings of these techniques. A first problem faced by operations research techniques was that scheduling problems often have a very large space of solutions to optimize. Consider that scheduling involves ordering objects and that given N objects there are N! different orderings (i.e., N * N – 1 * N – 2 … * 1).  So for a typical Hubble cycle of 4,500 visits, there are ~2 × 10¹⁴⁴⁸⁷ different orderings. In contrast, the estimated number of stars in the universe is 10²¹.  This computational explosion prevented operations research techniques from being directly used and motivated the use of heuristic search strategies.  A second problem for classical operations research techniques was that in many scheduling problems the goal to be solved is itself fuzzy and cannot be quantified in a form that can be used for optimization software. Below, I show how AI related techniques have been incorporated into the SPIKE system to handle these problems.

AI search algorithms can be divided into those using a systematic approach to explore a problem space versus those that use stochastic methods to randomly explore the space. SPIKE incorporates both approaches in its toolbox. The basic idea of systematic search algorithms is to use heuristic rules that embed knowledge about what makes a good schedule to guide the system towards better or good enough solutions. A common systematic approach is greedy search. In this approach, the scheduler iterates through all observations to be scheduled, choosing a time for each observation. Heuristics are used to drive the ordering in which observations are considered, and the assignment of a time for each observation. Each choice is greedily made based on the current state of the schedule. For example, a greedy search will often pick the most constrained observations to schedule first and pick a time for the observation based on an estimated least amount of congestion. An augmentation of this approach is guess-and-repair algorithms. First, an initial guess does a greedy search for all observations and then another set of heuristics is used to repair the schedule. SPIKE provides multiple methods for guess-and-repair schedules. In the conflict counting approach, the initial guess creates a schedule which greedily selects times with minimal conflicts for each observation (i.e., observations scheduled at the same time). The repair phase then attempts to remove conflicts by moving observations with the highest number of conflicts. In an iterative repair approach, the system systematically tries to repair conflicts by moving larger chains of observations to remove a conflict. In the first iteration, the algorithm attempts to move observations from conflicted to non-conflicted times. In the second iteration, the algorithm attempts to remove conflicts by first moving some non-conflicted observation from one non-conflicted time to another non-conflicted time, and then moving the conflicted observation into the time slot originally occupied by the non-conflicted observation. This procedure continues increasing the length of the chain of moved observations until the solution is good enough or some maximum length is reached.

While systematic search uses knowledge-based heuristics to guide each step, a stochastic search uses random methods to generate schedules, and then uses metrics to pick the best schedule. The SPIKE tool kit supports the use of genetic algorithms that evolve a population of good schedules through a stochastic process that mimics biological evolution. Starting with an initial population of schedules generated randomly or by heuristics, the algorithm repeatedly creates a new generation of schedules that are more “fit” according to a given schedule metric. To create a new generation, the algorithm combines random elements of the current generation to produce new candidate elements. After generating new candidates, the next generation population is determined by taking the best schedules out of the previous generation and the newly generated schedules. This generational process continues until the solution is good enough or some maximum number of generations is reached.

The SPIKE system takes a multi-objective approach to help mitigate the problem of not knowing exactly what is being optimized. In most scheduling applications, there are multiple possibly competing objectives by which the quality of a schedule is measured.  For example, for JWST, it is desirable to produce schedules that maximize time on-target and minimize dead time, slews, consumption of fuel, and the span in which observations within a single program are scheduled. Traditional approaches to scheduling create a single objective function using a weighted combination of measures for each metric. This traditional approach pre-determines the trade-offs between the competing metrics and determines a single best schedule. In multi-objective scheduling, the objectives are kept separate and the scheduling software builds a Pareto-optimal surface of potential schedules where no schedule on the surface scores worse than another schedule on the surface for all of the metrics. The end user of the scheduler is provided with a visualization tool which allows them to explore the trade-offs in the competing metrics to pick their desired best schedule.

While the AI techniques described above enable SPIKE to create high-quality plans and schedules, it is the use of a layered object-oriented architecture that allows the system to easily be adapted to different missions. SPIKE consists of layers for astronomical utilities for modeling astronomical domains, and for implementing planning and scheduling algorithms. Each layer has a controlled interface with the other layers, and elements of each layer have generic behavior that can be specialized to get the desired behavior for a specific mission. This architecture greatly simplifies the process of creating a new SPIKE application for a mission and has allowed SPIKE to be used in Hubble and JWST, as well as the SIRTF, Chandra, Subaru, and FUSE missions.