Citation
A mission of scheduling solution for high-agility earth imaging satellites

Material Information

Title:
A mission of scheduling solution for high-agility earth imaging satellites
Creator:
Smith, Gary Scott
Publication Date:
Language:
English
Physical Description:
xii, 89 pages : ; 29 cm

Subjects

Subjects / Keywords:
Artificial satellites ( lcsh )
Scheduling -- Mathematical models ( lcsh )
Production scheduling -- Mathematical models ( lcsh )
Artificial satellites ( fast )
Production scheduling -- Mathematical models ( fast )
Scheduling -- Mathematical models ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 87-89).
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Gary Scott Smith.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
166269101 ( OCLC )
ocn166269101
Classification:
LD1193.L622 2007m S57 ( lcc )

Full Text
A MISSION SCHEDULING SOLUTION FOR HIGH-AGILITY EARTH
IMAGING SATELLITES
by
Gary Scott Smith
Bachelor of Science, University of Colorado at Denver, 1996
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
2007


This thesis for the Master of Science
i
S
degree by
Gary Scott Smith
has been approved
by
!
I
!
I
(
}
i
Weldon Lodwick
i
i
i


Smith, Gary Scott (M.S., Applied Mathematics)
A Mission Scheduling Solution for High-agility Earth Imaging Satellites
Thesis directed by Associate Professor of Mathematics Stephen C. Billups
ABSTRACT
This thesis considers the problem of scheduling individual imaging opera-
tions for highly agile, low orbiting, earth imaging (remote sensing) satellites.
Vehicle and orbital characteristics create a large number of opportunities for the
sensor to capture a single image. This fact combined with the over-subscribed
nature of image tasking, creates a combinatorially large solution space.
Our work integrates a discrete time window of opportunity concept with a
dynamic programming model that results in an acyclic graph representation of
potential imaging operations. Because a window of opportunity can accommo-
date a large number of potential imaging start times with variable durations,
windows that overlap in time can result in opportunity cycles. These cycles
do not violate the acyclic nature of the graph, but do cause infeasibility in the
problem domain. Resolving the opportunity cycles can result in exponential
growth of nodes within the graph. An iterative algorithm is defined that com-
bines a longest path solution for acyclic networks with a so-called look-ahead
interval and branch and bound technique to reduce problem size. This dynamic
programming method results in an optimal sequence of imaging operations.
m


This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
IV


DEDICATION
This thesis is dedicated to my wife Erin and children Kaitlyn, Ashley, Tessa,
and Brennan. I could not have fulfilled this personal dream without your love,
support and encouragement. This thesis is the end of a journey that required
many late nights, over many years, away from home. I cannot express to you
how much I appreciate your sacrifice.


ACKNOWLEDGMENT
I would like to specifically acknowledge Mr. Myrick Crampton and Dr.
Stephen Billups.
It was Myricks mentorship and the work that he and I performed in the
development of a commercial global optimization product that influenced me to
pursue an advanced degree in mathematics. Thank you.
As my advisor, and professor for some of my favorite classes, Dr. Billups not
only guided and assisted me through the thesis process but more importantly
he encouraged me throughout my degree program. Thank you so much for your
patience, understanding, teaching, and friendship.
A special thanks go to Raytheon Space Systems, for supporting my educa-
tion and providing me an interesting and challenging problem.


CONTENTS
Figures................................................................... xi
Tables................................................................... xii
Chapter
1. Introduction............................................................ 1
2. The Image Satellite Mission Scheduling Problem.......................... 8
2.1 Satellite and Image Acquisition Fundamentals........................ 8
2.1.1 Satellite........................................................... 8
2.1.2 High Versus Low Agility............................................. 9
2.1.3 Targets............................................................ 11
2.2 Mission Management Fundamentals.................................... 11
2.2.1 Tasking............................................................ 11
2.2.2 Scheduling ........................................................ 12
2.2.3 Imaging Opportunity................................................ 12
2.3 Scheduling Complexity.............................................. 13
3. A Model For The Image Satellite Mission Scheduling Problem .... 16
3.1 Schedule Model Elements ........................................... 16
3.1.1 Discrete Time...................................................... 17
3.1.2 Activities......................................................... 17
3.1.3 Opportunities...................................................... 18
3.1.3.1 Image Quality.................................................... 19
Vll


3.2 Model Formulation
21
3.2.1 Mathematical Models .......................................... 22
3.2.2 Network Model................................................. 23
3.2.2.1 Left-Justified Schedules...................................... 24
3.2.2.2 Basic Network................................................. 25
3.2.2.3 Feasibility and Optimality in Solution Paths.................. 26
4. A Solution For The Image Satellite Mission Scheduling Problem ... 28
4.1 Solution Generation for the Basic Network........................ 28
4.1.1 Pulling Algorithm ............................................ 28
4.1.2 Resolving Opportunity Cycles.................................. 29
4.1.2.1 Subproblem Tree............................................... 32
4.1.2.2 Validation of Optimality in the Subproblems .................. 32
4.1.3 Run Time Improvement Through Branch and Bound................. 33
4.1.3.1 Reduced Paths and Lower Bounds................................ 33
4.1.3.2 Upper Bounds.................................................. 36
4.1.3.3 Branch and Bound Algorithm.................................... 37
4.2 Improved Efficiency in the Trimmed Network.................... 38
4.2.1 Transitive Arcs............................................... 39
4.2.2 The Trimmed Network........................................... 40
4.2.2.1 Node Removal.................................................. 41
4.2.2.2 Optimality and Efficiency in the Trimmed Network.............. 41
5. Algorithm Details.................................................. 43
5.1 Network Construction ............................................ 43
viii
5.1.1 The Look-Ahead Interval
44


5.1.2 Network Generation Implementation Details....................... 46
5.1.2.1 generatemetwork................................................... 46
5.1.2.2 get_next_ordered_opportunity...................................... 48
5.1.2.3 calculate_slew_duration .......................................... 49
5.1.2.4 get_next_discrete_timestep........................................ 50
5.1.2.5 get_existing_node................................................. 51
5.1.2.6 trim_transitive_arcs.............................................. 52
5.1.2.7 create_new_node................................................... 53
5.1.2.8 get_next_ordered_opportunity_intersecting_interval................ 54
5.2 Dynamic Programming with Branch and Bound.......................... 55
5.2.1 Node Removal by No-Op........................................... 55
5.2.2 Solution Generation Implementation Details...................... 58
5.2.2.1 generate_solution................................................. 58
5.2.2.2 find_optimal_path................................................. 60
5.2.2.3 path_contains_opportunity_cycle................................... 62
5.2.2.4 generate_cycle_free_path.......................................... 63
5.2.2.5 generate_subproblems.............................................. 65
6. Solution Results....................................................... 67
6.1 Test Case Generation................................................. 67
6.2 Test Case Results.................................................... 69
7. Solution Conclusions And Next Steps.................................... 73
7.1 Considerations for Future Work..................................... 74
Appendix
A. Glossary of Terms...................................................... 78
ix


B. Source Code..................................................... 86
References......................................................... 87
x


FIGURES
Figure
1.1 A projected window of opportunity onto the Earth............. 2
1.2 A high agility satellite can maneuver its field of view any-
where within its field of regard.............................. 4
2.1 Low agility field of regard and field of view................ 9
2.2 High agility field of regard and field of view ............. 10
2.3 A generic Window of Opportunity ............................ 13
2.4 The Window Constrained Packing problem...................... 14
3.1 A window of opportunity with associated suitability function 19
3.2 Image Duration Profile based on image quality over time . 21
3.3 Image Satellite Mission Scheduling problem represented as
a network. Each node represents a potential imaging activity. The
highlighted path shows the best set of scheduled activities. 24
3.4 Opportunity Cycle an infeasible path in the problem domain 27
4.1 Opportunity Cycle an infeasible path in the problem domain 30
5.1 A Look-Ahead Interval used to reduce the number of tran-
sitive arcs in the problem................................... 45
6.1 An illustration of the effects of target and opportunity gen-
eration...................................................... 69
xi


TABLES
Table
6.1 Trimmed Network Generation Results............................. 70
6.2 Dynamic Program Scheduling Results ............................ 72
xu


1. Introduction
Mission management of highly agile, Earth imaging (or remote sensing)
satellites is a challenging and complex operation. The most essential element
of managing the mission of such a satellite is scheduling the imaging activities
performed by its sensors. The goal of scheduling is to generate an optimal time
ordered sequence of activities, that allows the satellites resources to operate
efficiently, meet mission objectives, and satisfy user requests for images. We call
this the Image Satellite Mission Scheduling (ISMS) problem. The ISMS problem
is quite challenging. The scheduling process typically takes as input many more
user requests to image targets, often referred to as tasks, than can be satisfied
by the sensor at a given time. In this problem, the subset of tasks selected
for scheduling is primarily governed by a user assigned priority: in general, a
lower priority task cannot supersede a higher priority task. When a task is
allocated to the resource, the result is a scheduled activity. This allocation is
only permitted if certain constraints are satisfied, such as the satellites visibility
to the imaging target. The agility of the satellite accommodates many different
possible orderings of activities on the schedule. The order in which activities are
performed can have a profound effect on the efficiency of the satellites operation
and the number of activities scheduled. The ISMS problem is an NP-complete,
combinatorial optimization problem.
The physics governing the orbit of a satellite ensure that its movement
around the Earth is predictable. Because of this, it is possible to predict when
1


the satellite will see a target Figure 1.1 illustrates this concept by the projection
of an interval of time onto the surface of the Earth. This interval is called a
window of opportunity. A window of opportunity defines the start time and
end time that the satellite has visibility to a given target during its orbit. This
Figure 1.1: A projected window of opportunity onto the Earth
visibility provides an opportunity to collect an image of the target, hence the
name. Since each target has a unique location on the Earth and has an associated
window of opportunity, there is both a separation and a natural time ordering
of targets. Taking advantage of these physical characteristics of the problem,
we consider the satellites orbit to contribute towards the construction of a path
to be traversed, where the targets are separate locations to be visited along
the path. This abstraction highlights our fundamental approach: an acyclic
graphical model, that can be solved using dynamic programming. The nodes
2


of the graph represent opportunities to image a target at a specific time, and
arcs represent the satellites physical transition, or slew, from one target to the
next. A solution to the ISMS problem is a path through the acyclic graph that
maximizes the sum of the weights of the traversed nodes. A similar approach was
used by Gabrel and Vanderpooten in their paper, Enumeration and interactive
selection of efficient paths in a multiple criteria graph for scheduling an earth
observing satellite [5], and by Lemaitre et al in their paper, Selecting and
scheduling observations of agile satellites [10].
A significant limitation of the two approaches cited earlier is they assumed
a fixed window of opportunity for each task. In the case of Gabrel and Van-
derpooten, the opportunity is fixed in duration. The opportunity is the same
duration as the imaging activity, and that results in a unique time that an image
can be started for a given target. In the case of Lemaitre, the opportunity is fixed
in quality and activity duration. Their model makes a monotonicity assump-
tion that beginning a collection later in time does not improve the scheduling
result. This implies that image quality does not change over the duration of the
opportunity and neither does the activity duration. The idea of a fixed window
of opportunity, whether that be in opportunity duration, activity duration, or
image quality, is not a realistic assumption for a highly agile satellite. A highly
agile satellite has virtually unlimited mobility on either two axes (roll and pitch)
or three axes (roll, pitch and yaw). Because it can change its pointing attitude,
an opportunity can be orders of magnitude longer in duration than the associ-
ated imaging activity. This results in many potential times to begin an imaging
activity over the course of the opportunity for a given target, not just one. This
3


agility can result in a wide range of viewing angles to a target, and that can
affect how both image quality and activity duration change during the oppor-
tunity. Figure 1.2 depicts a highly agile satellite and its ability to adjust the
direction it points to image several targets within its field of regard, defined as
Figure 1.2: A high agility satellite can maneuver its field of view
anywhere within its field of regard
the area of the Earth that has the potential to be imaged. The figure shows
how the satellite slewed around its center of mass from time f3 to to place its
sensor field of view, the area to be imaged, into the correct position to capture
the next target. Because of this mobility, a more realistic way of modeling a
highly agile satellite is to use a variable window of opportunity.
A variable window of opportunity allows its parameters, such as activity
start time, activity duration, and image quality, to vary at each instant in time
across the window. This variability can be modeled by allowing multiple nodes
4


