# A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling

Authors: Xiaogeng Chu; Yuning Chen; Lining Xing
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

The agile earth observing satellite scheduling (AEOSS) problem consists of scheduling a subset of images among a set of candidates that satisfy imperative constraints and maximize a gain function. In this paper, we consider a new AEOSS model which integrates a time-dependent temporal constraint. To solve this problem, we propose a highly efficient branch and bound algorithm whose effective ingredients include a look-ahead construction method (for generating a high quality initial lower bound) and a combined use of three pruning strategies (which help to prune a large portion of the search space). We conducted computational experiments on a set of test data that were generated with information from real-life scenarios. The results showed that the proposed algorithm is efficient enough for engineering application. In particular, it is able to solve instances with 55 targets to optimality within 164 seconds on average. Furthermore, we carried out additional experiments to analyze the contribution of each key algorithm ingredient.


---

## Body

## 1. Introduction

Agile Earth observing satellites (AEOSs) have a stronger ability to collect images of specified areas of the Earth’s surface. And AEOSs play key roles in application such as environment surveillance, reconnaissance, resource investigation, and other fields. However, satellite resources are still scarce with respect to the increasing demands for imaging. Whereas nonagile satellites have only one degree of freedom on roll axis for acquiring images, the agile satellites have mobility on the three axes (roll, pitch, and yaw), giving opportunities for a more efficient use of the satellite imaging capabilities. As a result, the scheduling of the agile Earth observing satellites, which is a complex combinatorial optimization problem that has been proved to be NP-hard [1], is a key issue in the management of satellites. The scheduling problem of the AEOSs was studied by a number of researchers.It is believed that [1] was the first work introducing AEOS. They provided a comprehensive description of AEOS and analyzed four different methods. They studied the increased observation freedom provided by the agility and the complicated transition times, modeled a simplified version of the complete problem, and drew comparisons with four algorithms. The authors in [2] describe a synthesis of permutation-based search and constraint propagation for AEOS scheduling which incorporates the advantages of both techniques. They obtained the large neighborhood behavior of permutation search for oversubscribed resource scheduling problems and exploited the power of constraint propagation to retain as much flexibility as possible while building the schedule. Bianchessi [3, 4] considered the observation scheduling problem for a constellation of agile satellites. A tabu search algorithm was devised to produce solutions whose qualities were evaluated by a column generation algorithm on a linear programming relaxation of the problem. Habet et al. [5–7] proposed a tabu search based on the saturated and consistent neighborhood to solve the AEOS problem involving stereoscopic and time window constraints. The authors used a formulation of constrained optimization problems and a convex evaluation function. Moreover, the upper bounds were computed by relaxing the constraints and linearization of the objective function. Florio [8] developed a heuristic with look-ahead ability, in order to obtain a near-optimal schedule for an agile satellite constellation. They also tested the performance of various constellation configurations based on the schedules generated by the heuristic. Wang and Reinelt [9] discussed the AEOS scheduling problem for the first environmental and disaster monitoring and prediction satellite constellation of China. They proposed a nonlinear model of the problem and developed a heuristic with conflict avoidance, limited backtracking, and download-as-needed features. Meanwhile, a decision support system based on the model and the heuristic is also provided. Kananub et al. [10] show different observation situations of agile and nonagile EOSs. AEOS improves observation efficiency but also increases the difficulties of observation scheduling task. Tangpattanakul et al. [11] modeled the AEOS problem as a multiobjective optimization problem which maximizes the total profits and minimizes the maximum profit difference between users simultaneously. They proposed an indicator-based multiobjective local search to solve the problem. Xu et al. [12] assumed that different observation tasks may have priority levels, and the objective is to maximize the total priority of selected tasks. Meanwhile, they developed constructive algorithms to solve the problem, which adopt a priority-based sequential construction procedure to avoid conflicts and generate feasible solutions. Other works related to the AEOS problems can be found in [13–17].However, the scheduling problem is more difficult to solve as the attitude maneuver capability is more excellent. Meanwhile, the resource constraint is not as tight as before in the new generation of agile satellites. So the critical constraint is the time-dependent temporal constraint, which means the minimum transition time taken by a maneuver between the end of the former acquisition and the start of the following one is not constant and depends on the precise time at which the transition is triggered [1]. This aspect is close to work on time-dependent scheduling [18, 19], where transition times take particular forms, piecewise constant or piecewise linear.Pralet and Verfaillie [20] proposed the time-dependent simple temporal networks (TSTN), which cover temporal constraints for which the minimum and maximum distances required between two temporal positions x and y are not necessarily constant but may depend on the assignments of x and y. The TSTN are applied by several researchers [20, 21] on the management of temporal constraints for agile satellites.On the basis of this, a branch and bound algorithm for the optimal solution of the agile satellite scheduling problem is proposed in this paper.The remainder of this paper is organized as follows. In Section2, we proposed the mathematical model of the scheduling problem of the AEOS and analyzed the characteristics of the attitude maneuver function. In Section 3, the details of the branch and bound algorithm are illustrated, which contains the expression of a solution, the initialization method, and three pruning strategies. Experimental examples are designed according to the actual use requirements of the AEOSs and the examples are used to validate the efficiency of the algorithm in Section 4. Section 5 concludes the paper.


## 2. Agile Earth Observing Satellite Scheduling Problem

### 2.1. Problem Description

It is assumed that the resource constraints such as memory and energy are no longer the tight constraints of the scheduling problem with the development of the satellite platform. Therefore, temporal constraints are imperative in the agile satellite scheduling problem considered in this paper, which include visible time window constraint and time-dependent transition constraint.Since satellites are orbital spacecraft, a target is visible to a satellite only when it is flying over it. Compared to nonagile satellites, agile satellite’s pitching ability extends the visible time window [1]. Figure 1 illustrates the temporal constraints of agile satellites. As is shown in Figure 1(a), the visible time window of target_1 is [ws_1,we_1]. At any point of the time window, the satellite has a unique attitude for observing target_1. The attitude at ws_1 is attitude_ws_1. Figure 1(b) shows that an attitude maneuver is needed between two consecutive observations. Suppose that the end attitude of target_1 is atie_1 and the start attitude of target_2 is atis_2, and the difference between the start time of the latter observation and the end time of the former observation must be larger than the attitude maneuver time: that is, st2-et1>dmin⁡(atie1,atis2), where dmin⁡(atie1,atis2) denotes the minimum attitude maneuver time between atie_1 and atis_2. One notices that the minimum transition time taken by a maneuver between two observations is not constant and it depends on the precise time at which the transition is triggered.Figure 1
Temporal constraint of agile satellite.
(a)
(b)


### 2.2. Problem Formulation

In the modeling, we assume that all the targets have been processed into strip tasks which are along-track for good imaging quality as in [22]. The tasks such as point target and stereo imaging could be regarded as target with different duration times.A set of notations of the model is shown as follows:pi: the profit of target iwsi: the start time of the time window of target iwei: the end time of the time window of target iduri: the duration time of target isti: the start imaging time of target ieti: the end imaging time of target iatisi: the attitude of the start imaging time of target i, including the pitch, roll, and azimuthatiei: the attitude of the end imaging time of target i, including the pitch, roll, and azimuthdmin·,·: the minimum transition time between two attitudesNT: the total number of targetsS: the set of all combinations of targets.Objective function is(1)max∑i=1i=NTxi·pi.Decision variables are(2)xi=1,if taskiis executed,0,otherwise,yij=1,if taskjis executed after taski,0,otherwise.Constraints are(3)wsi≤sti<eti<wei,∀xi=1;(4)eti=sti+duri,∀xi=1;(5)eti+dmin⁡atiei,atisj<stj∀yij=1;(6)yii=0;(7)x0=1;(8)xNT+1=1;(9)xj=∑i=0i=NTyij,j=1,…,NT+1;(10)xi=∑j=1j=NT+1yij,i=0,…,NT;(11)∑i∈S∑j∈Syij≤S-1,S⊆1,…,NT,S≠∅;(12)xi=1∧xj=1,∀yij=1;(13)xi∈0,1,yij∈0,1,i,j=1,…,NT.Equation (1) states that the objective is to maximize the sum of the profits of the executed targets. Equation (2) introduces the decision variables of the model, where xi takes a value of 1 if target i is executed and xi=0; otherwise; yij takes a value of 1 if target j is executed after target i and yij=0 otherwise.Equations (3)–(13) give the constraints of the problem. Equation (3) states that any scheduled target should be executed in the time window. Equation (4) states that the end imaging time of a scheduled target is the sum of the start imaging time and the duration time of the target. Equation (5) states that the start imaging time of the following target should be bigger than the sum of the end imaging time of the former target and the maneuver time. Equation (6) states that a target could not be executed following itself. Equations (7) and (8) state that there are a virtual starting target and a virtual ending target whose start time and duration time are both 0. Equations (9) and (10) state that any executed target could only have one following target and one previous target. Equation (11) is the classical Dantzig, Fulkerson, and Johnson (DFJ) subtour elimination constraint [23]. Equation (12) states that target i and target j are both executed if target j is executed after target i. Equation (13) states the domain of the variables.The key to optimizing this model is to determine a feasible sequence of targets, which maximize the overall profits while satisfying all temporal constraints. Therefore, it is necessary to further analyze the attitude maneuver characteristics of agile satellites.


### 2.3. The Characteristics of the Functiondmin

