In this paper, the authors introduced a new approach to find the optimal collision avoidance maneuver considering multi threatening objects within short period, while satisfying constraints on the fuel limit and the acceptable collision probability. A preliminary effort in applying a genetic algorithm (GA) to those kinds of problems has also been demonstrated through a simulation study with a simple case problem and various fitness functions. And then, GA is applied to the complex case problem including multithreatening objects. Two distinct collision avoidance maneuvers are dealt with: the first is intrack direction of collision avoidance maneuver. The second considers radial, intrack, crosstrack direction maneuver. The results show that the first case violates the collision probability threshold, while the second case does not violate the threshold with satisfaction of all conditions. Various factors for analyzing and planning the optimal collision avoidance maneuver are also presented.
1. INTRODUCTION
Space debris or space junk refers to the uncontrollable objects among the artificial objects in the space. At present, it is estimated that there are about 22,000 pieces of space debris larger than 10 cm and more than 600,000 pieces larger than 1 cm with over millions of tiny space debris smaller than 1 cm (Liemer & Chyba 2010).
The number of space debris has been greatly increased in recent times especially by the interception experiment of the Chinese FengYun 1C in January, 2007 and the collision of the IRIDIUM 33 of the USA and the COSMOS 2251 of Russia in February, 2009. Thus, there is an increasing interest in the number of space debris worldwide. The USA, the space development frontier, and the European Space Agency (ESA) have already developed the system for the analysis of space debris collision risk and utilized it for the satellites of their countries (Morris 2004, Mariella 2006). However, the space debris collision risk analysis systems that have been developed until now do not provide any specific maneuver information for avoidance, just analyzing the risk of collision.
With regards the avoidance maneuver, ESA has conducted active studies on the collision avoidance methods based on variation of the orbit period or semi major axis, the timing of collision avoidance maneuver, and the change of the collision probability by the thrust direction at the expected collision timing (Alfano 2005, SánchezOrtiz et al. 2006). The collision avoidance method to increase the semi major axis and orbit period through the intrack direction velocity increment is often chosen in general because it consumes less fuel, according to the result. However, in the studies, the number of approaching space debris was assumed to be one, the position of the performing the collision avoidance maneuver was limited to the expected position of collision or the position half period before the expected position of collision, or the thrust direction of the collision avoidance maneuver was limited to one axis or two axes direction of the radial, intrack, crosstrack (RIC) coordinates.
In our study, we investigated the optimized collision avoidance maneuver method, considering the issues that have not be taken into account, i.e. the multiple approaching space debris pieces, the timing of collision avoidance maneuver and the velocity increment to the three directions of the RIC coordinates.
In this study, neither a differentiable object function may be constituted nor may an analytical method be applied, because different analytical methods such as orbit analysis as well as collision probability calculation based on the orbit analytical results. Thus, we employed the genetic algorithm (GA) that is relatively robust to this type of problem and useful to obtaining a global solution. The objective function of the GA (fitness function) was constituted for the collision probability and the miss distance.
2. PROBLEM DEFINITION AND ACCESS
The object chosen for the collision avoidance maneuver was the Korea MultiPurpose Satellite2 (KOMPSAT2). The orbit information of the satellite is shown in
Table 1
.
The assumed case was where multiple space debris pieces are approaching the KOMPSAT2 within a few days. The problem was applied, dividing the case to a simple case and a complex case. The simple case was applied in order to verify the applicability of the optimal solution obtained by the GA by simplifying the collision avoidance maneuver. For the complex case, the space debris orbits were designed so that multiple space objects may be approaching in order to compare the conventional collision avoidance maneuver methods and the one suggested in this study. The size of all the approaching space debris pieces was assumed to be 10 cm. The covariance matrix
Orbit information of KOMPSAT2.KOMPSAT2: Korea MultiPurpose Satellite2, RAAN: right ascension of ascending node.
Orbit information of KOMPSAT2. KOMPSAT2: Korea MultiPurpose Satellite2, RAAN: right ascension of ascending node.
of the individual pieces was assumed as shown in Eq. (1):
 2.1 Calculation of the Collision Probability
