A network flow approach for constellation planning

3.1. Task definition

The satellites, within the constellation, will be commanded to perform two distinct types of tasks. The first is an imaging task and the second a downlink task. The imaging task corresponds to collecting an image of a particular target and the downlink task corresponds to downlinking image data to a ground station. Both the imaging and downlink tasks have temporal and spatial constraints dictating how and when the task can be performed. The imaging task may have an additional lighting constraint. Each of these constraints is summarized in Table 2. The spatial and lighting conditions can be transformed into temporal conditions for each satellite by considering the satellite trajectory, which defines the position of the satellite as a function of time. Each constraint is now discussed by assuming that a time value and satellite position are specified.

The temporal constraint satisfaction is determined by evaluating whether or not the opportunity time occurs within the allowable execution window. Temporal constraints allow the system to set limits on when a target is available for collection due to seasonal or weather concerns, or when a ground system outage occurs for a downlink antenna.

The spatial constraints depend upon the position of the satellite. These constraints are defined in terms of elevation and azimuth angles and use frames centered at the imaging target or ground antenna. Generally, the elevation angle constraints for ground antennas are set to ensure line-of-sight access to the satellite from the antenna, whereas the elevation constraints for an imaging target ensure high overhead imaging to ensure quality data. The azimuth angle constraint controls which side is available to the satellite and can be used to avoid target or antenna occlusion from neighboring buildings or nearby mountainous terrain.

The calculations for the elevation and azimuth angles are performed in the East-North-Zenith (ENZ) frame as depicted in Figure 2, and denoted as $$ N $$ in this paper. The relative position of the satellite with respect to the target in this frame is given as

Figure 2. Depiction of a valid access window using elevation and azimuth constraints on the left and a discretized satellite trajectory through the window on the right.

The elevation angle of the satellite relative to the target is calculated as

The azimuth angle, of the satellite relative to the target, is calculated in a similar manner as described by

In addition to the temporal and spatial constraints, the imaging task may also include lighting constraints. For example, the simulation in Section 6 constrains all targets to be valid only during the daytime (i.e., sun elevation angle between 0\textdegree{} and 90\textdegree{}). The calculation of the sun elevation angle is done exactly as before by replacing the satellite location with the apparent location of the sun, as in

The time in question is considered valid for a particular satellite if the time is within the temporal bounds and the calculated elevation and azimuth angles from the target to the satellite, as well as from the target to the sun, are within the angular bounds at the given time. Given the valid access times, access windows for each task are found using root finding techniques to determine the start and end time of each window.

3.2. Graph node generation

The access window of each task forms an essential element to the creation of graph nodes. There are four types of nodes added to the graph. A starting and ending node for each satellite is added to the graph corresponding to the satellite position at the start and end time of the planning horizon. Backbone nodes are added (discussed in Section 5 as means to maintain connectivity of the graph when pruning edges). The fourth node type corresponds to a task (image collect start time or ground station opportunity start time discretized as shown in right-hand side of Figure 2). The nodes are denoted as $$ v_i $$, $$ i = 1, ..., n_v $$ where $$ n_v $$ is the total number of nodes in the graph. Each node corresponds to a specific satellite at a specific point in time, either performing a task or in standby.

The task nodes are created from a discretization of the access window for each task with each point of discretization becoming a node in the graph. A more accurate graph can be created with a finer sampling of the valid time windows, but at the cost of increasing $$ n_v $$, which adversely affects the graph complexity. Figure 2 illustrates a valid access window for a particular target and satellite flight path. The time window discretization is overlaid on the valid access window to arrive at the initial set of nodes for that particular target and satellite.

An orientation vector, $$ \gamma_i $$ where $$ i $$ is the node index, is associated with each node except the ending node. For the starting node, $$ \gamma_i $$ corresponds to the pointing vector of the camera at the starting time. For imaging and downlink nodes, $$ \gamma_i $$ corresponds to the vector pointing from the satellite to the target or ground antenna at that point in time while the backbone nodes assume a nadir orientation, and the final graph node is not assigned a value for $$ \gamma_i $$. Not associating an orientation with the final node effectively allows any node to be the final imaging task assigned for the satellite.

