Heuristic-Based Mission Planning for an Agile Earth Observation Satellite

Abstract

In this paper, mission planning for an earth observation satellite is studied. Generally, the mission planning problem is known as a highly combinational problem. While exact methods can provide optimal scheduling solutions, they require large computation time so the exact methods may not be adequate for timely operations. In this paper, a simple yet effective heuristic method for mission planning is proposed. An additional degree of freedom in pitch axis is taken into account, which can significantly increase the number of images compared to the roll-only observations. Also, possibility of reverse order observation is considered with a simple objective function. The proposed method is applied to short-horizon mission planning in low earth orbit. The exact brute-force search is utilized as a counterpart to analyze optimality and time-effectiveness of the proposed method. Numerical results show that the proposed method offers a slightly degraded solution but runs very fast due to its simplicity.

1 Introduction

Generally, a primary mission of earth-observing satellites is to acquire ground target images requested by users. Growing interests of ground observations for environmental monitoring and reconnaissance purpose result in a growing number of required images. Hence, a need for optimal solution to satellite scheduling problem, which selects feasible ground targets and schedules them optimally, has gained much attention in recent days. A general process of mission planning is summarized in Fig. 1. The mission planning problem is highly complex [1] due to its several models and constraints, which, in detail, are models of target, satellite, and ground station, and constraints from attitude maneuverability, data storage, and image downlink rates.

Fig. 1

A general process of mission planning

Many researchers have investigated on developing optimal algorithms for mission planning problem [1,2,3,4,5,6,7,8,9,10,11,12]. Bensana et al. [2] formulated and conducted mission planning for the daily management of the earth-observing satellite SPOT 5. They applied exact and inexact (approximate) methods and compared their performance. Lemaitre et al. [1] proposed the revised satellite scheduling algorithm for agile satellites, e.g., the Pleiades satellite, compared to the previous non-agile SPOT 5 satellite. References [3] and [4] also dealt with mission planning for the Pleiades satellite. A planning algorithm for synthetic aperture radar (SAR) instruments is proposed in [5]. In addition, planning algorithms for satellite constellation or satellite fleet, not just a single satellite, were proposed in [5,6,7].

In this paper, a heuristic algorithm is pursued to address the problem of mission planning for an earth observation satellite. Heuristic-based methods have been widely investigated in decision-making problems such as path planning of unmanned aerial vehicles [13, 14]. In addition, there have been attempts to apply the heuristic in satellite mission planning problems [4, 7, 8, 15]. The major advantage of the heuristic-based solutions over the exact optimal solutions is computation time-effectiveness that may enable on-board autonomous operations. For example, on-board automated mission planning was proposed for earth observation satellites in [4], which could accommodate the sudden weather change such as the presence of clouds by responsively updating the existing observation plan. This study also aims to develop a simple heuristic-based planning algorithm that may broaden autonomy of the attitude and orbit control system of existing studies such as the project for on-board autonomy (PROBA) of European Space Agency (ESA) [16].

In this paper, we mainly focus on maximizing imaging capability of an agile earth observation satellite by taking into account pitch maneuverability. While most of the previous studies were focused on considering constraints as many as possible (listed in Fig. 1) in mission planning problems, the consideration on the most important constraint that is attitude maneuverability has not been fully investigated yet. In this paper, we propose a new planning method that considers attitude maneuverability to fill this gap. A conflict-based heuristic model [8] is again applied like our previous study [7], but our previous algorithm has been significantly modified by adding pitch maneuverability in this paper. There are two major revisions. First, pitch maneuverability is newly taken into account. As explained in [2], agile satellites with an additional degree of freedom (DOF) in pitch axis (resulting in 2-DOF motion in total) could significantly increase the number of targets to be imaged, compared to 1-DOF motion that only depends on roll axis maneuver. However, this additional flexibility makes the planning problem very complex, and in this paper, a new computationally effective heuristic algorithm is proposed. Second, to evaluate optimality and time-effectiveness of the proposed method, the exact optimal algorithm is utilized for performance comparison.

