A MISSION SCHEDULING SOLUTION FOR HIGHAGILITY 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 Highagility 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 oversubscribed
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 socalled lookahead
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 LeftJustified 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 LookAhead 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 NoOp........................................... 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 LookAhead 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 NPcomplete,
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 sideeffect: 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 labelcorrecting
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 tasktarget 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 tasktarget 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, highagility 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 01 Knapsack Problem is a special
case of the WCP, and is in the class of ./VPcomplete 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 AAPcomplete 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 userdefined 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, nonpreempt.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 (31)
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 WolfeSorensen model [18].
3.2.1 Mathematical Models
Let T be the number of tasks to consider.
Let Pi = value(ti) be a nonnegative 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 nonnegative 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 tasktarget pairs, with their associated ge
ographic locations. Arcs represent slews between tasktargets. Recall from
Section 3.1.3 that the discretetime 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 LeftJustified 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 leftjustified schedules.
In the following section, we describe a network model, called the basic net
work in which all feasible leftjustified schedules are represented by paths in the
24
network, and conversely, every path in the network corresponds to a feasible
leftjustified 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
cyclefree ((9cyclefree) 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 leftjustified 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 step1. Otherwise, proceed to step3.
3. Set N = UfoWUM* ^ = 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 overcounted 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
cyclefree path from source node to sink node in the basic network is an optimal
leftjustified 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 (9cyclefree 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 (9cyclefree 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,
opportunity2 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 0cyclefree
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 (9cyclefree 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 Ocyclefree 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 Ocyclefree paths by recursively calling Algorithm
41, where each subproblem is a new input network.
5. If none of the subproblems contains a Ocyclefree path, return a flag in
dicating that no cycle free path exists in G.
31
6. Otherwise, determine the highest scoring of these 0cyclefree paths. Re
turn this path as the optimal Ocyclefree 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 Ocyclefree path in G is also a
path in at least one of the modified networks. So the optimal 0cyclefree path
in G is the highest scoring 0cyclefree 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 41 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 Ocyclefree 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 Ocyclefree.
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 leftjustified 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 43 is an Ocyclefree 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 0cyclefree 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 Ocyclefree 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 step10
6. Find an optimal path P' in G'.
7. Ifvalue(P') ^ GLB, then go to step5
8. Otherwise, if P' contains an opportunity cycle, then
(a) Create the reduced path P+ from P' using Algorithm 43.
(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 step5.
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 step5.
10. Return P* as the optimal Ocyclefree 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 0cyclefree 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 firstfeasible 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 nonnegative 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 nontransitive arcs of length 2. To generate a
trimmed network, we need to modify Algorithm 3.1 by adding a new step2 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 A3* 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 step1. Otherwise, proceed to step4
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 nontransitive 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 predecessorsuccessor 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 nontransitive 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 firstfeasible 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 firstfeasible
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 lookahead interval
that assists in transitive arc removal, and the noop 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 offline 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 LookAhead 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 lookahead interval. A
lookahead 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
lookahead interval, because such arcs would be transitive arcs. As Figure 5.1
shows, only opportunities that lie within the lookahead 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
lookahead interval will be extended from the end of that node.
The start of the lookahead 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 lookahead interval is defined by
LookAheadsfart rij r
LookAheadend = nJe + Max.SlewDuration
44
Figure 5.1: A LookAhead Interval used to reduce the number of
transitive arcs in the problem
In the lookahead 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 lookahead 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 lookahead 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 nodebased transitive arc trimming is used, as was discussed in the
previous chapter. Both the lookahead 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 starttime
2. Empty list N of starttimeordered, 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 = getnextorder edopportunity(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 + calculateslewduration(n,o'))
14. If s < nendjtime or s > o'endMme, then
15. goto step6
16. Else If s < o'start time, then set s = o'start time
17. Else s = getjnextdiscretetimestep(s,o')
18. If a node exists in o' at s, then
19. Set p = get existing jnode(o', s)
20. Call trimJransztivearcs(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^starttime ^endtime
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.nextorderedopportunityJ,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 = starttime
4. Else
5. For each start time s' in the profile
6. If starttime > 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 starttime, then
3. Set n = query for a node in node hash table for o at starttime
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 = getnextdiscreteJtimestep{ opportunity o, starttime)
2. Set d = the duration at s in the duration profile for o
53
3. Instantiate a new node n
4. Set flstarttime = &
5. Set fiendtime = S d
6. Set flparentopportunity = 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'
starttime
^ interval Istarttime and o'
starttime
I endtime 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, opportunitycyclefree (0cyclefree), leftjustified schedule
of payload activities. Chapter 4 described the process of resolving opportunity
cycles by removing nodes. In this implementation algorithm a noop process
will be using instead.
5.2.1 Node Removal by NoOp
A noop is a node in the network with a weight of zero. Such a node
represents a nonoperation, or noop, activity. A noop activity is equivalent
to an activity where no imaging operation is performed, thus noops 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 noops 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 resolved 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 Ocyclefree if at most
one node in each opportunity has a positive weight in the path.
Using the noop approach, the network topologies of all the subproblems
never change. Thus, the optimal Ocyclefree 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 Ocyclefree 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 Ocyclefree path
that includes noop nodes. Such paths would not necessarily be opportunity
cycle free in their parent problem because, some of the noop 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 (9cyclefree if no opportunity has
more than one node in S with positive weight.
Associated with each path P (or subpath S') in a noop 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 leftjustified 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 (9cyclefree path in a subproblem, then
PS(P) is a Ocyclefree subpath in the parent problem. Similarly, if S is an
(9cyclefree subpath in a subproblem, then PS(S) is an (9cyclefree subpath
in the parent problem.
It should also be clear that, if S is an optimal (9cyclefree subpath in
the parent problem, then PS(S) is also an optimal (9cyclefree 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 (9cycle
free subpath in at least one of the children.
Thus, if the longest path for a problem is not (9cyclefree, we can identify
an optimal (9cyclefree subpath by forming the k subproblems associated with
an opportunity cycle, finding the optimal 0cyclefree 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 0cyclefree subpath is identified for the original
network, we can convert it to an optimal leftjustified schedule, thereby produc
ing an optimal 0cyclefree path in the basic network.
To implement the branch and bound procedure using noops, 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 0cyclefree path in the basic
network, so its value is a lower bound on the optimal 0cyclefree 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' = findoptimaLpath(G', sourcenode)
8. If pathcontainsopportunitycycle(P'), then
9. If value(P') < GLB, then go to step5
10. Set P+ = generatecyclefreejpath(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 opportunitycycles)
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 recomputed 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 distancelabel BestDist then
9. BestDist j distancelabel
61
10.
BestPred = j
11. End If
12. End While Loop
13. Set idistancedabel BcstDist iaorth
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_opportnnitycycle
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 step2
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 noops. 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 step3
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 step3
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
objectoriented 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 XY plane: potential start times
run along the Xaxis and associated durations are on the Yaxis. 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 offfine 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 subproblems 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 lookahead
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 400opportunity 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 depthfirst, 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 depthfirst, 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
opportunitycycle. 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 ondemand tasks, espe
cially those that axe due immediately (nearreal time)?
Our solution assumes a nondynamic 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 ondemand or interactive
requests, with nearreal 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 subareas that are
more easily imaged. These subareas 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 areapercentcomplete 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 sideeffect 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 speedup of subproblem exploration be realized through
multiprocessing 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 sideeffect 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 ondemand, ad hoc
task request, either externally generated (by endusers) or internally self
generated due to some triggering event. It is assumed that scheduling
must occur in nearreal time to satisfy dynamic tasks.
ECF The Earthcenteredfixed coordinate system. This system is centered
at the Earth with the xaxis aligned with Greenwich, the zaxis aligned
with the Earths spin axis and the yaxis completing the righthanded
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
Highagility 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 TwoLine 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.
LookAhead 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.
Lowagility 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.
NoOp A nonoperation. 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 enduser 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 nonoverlapping 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,
multispectral 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 nonleaf 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 noops 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 userspecified and industryspecified tags.
Window of Opportunity See Opportunity.
85
Appendix B. Source Code
Refer to the associated Compact Disc (CDR) 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 labelsetting algorithms for Shortest Path problems. In particular,
a description of the Topological Acyclic Pulling algorithm is presented.
[2] Irfan Ali, Naofal AlDhahir, 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 nonagile
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/branchand
bound.html.
[7] Frederick Hillier and Gerald Lieberman. Introduction to Operations Re
search. McGrawHill, 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 imagequality equation: Giqe. Applied Op
tics, 36(32):83228328, 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, JeanMichel Lachiver,
and Nicolas Bataille. Selecting and scheduling observations of agile satel
lites. Aerospace Science and Technology, 6:367381, 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. WileyInterscience, 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