In this subsection, we introduce how to calculate the functiondmin and the method to compute the earliest start time of a target on the basis of the analysis of the characteristics of dmin.The functiondmin returns the minimum transition time given two attitudes. The maneuver process includes three phases: acceleration, plateau, and deceleration. The satellite first uniformly accelerates to a maximum speed and then remains in the maximum speed for a period and hereafter decelerates until stop. After maneuver, a tranquilization time is required to reach the pointing stability. Attitudes remain fixed during imaging and all targets are preprocessed to be along-track strips.Equation (5) is a key constraint of the AEOS scheduling problem. We note that the “delay function” defined in [20] is in fact a deformation of (5).Definition 1.
The delay function associated with an attitude maneuver constraintct:(eti,stj,dmin) is function delayct:D()×D()→R defined by delaycteti,stj=eti+dmin⁡(atiei,atisj)-stj, where yij=1.
Informally,delaycteti,stj is the delay obtained in stj if a transition in minimum time from atiei to atisj is triggered at time eti. This delay corresponds to the difference between the minimum arrival time associated with the transition eti+dminatiei,atisj and the required arrival time stj. A strictly negative delay corresponds to a transition ending before deadline stj, which means the constraint is satisfied. A strictly positive delay indicates that the constraint is violated. A null delay corresponds to an arrival right on time.Definition 2.
An attitude maneuver constraintct:(eti,stj,dmin) is said to be delay-monotonic iff its delay function delayct·,· satisfies the conditions below, where D() is the domain of the time variable: (14)eti≤eti′⟶delaycteti,stj≤delaycteti′,stj∀eti,eti′∈Deti,∀stj∈Dstj,stj≤stj′⟶delaycteti,stj≥delaycteti,stj′,∀eti∈Deti,∀stj,stj′∈Dstj,where yij=1.This definition means that, for being delay-monotonic, an attitude maneuver constraintct:eti,stj,dmin on two successive observations i and j must verify that, on the one hand, the later the transition is triggered in eti, the greater is the delay in stj, and on the other hand the earlier the transition must end in stj, the greater the delay is. The notion of delay-monotonicity is related to the notions of monotonic constraints, defined, for instance, in [24]. The delay-monotonicity of the attitude maneuver time constraint is the theoretical basis of the segment domination based pruning strategy proposed in Section 3.5.The transition temporal constraint of the agile satellite is delay-monotonic as shown in [20]. Now, we introduce a method to compute the earliest start time of the next target given the end time and the attitude of the current target. Such an evaluation is an optimization problem in itself, and an iterative method for approximating the earliest start time of the next target is illustrated in Figure 2 and formally defined in Algorithm 1. This method corresponds to the standard false position method, used to find a zero of an arbitrary function. Applied to the case of t-simple temporal constraints, the method works as follows. If leftmost point a1=(x1,f(x1)) has a negative delay f(x1)≤0, then a1 is directly returned. Otherwise, if rightmost point a2=(x2,f(x2)) has a strictly positive delay f(x2)>0, then +∞ is returned, which means there is no start time satisfying the temporal constraint. Otherwise, points a1 and a2 have opposite delay-signs (f(x1)≤0∧f(x2)>0) and then compute delay f(x3) in x3, the x-value of the intersection between segment (a1,a2) and the x-axis. See Figure 1 for an illustration. If the delay in a3=(x3,f(x3)) is negative, then the mechanism is applied again by taking a2←a3, otherwise taking a1←a3 if the delay is positive. The procedure stops when value f(x3) is less than a given precision. Algorithm 1 gives a possible way to compute the earliest start time of the next target.Algorithm 1:Iterative interpolation algorithm.
Input: wtsj=[t1,t2] // the time window of the start time
e
t
i // the end time of the previous target i
m
a
x
I
t
e
r // a maximum number of iterations
pre // a desired precision
output: t2 // the earliest start time of the next target
(1)f1←delayeti,t1; if f1≤0 then return t1
(2)f2←delayeti,t2; if f2>0 then return +∞
(3)fori=1 to maxIter
(4)t3←(f1∗t2-f2∗t1)/(f1-f2)
(5)f3←delay(eti,t3)
(6)if f3<pre then returnt3
(7)else if f3>0 then (t1,f1)←(t3,f3)
(8)else (t2,f2)←(t3,f3)
(9)endfor
(10)return t2Figure 2
Interpolation procedure used for computing the earliest start time.
(a)
(b)


## 2.1. Problem Description

It is assumed that the resource constraints such as memory and energy are no longer the tight constraints of the scheduling problem with the development of the satellite platform. Therefore, temporal constraints are imperative in the agile satellite scheduling problem considered in this paper, which include visible time window constraint and time-dependent transition constraint.Since satellites are orbital spacecraft, a target is visible to a satellite only when it is flying over it. Compared to nonagile satellites, agile satellite’s pitching ability extends the visible time window [1]. Figure 1 illustrates the temporal constraints of agile satellites. As is shown in Figure 1(a), the visible time window of target_1 is [ws_1,we_1]. At any point of the time window, the satellite has a unique attitude for observing target_1. The attitude at ws_1 is attitude_ws_1. Figure 1(b) shows that an attitude maneuver is needed between two consecutive observations. Suppose that the end attitude of target_1 is atie_1 and the start attitude of target_2 is atis_2, and the difference between the start time of the latter observation and the end time of the former observation must be larger than the attitude maneuver time: that is, st2-et1>dmin⁡(atie1,atis2), where dmin⁡(atie1,atis2) denotes the minimum attitude maneuver time between atie_1 and atis_2. One notices that the minimum transition time taken by a maneuver between two observations is not constant and it depends on the precise time at which the transition is triggered.Figure 1
Temporal constraint of agile satellite.
(a)
(b)


## 2.2. Problem Formulation

In the modeling, we assume that all the targets have been processed into strip tasks which are along-track for good imaging quality as in [22]. The tasks such as point target and stereo imaging could be regarded as target with different duration times.A set of notations of the model is shown as follows:pi: the profit of target iwsi: the start time of the time window of target iwei: the end time of the time window of target iduri: the duration time of target isti: the start imaging time of target ieti: the end imaging time of target iatisi: the attitude of the start imaging time of target i, including the pitch, roll, and azimuthatiei: the attitude of the end imaging time of target i, including the pitch, roll, and azimuthdmin·,·: the minimum transition time between two attitudesNT: the total number of targetsS: the set of all combinations of targets.Objective function is(1)max∑i=1i=NTxi·pi.Decision variables are(2)xi=1,if taskiis executed,0,otherwise,yij=1,if taskjis executed after taski,0,otherwise.Constraints are(3)wsi≤sti<eti<wei,∀xi=1;(4)eti=sti+duri,∀xi=1;(5)eti+dmin⁡atiei,atisj<stj∀yij=1;(6)yii=0;(7)x0=1;(8)xNT+1=1;(9)xj=∑i=0i=NTyij,j=1,…,NT+1;(10)xi=∑j=1j=NT+1yij,i=0,…,NT;(11)∑i∈S∑j∈Syij≤S-1,S⊆1,…,NT,S≠∅;(12)xi=1∧xj=1,∀yij=1;(13)xi∈0,1,yij∈0,1,i,j=1,…,NT.Equation (1) states that the objective is to maximize the sum of the profits of the executed targets. Equation (2) introduces the decision variables of the model, where xi takes a value of 1 if target i is executed and xi=0; otherwise; yij takes a value of 1 if target j is executed after target i and yij=0 otherwise.Equations (3)–(13) give the constraints of the problem. Equation (3) states that any scheduled target should be executed in the time window. Equation (4) states that the end imaging time of a scheduled target is the sum of the start imaging time and the duration time of the target. Equation (5) states that the start imaging time of the following target should be bigger than the sum of the end imaging time of the former target and the maneuver time. Equation (6) states that a target could not be executed following itself. Equations (7) and (8) state that there are a virtual starting target and a virtual ending target whose start time and duration time are both 0. Equations (9) and (10) state that any executed target could only have one following target and one previous target. Equation (11) is the classical Dantzig, Fulkerson, and Johnson (DFJ) subtour elimination constraint [23]. Equation (12) states that target i and target j are both executed if target j is executed after target i. Equation (13) states the domain of the variables.The key to optimizing this model is to determine a feasible sequence of targets, which maximize the overall profits while satisfying all temporal constraints. Therefore, it is necessary to further analyze the attitude maneuver characteristics of agile satellites.


## 2.3. The Characteristics of the Functiondmin

In this subsection, we introduce how to calculate the functiondmin and the method to compute the earliest start time of a target on the basis of the analysis of the characteristics of dmin.The functiondmin returns the minimum transition time given two attitudes. The maneuver process includes three phases: acceleration, plateau, and deceleration. The satellite first uniformly accelerates to a maximum speed and then remains in the maximum speed for a period and hereafter decelerates until stop. After maneuver, a tranquilization time is required to reach the pointing stability. Attitudes remain fixed during imaging and all targets are preprocessed to be along-track strips.Equation (5) is a key constraint of the AEOS scheduling problem. We note that the “delay function” defined in [20] is in fact a deformation of (5).Definition 1.
The delay function associated with an attitude maneuver constraintct:(eti,stj,dmin) is function delayct:D()×D()→R defined by delaycteti,stj=eti+dmin⁡(atiei,atisj)-stj, where yij=1.
Informally,delaycteti,stj is the delay obtained in stj if a transition in minimum time from atiei to atisj is triggered at time eti. This delay corresponds to the difference between the minimum arrival time associated with the transition eti+dminatiei,atisj and the required arrival time stj. A strictly negative delay corresponds to a transition ending before deadline stj, which means the constraint is satisfied. A strictly positive delay indicates that the constraint is violated. A null delay corresponds to an arrival right on time.Definition 2.
An attitude maneuver constraintct:(eti,stj,dmin) is said to be delay-monotonic iff its delay function delayct·,· satisfies the conditions below, where D() is the domain of the time variable: (14)eti≤eti′⟶delaycteti,stj≤delaycteti′,stj∀eti,eti′∈Deti,∀stj∈Dstj,stj≤stj′⟶delaycteti,stj≥delaycteti,stj′,∀eti∈Deti,∀stj,stj′∈Dstj,where yij=1.This definition means that, for being delay-monotonic, an attitude maneuver constraintct:eti,stj,dmin on two successive observations i and j must verify that, on the one hand, the later the transition is triggered in eti, the greater is the delay in stj, and on the other hand the earlier the transition must end in stj, the greater the delay is. The notion of delay-monotonicity is related to the notions of monotonic constraints, defined, for instance, in [24]. The delay-monotonicity of the attitude maneuver time constraint is the theoretical basis of the segment domination based pruning strategy proposed in Section 3.5.The transition temporal constraint of the agile satellite is delay-monotonic as shown in [20]. Now, we introduce a method to compute the earliest start time of the next target given the end time and the attitude of the current target. Such an evaluation is an optimization problem in itself, and an iterative method for approximating the earliest start time of the next target is illustrated in Figure 2 and formally defined in Algorithm 1. This method corresponds to the standard false position method, used to find a zero of an arbitrary function. Applied to the case of t-simple temporal constraints, the method works as follows. If leftmost point a1=(x1,f(x1)) has a negative delay f(x1)≤0, then a1 is directly returned. Otherwise, if rightmost point a2=(x2,f(x2)) has a strictly positive delay f(x2)>0, then +∞ is returned, which means there is no start time satisfying the temporal constraint. Otherwise, points a1 and a2 have opposite delay-signs (f(x1)≤0∧f(x2)>0) and then compute delay f(x3) in x3, the x-value of the intersection between segment (a1,a2) and the x-axis. See Figure 1 for an illustration. If the delay in a3=(x3,f(x3)) is negative, then the mechanism is applied again by taking a2←a3, otherwise taking a1←a3 if the delay is positive. The procedure stops when value f(x3) is less than a given precision. Algorithm 1 gives a possible way to compute the earliest start time of the next target.Algorithm 1:Iterative interpolation algorithm.
Input: wtsj=[t1,t2] // the time window of the start time
e
t
i // the end time of the previous target i
m
a
x
I
t
e
r // a maximum number of iterations
pre // a desired precision
output: t2 // the earliest start time of the next target
(1)f1←delayeti,t1; if f1≤0 then return t1
(2)f2←delayeti,t2; if f2>0 then return +∞
(3)fori=1 to maxIter
(4)t3←(f1∗t2-f2∗t1)/(f1-f2)
(5)f3←delay(eti,t3)
(6)if f3<pre then returnt3
(7)else if f3>0 then (t1,f1)←(t3,f3)
(8)else (t2,f2)←(t3,f3)
(9)endfor
(10)return t2Figure 2
Interpolation procedure used for computing the earliest start time.
(a)
(b)


