project image or logo

Background

The Compressed Large-scale Activity Scheduling and Planning (CLASP) project is a long-range scheduler for space-based or aerial instruments that can be modelled as pushbrooms -- 1D line sensors dragged across the surface of the body being observed. It addresses the problem of choosing the orientation and on/off times of a pushbroom instrument or collection of pushbroom instruments such that the schedule covers as many target points as possible, but without oversubscribing memory and energy. Orientation and time of observation is derived from geometric computations that CLASP performs using the SPICE ephemeris toolkit.

CLASP allows mission planning teams to start with a baseline mission concept and simulate the mission's science return using models of science observations, spacecraft operations, downlink, and spacecraft trajectory. This analysis can then be folded back into many aspects of mission design -- including trajectory, spacecraft design, operations concept, and downlink concept. The long planning horizons allow this analysis to span an entire mission.

A 12-day repeat schedule from the NISAR mission
The ascending swaths for one 12-day repeat cycle of the NISAR mission, as scheduled by CLASP (Doubleday 2016).

Problem

In general, we assume a scheduling problem characterization as: - a set of points \(P\) - a set of observations opportunities \(O\), each \(o \in O\) consists of a start (\(o.start\)), and a duration ( \(o.duration\)) - a function \(obs(p \in P) \) that returns the subset of \(O\) whose elements positively affect coverage of \(p\) - a function \(coverage(p, sol \subseteq obs(p)) \) that determines the level of coverage of \(p\) given \(sol\) - a bound on coverage \(minQuality\) that must be met for a point to be considered covered - a bound on memory \(memory\) - a rate at which memory is used while the instrument is on \(memRate\) - a rate at which memory is recovered during a downlink \(downRate\) - a function that returns the minimum duration to transition from one observation orientation to another \(trans(o_1,o_2 \in O)\) - a set of downlinks \(D\) where each \(d \in D\) consists of a start (\(d.start\)) and a duration (\(d.duration\)) Our goal is to select \(p.sol\) subset of \(obs(p)\) for each \(p \in P\) such that the number of \(p \in P\) that \(coverage(p,p.sol) \geq minQuality\) is maximized, yet at no time do we oversubscribe memory.

Since coverage is a black-box function, optimizing this in general is problematic. But if we make the assumption that coverage is monotone (adding another \(o\) to \(p.sol\) never makes it worse), then we can perform local optimization based on approximating that adding the \(o\) that gives us the best improvement now might give us good improvement overall.

Impact

The NISAR intermediate-fidelity SSR model

CLASP has been used for Mission Planning and Mission Design inputs on the DESDynI (and subsequent NISAR) mission (Knight and Hu 2009, Doubleday 2016). It was prototyped as a tool for early stage mission planning of the Mars Odyssey THEMIS instrument (Rabideau et al. 2010). CLASP has also been used to assess coverage of Europa by the Europa Clipper and JUpiter ICy moons Explorer missions (Troesch, Chien and Ferguson 2017) and several other short-term coverage analysis studies.

The NISAR mission used a custom, specialized data recorder model in CLASP to simulate the effects of discrete block sizes on NISAR's actual flight data recorder and other difficult to model properties like rule-based observation-to-file mappings, prioritized downlink queues and a deferred-deletion, selectively dual playback policy (Trowbridge and Doubleday 2017).

Modeling the data recorder as a message queue
Plot of NISAR SSR data volume over time

Status

CLASP is actively maintained production software that is used for long-range mission planning as part of spacecraft operations for the upcoming NASA-ISRO Synthetic Aperture Radar (NISAR) mission. It is baselined for long term planning in NISAR mission operations as class B/C software, with some CLASP components used in short-term tactical replanning.

CLASP's polygon library and geometry caching layer are being used the Eagle Eye project.

Description

DESDynl Deformation
A KML science campaign from the DESDynI/NISAR mission (Knight and Hu 2009)

Scheduling in CLASP starts with a definition of the spacecraft, the body being observed, which regions of the body should be observed, and the trajectory of the observer. The spacecraft design and SPICE configuration are specified in a Keyhole Markup Language file. The science campaigns that should be satisfied are specified as KML polygons on the body being observed, with metadata about which instrument modes can satisfy the request and how frequently the science target must be observed. The observer's trajectory can be either a Two-Line Element set (TLE) or a binary SPICE kernel (BSP/SPK).

CLASP's default scheduler is a greedy, strict priority ordered Sqeaky Wheel Optimization (SWO) scheduler. The squeaky-wheel optimization algorithm initially labels each target with a scheduling priority. This priority will increase as the scheduler fails to schedule the target.

Observational scheduler flow chart
Squeaky Wheel Optimization flow chart (Knight and Hu 2009).

Then, iteratively, for each target in scheduler priority, the scheduler attempt to schedule the target. Any target not scheduled gets its scheduling priority bumped up. After each scheduling session, the quality of the current schedule is checked against the quality of the best schedule found thus far. If the current schedule quality exceeds that of the previous best schedule, then we replace the best schedule with the current schedule. If we run out of time or if the little improvement seems likely (stagnation), we stop optimization and return the best schedule as the solution.

CLASP's scheduler can also be replaced with any other arbitrary algorithm by writing custom C++ code and binding it to the mission's CLASP adaptation.

CLASP's output files are text-based observation schedules, with time-tagged KML renderings of the scheduled coverage that allow mission planners to view the coverage plan in Google Earth, JMARS or any other web application/GIS platform that can display KML. Statistics about satisfaction rates for different campaigns are output to comma-separated values (CSV) files.

Applications

- Long-term (6-month+ duration) observation planning
- Mission science coverage assessment

Usages

- ECOSTRESS
- OCO-3
- EMIT
- NISAR
- SDC
- SBG

Publications

Team

- Russell Knight
- Joshua Doubleday
- Elly Shao
- Michael Trowbridge
- Gregg Rabideau
- Steve Chien
- Martina Troesch
- Amruta Yelamanchili
- Joseph Russino
- Christopher Wells