Also associated with node $$ i $$ is a score, $$ s_i \geq 0 $$. As each node is associated with a particular satellite at a particular point in time, the score for a particular task can vary based upon the satellite performing the task and the time at which the task is being performed. Establishing viable transitions between these nodes is discussed in the next section.

3.3. Graph edge creation

With the nodes established, it is now possible to evaluate the feasibility of the satellite to transition between them via an edge. Associated with each potential edge is a slew angle that corresponds to the change in orientation between nodes. The required slew rate is determined by calculating the required angular change divided bye allowable time between nodes. An edge is only added to the graph if the slew rate is below the allowable slew rate, defined by the agility of the particular satellite.

Given two pointing vectors, $$ \gamma_{i} $$ and $$ \gamma_{j} $$ corresponding to nodes $$ v_i $$ and $$ v_j $$, the angle between them, $$ \theta_{ij} $$, can be calculated using the relation between the cosine and dot product:

Using $$ t_i $$ and $$ t_j $$ to denote the times that correspond to nodes $$ v_i $$ and $$ v_j $$, the nominal slew rate is calculated as

A transition between nodes is deemed feasible if the nominal slew rate is below the maximum allowed slew rate for a particular satellite. If feasible, the edge is added to the graph. As no orientation angle is associated with the final node, an edge is allowed between all nodes and the final node. This effectively allows any node to transition to the final task guaranteeing at least one valid solution through the graph.

3.4. Graph scoring and costs

When performing a graph search, the optimization engine attempts to traverse the graph in a way that maximizes utility for the mission. Utility is defined as the score of performing a task minus the cost, or penalty, required to do so. The globally-optimal plan considers the mission holistically and selects a path through the graph for each satellite that accomplishes this. Each satellite is not necessarily optimal but the complete mission plan is.

For imaging tasks, the score is the parameter used for assessing priority of the collection and acts as a reward for arriving at the end node of the edge (i.e., the worth of the task performed at the end node). The notation $$ \sigma_i $$ represent the node index at the end of each edge $$ i $$, denoted $$ e_i $$. For example, if $$ e_i $$ connects nodes $$ j $$ and $$ f $$, then $$ \sigma_i = f $$. The notation $$ s_i $$ is used to represent the score of an edge. Imaging tasks scores are contained on the edge entering the imaging node.

For downlink tasks, the score for task $$ i $$ is calculated as the duration of the edge ($$ d_i $$) multiplied by the data rate ($$ r $$) and the arriving edge score ($$ s_{\sigma_i} $$), divided by the on-board memory size of the satellite ($$ p $$), or

For edges that end at a downlink task but do not come from a downlink task for the same ground station the score is 0, $$ s_i = 0 $$. This is because the graph must enter a downlink start node before realizing the downlink score when traversing the subsequent edges.

The cost, or penalty, associated with each edge of the graph is the weighted slew rate necessary to perform the maneuver between neighboring task opportunities (e.g., from node $$ h $$ to node $$ i $$), with a higher required slew rate resulting in a higher penalty. The utility at node $$ i $$, when transitioning from node $$ h $$, is given as

where the slew cost weighting factor is represented as $$ \beta $$. The utilities are combined into a single vector as $$ u = \begin{bmatrix} u_1 & u_2 & ... & u_{n_e} \end{bmatrix}^T $$, where $$ n_e $$ is the total number of edges.

3.5. The graph representation