## 3. A Branch and Bound Algorithm

In this section, the branch and bound (B&B) algorithm proposed in this paper is introduced. The B&B algorithm is actually a combined algorithm, and different components of the algorithm will be introduced, respectively, such as the expression of a solution, the initialization method, the pruning mechanism, and current best solution updating method.


### 3.1. General Framework

In this subsection, the general framework of the B&B algorithm is introduced. Components that need to be elaborated in a B&B algorithm include the branching strategy and variable branching order.Algorithm2 shows the general procedure of the B&B algorithm. The algorithm adopts depth-first search strategy to search the solution space. At each node of the search tree, the algorithm first computes the total profit of the corresponding solution and updates the current best solution if an improved solution is discovered. The algorithm then tests if the search space below the current node can be pruned. Specifically, three conditions are tested in the following order: 1 whether the symmetry breaking based pruning condition (lines (13)~(15)) is satisfied; 2 whether the segment domination based pruning condition (lines (16)~(19)) is satisfied; and 3 whether its upper bound is lower than the global lower bound (the total profit of the current best solution, lines (24)~(27)). Once a condition is satisfied, the subtree following the current node is pruned and the algorithm backtracks. The node needs to be extended if none of the three conditions is verified. The algorithm returns a current best solution in the first case and an optimal one in the second case. The details of the three pruning strategies (the symmetry breaking based pruning strategy, the segment domination based pruning strategy, and the bound based pruning strategy) will be presented in the following Sections 3.4~3.6.Algorithm 2:The branch and bound algorithm.
Input: tasks // the target list
a
t
i
S
t
a
t
e // the initial attitude state of the satellite
p
s
C // the current sequence solution
t
a
s
k
O
r
d
e
r // the extending order of the targets
p
s
O
p
t
C // the current best sequence solution
p
r
o
O
p
t
C // the current best profit
n
u
m // the number of look-ahead targets
Output: proOpt // the optimal sequence solution
p
s
O
p
t // the optimal profit
(1)ifIsEmpty(psOptC)
(2)[psOptC,proOptC]←LookaheadCon(tasks,atiState,num); //Initialization
(3)endif
(4)ssC←[];proC←0;
(5)if~IsEmpty(psC)
(6)ssC←ScheduleBuilderpsC,tasks,atiState;
(7)proC←Profit(ssC); // Computing the current profit
(8)ifproC>proOptC&&IsConsistent(psC,ssC)
(9)proOptC←proC; psOptC←psC; //Updating the current best plan
(10)endif
(11)endif
(12)unscheduledTasks←SelectTask(ssC); // Selecting the targets which still
have a visible time window
(13)ifIsEmpty(unscheduledTasks)||~IsConsistent(psC,ssC)
(14)return;//Backtracking if psC is not a consistent solution
(15)else
(16)dominatedBool←CurDominated(psC,psOptC,tasks)
(17)ifdominatedBool
(18)return;//Backtrackingifcurrentsolutionisdominated
(19)endif
(20)upBound←BasicUpBoundssC,tasks; // Computing the upper bound
(21)ifproC+upBound<proOptC
(22)return; // Backtracking if the upper bound of current solution is less than proOptC
(23)else
(24)dominatingBool←OptDominated(psC,psOptC,tasks)
(25)ifdominatingBool //Updating the current best solution
(26)[psOptC,proOptC]←UpdateOpt(psC,psOptC,tasks);
(27)endif
(28)numOfNext←NumberOfTask(unscheduledTasks); // Determining the number of targets that
have not been tried
(29)for i←1 to numOfNext
(30)nextNode←SelectTask(unscheduledTasks,i);
(31)psC←Apendix(psc,nextNode);//Extendingthecurrentsolution
(32)[proOptC,psOptC]←BranchBound(tasks,atiState,psC,taskOrder,proOptC,psOptC)
(33)endfor;
(34)end if
(35)end if
(36)proOpt←proOptC;
(37)psOpt←psOptC;In order to improve the efficiency of the B&B algorithm, it is a common way to provide a good lower bound of the problem at the beginning of the algorithm. So a look-ahead construction method is proposed to initialize the lower bound of the B&B algorithm, which is illustrated in Section3.3.


### 3.2. Solution Space and Solution Expression

Before presenting the search space of the B&B algorithm, two concepts are first introduced: “sequence solution” and “schedule solution.” A “sequence solution” is represented by a sequence of targets whose ordering is determined, while feasibility of the solution is not tested and the execution time of the observations is not arranged yet. The “schedule solution” is, on the contrary, a feasible solution with all temporal constraints satisfied and the execution time of the observations arranged.The B&B algorithm searches in the “sequence solution” space. Every time the B&B algorithm examines a node in the search tree where a sequence solution lies, the algorithm applies a “schedule builder” (SB) to build a “schedule solution” based on the sequence solution and then computes the total profits of the schedule solution.SB uses a greedy construction heuristic. Given a sequence solution ps, SB considers targets in the same order as they appear inps. SB tries to arrange the observation of each target at its earliest possible start time. If a target cannot be scheduled due to the violation of temporal constraints, SB discards it and continues to examine the next one. The schedule solution is obtained when all targets in the sequence solution are examined by SB. The total profits of the schedule solution are the sum of the profits of all selected targets.Proposition 3.
There must be a sequence solution in the search space that can be mapped onto an optimal schedule solution by the proposed schedule builder.Proof.
The schedule solution space can be divided into two subsets, sayS1 and S2. S1 contains all solutions whose selected observations are arranged at their earliest possible start time. In other words, in these solutions, no observation can be started earlier without violating the maneuver and time window constraints. While S2 is the complementary set of S1. We note that there must be an optimal schedule solution in S1. This is because, for any solution ss′ of S2, there must be a solution ss from S1 whose objective value is not worse than that of ss′. In fact, ss can be obtained by anticipating all selected observations of ss′ at their earliest possible start time. We also note that there must exist a sequence solution ps in the sequence solution space (which is also the search space of B&B) that can be mapped onto ss with the proposed schedule builder. The ps is the sequence solution having the same observation list and order as in ss.


### 3.3. Look-Ahead Construction Method

It is known that a good initial solution will contribute to speed up the pruning process. We propose a look-ahead construction method (LACM) to provide a good lower bound at the very beginning. Let us call the branch and bound algorithm without the initialization, pruning method, and the updating method (lines (1)~(3), (16)~(19), and (24)~(27)) a basic branch and bound algorithm (b-B&B for short), which could rapidly find the optimal solution of a small scale problem which contains about 12 targets. We design a heuristic algorithm based on the idea of rolling planning. The algorithm decides each target to be scheduled or not progressively according to the “natural” order which sorts the targets in their increasing start time of time windows. Given the current satellite attitude state, the algorithm finds the optimal solution of the next 12 targets with b-B&B and then selects the first target in the optimal partial solution. Afterwards, the algorithm updates the satellite attitude state and looks for the next optimal solutions of the subsequent 12 targets. The algorithm stops until the last target is considered. The pseudocode of the LACM is shown in Algorithm3. It should be noted that the while loop in the algorithm is not an infinite loop. This is because the number of the targets is limited, and each time the satellite selects a target to observe, it removes the targets that violate the temporal constraints from the candidate set. So the candidate set is shrinking during the process and the while loop stops when the candidate set becomes empty.Algorithm 3:Look-ahead construction method.
Input: tasks // the target list
a
t
i
S
t
a
t
e // the initial attitude state of the satellite
n
u
m // the number of look-ahead targets
Output: ps // the sequence solution
p
r
o
C // the profit of the sequence solution
(1)ps←[];
(2)taskOrder←SortByTimetasks;
/
/
A
s
c
e
n
d
i
n
g
o
r
d
e
r
b
y
t
h
e
m
i
d
d
l
e
t
i
m
e
o
f
t
i
m
e
w
i
n
d
o
w
s
(3)laTasks←ExtractTaskstasks,num,atiState;
/
/
E
x
t
r
a
c
t
i
n
g
t
h
e
n
e
a
r
e
s
t
n
u
m
t
a
r
g
e
t
s
(4)parOpt←BasicBranchBound(laTasks,atiState,[],taskOrder,0,[]);
(5)while ~isempty(parOpt)
(6)ps←Apendix(ps,parOpt(1));//selectingthefirsttaskinparOpt
(7)atiState←ComAtitude(laTasks,ps,atiState);//Updatingtheattitude
(8)laTasks←ExtractTasks(tasks,num,atiState); // Extracting at most num near targets
(9)parOpt←BasicBranchBound(laTasks,atiState,[],taskOrder,0,[]);
(10)endwhile
(11)ss←ScheduleBuilderps,tasks,atiState;
(12)proC←Profit(ss);An example is provided to illustrate the idea of our look-ahead initialization method in Figure3. Given the current attitude state atit0, the algorithm looks ahead num(num=12) targets and finds that the optimal partial solution is 3→7→9→6. Then it selects target 3 to be scheduled, which is contained in the optimal solution, and updates the state to atie3 (the attitude state at the end time of target 3).Figure 3
Look-ahead construction method.


### 3.4. Symmetry Breaking Based Pruning Strategy

