Planning Complex Sequences Using Compressed Representations
- Created: Saturday, 01 August 2009
Computation time and memory needed to generate schedules are greatly reduced.
A method that notably includes the use of compressed representations interleaved with non-compressed (time-line) representations of a general scheduling problem has been conceived as a means of increasing, by orders of magnitude, the speeds of computations needed for scheduling complex sequences of activities that include cycles wherein subsets of the activities and/or sequences are repeated. The method was originally intended to be used in scheduling large campaigns of scientific observations by instruments aboard a spacecraft. A typical such campaign could include observations of millions of targets, many observations to be made during long repeated passes. The method would also be useful on Earth for scheduling complex sequences of activities that include cycles.
The method is best summarized in the context of the original intended application, wherein the scheduling problem is formulated as that of selecting, from a candidate set of observations, those observations that cover as many target points as possible without oversubscribing energy and memory budgets. Inasmuch as observation opportunities repeat, the theoretical framework for evaluation of candidate solutions includes a cycle bound.
The method includes the use of an iterative optimization algorithm known in the art the “squeaky wheel optimization.” This algorithm consists of the following steps:
- Sort all of the target points according to priority.
- Schedule each target point, greedily, in order of priority.
- Increase priorities for those points that were omitted from the schedule in step 2.
- Iterate by repeating from step 1.
Thus, points that are not initially scheduled have a greater probability of being scheduled on subsequent iterations because each time a point is not scheduled, its priority is increased, until eventually it becomes the first point scheduled.
At each iteration, points are considered in order of priority and observations considered in descending order of the contribution of each to coverage until a minimum acceptable level of coverage of each affected point has been scheduled. Only observations that cannot oversubscribe memory or energy and that respect transition duration constraints are considered. The asymptotic time complexity (in effect, the time needed to perform the computations) is of the order of a number proportional to nlog(n) per iteration, where n is the number of points. This computation time is basically proportional to the time needed to sort the points according to priority.
For reasoning about multiple cycles, multiple cycles are used in representing energy and memory, but a single cycle is used in representing observations. The single-cycle representation can be characterized as compressed in that, relative to a time-line representation, it requires less memory to represent all possible observations over all cycles. Instead of listing all observations individually, one lists a single cycle of observations with labels that represent which observations belong to which cycles. The amount of memory needed to encode observations in this approach is proportional to the total number of observations.
This work was done by Steve Chien and Russell Knight of Caltech for NASA’s Jet Propulsion Laboratory.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-43768.