On the Bplane with the satellite at the center, the space debris approaches perpendicularly. Connection of the same values of the collision probability calculated with the positions of the satellite and the space debris as well as the positional uncertainties gives the elliptical shape shown in
Fig. 1
.
AdvCAT
^{®}
of STK using the Alfano formula was employed for the calculation of the collision probability. Eq. (2) shows the Alfano formula used in AdvCAT
^{®}
(Alfano 2007):
where
R_{c}
shown in
Fig. 2
denotes the cross sectional radius calculated by summing the area of two objects and assuming the area as that of a circle with the radius of
R_{c}
. Here,
σ_{x}
and
σ_{y}
denote the standard deviation in the direction of each axis, and
x_{m}
and
y_{m}
the distance from the center in the direction of each axis.
 2.2 Genetic Algorithm
The GA applied to this study is known to have excellent convergence to global minimum or maximum in various application problems compared with other optimization algorithms (Goldberg 1989).
Collision probability density function at Bplane (Klinkrad 2006).
The optimization processes based on the GA realized in this study were the Matlab
^{Ⓡ}
GA and the AGI STK/AdvCAT
^{Ⓡ}
software for the prediction of the orbit and the calculation of the collision probability (Kim et al. 2009).
Fig. 3
shows the algorithm flow chart of the realized process.
As shown in
Fig. 3
, the initial group generated by the GA was applied to assess the probability of collision with multiple pieces of space debris. Then, the objective function (fitness function) was acquired by reflecting the amount of fuel consumed by the orbit maneuver through penalizing strategy. The most widely used fitness function has the form described in the article ‘Algorithms and Examples’ by Deb & Agrawal (1999) as shown in Eq. (3):
where
f
denotes the objective value to be minimized and
g_{i}
and
h_{k}
the constraints.
R_{j }
and
r_{k}
are the penalizing factors. By constituting the fitness function as shown in Eq. (3), the optimum values considering the constraints can be calculated.
After the selection, crossover and mutation of the GA are performed, the newly generated variables are applied to calculate the objective function once again. The process of the GA was to be ended when the maximum number of generation is reached.
The most important thing in this process is the fitness function that is directly involved in the regeneration of the objects. The optimum solution can be obtained more rapidly and precisely depending on the fitness function
Cross section (Klinkrad 2006).
Flow chart of genetic algorithm.
values. In this article, three fitness functions are introduced and the results are compared.
3. SIMULATION RESULTS AND SUMMARY
 3.1 Simple Case
If the problem case is simplified, the optimum solution that satisfies the constraints is predictable. The study for the simple case was performed to verify the applicability of the optimization method by comparing the GA optimal solution with the predicted optimal solution.
Table 2
shows the space debris of which elevation is different from that of the KOMPSAT2 but close to it.
In this study, the collision probability and the distance in the radius direction were analyzed as the objective values. The collision probability of 1.0 × 10
^{7}
~1.0 × 10
^{6}
or the miss distance of 0.2 km or more is expected for all the pieces of the space debris.
Table 2
shows the predicted transfer orbit following the collision avoidance through elevation increase. To satisfy the allowable collision probability, the orbit will be transferred to 690.0218 km as the elevation is increased by 1.0833 km after consuming 0.2016 kg of the fuel. To satisfy the allowable radius distance, the orbit will be transferred to 689.224 km as the elevation is increased by 0.285 km after consuming 0.0533 kg of the fuel.
Fig. 4
briefly expresses the orbit shape of the KOMPSAT2 and the space debris pieces and the orbit transfer by the maneuver.
Orbit of K2 and Debris.
Information of space debris at simple case.
Information of space debris at simple case.
Each objective value has different constraints for optimization.
Table 3
shows the individual constraints. The constraint that the elevation should be higher than 688.939 km is because the elevation of the optimal solution is predicted to be higher than that current elevation (688.939 km). Low earth orbits basically adopt the strategy to increase the elevation for the collision avoidance maneuver because they have natural elevation decrease. With regard to the fuel condition, the constraint of the fuel consumption of the predictable optimum solution
Constraint according to objective.
Constraint according to objective.
Setting of genetic algorithm for simple case.
Setting of genetic algorithm for simple case.
Result of genetic algorithm (objective is acceptable collision probability).
Result of genetic algorithm (objective is acceptable collision probability).
Estimated result according to objective.
Estimated result according to objective.
Collision probability and range (objective is acceptable collision probability).
Collision probability and range (objective is acceptable collision probability).
is adopted so that the consumption may not exceed the value. The allowable probability of collision with the individual pieces of the space debris is 1.0 × 10
^{7}
~1.0 × 10
^{6}
and the allowable radius distance is 0.2 km or higher.
Table 4
shows the settings of the GA applied to obtain the optimum solution for the simple case.
 3.1.1 Simulation ResultCollision Probability