First a definition is introduced here, which is useful for presenting the details of the symmetry breaking based pruning strategy.Definition 4.
A sequence solutionps is said to be consistent with the schedule solution ss provided by the schedule builder when ss contains all the observations in ps (i.e., ps=ss, where  is the number of observations in the solution).As is shown in Figure4, the sequence solution ps2 is not consistent with its schedule solution ss, as target1 and target8 are not included in ss due to the violation of the attitude maneuver constraint. In contrast, the sequence solution ps1 is consistent with ss since ps1=ss.Figure 4
Sequence solution and scheduling builder.It could be learned from Figure4 that different sequence solutions may lead to the same schedule solution using the proposed SB. In other words, there are many symmetry configurations in the B&B search tree. Examining these symmetry configurations is a waste of time and does not lead to any improvement. To avoid this, a symmetry breaking based pruning strategy (SBBPS) is proposed and used during the searching process. The idea of the SBBPS is to break symmetries by pruning the subtrees below the sequence solutions that are inconsistent with their schedule solutions. This allows us to prevent examining duplicate sequence solutions that correspond to the same schedule solution. Specifically, at each node of the B&B algorithm, given a sequence solution ps, the algorithm builds a schedule solution ss with SB. If ps is inconsistent with ss, the algorithm prunes the subtrees below the node under consideration and alters the search to another branch. In the example shown in Figure 4, the subspace under the node of ps2(3→7→9→1) is pruned since ps2 is inconsistent with its schedule solution. Specifically, target1 of ps2 cannot be scheduled since time is not enough for the satellite to maneuver from target9 to target1. SBBPS is used in lines (13)~(15) of Algorithm 2.


### 3.5. Segment Domination Based Pruning Strategy

In this subsection, we propose a segment domination based pruning strategy (short for SDBPS hereafter) to further improve the search efficiency of the B&B algorithm. Before introducing the method, we first give a set of notations regarding the sequence solutionps. Let psj denote the jth target in the sequence and “+” connect two subsequences. Then ps=ps1,…,j+psj+1,…,ps,∀j≤ps. Pro(ps) returns the total profits of the schedule solution ss generated by SB. Notice that Pro(ps)≠Pro(ps1,…,j)+Pro(psj+1,…,ps) if ps is inconsistent with its schedule solution.The main idea of the SDBPS is to prune sequence solutions that are dominated by a segment of the current best feasible solution. A nodepsC can be pruned if there is a partial solution ps′ that has a higher profit and consumes less execution time than ps and all the targets observed in ps have no visible time window after the end time of psC.Theorem 5.
Given a current best sequence solutionpsOptC and a current node psC(psC=k), psC can be pruned if ∃j≤psOptC such that {Pro(psOptC1,…,j)>PropsC1,…,k-1 and stpsCk≥etcBPlanj+dmin⁡(atiecBPlanj,atispsCk)}.Proof.
P
r
o
(
p
s
O
p
t
C
1
,
…
,
j
)
>
P
r
o
(
p
s
C
1
,
…
,
k
-
1
) indicates that psC1,…,k-1 is dominated by psOptC1,…,j in terms of total profit and stpsCk≥etpsOptCj+dmin⁡(atiepsOptCj,atispsCk) ensures the subsequence psOptC1,…,j+psCk is consistent with its schedule solution.As is shown in Figure5, the current node psC is 3→7→1→6 and the current best solution psOptC is 3′→7′→9′→6′→4′. The target with “′” means it is in the current best solution psOptC. If (15) and (16) are simultaneously true, psC is worse than 3′→7′→9′→6 (which is for sure consistent with its schedule solution). For this reason, the current node psC can be pruned. Equation (16) also requires that the imaging start time of target6 in 3′→7′→9′→6 must be earlier than the imaging start time of target6 in 3→7→1→6(15)Pro3′⟶7′⟶9′>Pro3⟶7⟶1,(16)st6≥et9′+dminatie9′,atis6.Figure 5
Schematic diagram of the segment domination based pruning strategy.To test whether the condition of SDBPS is verified for the current sequence solutionpsC, the algorithm identifies a critical position j of psOptC that satisfies(17)PropsOptC1,…,j≥PropsC1,…,k-1>PropsOptC1,…,j-1.If there is no suchj, it means an improved best solution psC is found and the current best solution psOptC is updated with psC. Otherwise, the algorithm tests (18) and prunes psC if it is true(18)stpsCk≥etpsOptCj+dmin⁡atiepsOptCj,atispsCk.The following corollary justifies the practice of judging the domination of the current sequence solution with respect to the current best solution via the critical positionj.Corollary 6.
IfpsOptC1,…,j does not dominate the current sequence solution psC1,…,k-1, no other subsequences of psOptC can dominate psC1,…,k-1.Proof.
We have(19)PropsOptC1,…,h<PropsC1,…,k-1,∀h<j,according to (20)PropsOptC1,…,j≥PropsC1,…,k-1>PropsOptC1,…,j-1.And ∀h>j, etpsOptCh>etpsOptCj, according to the delay-monotonic (Definition 2), so(21)delayctetpsOptCj,stpsCk≤delayctetpsOptCh,stpsCk,∴etpsOptCj+dminatiepsOptCj,atispsCk-stpsCk≤etpsOptCh+dminatiepsOptCh,atispsCk-stpsCk,∵stpsCk<etpsOptCj+dmin⁡atiepsOptCj,atispsCk,∴0<etpsOptCj+dminatiepsOptCj,atispsCk-stpsCk≤etpsOptCh+dminatiepsOptCh,atispsCk-stpsCk,∴stpsCk<etpsOptCh+dminatiepsOptCh,atispsCk.
So there is no positionh other than j in psOptC such that cBPlan1,…,h dominates the sequence solution psC1,…,k-1.


### 3.6. Bound Based Pruning Strategy

#### 3.6.1. Upper Bounding Method

An efficient method is adopted to estimate the upper bound, which simply adds the profit of the current branch and the sum of profits of all the targets which still have a time window to be imaged according to the current state of the satellite. This upper bounding method is demonstrated to be effective according to our experiments.As shown in Figure6, the current node is psC(3→7→9→6). The imaging end time of the last target observation is et6. The target8 and target4 still have a time window to be observed, since et8 and et4 are both greater than et6. So the upper bound of the current node psC is p3+p7+p9+p6+p8+p4.Figure 6
Schematic diagram of the upper bound.


#### 3.6.2. Segment Replacement Based Lower Bound Updating Method

In this subsection, a segment replacement based lower bound updating method (short for SRBLBUM hereafter) is proposed to update the current best solutionpsOptC with the similar idea of the pruning method, which attempts to check whether the current node psC(psC=k) dominates a partial solution of the current best solution.If there is somej<psOptC such that {Pro(psOptC1⋯j)<PropsC and stpsOptCj+1≥etpsCk+dmin⁡(atiepsCk,atispsOptCj+1)}, then the current best solution could be updated by (22), where psOptC′ means the new current best solution(22)psOptC′=psC+psOptCj+1⋯pOptC.As is shown in Figure7, if the current node psC(3→7→9) satisfies the following inequalities (23), then the partial solution 3′→7′→1′ could be replaced with 3→7→9, where targets with “′” mean they are in the current best solution psOptC as before. And a new better current best solution 3→7→9→6′→4′ is generated(23)Pro3′⟶7′⟶1′<Pro3⟶7⟶9,st6′≥et9+dminatie9,atis6′.Figure 7
Schematic diagram of the segment replacement based lower bound updating method.And then, an effective method is developed to judge whether the current nodepsC dominates a partial solution of the current best solution psOptC. The critical dominated position j of psOptC could be found according to (24), where psC=k(24)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1.If there is no suchj, it means the current node psC could not be better than a partial solution of the current best solution psOptC. Otherwise, judge j whether to meet (25). Replace psOptC with psOptC′=psC+psOptCj+1⋯pOptC, if it is satisfied,(25)stpsOptCj+1≥etpsCk+dmin⁡atiepsCk,atispsOptCj+1.Corollary7 illustrates that it is rational to judge whether the current branch dominates the partial current best solution via the critical dominated position j.Corollary 7.
If the current nodepsC does not dominate the partial solution psOptC1,…,j, where j is the critical dominated position satisfying (24), there is no other position h of psOptC that makes psOptC1⋯h be dominated bypsC.Proof.
We have(26)PropsOptC1,…,h>PropsC,∀h>j,according to(27)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1;And ∀h<j, stpsOptCh+1<stpsOptCj+1, according to the delay-monotonic (Definition 2), and then(28)delayctetpsCk,stpsOptCh+1≥delayctetpsCk,stpsOptCj+1,∴etpsCk+dminatiepsCk,atispsOptCh+1-stpsOptCh+1≥etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1,∵stpsOptCj+1<etpsCk+dminatiepsCk,atispsOptCj+1,∴0<etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1≤etpsCk+dmin⁡atiepsCk,atispsOptCh+1-stpsOptCh+1,∴stpsOptCh+1<etpsCk+dmin⁡atiepsCk,atispsOptCh+1.
So there is no otherh that could make the partial solution psOptC1,…,h of the current best solution psOptC be dominated by the current node psC.


## 3.1. General Framework

In this subsection, the general framework of the B&B algorithm is introduced. Components that need to be elaborated in a B&B algorithm include the branching strategy and variable branching order.Algorithm2 shows the general procedure of the B&B algorithm. The algorithm adopts depth-first search strategy to search the solution space. At each node of the search tree, the algorithm first computes the total profit of the corresponding solution and updates the current best solution if an improved solution is discovered. The algorithm then tests if the search space below the current node can be pruned. Specifically, three conditions are tested in the following order: 1 whether the symmetry breaking based pruning condition (lines (13)~(15)) is satisfied; 2 whether the segment domination based pruning condition (lines (16)~(19)) is satisfied; and 3 whether its upper bound is lower than the global lower bound (the total profit of the current best solution, lines (24)~(27)). Once a condition is satisfied, the subtree following the current node is pruned and the algorithm backtracks. The node needs to be extended if none of the three conditions is verified. The algorithm returns a current best solution in the first case and an optimal one in the second case. The details of the three pruning strategies (the symmetry breaking based pruning strategy, the segment domination based pruning strategy, and the bound based pruning strategy) will be presented in the following Sections 3.4~3.6.Algorithm 2:The branch and bound algorithm.
Input: tasks // the target list
a
t
i
S
t
a
t
e // the initial attitude state of the satellite
p
s
C // the current sequence solution
t
a
s
k
O
r
d
e
r // the extending order of the targets
p
s
O
p
t
C // the current best sequence solution
p
r
o
O
p
t
C // the current best profit
n
u
m // the number of look-ahead targets
Output: proOpt // the optimal sequence solution
p
s
O
p
t // the optimal profit
(1)ifIsEmpty(psOptC)
(2)[psOptC,proOptC]←LookaheadCon(tasks,atiState,num); //Initialization
(3)endif
(4)ssC←[];proC←0;
(5)if~IsEmpty(psC)
(6)ssC←ScheduleBuilderpsC,tasks,atiState;
(7)proC←Profit(ssC); // Computing the current profit
(8)ifproC>proOptC&&IsConsistent(psC,ssC)
(9)proOptC←proC; psOptC←psC; //Updating the current best plan
(10)endif
(11)endif
(12)unscheduledTasks←SelectTask(ssC); // Selecting the targets which still
have a visible time window
(13)ifIsEmpty(unscheduledTasks)||~IsConsistent(psC,ssC)
(14)return;//Backtracking if psC is not a consistent solution
(15)else
(16)dominatedBool←CurDominated(psC,psOptC,tasks)
(17)ifdominatedBool
(18)return;//Backtrackingifcurrentsolutionisdominated
(19)endif
(20)upBound←BasicUpBoundssC,tasks; // Computing the upper bound
(21)ifproC+upBound<proOptC
(22)return; // Backtracking if the upper bound of current solution is less than proOptC
(23)else
(24)dominatingBool←OptDominated(psC,psOptC,tasks)
(25)ifdominatingBool //Updating the current best solution
(26)[psOptC,proOptC]←UpdateOpt(psC,psOptC,tasks);
(27)endif
(28)numOfNext←NumberOfTask(unscheduledTasks); // Determining the number of targets that
have not been tried
(29)for i←1 to numOfNext
(30)nextNode←SelectTask(unscheduledTasks,i);
(31)psC←Apendix(psc,nextNode);//Extendingthecurrentsolution
(32)[proOptC,psOptC]←BranchBound(tasks,atiState,psC,taskOrder,proOptC,psOptC)
(33)endfor;
(34)end if
(35)end if
(36)proOpt←proOptC;
(37)psOpt←psOptC;In order to improve the efficiency of the B&B algorithm, it is a common way to provide a good lower bound of the problem at the beginning of the algorithm. So a look-ahead construction method is proposed to initialize the lower bound of the B&B algorithm, which is illustrated in Section3.3.