in the graph for each opportunity. Each node represents a potential imaging
activity at a unique time within the window. Proper selection and ordering of
nodes can be determined by a dynamic programming algorithm.
Unfortunately, allowing multiple nodes within an opportunity introduces an
undesirable side-effect: opportunity cycles. An opportunity cycle is a traversal
of the nodes in the graph where two or more nodes are associated with the same
opportunity. A solution of this type would result in redundant collections (i.e.
repeated collections to the same target). This situation does not violate the
acyclic property of the graph, but does result in an infeasible solution for the
problem domain. A feasible solution can be achieved by iteratively modifying
the graph through the use of a branch and bound procedure.
Of the many papers addressing satellite scheduling, three stood out as most
applicable to the ISMS problem, Three scheduling algorithms applied to the
earth observing systems domain by Wolfe and Sorensen [18], and the two papers
cited earlier ([5], [10]). The Window Constrained Packing problem described in
[18] addresses several fundamental ideas that are central to the ISMS problem.
First, there is the window of opportunity. Second, is the idea of a suitability
function that allows for variation in the desirability of activity placement within
the opportunity. Third is that selection preference is given to higher priority
requests. Our work is an extension of these ideas specifically to the imaging
satellite domain. We take advantage of the suitability function concept and use
it to model activity duration over the window. The assumption is that activity
duration is a function of image quality and activity start time, because each
instant in time affords a different viewing angle to the target, especially in the
5


case of a low earth orbiting imaging satellite. We also add to the authors work
by accounting for idle time in slew transitions between tasks.
The work of [5] approaches the imaging satellite scheduling problem using
a two phased approach. The first phase is the creation of an acyclic graph of
potential imaging targets and the second is a shortest path solution that con-
siders slew times, using a variant of the topologically ordered label-correcting
algorithm. Their algorithmic approach is very similar to our proposed solution.
However, the specific problem they address is a simplification of the ISMS prob-
lem. In particular, the authors problem does not address a variable window of
opportunity: they assume that each imaging operation occurs at a unique time
on a given orbital pass.
The work that most closely resembles mine is that of [10]. The authors as-
sumed that the imaging satellite being scheduled is highly agile. They compared
four different solution algorithms, and one algorithm is a dynamic programming
technique using an acyclic graph with slew times on the arcs. Similar to [5],
the authors do not address a variable window of opportunity: they assume that
neither image quality nor activity duration change over the coruse of a window
of opportunity. In addition, their specific use of time ordered opportunities arti-
ficially restricts the number of opportunities that can overlap in time. Our work
has no such restrictions.
The work presented in this thesis combines aspects of all three approaches.
The scheduling of a highly agile earth imaging satellite is modeled using variable
windows of opportunity in an acyclic graph. A topologically based dynamic
programming approach is iteratively applied, using branch and bound controls,
6


to obtain an optimal solution.
The remainder of this thesis is organized as follows. Chapter 2 presents the
ISMS problem in detail, including the examination of a variety of constraints
involved in the problem. Chapter 3 presents the modeling aspects of our solu-
tion. Chapters 4 and 5 present our dynamic programming scheduling approach
and algorithms, respectively. Chapter 6 provides analysis and results from our
software implementation of the solution. Chapter 7 draws final conclusions and
lists avenues for future work. Appendices at the end of this thesis allow the
reader to examine the source code associated with the solution, as well as a
glossary of terms.
7


2. The Image Satellite Mission Scheduling Problem
The overall management of an earth imaging satellite typically consists of
collecting user requests for imaging, creating a payload and bus schedule, com-
manding the vehicle, processing the raw imagery data into useful products,
and distributing the products back to the users. The Image Satellite Mission
Scheduling problem is focused on the creation of a payload schedule for a sin-
gle satellite. The schedule, a time ordered sequence of imaging activities, is
generated by an algorithm that considers several constraints while calculating
the optimal sequence. To better understand the issues of the ISMS problem,
the next few sections will give a simple overview of imaging satellites and the
mission management process.
2.1 Satellite and Image Acquisition Fundamentals
There are many different types of imaging systems. For the purpose of this
thesis, we will generalize the many disparate imaging systems into a simple,
generic system. Earth imaging satellites take one of two basic forms, optical or
radar [14]. There are unique modeling considerations for each. This thesis will
focus on optical imaging, though the fundamental concepts presented also apply
to the scheduling of a radar based imaging satellite.
2.1.1 Satellite
The payload for an optical imaging satellite includes the telescope and one or
more sensors. It is analogous to the lens and imaging apparatus of a modern dig-
ital camera. Similar to a digital camera, lighting and viewing conditions are im-
portant constraints for satellite imagery. We will not address these constraints,
8


because they do not add to the fundamental mathematical considerations of the
problem. They ultimately affect access opportunities to the target, and such
calculations can be handled as a preprocessing step to scheduling. Other system
constraints, such as power consumption or thermal exposure, are ancillary to
the mathematics of our scheduling approach and will not be addressed.
2.1.2 High Versus Low Agility
This thesis focuses on highly agile, low earth orbiting satellites. The key
difference between a high and low agility satellite is that the mobility of a highly
agile satellite results in a larger field of regard (FOR). Figure 2.1 shows the
Figure 2.1: Low agility field of regard and field of view
imaging limitation of a low agility satellite, such as the SPOT series of earth
observing satellites. In the SPOT system the telescope field of view (FOV), what
the sensor can actually image, projects a swath onto the Earths surface due to
9


the movement of the satellite [14]. This eases the payload scheduling complexity,
since the only imaging requests to consider are those that fall within some small
angular distance on either side of the ground track [5]. In contrast, a highly agile
satellite is capable of slewing its pointing attitude along two or three axes [10];
therefore, a satellite of this type has a FOR that is considerably larger than its
FOV. Figure 2.2 shows how the FOR covers the entire visible portion of earth,
Figure 2.2: High agility field of regard and field of view
from the perspective of the satellite. Slewing is used to acquire virtually any
target within the FOR. This implies that highly agile satellites have a larger
solution space for the scheduling algorithm to consider. However, slewing comes
at a price: a slew can consume considerably more time than actually collecting
an image. Slewing is a fundamental aspect of the ISMS problem, and as such
it is taken into consideration. In addition to accessing many more targets than
10


a low agility satellite, this type of vehicle can access several different types of
targets.
2.1.3 Targets
A target represents a region on the surface of the Earth where an image
is to be collected. There are two basic types of targets: point and area. A
point target is one that can be captured in a single, small imaging strip or
dwell. While the dwell time to acquire the image is dependent on the actual
system, it is reasonable to say that it is short for a point target. Area targets are
larger in size, can be irregular in shape, and require the integration of multiple
imaging strips [10]. In this thesis, we will abstract away the complexities of
area targets by assuming they axe equivalent to point targets with long dwell
times. This is a reasonable assumption because any area target decomposition
calculations can be performed as a preprocessing step to scheduling. This work
uses a standard geographic coordinate system of latitude and longitude, where
altitude is assumed to always be zero for simplicity.
2.2 Mission Management Fundamentals
The mission management function of a satellite ground station centers
around the health and safety of the satellite and the management of its over-
all mission. The primary planning responsibility of mission management is the
scheduling of tasks for collection by a satellite.
2.2.1 Tasking
A task represents a users request for an image collection. A task might
include such information as preferred time of day, preferred resource, priority,
strategy, target location, minimum quality, and required angle of image. For our
11


purposes, only the preferred time interval for imaging, priority, target of interest,
and minimum quality are contained within the task. These items constitute a
basic task request. In addition, it is assumed that the collection strategy is a
simple monoscopic collection (a single image for a single target). Priority, a
numeric value that represents the importance of a task, is included because it
will play an important role in the scheduling algorithms objective.
2.2.2 Scheduling
The scheduling system must take many factors into consideration when at-
tempting to produce a schedule. The objective of the scheduling system is to
produce a time ordered sequence of allocations of task-target pairs to payload
resources, such that the optimizer
1. maximize the number of higher priority tasks,
2. maximize the total number of tasks satisfied,
3. maximize overall collection quality, and
4. maximize resource utilization.
This objective is tempered by the time constraints imposed by the window of
opportunity mentioned in Chapter 1.
2.2.3 Imaging Opportunity
Each task-target pair gives rise to many intervals of time when the satellite
can collect the associated image. Wolf and Sorensen [18] refer to each of these
intervals as a window of opportunity. The window of opportunity defines an
interval of time that the satellite has line of sight visibility to the target and
12