The fitness function described in Section 2.2 was constituted for the collision probability as shown in Eq. (4):
where
P_{c,max,i}
denotes the collision probability, Δ
f
the fuel consumption,
f_{ntf}
the allowable fuel consumption. Additionally, SMA
_{0}
denotes the initial semi major axis, and SMA the semi major axis of the transferred orbit following the collision avoidance maneuver.
Penalty is given including the weights w
_{1}
, w
_{2}
and w
_{3}
each time when the constraints in
Table 3
are violated. The
w_{1}
for the violation of the allowable collision probability (1.0 × 10
^{7}
~1.0 × 10
^{6}
) was chosen to be 10
^{2}
and 10, and w
_{2}
for the violation of the fuel condition 10
^{3}
. A penalty was also given when a lower elevation was selected (
w
_{3}
= 10
^{2}
) so that the calculation could be directed to increase of the elevation, because it is more advantages to choose the increased elevation for the collision avoidance maneuver than the decreased elevation in the following operation process. The fitness function was generated by summing all the penalties given to each piece of the space debris.
The fitness function of Eq. (4) was applied to the GA, and the result showed that all the constraints in
Table 3
were satisfied, as shown in
Table 5
.
The optimum solution of the GA was found to be very close to the results predicted in
Table 6
.
Table 7
shows the probability of collision and miss distance with the pieces of the space debris after the collision avoidance maneuver.
As shown in
Table 7
, the allowable collision probability was satisfied for all the pieces of the space debris.
Fig. 5
shows the GA result of the fitness function. The specific shape of the graphs was different at each time of the simulation, but all of them converged and calculated optimum solutions were similar.
 3.1.2 Simulation ResultMiss Distance
The fitness function mentioned in Section 2.2 was constituted for the collision probability as shown in Eq. (5):
where
R
_{min}
denotes the miss distance, Δ
f
the fuel consumption,
f
_{ntf}
the allowable fuel consumption. Additionally,
SMA
_{0}
denotes the initial semi major axis, and
SMA
the semi major axis of the transferred orbit following the collision avoidance maneuver.
Penalty is given including the weights
w
_{2}
and
w
_{3}
each time when the constraints in
Table 3
are violated. The penalty factor for the violation of the fuel condition was chosen as
w
_{2}
= 2. A penalty was also given when a lower elevation was selected (
w
_{3}
= 2) so that the calculation could be directed to increase of the elevation, because it is more advantages to choose the increased elevation for the collision avoidance maneuver than the decreased elevation in the following operation process. Additionally, since the distance is to be increased, the negative sign (‘’) was applied to the fitness function value in order to obtain the minimum. The fitness function was generated by summing all the penalties given to each piece of the space debris.
Result graph of genetic algorithm (objective is acceptable collision probability).
Result graph of genetic algorithm (objective is acceptable radial distance).
The fitness function of Eq. (5) was applied to the GA, and the result showed that all the constraints in
Table 3
were satisfied, as shown in
Table 8
.
The optimum solution of the GA was found to be very close to the results predicted in
Table 6
.
Table 9
shows the probability of collision and miss distance with the pieces of the space debris after the collision avoidance maneuver.
As shown in
Table 9
, the allowable miss distance was satisfied for all the pieces of the space debris, which is the same result of the predicted optimum solution.
Fig. 6
shows the GA result graph. The specific shape of the graphs was different at each time of the simulation, but all of them converged and calculated optimum solutions were similar.
 3.2 Complex Case