The graph $$ G $$ is now formally defined and contains set of nodes (or vertices), $$ V $$, and edges, $$ E \subset V \times V $$, i.e. $$ G =\{V, E\} $$. Given two nodes in the graph, $$ v_1, v_2 \in V $$, an edge from $$ v_1 $$ to $$ v_2 $$ implies that the pair $$ (v_1, v_2) $$ is in the edge set, $$ E $$, i.e. $$ (v_1, v_2) \in E $$. An example graph is shown in Figure 3 with four nodes and five edges. Recall that each node corresponds to an instant in time and applies to a particular satellite. Thus, given a constellation of $$ n_s $$ satellites, $$ G $$ consists of $$ n_s $$ distinct subgraphs.

Figure 3. A simple graph is presented with numbered circles as nodes and labeled edges. The right image illustrates two group constraints, one around nodes $$ v_2 $$ and $$ v_4 $$ and one around nodes $$ v_3 $$ and $$ v_4 $$.

The planning will make use of the graph's incidence matrix, $$ D $$, as defined in ^[35]. Note that the definition of incidence matrix often includes a positive one in both nonzero rows of each column. The incidence matrix as defined herein is also referred to as the coefficient matrix ^[36]. Given $$ |V| = n_v $$ and $$ |E| = n_e $$, where $$ |\cdot| $$ denotes the cardinality of a set, the incidence matrix is of dimension $$ n_v \times n_e $$. Each column of $$ D $$ is used to represent an edge. Expressing the $$ i^{th} $$ row of the $$ j^{th} $$ column as $$ d_{ij} $$, the incidence matrix can be expressed element-wise as follows:

The signed elements of the incidence matrix allow for quick evaluation of the number of incoming and outgoing edges for each node. This will be useful later to generate continuous paths through the graph. One additional matrix that will be used for evaluating the density of the graph is the directed adjacency matrix. The adjacency matrix, denoted $$ Adj $$, is an $$ n_v \times n_v $$ matrix where row $$ i $$ column $$ j $$ will equal $$ 1 $$ if an edge begins at node $$ v_i $$ and ends at node $$ v_j $$, with a value of $$ 0 $$ otherwise.

Simple Example of the Incidence and Adjacency Matrices:

For example, the incidence and adjacency matrices for the graph in Figure 3 are written as

Column $$ j $$ of $$ D $$ corresponds to edge $$ e_j $$ in Figure 3 with the positive element corresponding to the originating node. Row $$ i $$ of the adjacency matrix shows the nodes to which node $$ i $$ can directly connect. With nodes and edges connected and properly quantified for utility, the flow through the graph can now be investigated.

4.1. A Network flow approach to graph search

A mixed integer formulation of the graph search is developed by using a binary decision variable to represent each edge in the graph, denoted as $$ x_i \in \{0 \mbox{ } 1\} $$ for $$ i = 1, ..., n_e $$ (recall that $$ n_e = |E| $$). A value $$ x_i = 1 $$ indicates that edge $$ i $$ is part of the path and a value of $$ 0 $$ indicates that edge $$ i $$ is not. To select one path over another, the utility $$ u_i $$ discussed in Section 3.4 is associated with each edge. The total utility of the selected paths can be written as the summation of the individual utilities, $$ u_1x_1 + u_2x_2 + ... + u_{n_e} x_{n_e} = u^T x $$.

To ensure that the choice of $$ x_i $$ forms continuous paths from each satellite's starting node to each satellite's ending node, a network flow conservation constraint is employed. This constraint requires that the start node have a single exit path, the end node has only one entry path, and all other nodes, between the start and end node, have both a single entry and single exit to conserve flow. Imagine a simplistic network of pipes carrying water. Each node represents a connection point of various pipes and each edge represents the pipes. Special nodes called "sources" can provide water while others called "sinks" can store or consume the water. All other nodes are intermediary and must simply pass out whatever water comes into the node. Returning to the path planning problem, the "source" nodes are where the satellites start and the "sink" nodes are the terminal nodes for each satellite. All intermediary nodes are decision points. See ^[36] Chapter 10 for a thorough review of network flow problems.