## 3.2. Solution Space and Solution Expression

Before presenting the search space of the B&B algorithm, two concepts are first introduced: “sequence solution” and “schedule solution.” A “sequence solution” is represented by a sequence of targets whose ordering is determined, while feasibility of the solution is not tested and the execution time of the observations is not arranged yet. The “schedule solution” is, on the contrary, a feasible solution with all temporal constraints satisfied and the execution time of the observations arranged.The B&B algorithm searches in the “sequence solution” space. Every time the B&B algorithm examines a node in the search tree where a sequence solution lies, the algorithm applies a “schedule builder” (SB) to build a “schedule solution” based on the sequence solution and then computes the total profits of the schedule solution.SB uses a greedy construction heuristic. Given a sequence solution ps, SB considers targets in the same order as they appear inps. SB tries to arrange the observation of each target at its earliest possible start time. If a target cannot be scheduled due to the violation of temporal constraints, SB discards it and continues to examine the next one. The schedule solution is obtained when all targets in the sequence solution are examined by SB. The total profits of the schedule solution are the sum of the profits of all selected targets.Proposition 3.
There must be a sequence solution in the search space that can be mapped onto an optimal schedule solution by the proposed schedule builder.Proof.
The schedule solution space can be divided into two subsets, sayS1 and S2. S1 contains all solutions whose selected observations are arranged at their earliest possible start time. In other words, in these solutions, no observation can be started earlier without violating the maneuver and time window constraints. While S2 is the complementary set of S1. We note that there must be an optimal schedule solution in S1. This is because, for any solution ss′ of S2, there must be a solution ss from S1 whose objective value is not worse than that of ss′. In fact, ss can be obtained by anticipating all selected observations of ss′ at their earliest possible start time. We also note that there must exist a sequence solution ps in the sequence solution space (which is also the search space of B&B) that can be mapped onto ss with the proposed schedule builder. The ps is the sequence solution having the same observation list and order as in ss.


## 3.3. Look-Ahead Construction Method

It is known that a good initial solution will contribute to speed up the pruning process. We propose a look-ahead construction method (LACM) to provide a good lower bound at the very beginning. Let us call the branch and bound algorithm without the initialization, pruning method, and the updating method (lines (1)~(3), (16)~(19), and (24)~(27)) a basic branch and bound algorithm (b-B&B for short), which could rapidly find the optimal solution of a small scale problem which contains about 12 targets. We design a heuristic algorithm based on the idea of rolling planning. The algorithm decides each target to be scheduled or not progressively according to the “natural” order which sorts the targets in their increasing start time of time windows. Given the current satellite attitude state, the algorithm finds the optimal solution of the next 12 targets with b-B&B and then selects the first target in the optimal partial solution. Afterwards, the algorithm updates the satellite attitude state and looks for the next optimal solutions of the subsequent 12 targets. The algorithm stops until the last target is considered. The pseudocode of the LACM is shown in Algorithm3. It should be noted that the while loop in the algorithm is not an infinite loop. This is because the number of the targets is limited, and each time the satellite selects a target to observe, it removes the targets that violate the temporal constraints from the candidate set. So the candidate set is shrinking during the process and the while loop stops when the candidate set becomes empty.Algorithm 3:Look-ahead construction method.
Input: tasks // the target list
a
t
i
S
t
a
t
e // the initial attitude state of the satellite
n
u
m // the number of look-ahead targets
Output: ps // the sequence solution
p
r
o
C // the profit of the sequence solution
(1)ps←[];
(2)taskOrder←SortByTimetasks;
/
/
A
s
c
e
n
d
i
n
g
o
r
d
e
r
b
y
t
h
e
m
i
d
d
l
e
t
i
m
e
o
f
t
i
m
e
w
i
n
d
o
w
s
(3)laTasks←ExtractTaskstasks,num,atiState;
/
/
E
x
t
r
a
c
t
i
n
g
t
h
e
n
e
a
r
e
s
t
n
u
m
t
a
r
g
e
t
s
(4)parOpt←BasicBranchBound(laTasks,atiState,[],taskOrder,0,[]);
(5)while ~isempty(parOpt)
(6)ps←Apendix(ps,parOpt(1));//selectingthefirsttaskinparOpt
(7)atiState←ComAtitude(laTasks,ps,atiState);//Updatingtheattitude
(8)laTasks←ExtractTasks(tasks,num,atiState); // Extracting at most num near targets
(9)parOpt←BasicBranchBound(laTasks,atiState,[],taskOrder,0,[]);
(10)endwhile
(11)ss←ScheduleBuilderps,tasks,atiState;
(12)proC←Profit(ss);An example is provided to illustrate the idea of our look-ahead initialization method in Figure3. Given the current attitude state atit0, the algorithm looks ahead num(num=12) targets and finds that the optimal partial solution is 3→7→9→6. Then it selects target 3 to be scheduled, which is contained in the optimal solution, and updates the state to atie3 (the attitude state at the end time of target 3).Figure 3
Look-ahead construction method.


## 3.4. Symmetry Breaking Based Pruning Strategy

First a definition is introduced here, which is useful for presenting the details of the symmetry breaking based pruning strategy.Definition 4.
A sequence solutionps is said to be consistent with the schedule solution ss provided by the schedule builder when ss contains all the observations in ps (i.e., ps=ss, where  is the number of observations in the solution).As is shown in Figure4, the sequence solution ps2 is not consistent with its schedule solution ss, as target1 and target8 are not included in ss due to the violation of the attitude maneuver constraint. In contrast, the sequence solution ps1 is consistent with ss since ps1=ss.Figure 4
Sequence solution and scheduling builder.It could be learned from Figure4 that different sequence solutions may lead to the same schedule solution using the proposed SB. In other words, there are many symmetry configurations in the B&B search tree. Examining these symmetry configurations is a waste of time and does not lead to any improvement. To avoid this, a symmetry breaking based pruning strategy (SBBPS) is proposed and used during the searching process. The idea of the SBBPS is to break symmetries by pruning the subtrees below the sequence solutions that are inconsistent with their schedule solutions. This allows us to prevent examining duplicate sequence solutions that correspond to the same schedule solution. Specifically, at each node of the B&B algorithm, given a sequence solution ps, the algorithm builds a schedule solution ss with SB. If ps is inconsistent with ss, the algorithm prunes the subtrees below the node under consideration and alters the search to another branch. In the example shown in Figure 4, the subspace under the node of ps2(3→7→9→1) is pruned since ps2 is inconsistent with its schedule solution. Specifically, target1 of ps2 cannot be scheduled since time is not enough for the satellite to maneuver from target9 to target1. SBBPS is used in lines (13)~(15) of Algorithm 2.


## 3.5. Segment Domination Based Pruning Strategy

In this subsection, we propose a segment domination based pruning strategy (short for SDBPS hereafter) to further improve the search efficiency of the B&B algorithm. Before introducing the method, we first give a set of notations regarding the sequence solutionps. Let psj denote the jth target in the sequence and “+” connect two subsequences. Then ps=ps1,…,j+psj+1,…,ps,∀j≤ps. Pro(ps) returns the total profits of the schedule solution ss generated by SB. Notice that Pro(ps)≠Pro(ps1,…,j)+Pro(psj+1,…,ps) if ps is inconsistent with its schedule solution.The main idea of the SDBPS is to prune sequence solutions that are dominated by a segment of the current best feasible solution. A nodepsC can be pruned if there is a partial solution ps′ that has a higher profit and consumes less execution time than ps and all the targets observed in ps have no visible time window after the end time of psC.Theorem 5.
Given a current best sequence solutionpsOptC and a current node psC(psC=k), psC can be pruned if ∃j≤psOptC such that {Pro(psOptC1,…,j)>PropsC1,…,k-1 and stpsCk≥etcBPlanj+dmin⁡(atiecBPlanj,atispsCk)}.Proof.
P
r
o
(
p
s
O
p
t
C
1
,
…
,
j
)
>
P
r
o
(
p
s
C
1
,
…
,
k
-
1
) indicates that psC1,…,k-1 is dominated by psOptC1,…,j in terms of total profit and stpsCk≥etpsOptCj+dmin⁡(atiepsOptCj,atispsCk) ensures the subsequence psOptC1,…,j+psCk is consistent with its schedule solution.As is shown in Figure5, the current node psC is 3→7→1→6 and the current best solution psOptC is 3′→7′→9′→6′→4′. The target with “′” means it is in the current best solution psOptC. If (15) and (16) are simultaneously true, psC is worse than 3′→7′→9′→6 (which is for sure consistent with its schedule solution). For this reason, the current node psC can be pruned. Equation (16) also requires that the imaging start time of target6 in 3′→7′→9′→6 must be earlier than the imaging start time of target6 in 3→7→1→6(15)Pro3′⟶7′⟶9′>Pro3⟶7⟶1,(16)st6≥et9′+dminatie9′,atis6.Figure 5
Schematic diagram of the segment domination based pruning strategy.To test whether the condition of SDBPS is verified for the current sequence solutionpsC, the algorithm identifies a critical position j of psOptC that satisfies(17)PropsOptC1,…,j≥PropsC1,…,k-1>PropsOptC1,…,j-1.If there is no suchj, it means an improved best solution psC is found and the current best solution psOptC is updated with psC. Otherwise, the algorithm tests (18) and prunes psC if it is true(18)stpsCk≥etpsOptCj+dmin⁡atiepsOptCj,atispsCk.The following corollary justifies the practice of judging the domination of the current sequence solution with respect to the current best solution via the critical positionj.Corollary 6.
IfpsOptC1,…,j does not dominate the current sequence solution psC1,…,k-1, no other subsequences of psOptC can dominate psC1,…,k-1.Proof.
We have(19)PropsOptC1,…,h<PropsC1,…,k-1,∀h<j,according to (20)PropsOptC1,…,j≥PropsC1,…,k-1>PropsOptC1,…,j-1.And ∀h>j, etpsOptCh>etpsOptCj, according to the delay-monotonic (Definition 2), so(21)delayctetpsOptCj,stpsCk≤delayctetpsOptCh,stpsCk,∴etpsOptCj+dminatiepsOptCj,atispsCk-stpsCk≤etpsOptCh+dminatiepsOptCh,atispsCk-stpsCk,∵stpsCk<etpsOptCj+dmin⁡atiepsOptCj,atispsCk,∴0<etpsOptCj+dminatiepsOptCj,atispsCk-stpsCk≤etpsOptCh+dminatiepsOptCh,atispsCk-stpsCk,∴stpsCk<etpsOptCh+dminatiepsOptCh,atispsCk.
So there is no positionh other than j in psOptC such that cBPlan1,…,h dominates the sequence solution psC1,…,k-1.