To constitute a complex case, the orbit was set for multiple pieces of the space debris to approach the satellite. The pieces of the space debris were generated as shown in
Table 10
by altering all the orbit elements of the KOMPSAT2.
Table 11
shows the collision probability and the miss distance between the individual pieces of the space debris and the KOMPSAT2. The avoidance maneuver method considered not just one intrack direction but all the three directions of radial, intrack and crosstrack in order to compare the result with that of the conventional studies.
Fig. 7
shows the change of the collision avoidance maneuver timing and the collision probability between the Debris 4 in
Table 10
and the KOMPSAT2 by the velocity increment. The direction of the velocity increment was limited to the intrack direction.
Fig. 7
shows that the collision probability was greatly influenced by the collision avoidance maneuver timing and the velocity increment. The collision avoidance maneuver timing is closely related to the satellite operation relevant to the mission, and it changes the collision probability by greatly affecting the
Result of genetic algorithm (objective is acceptable radial distance).
Result of genetic algorithm (objective is acceptable radial distance).
Radial range and range (objective is acceptable radial distance).
Radial range and range (objective is acceptable radial distance).
relative distance and period. The collision direction and the velocity increment have a direct effect on the transfer orbit. For these reasons, the collision avoidance maneuver timing and the velocity increment were set as the input variables.
The collision avoidance maneuver timing is decided at the time as close as possible to the time when the collision is predicted, and it is usually 1 or 2 orbits before the predicted collision timing (Alfano 2005). In this study, the time range of the collision avoidance maneuver was set as the time 9,600 seconds before the time when the first collision is expected to occur among the four pieces of the space debris. 9,600 seconds, corresponding to about 2.67
Collision probability according to collision avoidance maneuver and ΔV.
Orbit information of K2 and debris at complex case.RAAN: right ascension of ascending node.
Orbit information of K2 and debris at complex case. RAAN: right ascension of ascending node.
Collision probability and RIC, range.RIC: radial, intrack, crosstrack.
Collision probability and RIC, range. RIC: radial, intrack, crosstrack.
hours, allow about 1.5 orbits until the time when the first collision is expected to occur. Additionally, the intrack direction velocity increment and the RIC direction velocity increment were set as the input variables for the collision avoidance maneuver direction in the simulation in order to compare the result with that of the conventional studies. The variable range of the velocity increment in each direction was set to be ±1 m/s. The allowable collision probability was set to be 9.9 × 10
^{6}
~1.0 × 10
^{6}
as the criterion for the optimum collision avoidance maneuver so that it could be satisfied for the four pieces of the space debris. The maximum fuel consumption was limited to 0.3 kg.
Table 12
shows the applied GA settings to obtain the optimum solution for the complex case. Since the analytical range of the variables was wider than that of the simple case, the number of individuals in each generation was increased to 200.
The fitness function introduced in Section 2.2 was applied, and its specific formula is shown in Eq. (6). Although minimization of the collision probability was the goal, all the objects are expected to satisfy the allowable collision probability and thus 10
^{6}
was set as the reference value. The fitness function,
F
, was constituted to have the minimum within the region, as shown in Eq. (6):
The value of
w
_{1}
is 1, if the allowable collision probability is satisfied; otherwise, 10, 10
^{2}
, 10
^{3}
and 10
^{4}
, case by case. In Eq (6),
f
_{ntf}
denotes the allowable fuel consumption, which is 0.3 kg, and Δ
f
the fuel consumption. The value of
w
_{2}
is 0,
Setting of genetic algorithm for complex case.
Setting of genetic algorithm for complex case.
Result of genetic algorithm with intrack maneuver.
Result of genetic algorithm with intrack maneuver.
if the allowable fuel consumption is satisfied; otherwise, 100.
The results of the simulation performed with the input variables of the collision avoidance maneuver timing and the intrack direction velocity increment are shown in
Figs. 8
and
9
, and
Table 13
.
Table 13
shows the values of
w
_{1}
in each case, indicating that the Space Debris 3 fails to satisfy the allowable collision probability in all the cases. The results of the simulation performed with the input
Result graph of genetic algorithm with intrack direction maneuver.
RIC direction distance after collision avoidance maneuver with intrack direction maneuver. RIC: radial, intrack, crosstrack.
variables of the collision avoidance maneuver timing and the RIC direction velocity increment are shown in
Figs. 10
and
11
, and
Table 14
. The result shows that
w
_{1}
satisfies the allowable collision probability in all the cases.
Comparison of the
Table. 13
and
14
indicates that the RIC direction velocity increment requires more than 35 times of increment than that of the intrack direction velocity increment. This is because the intrack direction
Result graph of genetic algorithm with RIC direction maneuver. RIC: radial, intrack, crosstrack.
RIC direction distance after collision avoidance maneuver with RIC direction maneuver. RIC: radial, intrack, crosstrack.
Result of genetic algorithm with RIC maneuver.RIC: radial, intrack, crosstrack.
Result of genetic algorithm with RIC maneuver. RIC: radial, intrack, crosstrack.
velocity increment does not provide the any case where the given allowable collision probability may be satisfied for the Space Debris 3. The RIC direction velocity increment provides the case where the given allowable collision probability may be satisfied for the Space Debris 3, while satisfying the allowable collision probability for other pieces of the space debris. This can be verified in
Figs. 9
and
11
showing the change of the RIC direction distance from that of the time before the collision avoidance maneuver. Comparison of the
Figs. 9
and
11
indicates that the transfer orbit is closer to the previous orbit at the time when the optimum solution appears in the intrack direction velocity increment than in the RIC direction velocity increment. Hence, the intrack direction velocity increment dose not satisfy the allowable collision probability for the Space Debris 3, while the RIC direction velocity increment dose.
In other words, when only the intrack direction velocity increment is considered, the allowable collision probability is never satisfied for the Space Debris 3 regardless of the weights. However, when the three RIC directions velocity increment is considered, the allowable collision probability is satisfied. This indicates that, although the intrack direction maneuver is often performed in general, the maneuver in other directions needs to be considered depending on the case and purpose.
 3.3 Analysis of the Fitness Function