For the graph search problem, the network flow conservation constraint consists of the source providing a unit of flow, the sink accepting a unit of flow, and all other nodes having a balance of flow (i.e., if an incoming edge to the node is selected, exactly one outgoing edge must also be selected). Recall that row $$ i $$ of the incidence matrix will have a "$$ 1 $$" in columns corresponding to edges that start at node $$ i $$ and a "$$ -1 $$" where edges terminate at node $$ i $$. Writing $$ d_i $$ as the $$ i^{th} $$ row of the incidence matrix, $$ d_i x = b_i $$ implies that there are $$ b_i $$ more edges originating at node $$ i $$ than terminating at node $$ i $$ (note, $$ b_i $$ can be negative). Thus, a source node must have $$ b_i = 1 $$, a sink node $$ b_i = -1 $$, and an intermediate node $$ b_i = 0 $$.

Assuming that no two satellites are collocated, each satellite will have a distinct access schedule to each imaging task. The aggregate graph nodes and edges could each be separated into $$ n_s $$ disjoint subsets, one for each satellite. Each disjoint subset has its own source and sink node. $$ D_l $$ is used to denote the incidence matrix corresponding to the access schedule of satellite $$ l $$. Assuming that the source node for each satellite corresponds to the first row of $$ D_l $$, the sink node corresponds to the final row, and an abuse of notation is used to write the edge variables corresponding to satellite $$ l $$ as $$ x_l $$, the network flow constraint for satellite $$ l $$ can be represented as

The aggregate network flow could be written by combining the disjoint components of the incidence matrix as follows.

The optimization problem can then be written to include this constraint as:

Simple Example of the Network Flow Constraint:

Consider the simple example from Figure 3 with corresponding incidence and adjacency matrices in (8). The network flow constraint in (9) would be reduced to

A line-by-line overview of the constraint can help to understand the flow constraint. Line 1 indicates that $$ e_1 $$ must be used. This is also obvious from Figure 3 as it is the only edge coming out of the source. Line five states that either $$ e_6 $$ be active or $$ e_7 $$, but not both, which is also readily apparent from the figure as these edges lead into the sink. Rows two, three, and four maintain the balance of incoming edges to outgoing edges and ensures the continuous flow through those nodes.

4.2. The group constraint

As each satellite has its own disjoint subgraph, each satellite could plan independently. However, multiple nodes in the graph exist for each task. A group constraint is added to provide the requisite coordination, ensuring that only one node for each task will be selected. Each group of nodes is collected into a set where $$ \mathcal{V}_i \subset V $$ corresponds to group $$ i $$ and there are a total of $$ n_g $$ groups (i.e., $$ i = 1, ..., n_g $$). The set of edges leading into group $$ i $$ is denoted as $$ \mathcal{E}_i $$, where

Note that this edge subset may include multiple edges corresponding to a single satellite's disjoint edge set or edges from multiple satellite edge sets. The index set, $$ \mathcal{I}_i $$, contains the edge indices corresponding to $$ \mathcal{E}_i $$. The constraint for group $$ i $$ can be written in summation form as

Combined with the fact that $$ x_j \in \{0, 1 \} $$, (10) ensures that a maximum of one edge will enter the group.

$$ \mathcal{I}_i $$ can be used to write the constraint in matrix form. The matrix $$ A_g $$ and vector $$ b_g $$ are used to represent the constraint as $$ A_g x \leq {\mathbb{1}}_{n_g} $$, where $$ {\mathbb{1}}_{n_g} $$ is a column vector of $$ {n_g} $$ ones. Allow $$ a^{g}_{ij} $$ to be the entry of $$ A^{g} $$ in the $$ i^{th} $$ row and $$ j^{th} $$ column. $$ A^{g} $$ can be expressed as

The problem, including the group formulation can now be written as

Note that the group constraint only limits the number of selected incoming edges to be at most one. Due to the flow conservation constraint, $$ Dx = b $$, the number of chosen edges proceeding from each group will also be at most one.

Simple Example of the Group Constraint:

We continue with the previous graph example describing the group constraint depicted in Figure 3. There are two group constraints depicted in green and red in the figure. The first is around nodes $$ v_2 $$ and $$ v_4 $$ with the incoming edge set $$ \mathcal{E}_1 = \{e_1, e_4\} $$ and the index set $$ \mathcal{I}_1 = \{1, 4 \} $$. The second is formed with nodes $$ v_3 $$ and $$ v_4 $$ with $$ \mathcal{E}_2 = \{e_2, e_5\} $$ and $$ \mathcal{I}_2 = \{2, 5 \} $$. The group constraints can be written as

4.3. Data constraints

Nodes corresponding to an imaging or downlink task, will affect the data onboard the satellite. Let $$ m_i $$ represent the memory consumption at node $$ i $$ with $$ m_i > 0 $$ for imaging tasks, $$ m_i < 0 $$ for downlink tasks, and $$ m_i = 0 $$ for all non-task nodes. The data onboard spacecraft $$ l $$ at time $$ k $$ is denoted as $$ y_{lk} $$. The data vector over time for spacecraft $$ l $$ is denoted as $$ y_l $$ and all data vectors are combined in the vector $$ y $$, i.e.,

where $$ n_t $$ is the total number of time steps being considered, $$ n_s $$ is the number of spacecraft, and $$ n_d $$ is the total number of data variables.

The data at time $$ k $$ will depend upon the data at the previous time step and the edge taken to arrive at time $$ k $$. The set $$ V_{lk} \subset V $$ represents the nodes associated with spacecraft $$ l $$ at time $$ k $$. As each node has an associated time value, two observations can be made about the structure of the graph:

$$ 1.\ $$The network flow constraint will restrict the number of edges entering $$ V_{lk} $$ to be at most one.

$$ 2.\ $$The edge taken to arrive at time $$ k $$ will come from a node in $$ V_{lj} $$ where $$ j \leq k $$.

Denote the index set $$ I_{lk} $$ as the set of edge indices corresponding to edges that terminate at a node in $$ V_{lk} $$. Recall that $$ \sigma_i $$ denotes the index of the node where edge $$ i $$ terminates (i.e., if $$ e_i = (v_j, v_p) $$, then $$ \sigma_i = p $$). The updated memory consumed at time $$ k $$ can then be written as

where $$ y_{l, 0} $$ is the initial data storage. Note that multiplying $$ x_j $$ by $$ m_{\sigma_j} $$ ensures that the contribution of node $$ \sigma_j $$ to the total data is only received when an edge is chosen that enters node $$ {\sigma_j} $$.

The variables of optimization are now a combination of the edge variables and dynamic variables, $$ z = [x^T \mbox{ } y^T] \in {\mathbb{R}}^{(n_e + n_d)} $$. Another index mapping, $$ \eta_{lk} $$, is used to map the data variables to their respective index in the optimization vector such that $$ z_{\eta_{lk}} = y_{lk} $$.

The relation in (13) can then be written in matrix form for spacecraft $$ l $$ by defining the matrix $$ A_{data}^l {\mathbb{R}}^{n_t \times (n_e + n_d)} $$ where

The aggregate data update constraint can then be written as

Note that each data element is assigned a zero utility (i.e., $$ u_{\eta_{l, j}} = 0 \mbox{ } \forall l, j $$). The optimization problem with group and on-board memory constraints can then be written as

4.4. Example graph formulation

This section will now provide an example of the problem formulation for a single satellite performing imaging only (i.e., no downlink operations). A later example will address the coupled imaging and downlink scenario. The graph shown in Figure 4 will now be formulated using the network flow method outlined above. The edges are labeled with the letter 'x' and a numeric subscript to indicate the edge number. A numeric value is present with each edge to show the utility score associated with that edge. The grouping of nodes within each ellipse represent discrete time steps from $$ k_1 $$ to $$ k_6 $$ and show that only one node within each group can be visited within that time step since the satellites are modeled as satellites that can only perform one task at a given time. This application of grouping constraints is critical to the planning technique presented in this work and unique to the literature previously referenced. The resulting $$ D $$ matrix is shown in Figure 5.