## 3.6. Bound Based Pruning Strategy

### 3.6.1. Upper Bounding Method

An efficient method is adopted to estimate the upper bound, which simply adds the profit of the current branch and the sum of profits of all the targets which still have a time window to be imaged according to the current state of the satellite. This upper bounding method is demonstrated to be effective according to our experiments.As shown in Figure6, the current node is psC(3→7→9→6). The imaging end time of the last target observation is et6. The target8 and target4 still have a time window to be observed, since et8 and et4 are both greater than et6. So the upper bound of the current node psC is p3+p7+p9+p6+p8+p4.Figure 6
Schematic diagram of the upper bound.


### 3.6.2. Segment Replacement Based Lower Bound Updating Method

In this subsection, a segment replacement based lower bound updating method (short for SRBLBUM hereafter) is proposed to update the current best solutionpsOptC with the similar idea of the pruning method, which attempts to check whether the current node psC(psC=k) dominates a partial solution of the current best solution.If there is somej<psOptC such that {Pro(psOptC1⋯j)<PropsC and stpsOptCj+1≥etpsCk+dmin⁡(atiepsCk,atispsOptCj+1)}, then the current best solution could be updated by (22), where psOptC′ means the new current best solution(22)psOptC′=psC+psOptCj+1⋯pOptC.As is shown in Figure7, if the current node psC(3→7→9) satisfies the following inequalities (23), then the partial solution 3′→7′→1′ could be replaced with 3→7→9, where targets with “′” mean they are in the current best solution psOptC as before. And a new better current best solution 3→7→9→6′→4′ is generated(23)Pro3′⟶7′⟶1′<Pro3⟶7⟶9,st6′≥et9+dminatie9,atis6′.Figure 7
Schematic diagram of the segment replacement based lower bound updating method.And then, an effective method is developed to judge whether the current nodepsC dominates a partial solution of the current best solution psOptC. The critical dominated position j of psOptC could be found according to (24), where psC=k(24)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1.If there is no suchj, it means the current node psC could not be better than a partial solution of the current best solution psOptC. Otherwise, judge j whether to meet (25). Replace psOptC with psOptC′=psC+psOptCj+1⋯pOptC, if it is satisfied,(25)stpsOptCj+1≥etpsCk+dmin⁡atiepsCk,atispsOptCj+1.Corollary7 illustrates that it is rational to judge whether the current branch dominates the partial current best solution via the critical dominated position j.Corollary 7.
If the current nodepsC does not dominate the partial solution psOptC1,…,j, where j is the critical dominated position satisfying (24), there is no other position h of psOptC that makes psOptC1⋯h be dominated bypsC.Proof.
We have(26)PropsOptC1,…,h>PropsC,∀h>j,according to(27)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1;And ∀h<j, stpsOptCh+1<stpsOptCj+1, according to the delay-monotonic (Definition 2), and then(28)delayctetpsCk,stpsOptCh+1≥delayctetpsCk,stpsOptCj+1,∴etpsCk+dminatiepsCk,atispsOptCh+1-stpsOptCh+1≥etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1,∵stpsOptCj+1<etpsCk+dminatiepsCk,atispsOptCj+1,∴0<etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1≤etpsCk+dmin⁡atiepsCk,atispsOptCh+1-stpsOptCh+1,∴stpsOptCh+1<etpsCk+dmin⁡atiepsCk,atispsOptCh+1.
So there is no otherh that could make the partial solution psOptC1,…,h of the current best solution psOptC be dominated by the current node psC.


## 3.6.1. Upper Bounding Method

An efficient method is adopted to estimate the upper bound, which simply adds the profit of the current branch and the sum of profits of all the targets which still have a time window to be imaged according to the current state of the satellite. This upper bounding method is demonstrated to be effective according to our experiments.As shown in Figure6, the current node is psC(3→7→9→6). The imaging end time of the last target observation is et6. The target8 and target4 still have a time window to be observed, since et8 and et4 are both greater than et6. So the upper bound of the current node psC is p3+p7+p9+p6+p8+p4.Figure 6
Schematic diagram of the upper bound.


## 3.6.2. Segment Replacement Based Lower Bound Updating Method

In this subsection, a segment replacement based lower bound updating method (short for SRBLBUM hereafter) is proposed to update the current best solutionpsOptC with the similar idea of the pruning method, which attempts to check whether the current node psC(psC=k) dominates a partial solution of the current best solution.If there is somej<psOptC such that {Pro(psOptC1⋯j)<PropsC and stpsOptCj+1≥etpsCk+dmin⁡(atiepsCk,atispsOptCj+1)}, then the current best solution could be updated by (22), where psOptC′ means the new current best solution(22)psOptC′=psC+psOptCj+1⋯pOptC.As is shown in Figure7, if the current node psC(3→7→9) satisfies the following inequalities (23), then the partial solution 3′→7′→1′ could be replaced with 3→7→9, where targets with “′” mean they are in the current best solution psOptC as before. And a new better current best solution 3→7→9→6′→4′ is generated(23)Pro3′⟶7′⟶1′<Pro3⟶7⟶9,st6′≥et9+dminatie9,atis6′.Figure 7
Schematic diagram of the segment replacement based lower bound updating method.And then, an effective method is developed to judge whether the current nodepsC dominates a partial solution of the current best solution psOptC. The critical dominated position j of psOptC could be found according to (24), where psC=k(24)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1.If there is no suchj, it means the current node psC could not be better than a partial solution of the current best solution psOptC. Otherwise, judge j whether to meet (25). Replace psOptC with psOptC′=psC+psOptCj+1⋯pOptC, if it is satisfied,(25)stpsOptCj+1≥etpsCk+dmin⁡atiepsCk,atispsOptCj+1.Corollary7 illustrates that it is rational to judge whether the current branch dominates the partial current best solution via the critical dominated position j.Corollary 7.
If the current nodepsC does not dominate the partial solution psOptC1,…,j, where j is the critical dominated position satisfying (24), there is no other position h of psOptC that makes psOptC1⋯h be dominated bypsC.Proof.
We have(26)PropsOptC1,…,h>PropsC,∀h>j,according to(27)PropsOptC1,…,j<PropsC≤PropsOptC1,…,j+1;And ∀h<j, stpsOptCh+1<stpsOptCj+1, according to the delay-monotonic (Definition 2), and then(28)delayctetpsCk,stpsOptCh+1≥delayctetpsCk,stpsOptCj+1,∴etpsCk+dminatiepsCk,atispsOptCh+1-stpsOptCh+1≥etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1,∵stpsOptCj+1<etpsCk+dminatiepsCk,atispsOptCj+1,∴0<etpsCk+dminatiepsCk,atispsOptCj+1-stpsOptCj+1≤etpsCk+dmin⁡atiepsCk,atispsOptCh+1-stpsOptCh+1,∴stpsOptCh+1<etpsCk+dmin⁡atiepsCk,atispsOptCh+1.
So there is no otherh that could make the partial solution psOptC1,…,h of the current best solution psOptC be dominated by the current node psC.


## 4. Experimental Study

In this section, the performance of the proposed B&B algorithm is evaluated. First, test data is designed according to the actual requirements of the AEOSs in China. And then, these data are employed to analyze the impact of different methods on the performance of the B&B algorithm.


### 4.1. Test Data

The examples of China’s agile satellite platform are used to validate the B&B algorithm. The maneuver process includes acceleration, uniform maneuver, and deceleration. Tranquilization time is required to reach the pointing stability allowing for good image quality as well. Maneuvers of 45° could be completed in about 60 seconds. Overall, the maneuver time is highly dependent on the rotation angle and axis. For good imaging quality, attitude is recommended to remain fixed during imaging, so the targets are all along-track strips. While the across-track tilt angle for nominal imaging acquisitions is±30°, the satellite could be figured to achieve ±45° off-nadir pointing capability.In general, an Earth observation satellite has an imaging time of 40 minutes in one track, and the targets are uniform distributed in both sides of the imaging track. In application, the time of the scheduling algorithm is demanded to be less than 10 minutes. In order to test the performance of the algorithm, the number of the targets ranges from 30 to 55. And other parameters such as the duration time and tranquilization time are in Table1. The parameters for instance generation are listed in Table 1 where the left part of the table associates with scenario attributes and the right part associates with maneuverability. The number of targets ranges from 30 to 55, and targets are uniform distributed in both sides of the imaging track which means each target has an imaging time window. The duration of the targets is a Gauss distribution with a mean value of 15 and a variance of 9. The profit of the targets is a Gauss distribution whose mean value is a function of the duration; this means a more time-consuming target may have a higher profit. The satellite has a maximum maneuver speed at 1°/s, an acceleration speed at 0.5°/s2, and a deceleration speed at 0.25°/s2. A tranquilization time of 5 s is needed after maneuver.Table 1
Parameters of the instances and satellite.
Target attribute
Maneuverability
Number of targets
[
30,55
]
Max maneuver speed
1
°
/
s
Target distribution
Uniform distribution
Acceleration
0.5
°
/
s
2
Duration distribution
N
(
15,9
)
Deceleration
0.25
°
/
s
2
Profit distribution
N
2
∗
d
u
r
i
-
5
,
100
Tranquilization time
5 sA total number of 260 instances were used to test our B&B algorithm, where, for each of the 26 different numbers of targets (from 30 to 55, see Table1), 10 random instances were generated. The B&B algorithm is coded in MATLAB 2014a and run on a computer with a 2.4 GHz i5 CPU and 3.79 GB RAM.