In this study, the optimization problem is dealt with using the GA. The fitness function including the objective values and constraints was constituted to solve the maximum or minimum problem. The convergence time and global solution calculation performance of the GA are dependent on the fitness functions. In this study, the performance was compared with regard to the fitness functions.
Besides the fitness function described in Section 2.2, there are various fitness functions. The fitness function constituted without setting specific penalty factor values is called adaptive fitness function. In an adaptive fitness function, the penalty factors are determined during the calculation process. Among the various adaptive fitness functions, two methods are introduced in this article. The first one is the method by introduced by Lemonge and Barbosa in 2004 (Helio & Afonso 2008), shown in
Fig. 12
.
As can be seen from the constitution of the fitness function, the objective function value is selected as the fitness function value in the allowed range, while an alternative value is selected in the constrained range. The greater value between the objective function value (
f
(
x
)) and the mean value of the objective function is chosen as the value of
denotes the mean objective function value of the generation that is currently calculated, and
v_{j}
(
x
) the constraint violation value. The penalty factors for the individual constraints are defined as in Eq. (8):
Adoptive fitness function (1) (Helio & Afonso 2008).
Adoptive fitness function (2) (Deb & Agrawal 1999).
The penalty factor is calculated as the ratio of the sum of the objective function values according to the degree of the violation. The second adaptive fitness function, which is similar to the first one but a little bit simpler, is shown in
Fig. 13
(Deb & Agrawal 1999).
As can be seen from the constitution of the fitness function, the objective function value is selected as the fitness function value in the allowed range, while an alternative value is selected in the constrained range.
f
_{max}
denotes the maximum objective function value in the generation, and
v_{j}
(
x
) the constraint violation value. Therefore, the objective function value used in the constrained region is the maximum objective function value in the allowed region, and the penalty is given according to the degree of the constraints.
The three fitness functions were applied to the GA for the simple case with respect to the collision probability. The result showed that they satisfied all the constraints in
Table 3
, indicating that the results were very close to the expected results. The convergence time of the GA was greatly affected by the fitness functions, as shown in
Figs. 14