Window of Opportunity
for Task.
l
Task
l
Priority p.
Activity n.
max.
[
0
W.
w.
n.
n.
-| Time
T
Figure 2.3: A generic Window of Opportunity
meets all the angular, time, and minimum image quality constraints of the task.
Figure 2.3 shows a generic window of opportunity. It has a start time {Wla) and
end time (Wie) for the ith task. This figure also shows the scheduled activity
within the opportunity starting and ending at nis and nie respectively, with a
duration of d*. The values dmini and dmaXi indicate that the associated activity
can vary in duration from a minimum to a maximum value. This is true for
the ISMS problem as well; however, the duration is a function of the chosen
start time, tasked image quality, position of satellite in its orbit, and lighting
conditions of the target (often referred to as sun elevation angle).
2.3 Scheduling Complexity
As discussed earlier, high-agility satellites can change their attitude, allowing
the field of view to scan more areas of the Earth than if the telescope had
limited pointing ability. Slewing allows for targets to be visited in virtually any
13


order. It also increases the number and duration of windows of opportunity for
a given target. Since collection duration and range of collection quality within
each opportunity vary with start time, this flexibility of the satellite imposes a
difficult sequencing problem for the scheduling algorithm.
In Chapter 1, we mentioned the Window Constrained Packing (WCP) prob-
lem developed by Wolfe and Sorensen [18]. As Figure 2.4 shows, the WCP prob-
Figure 2.4: The Window Constrained Packing problem
lem involves assigning up to N tasks onto a single satellite based on priority,
14


given the time constraints imposed by a single window of opportunity per task.
In their paper, they showed that the classic 0-1 Knapsack Problem is a special
case of the WCP, and is in the class of ./VP-complete problems. The WCP and
the ISMS problems are fundamentally very similar. In fact, the ISMS problem
is reducible to the WCP problem by assuming:
1. all targets are sufficiently close to one another that the slew time between
targets is zero,
2. opportunity durations are sufficiently short that the minimum duration
for a scheduled task does not vary across the opportunity, and
3. the suitability function over the opportunity is constant.
Since the ISMS problem is reducible to the WCP problem, then it too is in the
class of AAP-complete problems, as a discrete sequencing problem that falls into
the category of Combinatorial Optimization [12]. One strategy for solving a
combinatorial optimization problem to optimality is with an exhaustive search;
however, such a search through all possible solutions is not practical. A better
approach is to avoid searching unfruitful portions of the solution space. This
can be accomplished with the dynamic programming algorithm we will introduce
and discuss in Chapters 3 and 4.
15


3. A Model For The Image Satellite Mission Scheduling Problem
Before discussing the particulars of our model for the Image Satellite Mis-
sion Scheduling problem, we will restate our basic assumptions. The ISMS
problem concerns a priori scheduling of tasks onto a single, low earth orbiting,
highly agile, imaging satellite. The tasks to be scheduled describe requests for
monoscopic collections of point targets, with user-defined priority values. The
collection period for a given task is constrained within a continuous preferred
time window. Each task has an associated single window of opportunity. Each
window of opportunity defines the interval of time that is the intersection of
when there is line of sight visibility from the satellite to the target, and the
preferred time window of the task. Because collection duration varies over the
opportunity, the opportunity also has an associated image duration profile that
defines the imaging duration for a specified start time. The specifications just
given constitute the core ISMS problem, so in order to focus on the mathematics
of our approach the model assumes no additional problem constraints.
3.1 Schedule Model Elements
There are several items that are not supplied with task requests that are used
to facilitate task scheduling. These schedule model elements include discrete
time, activites, opportunities, and duration profiles. Discrete time is used as
a matter of convenience and consistency. Activities are the data structures
resulting from scheduling. Opportunities and duration profiles are calculated
prior to scheduling for efficiency purposes.
16


3.1.1 Discrete Time
To avoid unnecessary complications in the model, time is made discrete
within the ISMS problem, and is assigned some minimum discrete units, say
seconds or milliseconds. There are benefits to discrete time. One is that the
problem is modeled on known time boundaries. This makes allocation of a task
to the satellite resource over time simple, through the assignment of a specific
start time and end time. Another is consistency with satellite commanding
concepts: scheduled tasks are ultimately converted into a series of time tagged
commands that are sent to the satellite for execution. Of course there are
also the discrete data structures available in modern programming languages to
consider. Prom a problem modeling perspective, time plays several roles. One is
in the definition of a scheduling interval, an interval of time that bounds when
the scheduling of tasks can be performed. Another is the preferred window, the
interval of time that the task is desired. Other uses of time include the visibility
opportunity, the period of line of sight access a satellite has to a target; the slew
time, or amount of time for the satellite to transition from one target to another;
and the dwell time, the duration of time it takes the satellite sensor to collect
an image.
3.1.2 Activities
An activity represents a scheduled task, on a specific resource, with a start
time and duration. The resource allocation process of scheduling selects a subset
of tasks from the set of input tasks, and for each selected task creates one or
more associated activities. A given activity will be added to the schedule if its
presence on the schedule contributes to meeting the goal of the optimization
17


problems objective function (discussed in Section 3.2).
3.1.3 Opportunities
As mentioned in section 2.2.3, a window of opportunity, or simply opportu-
nity is an interval of time where the satellite has visibility to a particular target
and satisfies all plan independent constraints. A plan independent constraint is
a problem constraint that is independent of any scheduled task currently on the
plan (the resultant schedule). For example, the time at which a satellites orbit
allows its sensor to meet a minimum collection quality constraint is independent
of any other collection request. On the other hand, the slew time to a particular
target is considered plan dependent, because the slew duration is dependent on
the target location of the previously scheduled task.
In Chapter 2, we referred to a very similar problem to that of ISMS called the
Window Constrained Packing (WCP) problem. Figure 3.1 shows how an activity
is performed within its associated window of opportunity [w8i, wei\, and that each
activity is assigned a continuous, non-preempt.ive duration such that dmini ^
di ^ dmaXi. Wolfe and Sorensen [18] state that dmin and dmax are given for each
activity. They also state that there are preferences for activity placement within
the associated opportunity, and that a typical assumption is that the middle of
the window is preferred over the edges. This preference can be seen in Figure
3.1 by maximizing the area under the suitability function over the opportunity.
Though not explicitly stated, Wolfe and Sorensen assume that there is one
activity per opportunity. For an imaging satellite, the duration is not given in the
request, but is calculated based on several variables to meet the minimum image
quality constraint of the request. These variables lead to variations in activity
18


Task.
I
Priority p.
Activity n.
Minimum
Duration
Maximum
Duration
I
0
Window of Opportunity for Task .
Figure 3.1: A window of opportunity with associated suitability func-
tion
duration across the opportunity. We assume that an opportunity is allowed
to have many potential activities (states in dynamic programming parlance)
to reflect the various potential start times for the associated task; however,
scheduling solutions will only contain a single selected activity per opportunity.
We take advantage of the WCP suitability function to model the various image
activity durations.
3.1.3.1 Image Quality
The duration of an imaging activity is a function of several variables, in-
cluding sensor parameters, angle and distance of satellite to target, the angle of
the sun relative to the target, and the desired quality of the image. The basic
procedure for calculating an image activity duration is to first calculate the GSD
(ground sample distance) based on the position of the satellite at a given time,
and then calculate predicted NIIRS (a rating scale for image quality). Sample
19


GSD and NIIRS image quality equations can be found in [2]. If the predicted
NIIRS value is greater than or equal to the requested quality, then the scan rate
of the sensor is applied to the size of the target to obtain the duration needed
to capture the image. Because the orbit of a satellite is very predictable, it is
possible to calculate predicted NIIRS values and activity durations over some
sampling of the window of opportunity as a preprocessing step to scheduling.
If this type of preprocessing is performed, then the only impact to the runtime
of the scheduling algorithm is a simple look up, rather than a series of complex
calculations. This is the method we have chosen for handling activity durations.
For simplicity, we assume that all calculated activity durations for a window of
opportunity form a convex function. This is a reasonable simplifying assumption
if you consider a target that falls along the satellites ground track: the distance
from the satellite to the target (slant range) is at a maximum when the satellite
first has access to the target, and when the satellite passes directly over the
target, the slant range is at a minimum; the greater the slant range, the lower
the predicted NIIRS, all other things being equal. Figure 3.2 shows this no-
tional convex function mapped to a discrete image duration profile. The profile
divides the entire opportunity interval into discrete time slots, and associated
with each time slot is an image activity duration. For a proposed activity start
time t, rounded up to the next discrete time, the associated duration is simply
retrieved from the profile. It is further assumed that the activity end times
within the profile exhibit a monotonic characteristic: if an activity is started
later in the opportunity, then the end time of the activity is later than the end
times of all earlier potential activities within the opportunity. In other words,
20


Quality Continuous Convex
Figure 3.2: Image Duration Profile based on image quality over time
if the activities n* and rij represent two different choices for scheduling a task
within a given window of opportunity, then
"i. < njs = nie ^ nie (3-1)
where riis, nJe are activity start and end times, respectively.
This makes physical sense because if starting the task earlier results in finishing
later, one could simply delay the start.
3.2 Model Formulation
We now present our mathematical model for the Image Satellite Mission
Scheduling problem. The objective is to schedule a subset of time ordered tasks
that maximize the sum of the task priorities, respect window of opportunity
constraints, and account for nonnegative slew times between the scheduled tasks.
This scheduling problem is addressed using a dynamic programming approach.
21


The underlying model follows a network flow formulation. However, for ease
of understanding and variable description purposes, we will first show how the
problem is modeled with an integer programming formulation that is based on
the Wolfe-Sorensen model [18].
3.2.1 Mathematical Models
Let T be the number of tasks to consider.
Let Pi = value(ti) be a non-negative integer, that is the worth or weight
of task tj.
Let a window of opportunity be defined as [wis,Wie\ Vi [l,--* ,T],
which represents a time interval where there is visibility to the target.
Let the start time of activity rii be rijs.
Let the duration of activity rij, as a function time, be dH = D(f, <&), where
qi is the minimum required image quality and D : (t,q) > N is an image
quality function that returns the required duration, as a non-negative in-
teger, to meet the minimum quality assuming an activity starting time at
t.
Let Sij be the slew duration from activity rij to rij.
Let Xi be a binary variable indicating whether activity rij is in the schedule.
Xi = 1 indicates that activity rii is scheduled.
Let t/ij be a binary variable indicating whether activity i precedes activity
j in the schedule, yij = 1 indicates that activities rii and rij are in the
schedule, and rii precedes rij.
22


The following optimization model summarizes our scheduling goals:
T
Maximize: Z = ^ XiPi (3.2)
i=l
Subject to:
^ nis + (1 Xi)M
nia + dit ^ wie + (1 ~ xi)M
flis T djt + Sij 5^ 7ljs + (1 ]Jij) M
Vij T Vji ^ xi T Xj 1
Vij T Vji ^5 1
3.2.2 Network Model
Rather than solve the integer programming formulation described above, we
will instead create and solve a network model of the problem.
Nodes in the network represent task-target pairs, with their associated ge-
ographic locations. Arcs represent slews between task-targets. Recall from
Section 3.1.3 that the discrete-time window of opportunity associates a task to
a target with a range of potential collection start times. Because of this, any
one opportunity can have many associated nodes in the graph; with each node
representing a potential activity with a unique start time. The structure of the
network, is illustrated in Figure 3.3.
3.2.2.1 Left-Justified Schedules
23


Figure 3.3: Image Satellite Mission Scheduling problem represented
as a network. Each node represents a potential imaging activity. The high-
lighted path shows the best set of scheduled activities.
A key observation needed for our model is that the quality of a data collec-
tion can never be improved by delaying the start time. At worst, an earlier start
time may require a longer duration of the activity in order to achieve the same
quality. Moreover, with the monotonic assumption discussed in Section 3.1.3.1,
the completion of a task (at the desired quality) can never be made earlier by
starting later. This assumption assures that for any given ordering of tasks in
the schedule, an optimal strategy is to perform each task as early as possible
after the preceding task is completed. As such, to find an optimal schedule, it
is sufficient to consider only schedules consistent with this strategy, which we
shall refer to as left-justified schedules.
In the following section, we describe a network model, called the basic net-
work in which all feasible left-justified schedules are represented by paths in the
24


network, and conversely, every path in the network corresponds to a feasible
left-justified schedule. By weighting the nodes in the network according to the
values of the corresponding tasks, we can then search for paths in the network
which maximize the sum of the weights of the nodes visited. Such paths will be
referred to as longest paths. Unfortunately, such paths dont necessarily corre-
spond to valid schedules because they may include opportunity cycles which will
be discussed in section 3.2.2.3. After this material has been developed, we shall
argue that the ISMS problem is equivalent to finding the longest opportunity
cycle-free ((9-cycle-free) path in the basic network.
3.2.2.2 Basic Network
In the following definition of the basic network, nodes are used to represent
the scheduling of an activity at a specified start time. Typically multiple nodes
are defined for each task, with each node representing a different start time.
However, we will only define nodes corresponding to start times that could be
included in a left-justified schedule. Directed arcs are defined between two nodes
Ui and Uj if and only if 1) the nodes correspond to different tasks, and 2) the
start time for node n3 is the earliest time that the corresponding activity could
be performed following the completion of the activity represented by node
For the ensuing discussion, we shall make use of the following notation:
Let O = (oi,..., on) be the list of opportunities, ordered by start time.
Let Ma = (, -, n£) be the set of discrete nodes within opportunity oa.
Let r represent the root node (or root) for the network, and let s represent
the sink node (or sink).
25


For distinct opportunities oa and Ob, define f irst_f easible(nf,Ob) = nbp
where nb is the first node within for which it is feasible to slew from n to
rip If no such node exists, then first_feasible(n, Ob) = null. If oa o^
then f irst.feasible(nf, oa) = null. Also, f irst_feasible(r, oa) = n
for all oaE O.
The basic network can now be defined algorithmically as follows:
Algorithm 3.1 (Basic Network) Before beginning the algorithm, initialize
N = {r}, A0 = {}, and set k = 0.
1. Define Nk+l = {first_feasible(nj, oa)|nj E Nk,oa E O}. Ak+1 =
{(ni,nj)\nj E Nk,nj = f irst_f easible(ni, oa), oa E O}.
2. If Nk+1 0, set k = k + 1 and go to step-1. Otherwise, proceed to step-3.
3. Set N = Uf-oWUM* ^ = Ui=o U{(n) s)ln N \ {s}}; and return
(N,A).
3.2.2.3 Feasibility and Optimality in Solution Paths
Any path P through network G is executable by the satellite because an arc
between any two nodes nj and nj implies it is possible for the satellite to image
targefi and slew to tar getj. However, not all paths are considered feasible,
because a path might repeat a task. This is called an opportunity cycle: a
traversal through the graph where two or more nodes are associated with the
same opportunity, as illustrated in Figure 3.4. A solution of this type results in
a redundant collection (i.e. a repeated collection of the same target). This is
26


opportunity 2
Figure 3.4: Opportunity Cycle an infeasible path in the problem
domain
undesireable because the value of the data collection is over-counted in the path;
however, there is no actual value for repeating a data collection in the schedule.
Since there is no value in a redundant collection in the schedule, an optimal
solution to the ISMS problem corresponds to the longest path in the basic net-
work that does not include an opportunity cycle. Since the construction of the
basic network follows the optimal strategy outlined in 3.2.2.1, an optimal O-
cycle-free path from source node to sink node in the basic network is an optimal
left-justified schedule.
27