### 4.2. Results

This subsection analyzes the effect of different mechanisms, such as initialization solution, segment domination based pruning strategy, and best solution updating method, on the efficiency of the algorithm at different study scales. As the B&B algorithm will always find the optimal solution of the problem, we use the time cost as a measure to evaluate the efficiency of an algorithm.The effects of different mechanisms on the algorithm efficiency are analyzed by comparing the B&B algorithm with the incomplete algorithms which lack a single mechanism. In the experiment, 10 experiments are randomly generated for each study scale. And then, the average time cost and the maximum time cost are used to analyze the effects of different mechanisms on the efficiency of the algorithm.Three incomplete algorithms, noninitialization algorithm, nonpruning algorithm, and nonupdating algorithm, are designed for each mechanism.The noninitialization algorithm, which is referred to as “nonInit,” means that the algorithm has no initial solution before searching; that is, the current best solution is empty and the current best profit is 0 at the beginning of the search. However, the algorithm has the pruning method and best solution updating method corresponding to Sections3.4, 3.5, and 3.6.The nonpruning algorithm, which is referred to as “nonPrune,” only adopts the pruning strategy in Sections3.4 and 3.6, which prune a branch once the branch is found to be inconsistent, and does not use the pruning strategy SDBPS designed in Section 3.5. The initial solution of the algorithm is generated by the LACM of Section 3.3. And the SRBLBUM in Section 3.6.2 is used.The nonupdating algorithm, which is referred to as “nonUpdate,” is that the algorithm does not adopt the SRBLBUM of Section3.6.2. The initial solution of the algorithm is generated by the LACM of Section 3.3, and the pruning strategies of Sections 3.4 and 3.5 are adopted.The time cost statistics of the examples are shown in Figure8 and Table 2. The left column of Table 2 is the number of targets of the examples. The statistical data of the nonpruning algorithm is only shown in the table because the time cost of the algorithm is too large to test all the examples. However, the available data in Table 2 are sufficient to analyze the effect of the pruning mechanism on the solution efficiency. Figure 8(a) shows the average time cost of different algorithms under different scale cases; Figure 8(b) shows the maximum time cost. By comparing different incomplete algorithms and B&B algorithms, we can analyze the influence degree of different mechanisms.Table 2
The time costs of different algorithms.
Number of targets
Average time cost
Maximum time cost
NonPrune
NonIntial
NonUpdate
TDTCBB
NonPrune
NonInt
NonUpdate
TDTCBB
30
509.13
11.09
8.09
7.57
1529.64
23.67
22.31
22.26
31
1035.66
10.17
6.02
5.82
6856.14
20.38
14.48
13.19
32
1388.77
16.96
7.89
7.21
5212.03
25.59
17.12
13.65
33
879.92
16.77
11.04
9.53
1796.53
32.07
27.22
22.58
34
963.38
19.89
10.73
10.06
4515.09
47.50
26.71
21.62
35
6244.71
42.94
24.32
22.78
31498.4
157.88
63.27
56.17
36
—
41.69
23.85
22.35
—
98.36
54.02
44.21
37
—
28.37
20.18
15.01
—
43.52
57.85
23.92
38
—
33.26
18.92
18.55
—
44.95
34.48
30.50
39
—
47.54
19.16
19.10
—
117.78
50.05
49.90
40
—
55.58
26.14
22.41
—
95.87
52.14
44.07
41
—
58.15
36.96
31.23
—
124.96
91.81
66.03
42
—
104.20
60.50
54.53
—
331.95
179.80
152.06
43
—
95.43
33.39
32.31
—
150.99
46.79
45.63
44
—
84.07
33.05
31.58
—
133.42
58.17
58.13
45
—
275.32
107.78
106.79
—
1423.46
565.39
538.09
46
—
136.24
59.92
52.38
—
397.62
191.27
185.32
47
—
146.85
43.02
40.44
—
384.70
73.44
72.85
48
—
110.02
41.82
40.58
—
326.78
63.88
61.91
49
—
162.07
60.65
51.04
—
564.89
121.81
90.99
50
—
204.68
84.44
69.05
—
370.86
172.90
135.38
51
—
228.01
128.46
110.05
—
702.79
382.00
389.69
52
—
357.41
188.84
163.81
—
617.71
659.73
587.63
53
—
443.14
189.53
147.82
—
1005.12
898.90
495.71
54
—
503.18
168.74
149.32
—
1740.40
446.83
440.71
55
—
364.66
141.32
114.38
—
975.19
386.53
253.74Figure 8
The time cost of different algorithms.
(a)
(b)The average time cost of the B&B algorithm is less than 150 s when there are 55 targets, which indicates that the algorithm has a high efficiency. Experiments show that the algorithm can effectively deal with temporal constraints composed of the time-dependent maneuvering and imaging time windows. In the extreme case of the experiments, the maximum time cost of the B&B algorithm is 587.6 s, not more than 10 min. This indicates that the B&B algorithm meets the needs of the use of the agile satellites, and the algorithm could find the optimal solution of a problem that is about twice the size of the actual demand. The effects of the different mechanisms are analyzed in the following.The time costs of all the algorithms become larger with the increase of the size of the examples, but the growth rates of each algorithm are not the same, which shows that the robustness of each algorithm to the degree of difficulty is not the same. It can be seen from Figure8 that the B&B algorithm grows the slowest, followed by nonupdating algorithm, noninitialization algorithm, and nonpruning algorithm. This phenomenon indicates that the interaction of various solving strategies can help to increase the stability of the algorithm to difficult problems.It can be seen from Table2 that the time cost of the nonpruning algorithm rises a lot with the increase of the size of the examples. When the size of the example reaches 35, the average time of the nonpruning algorithm has reached 6244.71 s, but the average time cost of the B&B algorithm is only 22.78 s. This means that the pruning strategy SDBPS in Section 3.5 can greatly improve the efficiency of the algorithm.The change tendency of the time cost of the noninitialization algorithm is similar to that of the B&B algorithm. The difference between the two average time costs also rises with the increase of the example size. This shows that as the size of the example increases, the role of the initialization method increases. When the study size is around 55 targets, the time cost of the noninitialization algorithm is about two times that of the B&B algorithm; that is, the optimal solution time cost increases by about 219% in the case of no initialization method. This verifies that it could accelerate the algorithm where a good lower bound is provided at the beginning of the algorithm.When the number of targets is less than 50, nonupdating algorithm and the B&B algorithm are almost the same. When the scale of the problem is larger than 50, the time difference between the two is gradually increased. According to the analysis of the latter, we can see that the number of successful updating times is not a lot, but there is no small effect on the searching efficiency, and the time cost will increase by 20% when the SRBLBUM in Section3.6.2 is not adopted.With the increase of the difficulty of the problem, the difference of the time cost between different algorithms becomes larger, which means the effect of each mechanism on the solution efficiency is increasing when the problem is hard to solve. The B&B algorithm has the best performance under different scale targets, followed by nonupdating algorithm, noninitialization algorithm, and nonpruning algorithm. So the SDBPS in Section3.5 contributes the most, followed by the LACM in Section 3.3 and finally the SRBLBUM in Section 3.6.2.The difference of the maximum time cost between the incomplete algorithm and the B&B algorithm is larger than the difference of the average time cost between the algorithms, indicating that the B&B algorithm has better stability. When the time cost of the B&B algorithm is large, the difference between each incomplete algorithm and the B&B algorithm is also large, which indicates that the effect of each mechanism is more obvious in the face of difficult problems.To further analyze the effect of SDBPS and SRBLBUM on the efficiency of the solution, we also count the number of successes of various methods in different algorithms as shown in Figure9.Figure 9
The number of successful pruning and updating attempts.
(a)
(b)The number of successful SDBPS increases with the increase of the size of the problem, and the change trend is similar to the time cost. The more complex the problem is, the greater the dependence of the pruning strategy is, which verifies that the pruning strategy SDBPS plays a more important role in complex problems in the preceding paper. The number of successful SDBPS of the noninitialization algorithm is the highest, which is about 25000 when there are 53 targets, followed by the nonupdating algorithm and the B&B algorithm. This could be caused by the pruning position of the B&B algorithm that is closer to the root node. Further explanation could be that the other strategies are helpful to pruning earlier, and thus the searching efficiency is improved.The number of successful SDBPS and SRBLBUM is higher in the noninitialization algorithm, which means that SDBPS and SRBLBUM play a more important role in accelerating the optimal solution search. The number of successful SRBLBUM in the B&B algorithm is not large but has a slowly rising trend. Combined with the solution time, we can tell that it brings a good effect to the improvement of the searching efficiency, although there is only a small amount of successful SRBLBUM. When the problem is complex, SRBLBUM could save about 20% of the searching time.


## 4.1. Test Data

The examples of China’s agile satellite platform are used to validate the B&B algorithm. The maneuver process includes acceleration, uniform maneuver, and deceleration. Tranquilization time is required to reach the pointing stability allowing for good image quality as well. Maneuvers of 45° could be completed in about 60 seconds. Overall, the maneuver time is highly dependent on the rotation angle and axis. For good imaging quality, attitude is recommended to remain fixed during imaging, so the targets are all along-track strips. While the across-track tilt angle for nominal imaging acquisitions is±30°, the satellite could be figured to achieve ±45° off-nadir pointing capability.In general, an Earth observation satellite has an imaging time of 40 minutes in one track, and the targets are uniform distributed in both sides of the imaging track. In application, the time of the scheduling algorithm is demanded to be less than 10 minutes. In order to test the performance of the algorithm, the number of the targets ranges from 30 to 55. And other parameters such as the duration time and tranquilization time are in Table1. The parameters for instance generation are listed in Table 1 where the left part of the table associates with scenario attributes and the right part associates with maneuverability. The number of targets ranges from 30 to 55, and targets are uniform distributed in both sides of the imaging track which means each target has an imaging time window. The duration of the targets is a Gauss distribution with a mean value of 15 and a variance of 9. The profit of the targets is a Gauss distribution whose mean value is a function of the duration; this means a more time-consuming target may have a higher profit. The satellite has a maximum maneuver speed at 1°/s, an acceleration speed at 0.5°/s2, and a deceleration speed at 0.25°/s2. A tranquilization time of 5 s is needed after maneuver.Table 1
Parameters of the instances and satellite.
Target attribute
Maneuverability
Number of targets
[
30,55
]
Max maneuver speed
1
°
/
s
Target distribution
Uniform distribution
Acceleration
0.5
°
/
s
2
Duration distribution
N
(
15,9
)
Deceleration
0.25
°
/
s
2
Profit distribution
N
2
∗
d
u
r
i
-
5
,
100
Tranquilization time
5 sA total number of 260 instances were used to test our B&B algorithm, where, for each of the 26 different numbers of targets (from 30 to 55, see Table1), 10 random instances were generated. The B&B algorithm is coded in MATLAB 2014a and run on a computer with a 2.4 GHz i5 CPU and 3.79 GB RAM.