16
.
Table 15
shows the analytical results of the mean converged generation after 100 times of calculation for each of the fitness functions.
Result graph of genetic algorithm with fitness function (Deb, K.).
As indicated by
Figs. 14

16
and
Table 15
, the first adaptive fitness function converged most rapidly, while the basic fitness function converged most slowly. Therefore, an appropriate fitness function should be selected on the basis of the problem case in order to improve the GA performance.
 3.4 Summary
The usefulness of the GA was verified by analyzing the optimum collision avoidance maneuver in a simple case and the GA performance depending on the fitness
Result graph of genetic algorithm with adoptive fitness function (Helio & Afonso 2008).
Result graph of genetic algorithm with adoptive fitness function (Deb & Agrawal 1999).
Convergence generation according to fitness function.
Convergence generation according to fitness function.
functions, and the optimum solution was calculated by applying it to a complex case. The single intrack direction velocity increment is mostly employed as a collision avoidance maneuver method since it consumes less fuel. However, in the case where performance requirements are given including the allowable collision probability of multiple approaching objects, orbit maneuver timing and minimization of fuel consumption, the maneuver in the three RIC directions has to be taken into account because the collision avoidance maneuver considering only the intrack direction may not satisfy the performance requirements. In addition, it is assumed to be important to establish the differentiated optimum collision avoidance maneuver plants considering the characteristics of the individual missions of the current and future KOMPSATs. For example, the collision avoidance maneuver timing may be selected to minimize the mission resting phase as well as the fuel consumption, considering the imaging schedule of a satellite.
4. CONCLUSIONS
In this article, the optimum collision avoidance maneuver strategy considering multiple pieces of space debris soon approaching was suggested and the validity was verified. The collision probability is greatly affected by the collision avoidance maneuver timing and the velocity increment. The simulation result showed that consideration of on the single intrack direction fails to satisfy the allowable collision probability for all the approaching objects whereas consideration of the maneuver in the three RIC directions satisfies the collision probability for all the pieces of the space debris.
Future studies are supposed to deal with more complicated problems reflecting the satellite system constraints in the satellite imaging schedule and maneuver.
Alfano S
2005
Collision avoidance maneuver planning tool.
in Proceedings of the 15th AAS/AIAA Astrodynamics Specialist Conference
Lake Tahoe CA
711 Aug
Alfano S
2007
Review of conjunction probability methods for shortterm encounters.
in Proceedings of the AAS/AIAA Space Flight Mechanics Meeting
Sedona AZ
28 Jan1 Feb
Deb K
,
Agrawal S
,
Dobnikar A
,
Steele NC
,
Pearson DW
,
Albrecht RF
A nichedpenalty approach for constraint handling in genetic algorithms.
in Artificial neural nets and genetic algorithms: Proceedings of the International Conference in Portoroz Slovenia 1999
Springer Wien
1999
235 
243
Goldberg DE
1989
Genetic algorithms in search, optimization, and machine learning
AddisonWesley Reading
Helio JCB
,
Afonso CCL
An adaptive penalty method for genetic algorithms in constrained optimization problems in Frontiers in evolutionary robotics [Internet]
available from: http://www.intechopen.com/articles/show/title/an_adaptive_penalty_method_for_genetic_algorithms_in_constrained_optimization_problems
Kim HD
,
Bang H
,
Jung OC
2009
Genetic design of target orbits for a temporary reconnaissance mission.
JSpRo
46
725 
728
DOI : 10.2514/1.41620
Klinkrad H
2006
Space debris models and risk analysis
Praxis Publishing Ltd.
Chichester UK
215 
240
Mariella G
2006
GMV astrodynamics tools and techniques overview
in the 3rd ESA Workshop on Astrodynamics Tools and Techniques
Noordwijk The Netherlands
25 Oct
Morris R
2004
Space surveillance contributions to the STS 107 accident investigation.
in Proceedings of the 14th AAS/AIAA Space Flight Mechanics Conference
Maui Hawaii
812 Feb
SánchezOrtiz N
,
BellóMora M
,
Klinkrad H
2006
Collision avoidance maneuvers during spacecraft mission lifetime: risk reduction and required ΔV
AdSpR
38
2107 
2116
DOI : 10.1016/j.asr.2005.07.054