project image or logo

Background

The Eagle Eye project is a specialized ASPEN model that focuses on planning and scheduling observational coverage for space-based, steerable 2D framing instruments. This is a relatively young research area because most of the older space-based imaging sensors are 1D pushbrooms. Pushbroom sensors generate an image by dragging a 1D line across the target, like a scanner. 2D framing instruments acquire a whole rectangle at the same time, like a digital camera. The Eagle Eye model was originally created for the proposed Eagle Eye ISS-mounted gimballed telescope, but can also be used to schedule observations for body-fixed instruments if the scheduler is allowed to steer the bus.

Revisits as interleaved Temporal Constraint Networks

A schedule consists of a set of observations that satisfy some science campaign. Science campaigns can include individual points and polygons on an observed body, or a distant celestial objects. Observations could be observed once, or repeatedly with revisits forming a temporal constraint network (TCN). The interface for science campaigns is with an extension of the Keyhole Markup Language (KML). This allows science teams to draw their campaigns in external tools like Google Earth.

Eagle Eye draws from heritage software. Spacecraft and celestial ephemeris-related computations are computed using the SPICE framework. Polygon operations, computational optimizations and KML input/output are re-used from the CLASP swath module library.

Problem

The Eagle Eye project focuses on a larger scale planning/scheduling problem where the planner must choose which targets are visited in which sequence to maximize the satisfaction of the input science campaign deck. There is a second, lower-level planning problem that focuses on how to effectively tile out and schedule polygon area requests.

Higher level scheduling problem

We start with the larger planning problem, which we derive from the Earth Observational Scheduling problem (Globus et al. 2004) as a best effort tour of all vertices with time varying edge costs, cycles within the graph (revisits) and time interval restrictions (visibilities). Given a graph \(G= ( V,E)\) where each vertex \(v_i \in V\) is a desired visit to a science target and time varying transit cost \( e_i(t)\in E\) between science target visits, choose the path \( P \subseteq G\) that maximizes fitness score \( f_{sat}=f(P)\), where a \(P\) that visits all \(V\) within the planning horizon \([0 ,t_{end})\) may not exist. By analogy to the job flow problem of minimizing tardiness with sequence dependent setup costs (Allahverdi et al. 2008), optimal EOS scheduling is expected to be at least NP-hard (Lewellen et al. 2017).

The geometry of an observer flying by a target that is rotating was the observer flies by adds two challenging aspects to this scheduling problem: - The cost of a slew between two observations is time varying - The cost of a slew between two observations is asymmetric Time varying slew costs mean that any approach that relies on a triangle rule to prune search space may be invalidated. Asymmetric slew costs mean that an exhaustive solution cannot discard 1/2 of the search space using a symmetry argument.

Lower-level scheduling: area coverage planning

This problem deals with the process of decomposing a target area polygon into a set of images from space that cover the target in the smallest possible schedule duration (makespan). Formally, given a set of target great-circles polygons on a triaxial ellipsoid, \begin{equation} P = \left\{(p_1,p_2,p_3)_i\right\} \end{equation} a set of all possible valid observations \begin{equation} \label{eq:all-possible-observations} B = \left\{(\mathbf{r}_\textrm{obs},\mathbf{r}_\textrm{tgt},\theta,t)_i\right\}, t_0\leq t < t_f \end{equation} a function to create an image polygon \(g\) from an observation \begin{equation} g \gets \textrm{footprint}(\mathbf{r}_\textrm{obs},\mathbf{r}_\textrm{tgt},\theta,t) \end{equation} a function that returns \(\bigcup_{i=1}^{|G|} g_i \) if all footprint images \(g\in G\) have sufficient overlap, \(\emptyset\) otherwise \begin{equation} tileUnion \gets \textrm{mosaic}(\left\{ g_i \right\}) \end{equation} a Boolean valued function to check if sufficient time exists to slew between observations \(b_i\) and \(b_j\) \begin{equation} Boolean \gets \textrm{slewOk}(b_i, b_j) \end{equation} \(A \subseteq B\) is a valid solution schedule iff \begin{equation} \label{eq:covers-target} P \subseteq \textrm{mosaic}\left( \left\{ \textrm{footprint}\left( a_i \right)|i\in 1,2,\ldots,|A| \right\} \right) \end{equation} and \begin{equation} \label{eq:slews-ok} \bigwedge_{i=1}^{|A|-1} \textrm{slewOk}\left(a_i, a_{i+1} \right) \end{equation}

Gaps in an area tiling plan
Gaps in an area tiling plan

The biggest challenge in the area coverage planning problem is that changes in the observer's position and perspective over time cause an initial tiling plan to develop gaps. We can address this by adding margin to the plan and taking images that have more overlap than is required, but this conflicts with our goal of producing the minimum makespan schedule.

Impact

Eagle Eye has been used to produce high fidelity observation schedules for science return estimates of several proposed missions:

- Eagle Eye ISS-mounted, Earth-observing telescope
- Mission to Understand Ice Retreat (MUIR)
- Topographic Earthquake Mapping By Landforms for Research (TEMBLoR)

Eagle Eye was also used to produce the baseline schedule in a software prototype for next-generation onboard autonomous response software that would run on a commercial imagery spacecraft that could retask itself based on acquired imagery within the same overflight (Chien et al. 2015, Chien and Troesch 2015). It has been used as a testbed for general research into framing instrument scheduling algorithms.

Status

Eagle Eye is being used in simulated EOS scenarios for proposal development and scheduling algorithm research.

Applications

- Earth observation satellite operations
- Comet fly-by framing instrument image scheduling

Publications

Team

- Russell Knight
- Amos Byon
- Christopher Davies
- Evan Davis
- Elly Shao
- Daniel Tran
- Michael Trowbridge
- Andrew Watson