4. A Solution For The Image Satellite Mission Scheduling Problem
The overall scheduling strategy is to generate the basic network described
in the previous chapter, and then find an optimal (9-cycle-free path, where by
optimal, we mean the path that maximizes the sum of the node weights. This
chapter describes an algorithm for finding the optimal (9-cycle-free path. Once
this algorithm is presented for the basic network, we will then discuss improve-
ments to the network and the algorithm which greatly improve the computa-
tional efficiency of the approach.
4.1 Solution Generation for the Basic Network
The previous section described a network generation process that produces
a directed, acyclic network. Since it is acyclic, it has a topological ordering. A
shortest path algorithm is described in [1] that runs in 0(m) time, where m is
the number of arcs, for acyclic networks with a defined topological ordering. The
algorithm is called the Pulling Algorithm for shortest path problems in acyclic
networks, and it is equivalent to dynamic programming. We shall refer to it as
the Pulling Algorithm.
4.1.1 Pulling Algorithm
The Pulling Algorithm is a label setting algorithm. Each node i in the
network is assigned a label that is the lower bound of the longest path from the
root node to node i. We define dist(i) as the value of the path that maximizes
the sum of the node weights, from the root node to node i.
28


The algorithm begins by setting dist(r) = 0, the weight of the root node.
The algorithm then processes each node in the graph according to the topological
order of the nodes. At the jth iteration, the label for node j is set according to the
equation dist(j) = max^^^distii) + pj for all incoming arcs Note that
the topological ordering of the nodes ensures that dist(i) has been previously
calculated for all incoming arcs of node j. Upon completion of this step in the
algorithm, a longest path from the root node to node j has been identified, and
dist(j) is the value of that path. The algorithm continues until the sink node
has been processed, and hence the longest path found for the network.
Maximizing the weight of the nodes along the path accomplishes three of
the scheduling goals stated in Section 2.2.2: one, higher priority tasks are given
precedence; two, as many tasks as possible are scheduled; and that results in
three, an increase in the resource usage. The remaining goal of maximizing col-
lection quality is an artifact of building the network: no nodes are generated
that do not meet the minimum required collection quality. The objectives of the
ISMS problem appear to be addressed by this solution procedure; however, the
presence of any opportunity cycles, introduced in Section 3.2.2.3, in the result-
ing path prevent the algorithm from producing a feasible solution. A method
for finding and resolving opportunity cycles must be added to the solution gen-
eration procedure.
4.1.2 Resolving Opportunity Cycles
The Pulling Algorithm will produce a mathematically optimal path through
the network. Unfortunately, a mathematically optimal path is not always opti-
mal in the ISMS problem domain because it might contain opportunity cycles,
29


which were described in Section 3.2.2.3. Figure 4.1 shows a case of when an
Figure 4.1: Opportunity Cycle an infeasible path in the problem
domain
opportunity cycle can be introduced into a path. In this case two opportunities,
opportunity-2 and opportunity3, overlap in time. When the Pulling Algorithm
is searching for predecessors of node n22, its Markovian nature (conditionally
independent of past states) allows it to consider n3, even though n2l is already
on the path that passes through n3.
One approach for resolving this issue is to construct two subproblems, each
formed from the original problem by removing one of the nodes in the opportu-
nity cycle. That is, the first modified network in Figure 4.1 would have node n2l
removed and the second would have n22 removed. Observe that every path in
the original network that does not include both n2l and n22 will also be a path
in at least one of the two modified networks. In particular, any 0-cycle-free
path in the original network will also be a cycle free path in at least one of the
30


two modified networks.
This suggests the following recursive strategy for finding the optimal oppor-
tunity (9-cycle-free path in the network.
Algorithm 4.1 (Basic DP Algorithm) Let the original network G be the
initial network passed as input to the algorithm, i.e. the input network.
1. Find an optimal path from the root node r to the sink node s in the input
network, by applying the Pulling Algorithm. If no such path exists, return
a flag indicating that no cycle free path exists.
2. If the optimal path contains no opportunity cycles, return this path as an
optimal O-cycle-free path.
3. Otherwise, find the first opportunity cycle in the optimal path, by scanning
each node in order along the path, until an associated opportunity o is
repeated.
4. Let {n^,..., nlk) be the repeated nodes from cycled opportunity o. Then
(a) Create k subproblems, with networks G\,... ,G'k, where G' is formed
from the input network by removing all of the repeated nodes in op-
portunity o except riij.
(b) Find the optimal O-cycle-free paths by recursively calling Algorithm
4-1, where each subproblem is a new input network.
5. If none of the subproblems contains a O-cycle-free path, return a flag in-
dicating that no cycle free path exists in G.
31


6. Otherwise, determine the highest scoring of these 0-cycle-free paths. Re-
turn this path as the optimal O-cycle-free path for G.
4.1.2.1 Subproblem Tree
Conceptually, Algorithm 4.1 generates a tree of subproblems, where the root
node of the tree corresponds to the original network G, and the children of each
node in the tree axe the subproblems created in step 4(a) of the algorithm. A
node will have no children if either the corresponding network has no path from
the start node to the sink node, or if an optimal path was found that is free of
opportunity cycles.
4.1.2.2 Validation of Optimality in the Subproblems
In the above algorithm, note that G\ contains every path in G that does
not include any of the nodes ni2,.. .,nik. Similar statements can be made about
each of the other networks G2,... G'k. Thus, any path in G that contains at
most one of the nodes from the set {n^,,nik} is also a path in at least one
of the networks G\,..., G'k. In particular, any O-cycle-free path in G is also a
path in at least one of the modified networks. So the optimal 0-cycle-free path
in G is the highest scoring 0-cycle-free path for any of the subproblems.
The following proposition establishes that Algorithm 4.1 terminates.
Proposition 4.2 (Subproblem Termination) Given an initial network G,
the recursive Algorithm 4-1 will terminate in a finite number of steps.
Proof:
By construction, Algorithm 4.1 will generate subproblems G' from G such that
32


there is at least one fewer node in G'. Since there are a finite number of nodes
in the original network G, the depth of the subproblem tree cannot exceed \J\f\.
Let W be the maximum number of nodes in any opportunity. Clearly, each node
in the tree can have at most W children, so the number of nodes in the tree is
bounded by W^NL Thus, Algorithm 4.1 can be called at most a finite number
of times.
4.1.3 Run Time Improvement Through Branch and Bound
The scheduling strategy developed thus far leads to solutions for the prob-
lem. Unfortunately, it requires searching the entire subproblem tree, which can
potentially be quite large. We now present a branch and bound strategy that
enables us to search only a portion of the subproblem tree.
The main idea of the strategy is to determine when the investigation of
a subproblem is no longer fruitful by keeping track of a lower bound on the
optimal O-cycle-free path, denoted GLB, and use this to prune portions of the
subproblem tree.
4.1.3.1 Reduced Paths and Lower Bounds
To calculate the lower bound GLB, we begin by showing that for any path
P in the basic network, there is an associated reduced path P+ with the following
properties:
1. P+ is O-cycle-free.
2. P+ visits the same opportunities as P and in the same order. (That is in
the order determined by the first node visited for each opportunity).
33


Let P = r > rijj > ni2 > > nim > s be a path in the basic network.
Recall that, by construction of the basic network, this path corresponds to a
feasible schedule for the satellite in that it is physically possible for the satellite
to perform the activities specified by the nodes at the times specified by the
nodes. Clearly, by skipping any number of these activities, it would also be
possible for the satellite to perform any subset of these activities. Of course,
such a schedule would not necessarily be a left-justified schedule, so would not
necessarily correspond to a path in the basic network.
To define P+, let {n3l,... ,rijk) be a subsequence of (n^,...,nim) that in-
cludes only the first node visited for each opportunity, and let (o^,..., Ojk) be
the corresponding sequence of opportunities. As argued above, this subsequence
of nodes corresponds to a feasible schedule, so it is possible for the satellite to
perform the tasks corresponding to these nodes in the order specified. We can
then construct P+ as follows:
Algorithm 4.3 (Reduced Path Construction) Given a path P = r
71 jj > rii2 * > 7ijm > s in the basic network G.
1. Let (ojj,..., Ojk) be the ordered sequence of opportunities visited by P.
2. Let nf = f irst_feasible(r,o3l).
3. For i = 2,..., k, let nf = f irst_feasible(n^tl1, OjJ.
4. Define P+ = r > nf 5 ^ nf > s.
Proposition 4.4 (Validity of Reduced Path) The path P+ defined in Al-
gorithm 4-3 is an O-cycle-free path in the basic network.
34


Proof: Let (n^,..., rijk) be a subsequence of (nq,..., nim) that includes
only the first node visited for each opportunity included in P. By definition
of the basic network, for all o (E O, f irst_f easible(r, o) is contained in Af and
(r, f irst_feasible(r, o)) G A. In particular, nf = f irst_feasible(r, Ojf) G Af
and {r,nf) G A. Moreover, by the definition of f irst_feasible(r, o), the start
time for node nf is no later than the start time for node nj1.
Now for each i > 1, suppose that nf G Af and that the start time of
nf is no later than the start time for node nJt. Since P includes a path
from node riji to node nJi+1, first_feasible(nJi, oji+1) A null. Since the
start time for node nf is no later than that of node n^, it follows that
f irst_f easible(n+, oJi+1) 7^ null and that the start time of this node is no
later than that of f irst_f easible(nJi, Oji+1). Thus, by the definition of the
basic network, nf+1 G Af, its start time is no later than that of nji+1, and
{nf ,nf+l) G A. By induction on i, P+ is a path in the basic network.
The construction of the path P+ described above allows us to use any path
P in the basic network to calculate a lower bound LB{P) = value(P+) for the
optimal 0-cycle-free path in the basic network. Note however that this lower
bound can be calculated without actually creating P+ simply by adding up the
values of all the opportunities visited by the path P. The value of an opportunity
(value(o)) is the value of the task associated with the opportunity, which is also
the value of any node within the opportunity.
More precisely, define 0{P) = {o G 0\nt G P, and n{ G Af0}. In words,
O(P) is the set of opportunities that contain at least one node in P. Then,
35


define
LB(P)= £ value (o).
{oeo(p)}
We shall calculate LB(P) for every optimal path P found for each subprob-
lem. At any stage of our algorithm we then define the greatest lower bound
GLB to be the maximum value of LB(P) calculated so far.
This value of GLB can then be used to prune the subproblem tree. In
particular, when processing a subproblem, we can calculate an upper bound on
the value of the optimal path for that subproblem and all of its children.
4.1.3.2 Upper Bounds
When generating subproblems, each removal of an opportunity cycle causes
one or more nodes on the optimal path to be removed; therefore, subprob-
lem generation results in a monotonically decreasing objective function value as
stated in the following Proposition.
Proposition 4.5 (Subproblem Objective Value) If G is a basic network
with opportunity cycles and G' is a subproblem ofG, then the value of an optimal
path through G1 is less than or equal to the value of an optimal path through G.
Proof: Suppose G is a basic network with optimal path P. Let G1 be a sub-
problem of G that is solved for an optimal path P1. Since a path in G' is also a
path in G, value(P') ^ value(P).
With this in mind, if the value of the optimal path for a subproblem is less
than GLB, we can remove that subproblem and all of its descendants in the
subproblem tree from consideration.
36


We are now ready to define the branch and bound algorithm.
4.1.3.3 Branch and Bound Algorithm
Algorithm 4.6 (Complete DP Algorithm) Let the original network G be
the initial network passed as input to the algorithm, i.e. the input network.
1. Initialize the greatest lower bound GLB = 0
2. Find an optimal path from the root node r to the sink node s in the input
network, by applying the Pulling Algorithm.
3. If the optimal path contains no opportunity cycles, return this path as the
optimal O-cycle-free path.
4. Otherwise, push the input network onto a subproblem stack
5. Pop a network G' off of the stack. If the stack is empty go to step-10
6. Find an optimal path P' in G'.
7. Ifvalue(P') ^ GLB, then go to step-5
8. Otherwise, if P' contains an opportunity cycle, then
(a) Create the reduced path P+ from P' using Algorithm 4-3.
(b) If value(P+) > GLB then set GLB = value(P+), and set P* = P+
(c) Find the first opportunity cycle in P', by scanning each node in order
along the path, until an associated opportunity o is repeated.
(d) Let {rijj,... ,nik} be the repeated nodes from cycled opportunity o.
Then
37


i. Create k subproblems, with networks G[,...,G'k, where G' is
formed from\ G' by removing all of the repeated nodes in opportu-
nity o except nij.
ii. Push all subproblems onto the stack and go to step-5.
9. If P' does not contain an opportunity cycle, then
(a) If value(P') > GLB then set GLB = value(P'), and set P* = P1
(b) Go to step-5.
10. Return P* as the optimal O-cycle-free path of G.
Algorithm 4.6 describes the complete scheduling strategy for providing a
solution to the ISMS problem: a dynamic programming algorithm, managed
with a branch and bound strategy. Once all branches of the pruned solution
tree have been explored, the best solution found is the optimal schedule of
activities for the ISMS problem.
4.2 Improved Efficiency in the Trimmed Network
The basic network generated by Algorithm 3.1 has far more arcs than are
necessary in order to find the optimal schedule. Because the Pulling Algorithm
will explore all available arcs during its search, a reduction in the number of arcs
within the network will improve the efficiency of the algorithm. In this section
we will discuss the formation of a new network, called the trimmed network,
that has fewer arcs and contains all optimal 0-cycle-free paths that exist in the
basic network.
4.2.1 Transitive Arcs
38


An arc (i, k) in the basic network G is a transitive arc if there also exists
in G a path n* nj n^. Such arcs exist in G due to the definition of
Algorithm 3.1, which created the basic network. For each node under consider-
ation, an arc to every future first-feasible node is generated. Observe that the
Pulling Algorithm improves its objective function value by including as many
nodes as possible in its resulting path. Since the definition of a transitive arc
(z, k) implies that there exists at least one node j that is reachable from node 7,
and node k is reachable from node j, the Pulling Algorithm will prefer the path
in G that passes through node j, if nodes i and k are also on the optimal path.
In fact, there is always an optimal path in any of the basic network subproblems
that contains no transitive arcs.
Lemma 4.7 (Transitive Arc Elimination) Any optimal path through a net-
work G' with transitive arcs removed and non-negative node weights, is also an
optimal path through the basic network G that formed G'.
Proof: Let P' be an optimal path in G', Let P be a longest optimal path in G
(that is, an optimal path that contains the greatest number of arcs). Any path
in G' is also a path in G, so value(P') ^ value(P). If P contains a transitive arc
(7, k), then there exists a path rij > nj * n*, in G. Let P* be formed from P by
replacing arc (7, k) with the intermediate arcs (7, j), (j, k). P* includes all of the
nodes in P, so its value is at least as large as the value of P, and P* is longer.
This contradicts that P was the longest optimal path; so P cannot have any
transitive arcs. Thus P is a path in the network G'. Thus, value(P) ^ value(P')
(since P' is optimal in G'). Since P' is also a path in G, then it is optimal in G.
39


4.2.2 The Trimmed Network
A trimmed network is a network formed from a basic network by removing
transitive arcs corresponding to non-transitive arcs of length 2. To generate a
trimmed network, we need to modify Algorithm 3.1 by adding a new step-2 as
follows:
Algorithm 4.8 (Trimmed Network) Before beginning the algorithm, initial-
ize N = {r}, A0 = {}, A = {}, and set k = 0.
1. Define Nk+1 = {first_feasible(ni, oa)\ni G Nk,oa G O}. A*+1 =
{(ni,rij)\nj G oa,nj = f irst_f easiblefy*, oa), oa G O}.
2. Define Q = {(n^, n^) G A|3* such that () G Ak+1 and G A}.
Define A = A{JAk+1\Q.
3. If Nk+1 0, set k = k + 1 and go to step-1. Otherwise, proceed to step-4-
4 Set N = U*L0 Nl U(s}> A = ^U{(n> s)ln ^ A \ {s}}; and return (N, A).
Algorithm 4.8 verifies that for any node k added to the network, no imme-
diate predecessor i of node k is also a predecessor of node j that is generating k.
We can now use the trimmed network in our algorithm instead of the basic net-
work. Observe that at any stage of the algorithm, the current trimmed network
includes all of the non-transitive arcs for the corresponding basic network. By
Lemma 4.7, any optimal path in the trimmed network is also an optimal path
in the corresponding basic network.
40


4.2.2.1 Node Removal
We discussed in Section 4.1.2 opportunity cycles and their removal. Since
the trimmed network is formed from the basic network, any optimal path in
a trimmed network may also contain opportunity cycles that need to be re-
moved. To remove a node n from the trimmed network G, we need to look
at all predecessor-successor arc pairs (p, s) (i.e. (p, n) and (n, s) are the arcs
in the trimmed network). Let o be the opportunity corresponding to s. Let
t = f irst_feasible(p, o). If node t and node s are the same, add arc (p, s).
Now remove arcs (p, n) and (n, s) from trimmed network G.
Now that we have removed node n from the trimmed network, G still con-
tains only non-transitive arcs and those arcs are in the corresponding basic
network. In the removal process, either a new arc (p, s) is added to the network
or not. In the case where it is added, node s is first-feasible and reachable from
node p, thus the arc exists in the basic network. Also, axes (p, n) and (n, s)
are removed, so arc (p, s) is not transitive in G. In the case where arc (p, s)
is not added, there exists a node t ^ s in opportunity o that is first-feasible
and reachable from node p. This arc (p, t) already exists in G and provides the
algorithm with an alternate path to search for the optimal solution.
4.2.2.2 Optimality and Efficiency in the Trimmed Network
Throughout Section 4.2 we discussed that the algorithm for producing the
basic network created transitive arcs. It was further discussed that these arcs
are unnecessary and decrease the efficiency of the underlying Pulling Algorithm.
We showed how transitive arcs can be removed and how nodes involved in oppor-
tunity cycles can be removed. The resulting trimmed network contains efficient
41


paths (from the Pulling Algorithm perspective) and all such paths exist in the
corresponding basic network. So finding an optimal path in the trimmed network
always produces an optimal path in the corresponding basic network.
In Chapter 5 we will outline the implementation details of the algorithm,
from formation of the trimmed network to optimal solution generation. In addi-
tion, we shall introduce two implementation procedures: the look-ahead interval
that assists in transitive arc removal, and the no-op process that better facilitates
node removal when resolving opportunity cycles.
42


5. Algorithm Details
This chapter aggregates the algorithms discussed in Chapters 3 and 4 but
presents them in a manner that is better suited for implementation as a computer
program. The complete scheduling algorithm has two main parts. The first part
constructs the trimmed network network. It is dependent on opportunity data,
each with associated target information (latitude and longitude) and a duration
profile (a series of start times mapped to durations). The second part of the
scheduling algorithm solves the network via dynamic programming and branch
and bound.
5.1 Network Construction
This portion of the complete scheduling algorithm constructs the trimmed
network of nodes. Nodes are connected to each other through a node adjacency
list that represents predecessor arcs. The algorithm starts with a predefined node
known as the source and a collection of opportunities. It is assumed that the
opportunities were generated by an off-line process and the results are available
to this portion of the algorithm. Nodes are created within the opportunities at
the correct time by using a trivial spacecraft model that determines the time
necessary to transition from a previous node to the next opportunitys target.
The acyclic nature of the network is maintained by reaching out from a node
to opportunities, or portions of opportunities, that are in the future relative to
the end time of the node. A node on the path is a network representation of an
activity (a scheduled task).
43


5.1.1 The Look-Ahead Interval
As discussed in Chapter 4, a trimmed network is created by removing tran-
sitive arcs. This was accomplished by identifying and removing transitive arcs
between nodes throughout the entire network. The implementation of transi-
tive arc removal is more efficient through the use of a look-ahead interval. A
look-ahead interval is an interval of time that constrains the creation of new
nodes that can be reached from an existing node, and as a result it reduces the
number of transitive arcs generated dming the creation of the network. We will
show that there is never a need to consider creating arcs to nodes outside the
look-ahead interval, because such arcs would be transitive arcs. As Figure 5.1
shows, only opportunities that lie within the look-ahead interval are candidates
for the creation of new nodes. In the figure, no arc was generated from node
rij to a node in opportunitym because that opportunity lies outside the interval.
Once all arcs are created for node rij, arcs will be generated for node Uj and the
look-ahead interval will be extended from the end of that node.
The start of the look-ahead interval is the end time of the node from which
new arcs are being generated. This makes sense because all new nodes must be
in the future. The end of the interval is calculated based on the end time of
the next topologically ordered node that can be reached from the current node.
We add the maximum possible slew duration of the satellite to that end time.
Thus, the look-ahead interval is defined by
LookAheadsfart rij r
Look-Aheadend = nJe + Max.Slew-Duration
44


Figure 5.1: A Look-Ahead Interval used to reduce the number of
transitive arcs in the problem
In the look-ahead definition, nie is the end time of the node from which arcs are
being generated. Also, nJe is end time of the next topologically ordered node
after nt that can be reached from node n,.
The rationale is that every node np beyond the look-ahead interval is reach-
able from node rij, thus (nu np) would be a transitive arc, since (n*, rij) and
(rij, np) would be feasible arcs.
The look-ahead interval only reduces the total number of transitive arcs in
the network, in particular those arcs that extend beyond the maximum slew
distance of the satellite. However, it does not prevent transitive arcs from be-
ing generated within instances of the interval. To eliminate those, the original
process of node-based transitive arc trimming is used, as was discussed in the
previous chapter. Both the look-ahead interval and transitive arc trimming are
incorporated in the following implementation algorithm for creating the trimmed
45


network.
5.1.2 Network Generation Implementation Details
5.1.2.1 generate_network
This algorithm constructs the acyclic network of nodes based on opportuni-
ties associated with tasks.
Input
A predefined source node (activity) with an end time prior to the start
time of the first opportunity to schedule
A collection of opportunities
Output
An indexed and ordered list of nodes, where the ordering is by start time
Begin Algorithm
1. Add all opportunities to list O, ordered by start-time
2. Empty list N of start-time-ordered, processed nodes
3. Empty a temporary opportunity list O'
4. Initialize the look_ahead interval LAstart tirne = 1, LAendtime = 1
5. Add the source node to temporary list T
6. While T is not empty
7. Remove a node n from list T
46


8. o = get-next-order ed-opportunity(n, O)
9. Add o to O'
10. Reset the look_ahead interval LAendMme = 1
11. While O'is not empty
12. Remove an opportunity o from O'
13. Set start_time s = (nendj.ime + calculateslew-duration(n,o'))
14. If s < nendjtime or s > o'endMme, then
15. goto step-6
16. Else If s < o'start time, then set s = o'start time
17. Else s = getjnext-discrete-timestep(s,o')
18. If a node exists in o' at s, then
19. Set p = get -existing jnode(o', s)
20. Call trimJransztive-arcs(n, p)
21. Else set p = createjnew -node(o', s)
22. Add node n to node ps predecessor list
23. Add node p to temporary list T
24. If LAend_time 0 then
47


25.
Set look_aJiead St8jt_tim6 L^-start-time ^end-time
26.
Set look_ahead end_time LAen(iMme = PendMme + max slew
27.
Else set LA,
end.time
min (LAend Ume, (PendJtime T maxslew))
28.
o = get-.next-ordered-opportunityJ,ntersectingjinterval(0, n, LA)
29.
Add o to O'
30. End While Loop
31. If node n is not in N, then
32.
Add node n to N, indexed and ordered by start time
33. End While Loop
34. Return N
End Algorithm
5.1.2.2 get_next_ordered_opportunity
This algorithm finds the next opportunity, given a current position and
ordered list of opportunities.
Input
A node with an associated opportunity
An ordered list of opportunities
Output
48


The next topologically ordered opportunity or NULL
Begin Algorithm
1. Initialize p = NULL
2. Find opportunity o, parent of node n, in the ordered list of opportunities
3. If there axe more nodes after o in the ordered list of opportunities, then
4. Set p the next opportunity in the ordered list of opportunities
5. End If
6. Return p
End Algorithm
5.1.2.3 calculate_slew_duration
This algorithm calculates a slew duration from one target to another. If
ephemeris data is available then this algorithm would make use of vector calcu-
lations within an ECF (earth centered fixed) coordinate system. Because this
work did not use ephemeris data, this algorithm uses grossly simplified equations
and assumes the relationship between the satellite and the two targets can be
modeled with a right triangle, where the satellite is positioned directly over the
target where the slew begins.
Input
A node with an associated opportunity that contains a target to slew from
An opportunity that contains a target to slew to
49


Output
The amount of time required to slew
Begin Algorithm
1. Set Tjrom = the target in node n
2. Set Tto = the target in opportunity o
3. Set GCD = the great circle distance between Tfrom and Tto
4. Set a = arctan(-a^gggtitude)
5. Set t = sfewarate, where slew.rate is in degrees per second
6. Return t
End Algorithm
5.1.2.4 get _next _discret e_t imestep
This algorithm finds the next discrete time step within an image duration
profile, given a proposed start time.
Input
A proposed start time
An opportunity that contains an image duration profile
Output
A start time on a profile boundary or NULL
50


Begin Algorithm
1. Initialize s = NULL
2. If proposed start_time exists in the profile, then
3. Set s = start-time
4. Else
5. For each start time s' in the profile
6. If start-time > s' then set s = s'
7. Break from loop
8. End for
9. End If
10. Return s
End Algorithm
5.1.2.5 get_existing_node
This algorithm retrieves a node with a particular start time stored within
an opportunity.
Input
An opportunity that contains a previously created node
A start time
51


Output
An existing node or NULL
Begin Algorithm
1. Initialize n = NULL
2. If a node exists in node hash table for opportunity o at start-time, then
3. Set n = query for a node in node hash table for o at start-time
4. End If
5. Return n
End Algorithm
5.1.2.6 trim_transitive_arcs
This algorithm removes any transitive arcs between two nodes.
Input
A node starting the arc
A node ending the arc
Output
void
Begin Algorithm
1. Set sPList = list of predecessor nodes for node starting the arc
52


2. Set ePList = list of predecessor nodes for node ending the arc
3. While there are more nodes n in the ePList
4. If n is contained in sPList, then
5. Remove node n from the ePList of the node ending the arc
6. End If
7. End While Loop
End Algorithm
5.1.2.7 create_new_node
This algorithm creates a new node within an opportunity, at a given start
time.
Input
An opportunity
A start time
Output
A new node
Begin Algorithm
1. Set s = get-next-discreteJtimestep{ opportunity o, start-time)
2. Set d = the duration at s in the duration profile for o
53


3. Instantiate a new node n
4. Set flstart-time = &
5. Set fiend-time = S d
6. Set flparent-opportunity = 0
7. Add n to o
8. Return n
End Algorithm
5.1.2.8 get_next_ordered_opportunity_intersecting_interval
This algorithm retrieves the next ordered opportunity that resides within a
given interval of time.
Input
An ordered list of opportunities
A node from which to begin the search
A time interval
Output
The next topologically ordered opportunity in the interval or NULL
Begin Algorithm
1. Initialize p = NULL
54


2. Find opportunity o, parent of node n, in the ordered list of opportunities
3. For each opportunity o', topologically ordered after o
4. If o'
start-time
^ interval Istart-time and o'
start-time
I end-time then
5.
Set p = o'
6.
Break from loop
7. End If
8. End For Loop
9. Return p
End Algorithm
5.2 Dynamic Programming with Branch and Bound
This portion of the complete scheduling algorithm uses the trimmed network
to find the optimal, opportunity-cycle-free (0-cycle-free), left-justified schedule
of payload activities. Chapter 4 described the process of resolving opportunity
cycles by removing nodes. In this implementation algorithm a no-op process
will be using instead.
5.2.1 Node Removal by No-Op
A no-op is a node in the network with a weight of zero. Such a node
represents a non-operation, or no-op, activity. A no-op activity is equivalent
to an activity where no imaging operation is performed, thus no-ops add no
value to the solution. We will show that removing a node n from the network
55


is equivalent to leaving node n in the network and setting its weight to a value
of zero. The motivation for considering no-ops is a matter of efficiency in the
implementation.
In each subproblem of the following implementation algorithm, all of the
nodes except for one in a cycled opportunity have their worth (node weight)
reset to a value of zero. Each subproblem is re-solved for a longest path by the
Pulling Algorithm from the first node in the affected opportunity to the end of
the path. This runtime improvement is possible because the topological ordering
ensures that all nodes on incoming arcs for the node in question have had their
distance labels previously updated. The best feasible solution is stored at each
iteration of the algorithm, until all subproblems have been explored. A branch
and bound scheme is used to reduce the search space of subproblem exploration.
We define a path in any of the subproblems to be O-cycle-free if at most
one node in each opportunity has a positive weight in the path.
Using the no-op approach, the network topologies of all the subproblems
never change. Thus, the optimal O-cycle-free path in the original network, is
also a path in every subproblem. Furthermore, at least one child of the root
node will have every node on this path have positive weight. Thus, that path
will be an optimal O-cycle-free path for at least one child of the root node, and
at least one of its children, and so on.
Unfortunately, each subproblem may also have an optimal O-cycle-free path
that includes no-op nodes. Such paths would not necessarily be opportunity-
cycle free in their parent problem because, some of the no-op nodes might have
positive weight in the parent problem. To address this issue, we define something
56


called a subpath.
Let P = riij > ni2 > nim be a path. A subpath of P is a subse-
quence (n]l,..., nJk) of the sequence (n^,..., n,m). Note that a subpath is not
necessarily a path in the network; but it does correspond to a feasible schedule
for the satellite. We say that a subpath S is (9-cycle-free if no opportunity has
more than one node in S with positive weight.
Associated with each path P (or subpath S') in a no-op network, we define
the positive subpath of P (or S), PS(P) (or PS(S)) to be the subpath formed
from by removing all of the nodes with weight zero. Using arguments similar
to those described in Algorithm 4.3, we can then left justify the corresponding
feasible schedule. This left-justified schedule corresponds to a path P in the
basic network, which we call the positive trimmed path of P or S.
By these definitions, if P is an (9-cycle-free path in a subproblem, then
PS(P) is a O-cycle-free subpath in the parent problem. Similarly, if S is an
(9-cycle-free subpath in a subproblem, then PS(S) is an (9-cycle-free subpath
in the parent problem.
It should also be clear that, if S is an optimal (9-cycle-free subpath in
the parent problem, then PS(S) is also an optimal (9-cycle-free subpath in the
parent with all nodes having positive weight. For at least one of the subproblems,
all of these nodes will have positive weight, so PS(S) will be an optimal (9-cycle-
free subpath in at least one of the children.
Thus, if the longest path for a problem is not (9-cycle-free, we can identify
an optimal (9-cycle-free subpath by forming the k subproblems associated with
an opportunity cycle, finding the optimal 0-cycle-free subpaths associated with
57


each of the subproblems, and then choosing the subpath S with the highest
value. Then the positive subpath of S, PS(S), is an optimal subpath of the
parent problem.
Finally, once an optimal 0-cycle-free subpath is identified for the original
network, we can convert it to an optimal left-justified schedule, thereby produc-
ing an optimal 0-cycle-free path in the basic network.
To implement the branch and bound procedure using no-ops, we have to also
modify our definition of the lower bound function LB(-). Using a procedure
similar to that discussed in Algorithm 4.3, for any path P or subpath S, we
can define a reduced path P+ by first creating a subpath consisting of only the
first nonzero weighted nodes of each opportunity, and then left justifying the
associated schedule. This reduced path P+ is an 0-cycle-free path in the basic
network, so its value is a lower bound on the optimal 0-cycle-free path. Thus,
we redefine the lower bound associated with a path P as follows:
LB(P) = value (P+).
Note also that the value of this path is equal to the sum of the values of the
opportunities for which there is at least one node in P with positive weight, so
this value can be easily calculated, without having to construct P+.
5.2.2 Solution Generation Implementation Details
5.2.2.1 generate_solution
Input
An ordered list of opportunities
58


A time interval
Output
the next topologically ordered opportunity or NULL
Begin Algorithm
1. Initialize the greatest lower bound GLB = 0
2. Initialize the best path P* = NULL
3. Initialize the best path score BestScore = 0
4. Add network G to the subproblem list S
5. While S not empty
6. Remove a network G' from S
7. P' = find-optimaLpath(G', source-node)
8. If path-contains-opportunity-cycle(P'), then
9. If value(P') < GLB, then go to step-5
10. Set P+ = generate-cycle-freejpath(P')
11. Set LB = value (P+), a generated lower bound score
12.
If LB > GLB, then set GLB = LB
13.
Set LIST = generatesubproblems(G', P')
14.
Add all subproblem networks in LIST to S
59


15.
Else (P' contains no opportunity-cycles)
16. Set LB = value(P'), a feasible solution score
17. If LB > GLB, then update the best path and scores
18. Set GLB = LB
19. Set P* = P
20. Set BestScore = GLB
21. Else If LB == GLB & LB > BestScore, then update best path
22. Set P* = P'
23. Set BestScore = LB
24. End If
25. End If
26. End While Loop
27. Return P*
End Algorithm
5.2.2.2 find_optimal_path
This algorithm finds the longest path through a topologically ordered,
acyclic network of nodes that are connected by an adjacency list of predecessor
arcs. The search for the longest path begins with an input node. This allows
60


the remaining portion of the ordered network to be re-computed from the input
node. The worth of each node is either the priority of the associated task or
zero. The longest path generated by this algorithm is an activity schedule.
Input
An ordered list of nodes that represent the acyclic network
A node acting as the root, from which to begin the search
Output
An ordered list of nodes that is the longest path through the network
Begin Algorithm
1. Set node i to be the node in the network G matching the input node n
2. For each node i in topologically ordered network G
3. Set BestDist = 1
4. Set BestPred = NULL
5. Set PREDS = to the list of preceding adjacent nodes of i
6. While there are nodes in PREDS
7. Remove a node j from PREDS
8. If j distance-label BestDist then
9. BestDist j distance-label
61


10.
BestPred = j
11. End If
12. End While Loop
13. Set idistancedabel BcstDist ia-orth
14. Set ipred 3
15. End For Loop
16. Traverse the path from the sink node to the root node, adding the nodes
to reverse ordered list P
17. Return path P
End Algorithm
5.2.2.3 path_contains_opportnnity-cycle
This algorithm determines if the path within a network contains at least one
opportunity cycle.
Input
An ordered list of nodes that represent the path through a network
Output
TRUE if an opportunity cycles was found on the path; otherwise, FALSE
Begin Algorithm
1. Empty the temporary opportunity list T
62


2. For each node n in path P starting from the source node, where nworth > 0
3. Set o = the parent opportunity of node n
4. If o is not in T then
5.
Add o to T
6.
Go to step-2
7. Else
8.
Return TRUE
9. End If
10. End For Loop
11. Return FALSE
End Algorithm
5.2.2.4 generate_cycle_free_path
This algorithm takes a path that contains an opportunity cycle and creates
a modified version of the path with all opportunity cycles removed. The cycle
removal is accomplished by keeping the highest worth node in a cycled oppor-
tunity and setting the worth of all other nodes in the opportunity to a value of
zero, effectively turning those nodes into no-ops. The resulting path is a feasible
solution.
Input
63


An ordered list of nodes that represents a path containing opportunity
cycles
Output
An ordered list of nodes that represents a feasible path, as a modification
of the input path without opportunity cycles
Begin Algorithm
1. Empty the temporary opportunity list T
2. Copy input path P to create a new path P'
3. For each node n in P' starting from the source node, where nworth > 0
4. Set o = the parent opportunity of node n
5. If o is not in T then
6.
Add o to T
7.
Go to step-3
8. Else
9.
Find the node q in o of greatest worth
10.
Set all nodes in o to a worth of zero, except node q
11. End If
12. End For Loop
64


13. Return P'
End Algorithm
5.2.2.5 generate_subproblems
This algorithm resolves the first opportunity cycle in a network. For each
node in the cycled opportunity, a new version of the network is generated, where
all other nodes in the opportunity have their worth set to a value of zero. This
process creates multiple subproblem networks, each having one fewer opportu-
nity cycles.
Input
An ordered list of nodes that represents the network
An ordered list of nodes that represents the path through the network
Output
A collection of lists of nodes, where each list is a different network repre-
sentation (subproblem)
Begin Algorithm
1. Empty the temporary opportunity list T
2. Empty the list of returned networks S
3. For each node n in P, starting from the source node
4. Set o = the parent opportunity of node n
5. If o is not in T then
65


6.
Add o to T
7. Go to step-3
8. Else
9. For each node q in cycled opportunity o
10. Copy input network G to create a new network G'
11. Set all nodes in o, in G', to a worth of zero except q
12. Add G' to S
13. End For Loop
14. Break from loop
15. End If
16. End For Loop
17. Return S
End Algorithm
66


6. Solution Results
The trimmed network generation procedure and dynamic programming al-
gorithm were successfully implemented and tested against a set of randomly
generated input data. The code was not optimized for runtime or memory per-
formance; instead, the implementation focused on flexibility from a research
perspective. The code was structured in such a way that command line pa-
rameters could be passed into the executable at initialization time that allowed
certain features or behaviors to be turned on or off, or tuned. For example,
a parameter could be set that allowed the branch and bound behavior to be
turned on or off, so that its affect could be more easily measured.
The algorithms referenced in Chapters 4 and 5 were implemented using an
object-oriented paradigm in the Java programming language, version 1.4.2_09.
The code is compatable with Java version 1.5, but does not take advantage of
the newer features in 1.5. All test cases were run on an Apple G5 PowerMac
desktop computer, with dual 2 GHz PowerPC G5 processors and 2 GB of RAM,
running the Macintosh OS X Server version 10.4.4 (Tiger) operating system. The
application was assigned a minimum memory size of 512 MB and a maximum
of 1.5 GB for all test cases.
6.1 Test Case Generation
The data for each test set is randomly generated over a uniform distribution,
and all parameters are controlled through a configuration file. Because the
network generation portion of the algorithm takes a set of opportunities as
67


input data, the test case generator builds random opportunities directly instead
of tasks. The data in an opportunity includes start time, end time, target
location, task priority, and duration profile.
Targets are randomly generated within a bounded box. The box is created
by specifying a center point in latitude and longitude and offset values in each.
See Figure 6.1.
Task priorities are randomly generated between a minimum value of 1 and
a configurable maximum value (nominally a value of 10).
The duration profile assumes that activity durations over time form a con-
vex function. Since time is assumed to be discrete in this problem, a simple
arithmetic process of 1st and 2nd order differences is used to form a discrete
convex function, similar to a histogram in the X-Y plane: potential start times
run along the X-axis and associated durations are on the Y-axis. See Figure 6.1.
A start time is chosen for the opportunity and the end time is with respect
to the last entry in the associated duration profile. Choosing the start time is
based on the distance between the opportunitys target and a reference target,
called the root node. A sink node is created at an arbitrary distance away from
the (topologically) last opportunity. Both the root and sink nodes are fictitious,
relative to the randomly generated targets, and exist simply as a matter of
convenience for the network based algorithm. However, in a real problem the
root node could either be the last scheduled activity from a previous scheduling
run, or some known orbital or geospatial event (e.g. perigee or the ground tracks
crossing of a geopolitical border).
68


Figure 6.1: An illustration of the effects of target and opportunity
generation.
Finally, a configurable number of these randomly generated opportunities
are created and written to an XML file. This process is separate from the
algorithm so that many test cases can be iteratively generated. Once a test
opportunity file is created, then the algorithm can be run by specifying the
opportunity file to process for a solution. The output of the algorithm is then
piped to a text file for off-fine analysis.
6.2 Test Case Results
There are ten basic test cases, ranging from 25 opportunities to 1000. The
values recorded (see Tables 6.1 and 6.2) are the result of an average of 10 runs
for each test case. Table 6.1 records the results for the generation of the orig-
inal trimmed network, prior to any optimal path solution. It records the total
69


number of nodes and arcs generated in the network, and also records the to-
tal number of transitive arcs removed from the network to obtain the final arc
count. The average duration for all opportunities is 66 seconds, the minimum
activity duration 1.0 seconds, and the maximum activity duration 30.0 seconds,
for all test cases. The last column of Table 6.1 records the total time required
to generate the network.
Table 6.1: Trimmed Network Generation Results
Columns that express time durations will give values in fractional sec-
onds, in the format seconds.milliseconds. If the duration is long enough
to represent minutes, then the format is minutes .seconds.milliseconds.
Test Case Total Opportunites Total Nodes Total Arcs Transitive Arcs Removed Network Generation Time
1 25 134 543 111 0.186
2 50 311 2520 723 0.505
3 75 483 5741 2106 1.310
4 100 651 9479 4643 1.802
5 200 1342 35276 26803 9.556
6 300 2028 71424 68362 28.852
7 400 2713 115025 133698 1:3.980
8 500 3406 169685 231703 2:10.337
9 750 5134 331062 572482 7:28.693
10 1000 6856 537924 1085743 18:51.609
70


Table 6.2 records the average values of the optimal solutions for each test
case. The number of activities scheduled and the total number of opportunities
submitted as input to the problem are recorded. An average priority of 10.0 is
the maximum possible and would imply that all scheduled activities have the
maximum priority value. The % Resource Util is a measure of the amount of
time consumed by scheduled activities over the makespan. The makespan (un-
recorded) is the duration of time starting from the earliest scheduled activity to
the end of the latest scheduled activity. The NetDP column records the aver-
age runtime of the algorithm using the branch and bound technique. The total
number of sub-problems solved for an optimal path and the number of pruned
nodes, are both associated with running the algorithm with branch and bound
enabled. The final column records the average runtime of the algorithm without
enabling branch and bound. The algorithm was configured to prematurely exit
after a maximum of 200,000 subproblems were solved, or 50.000 subproblems
had been solved without any improvement since the last, best schedule found
so far. This was done for convenience; enabling us to make many test runs and
average the results. These threshold limits were only hit during the 75, 100,
200, and 300 opportunity test cases. On average, four of the ten runs in each of
these test cases exited prematurely.
71


Table 6.2: Dynamic Program Scheduling Results
All columns that express time durations will give values in fractional sec-
onds, in the format seconds.milliseconds. If the duration is long enough
to represent minutes, then the format is minutes:seconds.milliseconds.
% Total Total NetDP NetDP
Num Activites Avg Resource Sub- Pruned Runtime Runtime
Opps Scheduled Priority Util Problems Nodes w/ B&B w/o B&B
25 5 7.6 48.5 394 148 0.476 0.353
50 7 7.4 50.4 15228 5542 7.743 1:6.630
75 8 7.7 53.3 59586 36691 57.045 2:18.353
100 10 7.2 57.3 51923 16757 1:17.248 4:50.054
200 12 7.3 61.5 78166 39987 6:54.671 13:11.846
300 13 8.1 69.3 62956 42973 10:27.607 25:0.415
400 16 7.8 71.4 5345 568 1:8.959 38:55.029
500 17 7.8 73.8 582 287 2:25.199 55:17.330
750 20 8.1 81.8 25 5 10:49.028 8:31.701
1000 21 8.1 80.8 163 35 16:54.749 17:57.673
72


7. Solution Conclusions And Next Steps
This thesis presented the Image Satellite Mission Scheduling problem and
an algorithm that provides an optimal solution. The ISMS problem is a com-
plex combinatorial optimization problem that exhibits characteristics of both
the classic Knapsack and Traveling Salesman problems. Our thesis leveraged
the efforts described in several papers, but was most influenced by the combina-
tion of work from Wolfe and Sorenson [18], and Lemaitre, Verfaillie, Jouhaud,
Lachiver, and Bataille [10]. Our model for the problem used a trimmed, di-
rected, acyclic network. We used a dynamic programming approach, managed
by a branch and bound strategy, to obtain optimal scheduling solutions.
The results of our analysis and implementation show that dynamic program-
ming appears to be an appropriate method for modeling and providing solutions
to the ISMS problem. Other approaches have abstracted away or simply ignored
the window of opportunity and its associated complexities. We believe it is a key
element to solving a real mission scheduling problem for many satellite systems.
However, windows of opportunity cause the problem size to grow exponentially
when applying a network based solution. To that end, the use of a look-ahead
interval and branch and bound technique were key to problem tract ability.
While the algorithm provides optimal solutions, it may be limited to prob-
lems with a reasonably small solution space for it to run in a reasonable amount
of time (under 20 minutes). Even short duration opportunities generated large
numbers of potential nodes. Our assumption is that increasing the fidelity of the
73


opportunities (i.e. smaller discrete time steps) or simply adding many more in-
put tasks may sufficiently increase the solution space that runtime performance
is driven to unacceptable levels. The trend of our test results appeared to sup-
port this assumption, but then an unexpected result appeared. It was observed
that beginning with the 400-opportunity test case, the number of subproblems,
and hence the algorithm runtime, dropped significantly. It is not clear why this
occurred.
The Image Satellite Mission Scheduling problem is a difficult combinato-
rial optimization problem. This thesis was successful in addressing a simplified
version of the real problem. We believe the concepts and implementation can
be leveraged as the basis for ongoing work in this interesting and challenging
problem domain.
7.1 Considerations for Future Work
The following is a list of ideas for future work.
What are the performance implications of accommodating longer opportu-
nities (in the range of 2 to 15 minutes) that have short activity durations
(ranging from ^ to 10 seconds), and how can such implications be ad-
dressed?
How do various subproblem creation strategies affect algorithm perfor-
mance?
Would a depth-first, binary search tree method with mutually ex-
clusive branches produce solutions more quickly, while minimizing
the total number of generated solutions? The process would involve
74


creating two subproblems in the first opportunity of an opportunity-
cycle. The first, subproblem would keep the first node and remove (or
set to a weight of zero) ail others in the cycled opportunity. The sec-
ond subproblem is the opposite: removing the first node and keeping
all others.
Would a depth-first, balanced search tree method result in larger
priming of the Branch and Bound solution tree? The process would
again involve creating two subproblems in the first opportunity of an
opportunity-cycle. In this case, the first subproblem would keep the
first half of ail nodes in the cycled opportunity and remove (or set
to a weight of zero) the second half. The second subproblem is the
opposite: removing the first half of ail nodes in the cycled opportunity
and keeping all others.
How does orbit altitude affect the performance of the algorithm?
Can an upper bound on satellite altitude be established that if ex-
ceeded causes the number of possible combinations (axes and nodes)
to sufficiently overwhelm the algorithm as to render it impractical for
an operational environment?
How can the algorithm be extended to schedule multiple resources across
a constellation of satellites?
How can the algorithm be extended to consider complex collection strate-
gies that require the coordination of multiple collections, such as stereo-
scopic or monitor collections, for a single satellite? Or if considering a
75


constellation of satellites, how can a time coincident (or time synchronous)
collection using multiple satellites simultaneously be achieved?
How can the algorithm be extended to consider on-demand tasks, espe-
cially those that axe due immediately (near-real time)?
Our solution assumes a non-dynamic tasking environment. This sug-
gests that there is sufficient time to run the algorithm prior to the
satellite executing the activities. In contrast, a dynamic tasking en-
vironment can be characterized as having on-demand or interactive
requests, with near-real time scheduling and plan execution require-
ments. Can such asynchronous planning cycles be accommodated?
What is the most appropriate way of scheduling area targets?
Often an area target is decomposed into smaller sub-areas that are
more easily imaged. These sub-areas should not be treated like any
other individual point target, because the task is to collect the larger
area, at least up to some minimum area-percent-complete threshold.
How should preference be given to decomposed area targets to en-
courage their completion?
Should active target bonusing be used to increase the efficiency of the
algorithm?
A bonused target is one that is collected or whose task is implic-
itly satisfied as a side-effect of scheduling a different task, i.e. if
the bonused target falls within the collected image of another task
76


assuming all other task constraints being equal. We define Passive
Bonusing as the process of removing a task and its associated op-
portunity from scheduling consideration if the task (target) will be
bonused by a task currently on the schedule, or has been bonused
by a previously scheduled task. Active Bonusing would be the auto-
matic creation of an ad hoc task and target location that purposefully
bonuses several input task requests (the use a compromised boresight
or pointing location). Should a technique of this type be performed
as a preprocess to scheduling?
Can sufficient speed-up of subproblem exploration be realized through
multi-processing techniques?
What techniques or heuristics can be introduced to the current implemen-
tation that reduce the solution space and increase runtime performance?
How different are the test case results when a real image duration function
and real ephemeris are used?
77


Appendix A. Glossary of Terms
Activity A scheduled imaging operation performed by the payload.
Arc An element of a graph or network that represents the slew between two
possible activities on a schedule.
Area Target A potentially large area on the surface of the earth to be imaged,
often defined by a set of latitude/longitude coordinates that describe an
arbitrary polygon.
Attitude A spacecrafts orientation in three dimensional space.
Bonused Target A target that is collected as a side-effect of a different task,
where the task satisfies all objectives of the associated bonused task. The
bonused task no longer needs to be scheduled because it is implicitly sat-
isfied.
Boresight The axis or pointing direction of a satellite antenna or telescope.
Bus A set of electronic and mechanical equipment that controls the health,
safety and maneuverability of a satellite.
Collection See Activity.
Dwell The period of time a sensor collects data over a given target, i.e. the
duration of the collect.
78


Dynamic Tasking An environment that accommodates on-demand, ad hoc
task request, either externally generated (by end-users) or internally self-
generated due to some triggering event. It is assumed that scheduling
must occur in near-real time to satisfy dynamic tasks.
ECF The Earth-centered-fixed coordinate system. This system is centered
at the Earth with the x-axis aligned with Greenwich, the z-axis aligned
with the Earths spin axis and the y-axis completing the right-handed
orthogonal system. The coordinate system rotates with the same angular
velocity as the Earth.
Ephemeris A table or listing of the predicted spatial coordinates of a satellite
as a function of time.
Feasible Solution A schedule with no opportunity cycles.
Field of Regard (FOR) All of the points of the physical environment that are
within line of sight from the satellite, regardless of the satellite attitude.
Field of View (FOV) All of the points of the physical environment that are
visible to a payload instrument, with respect to the satellite attitude at a
given moment.
Ground Sampled Distance (GSD) is a measure of both image scale and res-
olution, described in meters, feet or inches. GSD refers to the amount of
ground thats imaged by a single pixel in the sensor.
Ground Track A satellites orbital path projected onto the surface of the
earth.
79


High-agility A satellite that is fully maneuverable along two or three axes:
roll, pitch and (optionally) yaw.
Imaging The operation performed by a sensor that results in an image of the
Earth.
ISMS Image Satellite Mission Scheduling problem. The problem domain for
this thesis.
Keplerian Two-Line Element Data A standard mathematical model for
describing the orbit of a satellite. When combined with a series of time
calculations, it results in ephemeris.
Look-Ahead Interval An interval of time used by a network generation pro-
cedure to limit what nodes can be reached by arcs. Used in the reduction
of transitive arcs.
Low-agility A satellite that is only maneuverable along at most one axis, e.g.
pitch, or is very limited in its ability to maneuver on a second axis (e.g.
only a few degrees of rotation about the role axis).
Low Earth Orbit an orbit usually within the range of 500 to 2000 kilometers
above the surface of the Earth.
Mission Management A functional aspect of a satellite command and control
system that is responsible for ingesting tasking requests and producing a
payload schedule for the satellite.
80


Monitor Collection Strategy A type of tasking that seeks to perform mul-
tiple collections of a target, evenly distributed over time. There can an
associated minimum and maximum number of individual collections of the
target, where the minimum is a hard constraint and the maximum is a soft
constraint.
Monoscopic Image A single image of a target.
Nadir The point on a celestial sphere directly below the observer.
NIIRS The National Image Interpretability Rating Scales. A numeric value
ranging from 1.0 to 9.0 that corresponds to a ground resolution distance
in meters, e.g. NIIRS 3 implies that objects of length 2.5 to 4.5 meters
can be resolved, or distinguished, in an image.
Node An element of a graph or network that represents a possible activity for
a schedule.
No-Op A non-operation. A scheduled activity with a node weight of zero,
indicating that the satellite will point at the associated target for the
required duration but will not perform the imaging operation. Such nodes
in the network representation of the ISMS problem can be removed for
efficiency purposes.
Opportunity An interval of time that meets all constraints of a Task for a
given Target. Often expressed as the interval of time when a sensor will
have visibility to a target.
81


Opportunity Cycle When the schedule contains two or more activities, with
the same associated opportunity, resulting in a target being visited more
than once. A redundant collection.
Optimal Path/Solution A feasible solution that maximizes the sum of the
weights (priorities) of the nodes (activities) on the path (solution), with
respect to all possible paths (solutions) for an ISMS problem instance.
Optimizer A software component that realizes a mathematical optimization
algorithm.
Payload A package of one or more sensors and other related equipment (such
as an antenna, telescope, receiver, etc) on a satellite used to perform a
specific kind of mission.
Perigee The point in a satellites elliptical orbit that is closest to the Earth.
Periodicity An indication of how often a particular task is to be executed,
often at regular intervals. For example, a task could have daily or weekly
periodicity.
Point Target A relatively small area on the surface of the earth to be imaged,
often defined by a latitude/longitude coordinate and small radius.
Priority A numerical measure of the importance of a task, often assigned by
the end-user making a task request.
Resource Allocation Process See Scheduling.
82


Root Node A real or fictitious activity, or other orbital event, that serves
as the starting point for a graph or network representation of the ISMS
problem.
Schedule A time ordered sequence of non-overlapping activities, where each
activity is assigned to a satellite resource (e.g. a sensor), and the time
between successive activities is a valid slew. The schedule is produced by
a scheduler for the purpose of determining the actions of a satellite.
Schedule Independent Constraints A set of constraints on the problem
that are independent of the current contents of the schedule. For ex-
ample, satisfying the line of sight visibility from the satellite to a target is
independent of any other activities on the schedule; by contrast, slew time
to a target is dependent on a previously scheduled activity.
Scheduler A software component or application that manages physical models
of the system and an optimizer for the purpose of creating a schedule.
Scheduling The act of creating a schedule with a scheduler.
Sensor A device that detects electromagnetic radiation and converts it into
data that represents an image. Types of data can include panchromatic,
multi-spectral or infrared.
Sink Node A real or fictitious activity, or other orbital event, that serves as the
ending point for a graph or network representation of the ISMS problem.
Slew/Slewing A change in attitude of the satellite in order to change where
83


its payload is pointing. A slew maneuver is costly in terms of time and
resources (electric gyros or fuel).
Solution Tree A Branch and Bound tree data structure that holds the solu-
tions to all solved subproblems of the ISMS problem. Leaf nodes of the
tree are feasible solutions and non-leaf nodes are solution containing one
or more opportunity cycles.
SPOT Satellite Pour lObservation de la Terre (Satellite Earth Observation
System), a low agility remote sensing satellite system designed in France
for imaging the Earth.
Stereo/Stereoscopic Image An image of the same target taken from two
different angles that results in the image having a three dimensional or
exaggerated vertical effect.
Subproblem A transformed ISMS network that maintains the same topology
as the original ISMS problem network, but has certain nodes converted
into no-ops to reduce or eliminate opportunity cycles. A child problem
(network) of the original problem (ISMS network).
Sun Synchronous Orbit An Earth satellite orbit in which the orbital plane
is near polar and such that a satellite will always pass over a specific place
on earth at the same local sun time, at fixed time intervals (e.g. once every
18 days).
Target A point or area on the surface of the earth to be imaged.
84


Task/Tasking A request for imaging combined with parameters that define
and constrain the request, such as latitude and longitude of the target,
periodicity and priority. Input data used by the scheduler to produce a
schedule of activities.
Time Coincident A complex collection strategy that requires imaging many
targets over a large region of the Earth, that often requires multiple satel-
lites to accomplish, over a small period of time.
XML Extensible Markup Language. A W3C (World Wide Web Consortium)
initiative that allows information and services to be encoded with mean-
ingful hierarchical structure and semantics that computers and humans
can understand. XML is great for information exchange, and can easily
be extended to include user-specified and industry-specified tags.
Window of Opportunity See Opportunity.
85


Appendix B. Source Code
Refer to the associated Compact Disc (CD-R) for all source code.
86


REFERENCES
[1] Ravindra Ahuja, Thomas Magnanti, and James Orlin. Network Flows:
Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River,
New Jersey, 1993. This text is considered by many to be the definitive
reference on Network Flow models and algorithms. Chapter four is the
focus of label-setting algorithms for Shortest Path problems. In particular,
a description of the Topological Acyclic Pulling algorithm is presented.
[2] Irfan Ali, Naofal Al-Dhahir, and John Hershey. Predicting the visibility of
leo satellites. This paper presented an algorithm to approximate the access
times (windows of visibility opportunity) to a circular, low earth orbiting
satellite and a fixed ground target.
[3] T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. The
MIT Press, Cambridge, Massachusetts, 1990. The classic reference for al-
gorithms of computer science. This text was used by both the authors of
Selecting and scheduling observations of agile satellites and this author
to reference the classic dynamic programming algorithm.
[4] Stuart Dreyfus and Averill Law. The Art and Theory of Dynamic Program-
ming. Academic Press, New York, New York, 1977. The first chapter of the
text provides a simple and concise explanation of Dynamic Programming
as an optimization method. A network flow example is presented, along
with all (recursive) partial solutions. This chapter also provides definitions
and in depth discussion of the optimality principals and key features which
constitute a dynamic program. The remainder of the text presents various
problem types, models and examples, giving a rather extensive treatment
of the subject.
[5] Virginie Gabrel and Daniel Vanderpooten. Enumeration and interactive se-
lection of efficient paths in a multiple criteria graph for scheduling an earth
observing satellite. European Journal of Operational Research, 139:533
542, 2002. This paper presented a model for mission planning of non-agile
low earth orbiting satellites. The authors present a dynamic programming
algorithm. This paper is also of particular interest to this thesis; however,
the model is too restrictive for direct comparison.
87


[6] William Hart. Branch and Bound. Sandia National Laboratories, 1997.
This description of the Branch and Bound algorithm is located on the
World Wide Web, at http://www.cs.sandia.gov/opt/survey/branch-and-
bound.html.
[7] Frederick Hillier and Gerald Lieberman. Introduction to Operations Re-
search. McGraw-Hill, Inc., New York, New York, 1995. This text covers
many different forms of modeling and algorithms within the field of opera-
tions research. Of particular interest is chapter 10, Dynamic Programming.
This chapter introducing the classic Dynamic Programming technique and
provides several characteristics that may make a problem suitable for Dy-
namic Programming.
[8] T. C. Hu and M. T. Shing. Combinatorial Algorithms, Second Edition.
Dover Publications, Inc., Mineola, New York, 1982. This text covers many
algorithmic techniques for solving combinatorial optimization problems. In
particular, this author referenced the section cover Branch and Bound.
[9] Jon Leachtenauer, William Malila, John Irvine, Linda Colburn, and
Nanette Salvaggio. General image-quality equation: Giqe. Applied Op-
tics, 36(32):8322-8328, 1997. This paper presented a model relating image
quality, expressed in terms of the National Imagery Interpret ability Rating
Scale (NIIRS), to fundamental image attributes.
[10] Michal Lemaitre, Gerard Verfaillie, Frank Jouhaud, Jean-Michel Lachiver,
and Nicolas Bataille. Selecting and scheduling observations of agile satel-
lites. Aerospace Science and Technology, 6:367-381, 2002. This paper pre-
sented a model for mission planning of agile low earth orbiting satellites.
The authors present four algorithms and compare them. Of particular in-
terest to this thesis is the use of a dynamic programming implementation
similar to that proposed by this thesis.
[11] George Nemhauser. Introduction to Dynamic Programming. John Wiley
and Sons, Inc., New York, New York, 1966. The introductory chapter of
this book was used to obtain a basic description of Dynamic Programming.
[12] George Nemhauser and Laurence Wolsey. Integer and Combinatorial Opti-
mization. Wiley-Interscience, John Wiley and Sons, Inc., New York, New
York, 1999. This text covers many fine details in integer and combinatorial
optimization. It presents theorems, models, algorithms, examples and com-
plexity results on many different discrete problems. This text is considered
an excellent comprehensive reference on the topic.
88