## 4.2. Results

This subsection analyzes the effect of different mechanisms, such as initialization solution, segment domination based pruning strategy, and best solution updating method, on the efficiency of the algorithm at different study scales. As the B&B algorithm will always find the optimal solution of the problem, we use the time cost as a measure to evaluate the efficiency of an algorithm.The effects of different mechanisms on the algorithm efficiency are analyzed by comparing the B&B algorithm with the incomplete algorithms which lack a single mechanism. In the experiment, 10 experiments are randomly generated for each study scale. And then, the average time cost and the maximum time cost are used to analyze the effects of different mechanisms on the efficiency of the algorithm.Three incomplete algorithms, noninitialization algorithm, nonpruning algorithm, and nonupdating algorithm, are designed for each mechanism.The noninitialization algorithm, which is referred to as “nonInit,” means that the algorithm has no initial solution before searching; that is, the current best solution is empty and the current best profit is 0 at the beginning of the search. However, the algorithm has the pruning method and best solution updating method corresponding to Sections3.4, 3.5, and 3.6.The nonpruning algorithm, which is referred to as “nonPrune,” only adopts the pruning strategy in Sections3.4 and 3.6, which prune a branch once the branch is found to be inconsistent, and does not use the pruning strategy SDBPS designed in Section 3.5. The initial solution of the algorithm is generated by the LACM of Section 3.3. And the SRBLBUM in Section 3.6.2 is used.The nonupdating algorithm, which is referred to as “nonUpdate,” is that the algorithm does not adopt the SRBLBUM of Section3.6.2. The initial solution of the algorithm is generated by the LACM of Section 3.3, and the pruning strategies of Sections 3.4 and 3.5 are adopted.The time cost statistics of the examples are shown in Figure8 and Table 2. The left column of Table 2 is the number of targets of the examples. The statistical data of the nonpruning algorithm is only shown in the table because the time cost of the algorithm is too large to test all the examples. However, the available data in Table 2 are sufficient to analyze the effect of the pruning mechanism on the solution efficiency. Figure 8(a) shows the average time cost of different algorithms under different scale cases; Figure 8(b) shows the maximum time cost. By comparing different incomplete algorithms and B&B algorithms, we can analyze the influence degree of different mechanisms.Table 2
The time costs of different algorithms.
Number of targets
Average time cost
Maximum time cost
NonPrune
NonIntial
NonUpdate
TDTCBB
NonPrune
NonInt
NonUpdate
TDTCBB
30
509.13
11.09
8.09
7.57
1529.64
23.67
22.31
22.26
31
1035.66
10.17
6.02
5.82
6856.14
20.38
14.48
13.19
32
1388.77
16.96
7.89
7.21
5212.03
25.59
17.12
13.65
33
879.92
16.77
11.04
9.53
1796.53
32.07
27.22
22.58
34
963.38
19.89
10.73
10.06
4515.09
47.50
26.71
21.62
35
6244.71
42.94
24.32
22.78
31498.4
157.88
63.27
56.17
36
—
41.69
23.85
22.35
—
98.36
54.02
44.21
37
—
28.37
20.18
15.01
—
43.52
57.85
23.92
38
—
33.26
18.92
18.55
—
44.95
34.48
30.50
39
—
47.54
19.16
19.10
—
117.78
50.05
49.90
40
—
55.58
26.14
22.41
—
95.87
52.14
44.07
41
—
58.15
36.96
31.23
—
124.96
91.81
66.03
42
—
104.20
60.50
54.53
—
331.95
179.80
152.06
43
—
95.43
33.39
32.31
—
150.99
46.79
45.63
44
—
84.07
33.05
31.58
—
133.42
58.17
58.13
45
—
275.32
107.78
106.79
—
1423.46
565.39
538.09
46
—
136.24
59.92
52.38
—
397.62
191.27
185.32
47
—
146.85
43.02
40.44
—
384.70
73.44
72.85
48
—
110.02
41.82
40.58
—
326.78
63.88
61.91
49
—
162.07
60.65
51.04
—
564.89
121.81
90.99
50
—
204.68
84.44
69.05
—
370.86
172.90
135.38
51
—
228.01
128.46
110.05
—
702.79
382.00
389.69
52
—
357.41
188.84
163.81
—
617.71
659.73
587.63
53
—
443.14
189.53
147.82
—
1005.12
898.90
495.71
54
—
503.18
168.74
149.32
—
1740.40
446.83
440.71
55
—
364.66
141.32
114.38
—
975.19
386.53
253.74Figure 8
The time cost of different algorithms.
(a)
(b)The average time cost of the B&B algorithm is less than 150 s when there are 55 targets, which indicates that the algorithm has a high efficiency. Experiments show that the algorithm can effectively deal with temporal constraints composed of the time-dependent maneuvering and imaging time windows. In the extreme case of the experiments, the maximum time cost of the B&B algorithm is 587.6 s, not more than 10 min. This indicates that the B&B algorithm meets the needs of the use of the agile satellites, and the algorithm could find the optimal solution of a problem that is about twice the size of the actual demand. The effects of the different mechanisms are analyzed in the following.The time costs of all the algorithms become larger with the increase of the size of the examples, but the growth rates of each algorithm are not the same, which shows that the robustness of each algorithm to the degree of difficulty is not the same. It can be seen from Figure8 that the B&B algorithm grows the slowest, followed by nonupdating algorithm, noninitialization algorithm, and nonpruning algorithm. This phenomenon indicates that the interaction of various solving strategies can help to increase the stability of the algorithm to difficult problems.It can be seen from Table2 that the time cost of the nonpruning algorithm rises a lot with the increase of the size of the examples. When the size of the example reaches 35, the average time of the nonpruning algorithm has reached 6244.71 s, but the average time cost of the B&B algorithm is only 22.78 s. This means that the pruning strategy SDBPS in Section 3.5 can greatly improve the efficiency of the algorithm.The change tendency of the time cost of the noninitialization algorithm is similar to that of the B&B algorithm. The difference between the two average time costs also rises with the increase of the example size. This shows that as the size of the example increases, the role of the initialization method increases. When the study size is around 55 targets, the time cost of the noninitialization algorithm is about two times that of the B&B algorithm; that is, the optimal solution time cost increases by about 219% in the case of no initialization method. This verifies that it could accelerate the algorithm where a good lower bound is provided at the beginning of the algorithm.When the number of targets is less than 50, nonupdating algorithm and the B&B algorithm are almost the same. When the scale of the problem is larger than 50, the time difference between the two is gradually increased. According to the analysis of the latter, we can see that the number of successful updating times is not a lot, but there is no small effect on the searching efficiency, and the time cost will increase by 20% when the SRBLBUM in Section3.6.2 is not adopted.With the increase of the difficulty of the problem, the difference of the time cost between different algorithms becomes larger, which means the effect of each mechanism on the solution efficiency is increasing when the problem is hard to solve. The B&B algorithm has the best performance under different scale targets, followed by nonupdating algorithm, noninitialization algorithm, and nonpruning algorithm. So the SDBPS in Section3.5 contributes the most, followed by the LACM in Section 3.3 and finally the SRBLBUM in Section 3.6.2.The difference of the maximum time cost between the incomplete algorithm and the B&B algorithm is larger than the difference of the average time cost between the algorithms, indicating that the B&B algorithm has better stability. When the time cost of the B&B algorithm is large, the difference between each incomplete algorithm and the B&B algorithm is also large, which indicates that the effect of each mechanism is more obvious in the face of difficult problems.To further analyze the effect of SDBPS and SRBLBUM on the efficiency of the solution, we also count the number of successes of various methods in different algorithms as shown in Figure9.Figure 9
The number of successful pruning and updating attempts.
(a)
(b)The number of successful SDBPS increases with the increase of the size of the problem, and the change trend is similar to the time cost. The more complex the problem is, the greater the dependence of the pruning strategy is, which verifies that the pruning strategy SDBPS plays a more important role in complex problems in the preceding paper. The number of successful SDBPS of the noninitialization algorithm is the highest, which is about 25000 when there are 53 targets, followed by the nonupdating algorithm and the B&B algorithm. This could be caused by the pruning position of the B&B algorithm that is closer to the root node. Further explanation could be that the other strategies are helpful to pruning earlier, and thus the searching efficiency is improved.The number of successful SDBPS and SRBLBUM is higher in the noninitialization algorithm, which means that SDBPS and SRBLBUM play a more important role in accelerating the optimal solution search. The number of successful SRBLBUM in the B&B algorithm is not large but has a slowly rising trend. Combined with the solution time, we can tell that it brings a good effect to the improvement of the searching efficiency, although there is only a small amount of successful SRBLBUM. When the problem is complex, SRBLBUM could save about 20% of the searching time.


## 5. Conclusion

This paper considers a new AEOSS problem with time-dependent temporal constraints which was not investigated in the literature. To address this new problem, we proposed a highly efficient branch and bound (B&B) algorithm to find its optimal solution. The proposed B&B algorithm uses a look-ahead construction method to generate a high quality initial lower bound at the very beginning. It is also equipped with three complementary pruning strategies, namely, the symmetry breaking based pruning strategy, the segment domination based pruning strategy, and the bound based pruning strategy. The combined use of these three pruning strategies greatly reduces the search space and accelerates the search process. To validate the efficacy of the proposed algorithm, we conducted empirical experiments on a set of instances that are closely related to the real-life scenario. Computational results disclosed that the proposed B&B is highly efficient which meets engineering demand very well. Indeed, it is able to solve instances with 55 targets using only 164 seconds on average and 588 seconds in maximum. Additional experiments were also conducted to evaluate the effectiveness of three algorithm ingredients: the look-ahead construction method (LACM), the segment domination based pruning strategy (SDBPS), and the segment replacement based lower bound updating method (SRBLBUM, which is used within the bound based pruning strategy). The results revealed that all of the three ingredients contribute to improve the performance of the B&B algorithm, and the most contributive one is SRBLBUM, followed by LACM and finally SDBPS.



---

*Source: 7345941-2017-09-07.xml*