Figure 4. The optimal path through the graph when solving this problem using the network flow approach outlined. The path through the nodes is given as edges 2, 8, 15, 20, and 22.

Figure 5. The resulting $$ D $$ matrix from the example graph.

Solving the problem, using the network flow implementation, results in the edge selection sequence of 2, 8, 15, 20, 23 as shown in Figure 4. The edges emphasized with green illustrate the optimal path through the graph when only considering imaging opportunities.

The network flow concept is now presented in the presence of imaging and downlink tasks within a memory-constrained satellite environment. Consider the same graph from above but now with nodes 5, 8, and 9 becoming downlink opportunities instead of imaging operations. To properly create the $$ A_{data} $$ matrix, we must specify the amount of memory associated with each node, or edge, in the graph.

The memory associated with each operation is shown overlaid on the graph as purple numbers in Figure 7. Note that memory associated with imaging operations are applied at the node but downlinking operations bookkeep memory on the edge between downlink nodes due to the time discretization applied in the problem. The actual amount of memory downlinked however, is the product of the length of the edge and the downlink rate. This ensures proper accounting for edge length since downlinking occurs over extended periods of time and imaging operations are modeled as instantaneous collections. Memory for downlinking is computed by multiplying the edge length (time) by the downlink rate of the spacecraft. Notice that the start and end nodes are assigned a memory value of 0 while the edges between nodes 5, 8, and 9 have all been allocated a memory amount of -11 to denote downlink to the ground terminal. The resulting $$ A_{data}^1 $$ matrix (1 for a single satellite) is shown in Figure 6.

Figure 6. The $$ A_{data}^1 $$ matrix representing the flow of memory through the graph.

Figure 7. The path solution resulting when constraining the on-board memory to a value of 20. The path of edges is given as 2, 8, 14, 16, and 21.

For this initial example, the memory limit is set to a value of 20. Note that this limit applies to every time step within the planning graph and ensures that the satellite does not collect more image data than it can save on-board. Solving this problem again with a memory limit set results in a new sequence through the graph nodes. This new sequence is shown in Figure 7. Note, that the new graph solution deviates from the original and passes through nodes 8 and 9 to reduce the amount of image data on-board the vehicle. The resulting data storage at each time step, from $$ k_1 $$ to $$ k_6 $$, is given in Table 3.

6.1. Orbital scenario

A 500 km sun-synchronous orbit was chosen to provide realistic access periods to both targets and ground stations within the view of the Earth imaging satellites. The epoch for this scenario is August 1, 2021 at 18:00:00 UTC with accompanying orbital elements specified in Table 4. This orbit represents the seed satellite of a Walker delta constellation of 100 satellites and 25 orbital planes with no relative phasing between neighboring planes. A Walker delta pattern constellation provides a simple, parameterized method for conveying the orbital geometry for a constellation of many satellites. These parameters specify the inclination, total number of satellites, number of orbital planes, and the relative phasing between satellites in neighboring planes. This phasing angle is the angle difference, in the direction of orbital motion, from the ascending node to the closest satellite, when a satellite in the next westerly plane is at its ascending node. Again, in this example the relative phasing is 0\textdegree. A Walker delta pattern constellation starts with a seed satellite and generates the entire constellation from its orbital information. For more information about Walker constellations, see ^[38]. The ground terminals supporting downlinking operations are located in Alaska, Antarctica, Australia, Hawaii, and Norway. A total of 2, 814 imaging targets were considered during planning, with these targets being approximately evenly spaced across the Earth's land mass as depicted in Figure 12.

Figure 12. Imaging target distribution across the Earth's land mass area with targets accessible during the planning period marked in green. Targets marked in red do not meet the lighting constraints due to being in eclipse during the planning period.