The remainder of this paper is constructed as follows. Section 2 provides the problem definition and general mission planning algorithms. Section 3 summarizes our previous mission planning algorithm and Sect. 4 proposes a new mission planning algorithm. Section 5 presents numerical results and discussion to support the proposed method and Sect. 6 concludes the paper with future work.

2 Problem Definition and General Mission Planning Algorithms

2.1 Problem Definition

Figure 2 illustrates an example of satellite ground trajectory and interested ground targets. In this paper, importance of each target that is typically determined by users is represented by $w(n)$. The goal of mission planning is to schedule the image sequence to maximize the sum of importance of imaged targets. Possibility of imaging of certain target can be represented by

$$ \pi (n) = \left\{ {\begin{array}{*{20}l} {w(n),} \hfill & {{\text{if}}\,\,{\text{target }}n{\text{ is included in the image sequence}}} \hfill \\ 0, \hfill & {{\text{if}}\,{\text{target }}n{\text{ is not included in the image sequence}}} \hfill \\ \end{array} } \right. $$

(1)

, and performance of image sequence can be characterized by

$$ {\text{PI}} = \sum\limits_{n = 1}^{N} {\pi (n)} , $$

(2)

where ${\text{PI}}$ is the sum of importance of targets that are included in the particular image sequence. However, in general, investigating all image sequences and comparing their performances would be impossible when there exist many ground targets of interest. Hence, computational efficiency of mission planning algorithm is important as well as its optimality.

Fig. 2

Satellite ground trajectory and ground targets

2.2 Mission Planning Algorithms with Non-agile and Agile Satellites

Conventional non-agile satellites acquire targets along an elevation direction only (in roll axis), i.e., an azimuth angle (pitch angle) is constrained to zero as assumed in the SPOT 5 satellite [2]. Meanwhile, agile satellites can perform pitch maneuver rapidly, with the aid of high-torque reaction wheels or control momentum gyros, and time window of each target can be widened with this additional DOF. In this paper, zero-pitch one-DOF mission planning is defined as 1DMP and the latter is defined as 2DMP. The image time window of 1DMP is scalar, whereas the image time window of 2DMP is given as an interval, and this difference can be seen in Fig. 3.

Fig. 3

Image time windows of zero-pitch case (left) and nonzero pitch case (right)

2.3 Exact and Approximate Mission Planning Algorithms

Mission planning algorithms can be divided into two categories: exact and approximate algorithms [2]. Generally, the exact algorithms provide the optimal solution, whereas the approximate algorithms provide the sub-optimal solution. However, the approximate algorithms have a great advantage in computation time, especially for problems of agile satellite mission planning. Examples of exact methods are brute-force search, backtracking search, and branch and bound search. In the approximate methods, there are greedy search, tabu search, and heuristic method. This paper proposes a new heuristic-based method, and its performance is compared with the exact brute-force method in two aspects: optimality and computation time-effectiveness.

3 Previous Algorithm: 1DMP

The previous heuristic method for 1DMP [7] is briefly explained. There are two steps in the previous method: sorting step and selecting step.

At the first step, an idea of confliction-based method [8] is utilized in scheduling observations. The confliction arises when imaging one target hinders imaging another target. Figure 4 provides an example process of analyzing confliction between targets. First, at the top of the figure, allowable time windows for imaging targets are drawn and they correspond to target locations and satellite ground trajectory depicted in Fig. 2. Note that the image time windows are scalar because the 1DMP problem is assumed; there exists single opportunity to image each target. Two imaging sequences are assumed: sequence #1  → #2 and sequence #1 →  #3. In the first sequence (middle of the figure), both targets can be imaged because the maneuver from target #1 to target #2 ends before the image start time of target #2, T(2). Hence, there occurs no confliction between target #1 and target #2. However, in the second sequence (bottom of the figure), there occurs a confliction because the maneuver is not accomplished before the image start time of target #3, T(3).

Fig. 4

Time windows and two image sequence examples in 1DMP

The aforementioned statements can be mathematically formulated as follows. First, a confliction between targets is defined as

$$ {\text{conf}}(m,n)=\left\{ {\begin{array}{*{20}l} {0,} \hfill & {{\text{if}}\;{\text{both}}\,{\text{targets}}\,{\text{can}}\,{\text{be}}\,{\text{acquired}}} \hfill \\ {w(n),} \hfill & {{\text{if}}\,{\text{target}}\,n\,{\text{cannot}}\,{\text{be}}\,{\text{acquired}}} \hfill \\ \end{array} } \right., $$

(3)

where ${\text{conf}}(m,n)$ denotes the confliction between target m and target n. There is no confliction if the following equation holds:

$$ T(n) \ge T(m) + t_{\text{imgDur}} (m) + t_{\text{man}} (m,n) + t_{\text{s}} , $$

(4)

where $T(m)$ and $T(n)$ are the image start times (single opportunities in 1DMP) of targets m and n, and $t_{\text{imgDur}} (m)$ is the image duration of target m. The $t_{\text{man}} (m,n)$ is the maneuver time from target m to target n, and it is defined in 1DMP as

$$ t_{\text{man}} (m,n) = \frac{{\left| {\phi (n) - \phi (m)} \right|}}{{\dot{\alpha }}}, $$

(5)

where $\phi (m)$ and $\phi (n)$ are the roll angles (look angles) for imaging targets m and n, and $\dot{\alpha }$ is the average slew rate that is assumed as constant in this paper. The last term in Eq. (4), $t_{\text{s}}$, denotes the stabilization time after the maneuver. Then a confliction of target m to the other targets including target n can be defined by analyzing conflictions to the other targets and summing up them as

$$ {\text{conf}}(m) = \sum\limits_{n = 1}^{N} {{\text{conf}}(m,n)} , $$

(6)

where ${\text{conf}}(m,m)$ is automatically zero. Finally, an image priority of each target is defined as

$$ {\text{need}}(m) = \frac{w(m)}{{{\text{conf}}(m)}}, $$

(7)

where ${\text{need}}(m)$ denotes the image priority of target m, and the image priorities of the other targets can be obtained in the same manner. Equation (7) states that the image priority of the target is higher as the importance of the target $w(m)$ is large and the confliction to the other targets ${\text{conf}}(m)$ is small.

In the second step that is defined as the scheduling step, we select targets based on the image sequence candidate, which is scheduled in order of ${\text{need}}(m)$. Let us assume that the image sequence candidate is $k_{\text{imgCand}} = [4,5,1,2,7,8,3,6]$ with eight targets, $N = 8$. We first put target #4 in the final image sequence as $k_{\text{imgFinal}} = [4]$. Next we examine if target #5 is obtainable by checking Eq. (6), and include target #5 if it is feasible or discard target #5 if it is infeasible. We check all targets included in $k_{\text{imgCand}}$ sequentially and get the final image sequence.

4 Proposed Algorithm: 2DMP

While the previous 1DMP method is effective when the targets are scattered and multi-pass orbits (long mission periods like several-day mission planning) are considered such as in [7], the 1DMP method could be ineffective when the targets are concentrated in certain regions. This is because the simplification of scalar time windows described in Fig. 4 constraints possible image sequences with interval-like time windows, which are depicted in Fig. 3. With pitch maneuverability, the image start time can be selected among the corresponding image time windows such that

$$ T(m,\theta_{m} ) \in {\mathbf{TW}}(m), $$

(8)

where ${\mathbf{TW}}(m)$ is the image time window of target m with pitch maneuverability and $T(m,\theta_{m} )$ is the image start time of target m with the pitch angle $\theta_{m}$ that is constrained as

$$ \theta_{m} \in [ - \theta_{\text{max} } ,\,\,\theta_{\text{max} } ] $$

(9)

with the maximum pitch angle $\theta_{\text{max} }$. In addition, the maneuver time between targets m and n, $t_{\text{man}} (m,n)$ in Eq. (5), becomes variable as a function of pitch angles $\theta_{m}$ and $\theta_{n}$, which results in $t_{\text{man}} (m,n,\theta_{m} ,\theta_{n} )$. In short, there are infinite candidates in selecting the image start time and the maneuver time so that image capability can be enhanced with the aid of pitch maneuverability.

In this section, a new mission planning algorithm that considers this additional degree of freedom in pitch axis, defined as 2DMP, is proposed. The idea of 2DMP was first presented in [12]. As the 1DMP method [7], a conflict-based method [8] was pursued. The 2DMP method can be broken down into three steps: sorting, selecting and scheduling, and realization and verification. Each step is explained in detail in the following subsections.

4.1 Sorting

A definition of confliction is revised to describe an amount of confliction between targets, not just express the confliction as pass or fail as defined in Eq. (3). The new definition is

$$ {\text{conf}}(m,n) = \left\{ {\begin{array}{*{20}l} { - w_{n} \theta_{\mathrm{max} } ,} \hfill & {{\text{if}}\;\theta_{n} > \theta_{\mathrm{max} } } \hfill \\ { - w_{n} \theta_{n} ,} \hfill & {{\text{if}}\; - \theta_{\mathrm{max} } \le \theta_{n} \le \theta_{\mathrm{max} } } \hfill \\ {w_{n} \theta_{\mathrm{max} } ,} \hfill & {{\text{if}}\;\theta_{n} < - \theta_{\mathrm{max} } } \hfill \\ \end{array} } \right., $$

(10)

where the pitch angle for target n observation, $\theta_{n}$, is obtained by assuming that the previous pitch angle $\theta_{m}$ is zero. The new confliction parameter ${\text{conf}}(m,n)$ is now a real number not a binary as defined in 1DMP. Figure 5 explains the concept of the new confliction parameter. First, at the top of the figure, it can be observed that the time windows are described as intervals not scalar values; there exist infinite opportunities even in imaging single target according to pitch angles. Two imaging sequences are assumed again: sequence #1 →  #2 and sequence #1 →  #3. In the first sequence, it can be seen that the image start time for target #2 is moved forward with the pitch-up maneuver, $\theta_{n} > 0$, compared to the zero-pitch image start time $T(n = 2,\,\,\theta_{n} = 0)$ applied in Fig. 4. This advanced image start time $T(n = 2,\,\,\theta_{n} > 0)$ provides a benefit by finishing target n observation earlier so that the satellite could acquire more targets afterward. In addition, from Eq. (10) the confliction value between targets, ${\text{conf}}(1,2)$, becomes negative. In the second image sequence, target #3 can be acquired with the pitch-down maneuver, $\theta_{n} < 0$, while target #3 was not obtainable with 1DMP, as depicted in Fig. 4. However, the image start time $T(n = 3,\,\,\theta_{n} < 0)$ is moved backward from the zero-pitch image start time $T(n = 3,\,\,\theta_{n} = 0)$, and this is represented as the positive confliction value, ${\text{conf}}(1,3)$. Meanwhile, in both image sequences, the pitch angle corresponds to the margin of time from the end of maneuvering to the start of next imaging. This is the reason to use pitch angle in quantifying the confliction in Eq. (10). Use of pitch angle has an advantage compared to use of time margin because in 2DMP, the maneuvers are performed in roll/pitch-coupled axes and the pitch angle can consider this roll/pitch coupling, whereas the time margin based on 1DMP is obtained with zero-pitch-angle assumption so it cannot consider the roll/pitch coupling properly.

Fig. 5

Time windows and two image sequence examples in 2DMP

A confliction of target m to the other targets including target n is defined as

$$ {\text{conf}}(m) = (W - w(m))\theta_{\mathrm{max} } + \sum\limits_{n = 1}^{N} {{\text{conf}}(m,n)} , $$

(11)

where $W$ is the sum of the importance of targets, $\sum\nolimits_{n = 1}^{N} {w(n)}$, and ${\text{conf}}(m,m)$ is automatically zero. In Eq. (11), the term $(W - w(m))\theta_{\text{max} }$ is augmented to make ${\text{conf}}(m)$ positive so that the image priority ${\text{need}}(m)$ in Eq. (7) remains positive.

The remaining part in constructing a set of ${\text{conf}}(m)$ is obtaining the pitch angle $\theta_{n}$ in Eq. (10). To obtain $\theta_{n}$, the image start time of target n is formulated as

$$ T(n,\theta_{n} ) = T(m,\theta_{m} ) + t_{\text{man}} (m,n,\theta_{m} ,\theta_{n} ) + t_{\text{imgDur}} (m) + t_{s} + t_{\text{marg} } , $$

(12)

where corresponding graphical descriptions can be seen in Fig. 5. In Eq. (12), the $\theta_{m}$ is defined in $[ - \theta_{\text{max} } ,\,\,\theta_{\text{max} } ]$ that includes the zero-pitch angle case, $\theta_{m} = 0$, which is a baseline of ${\text{conf}}(m,n)$ calculation in Eq. (10). However, in Eq. (12), it is not straightforward to mathematically formulate the terms $T(n,\theta_{n} )$ and $t_{\text{man}} (m,n,\theta_{m} ,\theta_{n} )$. In this paper, two assumptions are defined and applied to simplify formulation of the two terms. First, $T(n,\theta_{n} )$ can be approximated as

$$ T(n,\theta_{n} ) \simeq T(n,\theta_{n} = 0) - k_{\text{pitch}} \theta_{n} $$

(13)

with the flat earth assumption. The transition parameter $k_{\text{pitch}}$, from pitch angle to time, becomes constant with the flat earth assumption, while in fact $k_{\text{pitch}}$ is a variable depending on $\theta_{n}$ because the earth is spherical and the ratio of the orbit altitude to the earth radius is not negligible even in low earth orbits. However, the approximation in Eq. (13) is acceptable when the maximum pitch angle $\theta_{\text{max} }$ is not too large. Second, $t_{\text{man}} (m,n,\theta_{m} ,\theta_{n} )$ can be approximated as

$$ t_{man} (m,n,\theta_{m} ,\theta_{n} ) \simeq \frac{{\alpha (\phi (m),\phi (n),\theta_{m} ,\theta_{n} )}}{{\dot{\alpha }}} $$

(14)

with the assumption that the orbit frames at two instants, $T(m,\theta_{m} )$ and $T(n,\theta_{n} )$, are the same. In fact, the maneuver angle $\alpha$ depends not only on Euler angles, $\phi (m)$, $\phi (n)$, $\theta_{m}$, and $\theta_{n}$, but also on the difference of the two orbit frames. However, the assumption of identical orbit frames is acceptable when two image start times are close to each other. With the assumption, the maneuver angle $\alpha$ can be obtained as a rotation angle along the eigen-axis between two Euler angles [17]. Finally, after substituting Eqs. (13) and (14) into Eq. (12), the pitch angle $\theta_{n}$ can be determined. In this paper, the Newton–Raphson method is applied and only a maximum of three iterations were needed to achieve $\theta_{n}$ within a 0.01° error in various Euler angle boundary conditions. Meanwhile, due to the two assumptions used, the approximation error arises and it becomes problematic when the approximated solution of $\theta_{n}$ is larger than that of the exact solution, and in this case, the approximated solution obtained becomes the overestimated solution. The overestimation could yield the infeasible solution that the exact $\theta_{n}$ could be less than $- \theta_{\text{max} }$. In this paper, to avoid the overestimation problem, the time margin $t_{\text{marg} }$ is augmented in Eq. (12). A conservative value of $t_{\text{marg} }$, that is 2 s in this paper, successfully resolved the approximation error issue.

4.2 Selecting and Scheduling

Based on the conflict value ${\text{conf}}(m)$ in Eq. (11), the image sequence candidate $k_{\text{imgCand}}$ can be generated. Then, in the second step (selecting and scheduling step), the image sequence candidate is examined and the final image sequence is generated by selecting targets that are obtainable within constrained attitude maneuverability.

In the proposed 2DMP algorithm, the biggest difference to 1DMP, at the second step, is that the image start times are not fixed but continuously change as the image sequence is updated. Table 1 illustrates an example of this process. The image sequence candidate from the sorting step, $k_{\text{imgCand}}$, is assumed again as $[4,5,1,2,7,8,3,6]$. The target numbers from #1 to #8 are listed in order of image start time at zero-pitch angle. The final image sequence $k_{\text{imgFinal}}$ is obtained in round 8 as it was previously done in 1DMP; however, it can be seen that the pitch angles are changing as the target candidate is added. In round 1, there is only one target candidate and the pitch angle is set to 30° which is the maximum pitch angle assumed in this example. In round 3, target #1 becomes the first target and the pitch angle for target #1 is set to 30°, and the pitch angles for targets #4 and #5 are modified by Eq. (12). In round 7, target #3 is not included in the final image sequence because at least one of the targets originally included in the image sequence in round 6 now has infeasible pitch angle, e.g., − 40°, as target #3 is tried to be included in the image sequence. On the contrary, target #6 is included as the new target in round 8 because the pitch angle constraints are satisfied in all targets. The example illustrated in Table 1 clearly shows the difference of target selecting logics between 1DMP and 2DMP.

Table 1 An example process at the selecting and scheduling step

However, in the previous example in Table 1, it is restricted to change order of imaging in internal elements. For example, imaging target #5 before imaging target #4 is not allowed. This simplification on order of imaging was originally applied in 1DMP, and generally the mission planning solution based on this simplification provides the sub-optimal solution so it is used widely in mission planning problems. In addition, the complexity of problems can be significantly reduced with the simplification. However, there often exist situations that image capability can be significantly enhanced by allowing the change in order of imaging, e.g., reverse order imaging, and these situations more frequently arise when concentrated/condensed targets are considered for mission planning such as in this paper. From the next paragraph, a specific example describing a limitation of the proposed 2DMP method that neglects the reverse order observations, that will be denoted as HRST1, is illustrated. In addition, a new 2DMP algorithm considering reverse order observations, that will be denoted as HRST2, is proposed.

Figure 6 illustrates a limitation of the proposed HRST1 method. In Fig. 6, the targets are positioned in a zigzag manner, and with HRST1, a lengthy total maneuvering time is required and it may fail to acquire all five targets if attitude maneuverability is not sufficient. On the other hand, with HRST2 the total maneuvering time can be significantly reduced by modifying order of imaging. In detail, the three left-hand-side targets are imaged at once, without the interim maneuvers to the right-hand-side targets.

Fig. 6

An example scenario showing the limitation of HRST1

A detailed logic of HRST2 is provided as follows. HRST2 is a more flexible method than HRST1 allowing the change in order of imaging. HRST2 is formulated as a greedy method having two objectives: one is to reduce the total maneuvering time by giving an image priority to the nearest target from current target m, and the other is to increase the total mission period by giving an image priority to the target that has the fastest time window. However, the two objectives are often mutually exclusive so that a following simple objective function is defined in HRST2:

$$ J(n) = \Delta \theta_{m,n} - \beta T(n,\theta_{n} = 0), $$

(15)

where $\Delta \theta_{m,n}$ is the pitch angle difference $\theta_{n} - \theta_{m}$ and can be found from Eq. (12), and $\beta$ is the weight parameter between the two objectives. As an illustrative example, suppose that target m is the current target. Among the targets that are not included in the image sequence yet, two targets n and p having the fastest time windows are considered as the candidates of the next target. Then their objective values in Eq. (15) are calculated and the target having the larger objective value is finally selected as the next target. An effect of the weight parameter $\beta$ on scheduling is illustrated in Fig. 7. Three potential solutions are depicted with the different values of $\beta$. When $\beta$ is small, the nearest target to the current target is sequentially selected. In other words, the target that can be imaged with the minimum maneuvering time is selected. When $\beta$ is large, more weights are imposed on the second objective, that is selecting the target of fastest time window, and eventually the scheduling logic becomes equivalent to HRST1 when $\beta$ goes to infinite. In this paper, with the extensive analysis on determining the best $\beta$ to optimize mission planning, $\beta$ is set to 1.0, and this corresponds to the result of the red-dashed line in Fig. 7.

Fig. 7

Three potential image sequences with the different weight parameters in HRST2

4.3 Realization and Verification

As explained in Eqs. (13) and (14), the scheduling solution obtained in Sect. 4.2 is only an approximate solution so it cannot be directly applied to actual mission planning. Specifically, a set of pitch angles and corresponding image start times for targets should be updated by considering orbit environments, which are spherical earth shape and change of the orbit frame with respect to time. This update process is defined as the realization step in this paper. The existence of scheduling solution of 2DMP can be guaranteed with the use of conservative value of $t_{\text{marg}}$ in Eq. (12), while the conservative value could slightly decrease the optimality of the scheduling solution. After the realization process, the validity of the scheduling solution is evaluated by substituting the solution into satellite orbit data and testing if the targets are acquired at the predicted image start times.

Figure 8 summarizes the three steps of the proposed 2DMP algorithm. In the figure, the initialization step is included, which obtains the zero-pitch image time windows of targets and corresponding roll angles.

Fig. 8

Solution derivation procedure in 2DMP

5 Numerical Results and Discussion

5.1 Simulation Conditions

Numerical results are presented to demonstrate the effectiveness of the proposed 2DMP method. Table 2 summarizes the orbit model, attitude agility model, and target model. A short-horizon problem is assumed such that the difference between zero-pitch image start times of the first and final targets is only 50 s. Ground targets are randomly located in a 340 km (along track) × 800 km (cross-track) region, where the value of 340 km comes from the ground speed of 6.8 km/s and the value of 800 km comes from the maximum roll angle, which is assumed as 30°. Note that in Table 2 the importance of the targets is assumed as the same, and it means that the original importance maximization problem can be converted to the problem of maximizing the number of imaged targets in this simulation.

Table 2 Simulation conditions

5.2 Performance Comparison Between Mission Planning Algorithms

Performance of mission planning algorithms is compared. Four algorithms, which are 1DMP, HRST1 (2DMP), and HRST2 (2DMP), and the exact brute-force method are applied. The first three methods are heuristic-based methods.

First, with 1DMP and HRST1 comparison, the benefit of pitch maneuverability can be seen. Figures 9 and 10 show the obtained image sequences, and roll and pitch angles from 1DMP and HRST1, respectively. While only three targets are obtainable without pitch maneuver in Fig. 9a, seven targets can be acquired with appropriate pitch maneuver in Fig. 10a. This is mainly due to the increase of mission period with the maximum pitch angles applied at the start and final times. In Fig. 10a, the first target that is target #1 is imaged before $T(1,\,\,\theta = 0)$ with pitch-up maneuver, and the last target that is target #8 is imaged after $T(8,\,\,\theta = 0)$ with pitch-down maneuver. The pitch angles and image starting times for interim targets are automatically generated by the proposed HRST1 method. In Fig. 9b, it can be verified that the pitch angles are zero and roll angles are very similar due to the constrained image time window. On the other hand, in Fig. 10b, extensive roll and pitch variations can be seen with the reorientation maneuvers.

Fig. 9

1DMP scheduling results

Fig. 10

2DMP (HRST1) scheduling results

Second, the benefit of reverse order imaging in mission planning is validated by comparing HRST1 and HRST2. By comparing Figs. 10 and 11, it can be seen that the number of images is increased by one with HRST2, specifically target #4 is now obtainable. While there are number of differences between HRST1 and HRST2, the most important difference is a decision made at last five targets, specifically from target #4 to target #8. In Fig. 10a, the distances of targets between (#4 and #5), (#5 and #6), and (#6 and #7) are very lengthy, and one of them should be abandoned if the image sequence is constrained to the sequential image logic as in HRST1. In this simulation, target #4 observation is sacrificed. On the contrary, in Fig. 11a, it can be seen that the reverse order acquisition is performed between targets (#4 and #5) and (#7 and #8), which results in saving total maneuvering time. As a result, target #4 is now able to be included in the image sequence.

Fig. 11

2DMP (HRST2) scheduling results

Third, the exact brute-force method is applied in mission planning. In this approach, all combinations of image sequences are examined, and the image sequence that provides the largest number of targets is selected. If multiple optimal solutions exist, the optimal solution found at first is selected in this paper. Figure 12 provides the results with the brute-force method. While the image sequence is slightly different to that with the HRST2 method provided in Fig. 11, their performance are the same; all the targets are obtainable.

Fig. 12

Exact brute-force method scheduling results

5.3 Monte Carlo Simulations

Mission planning simulations were conducted ten times with randomly generated target locations for each sample. The numbers of imaged targets and computation times of HRST1, HRST2, and the exact brute-force method are compared. In all samples, the brute-force method showed better or at least equivalent performance compared to HRST2. The average number of targets obtainable with the brute-force method was 8.0 which is greater than 7.4 targets with HRST1 and 7.9 targets with HRST2. However, computation time of the brute-force method was over 60 s and it is excessive than those of HRST1 and HRST2; their computation times were less than 0.1 s. While time-effectiveness of the exact method can be enhanced by utilizing other exact method such as backtracking algorithm or branch and bound algorithm, the reduction in computation time may not be huge due to its inherent complexity of mission planning problems. More details on ineffectiveness of the exact methods in planning problems can be found in [2].

Table 3 summarizes the results of Monte Carlo simulations with change in number of targets. Again, the exact brute-force method provides optimal solutions regardless of the change in number of targets. While the number of targets is 7 or below 7, all three algorithms are able to provide optimal solutions; all the interested targets are obtainable. However, as the number of targets exceeds 7, the optimality of HRST1 and HRST2 do not hold any more, while the brute-force method examined all the combinations in image sequences and successfully found the optimal solution. However, it can be seen that computation time of the brute-force method increases rapidly with the increase of number of targets. In fact, the brute-force method has time complexity of N factorial. On the contrary, computation time of the proposed HRST2 method is below 0.1 s even when there are 10 interested targets in Table 3 and this property remained until the number of targets increases up to 15 in our extra simulations.

Table 3 Average numbers of imaged targets and average computation times with three algorithms

6 Conclusion

A simple yet effective method for mission planning is proposed. The method consists of three steps and its logic is intuitive. Pitch maneuverability is considered and numerical studies show that the number of images can be significantly increased compared to the roll-only observations. The optimality of the derived solution is slightly degraded compared to the exact optimal solution, but computation time was significantly reduced.

The proposed method may be adopted to on-board mission planning for urgent situations that require timely processing. For example, image sequence can be modified with the proposed method, to improve image capability in sudden weather change. In addition, the proposed method can be generalized by incorporating general nonlinear agility requirements. While this paper assumed that the average slew rate is constant for simplicity, a general agility table of angle versus slew rate can be readily augmented into the proposed method. The only difference exists in calculation of the confliction values at the sorting step.