6.2. Results

The network flow constellation planning algorithm discussed throughout this paper was run on the mission scenario described previously to arrive at a constellation flight schedule. Several metrics were collected for each of the satellites to assess their performance and help evaluate the constellation planning routine. The metrics of particular interest in the DRM are satellite utility, number of targets collected, number of targets downlinked, and overall satellite memory state. These metrics are shown over the planning horizon timeline of approximately 3 hours (2 orbit revolutions) in Figure 13. The figure illustrates the performance that can be anticipated when using the network flow constellation planning routine presented. For context, Figure 14 also shows the satellite constellation with orbit trajectories, imaging events, and downlink operations illustrated.

Figure 13. These figures show the results from a simulation with 100 satellites in 25 planes with 2814 ground targets spread over the surface of the earth and 5 ground stations in Alaska, Antarctica, Australia, Hawaii, and Norway. The left axis (in blue) shows the collective satellite values and the right axis (in red) shows the values for individual satellites.

Figure 14. Global view of satellite planes and orbital configuration analyzed using 100 satellites in 25 planes with 5 ground terminals. In the left illustration, the red dots show where the satellite was located when an image was captured while the pink line illustrates the pointing at the time of collection. In the right illustration, the pink lines centered on the ground stations mark the downlink access periods. The targets colored in blue are those that were not considered during planning due to being in eclipse and not meeting the specified lighting constraints.

The results shown in Figure 13 provide insight into specific satellite assignments with red dashed lines representing individual satellites while the blue line in each plot highlights the collective performance across the constellation. The utility score, number of targets collected, and number of targets downlinked trend in an upward fashion since these metrics are cumulative and continue to increase as the satellites perform the imaging and downlinking operations over the simulation period. The satellite memory state plot is more variable as the satellites balance on-board memory capacity with new imaging collection opportunities and downlink operations. The memory plots show some satellites reaching a plateau in consumed on-board memory, indicating that imaging or downlink opportunities were either not selected or unavailable during that time, while other satellites show both imaging and downlinking operations occurring. The simulation was initiated with all satellites having all memory available on-board. Due to this, the global blue line trends upward for this simulation as memory across the constellation is consumed with imaging operations across the fleet.

Planning the imaging and downlink operations for 100 satellites over a multi-revolution period on a desktop PC is a challenging endeavor, yet the network flow technique proved to be capable. This implementation shows the ability to arrive at an optimal plan for a large constellation of 100 satellites while not exceeding the individual satellite's resources. Furthermore, the plots show a relative global consistency for the constellation while also identifying unique trends and behaviors for each satellite. This consistency is due to the fairly homogeneous distribution of satellites relative to the imaging and downlink opportunities across the globe and lends confidence to the viability and consistency of the resulting solution.

The utility score and targets collected plots show a strong trend upward, meaning that imaging continues to progress throughout the planning period. Similarly, downlink is being optimized across the constellation, as illustrated by number of targets downlinked and onboard memory state plots, to ensure delivery of the data and prevent on-board resources from being exceeded. These results highlight the power behind the network flow method and support further research into this area. In particular, further research is warranted into additional methods for understanding the elapsed time from the collection of a specific image to the time that image information is delivered to the ground. The current implementation focuses on prioritized data collection and delivery but does not account for the value of quick delivery of image data. The latency metric is of particular interest to GEOINT missions due to the value in timely intelligence. Low-latency information allows planners to make time-critical decisions with greater confidence and is thus an important metric within the GEOINT community ^[39].

Authors' contributions

Skylar A. Cox (Conceptualization, Methodology, Formal Analysis, Writing); Greg N. Droge (Conceptualization, Methodology, Formal Analysis, Writing); John H. Humble (Software Development, Mission Simulation); and Konnor D. Andrews (Software Development, Mission Simulation).

Availability of data and materials

Not applicable

Financial support and sponsorship

None.

Conflicts of interest

All authors declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2022.