Collision Avoidance Algorithm for Satellite Formation Reconfiguration under the Linearized Central Gravitational Fields
Collision Avoidance Algorithm for Satellite Formation Reconfiguration under the Linearized Central Gravitational Fields
Journal of Astronomy and Space Sciences. 2013. Mar, 30(1): 11-15
Copyright ©2013, The Korean Space Science Society
This is an open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License ( which premits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : October 13, 2012
  • Accepted : November 23, 2012
  • Published : March 15, 2013
Export by style
Cited by
About the Authors
InYoung, Hwang
Sang-Young, Park
Chandeok, Park

A collision-free formation reconfiguration trajectory subject to the linearized Hill’s dynamics of relative motion is analytically developed by extending an algorithm for gravity-free space. Based on the initial solution without collision avoidance constraints, the final solution to minimize the designated performance index and avoid collision is found, based on a gradient method. Simple simulations confirm that satellites reconfigure their positions along the safe trajectories, while trying to spend minimum energies. The algorithm is applicable to wide range of formation flying under the Hill’s dynamics.
When many satellites flying in formation perform reconfiguration, they are subject to collision with each other. While it is possible to prevent the collision by immediately applying the thrust on detecting the risk of collision, it usually requires large fuel consumptions, and thus shortens mission life time (Katz et al. 2011). Thus it is more fuel-efficient to design a collision-free reconfiguration trajectory a priori, if possible.
Recently, many relevant studieshave been conducted. Sultan et al. (2006) suggested an algorithm optimizing the way-point using a gradient methodin the gravity-free, deep space. Schaft et al. (2006) demonstratedan algorithm using direct optimization method in free space. Min et al. (2010) solved the optimal control problem using the linear programming by reconstructing the Hill’s dynamics (Clohessy & Wiltshire 1960) as parametric expressions. Sauter & Palmer (2012) obtained the solution from the Model Predictive Control (MPC) using an analytic solution of optimal control problem under the Hill’s dynamics. Sun et al. (2012) tried to obtain the safe reconfiguration trajectories by redefining the Hill’s dynamics as a static model and employinga genetic algorithm.
This paper extends Sultan et al.’s method for collision avoidance reconfiguration algorithm for gravity-free, deep spaceinto that for a central gravity field near the Earth.Similarly in the case of Sultan’s algorithm forgravity-free space, way-points are introduced for collision avoidance and trajectories of satellites are represented by states of way-points. In order to generate the reconfiguration trajectories between neighboring way-points, the analytic solution of energy optimal control problem under the Hill’s dynamics is used. The optimal way-points which generate collision-free trajectories are found by a gradient method. Then, the obtained way-points and analytic solution generate the whole trajectories by connecting the subinterval reconfiguration trajectories. The proposed algorithm can develop safe reconfiguration trajectories and is easily applicable to the case of multiple satellites reconfiguration.
This paper is organized as follows. Section 2 describes parameterization of energy optimal control problem-performance index, equation of motion, boundary condition-with collision avoidance constraints using the state of way-points. Section 3 explains various optimization algorithms. Section 4 shows the result and interpretation of applying the algorithm to a simple collision avoidance example. The conclusion and the future works follow in Section 5.
- 2.1 Energy optimal control problem with collision avoidance constraints
A collision-free optimal trajectory can be estimated by solving the optimal control problem with collision avoidance constraints. In order to take account of the Earth’s gravitational effects, the circular unperturbed Hill’s dynamicsare incorporated. The optimal collision avoidance problem can be mathematically stated as follows:
Lager Image
Eq. (1) represents the total performance index of N satellites in formation, which is simply a summation of integral- squared control of each spacecraft. x 1 and u 1 are state and control vector of l -th satellite and x and u are total state and control vector of entire satellites, respectively. Eq. (2) sets the distance limit between two satellites for collision avoidance in reconfiguration:
Lager Image
r l is the position vector of l -th satellites and R l is radius of buffer region centered on l -th satellite. If the distance between two satellites is smaller than the summation of two radii, these satellites are considered to collide. The summation of two radii is called the safe limit distance.
In order to apply the collision avoidance inequality constraints, the way-points are defined as the location which satellites must pass through (Sultan et al. 2006). The optimal way-points that do not cause a collision can yield collision-free optimal trajectories.
- 2.2 General solution of optimal control problem
The trajectories between M +2 way-points including the initial and final positions can be estimated by using an analytic solution of optimal control problem with initial and final conditions. Eq. (3) is an analytic expression for the energy-optimal control problem satisfying rendezvous- type boundary conditions under the Hill’s dynamics (Lee & Park 2011). Note that it is a solution without collision avoidance constraints. As it is difficult to solve the energy optimal control problem directly with collision avoidance constraints, our algorithm begins with an initial analytic solution without collision avoidance constraints
Lager Image
Lager Image
Lager Image
The analytic expression for optimal control can be factored into time-dependent terms and prescribed boundary conditions as in Eq. (4). By applying Eq. (3) to the Hill’s dynamics, the analytic trajectory of the energy optimal control problem with boundary conditions can be developed as
Lager Image
which can be also factored into a time-dependent function and prescribed boundary conditions.
Lager Image
Lager Image
Eqs. (4) and (6) are analytic solutions for the whole time interval [t 0 , t f ]. Likewise, analytic solutions between neighboring j - th and ( j + 1 )-th way-points can be estimated. With the j - th and ( j + 1 )-th way-points as initial and final conditions, the optimal state and control trajectories can be expressed as
Lager Image
Lager Image
If these analytic solutions for the time interval [t j , t j+1 ] are applied and linked to all way-points, the solution for the entire time span [t 0 , t f ] can be calculated.
- 2.3 Optimal control problem and parameterization
In Section 2.1, the states of way-points are defined as x. Two additional variables are also defined. U is a variable for M +2 way-points of entire satellites:
Lager Image
The initial and final conditions of each satellite are given in U. M way-points of entire satellites which excludethe boundary conditionsare combined into the vectorz, which is introduced for collision avoidance algorithm:
Lager Image
With these variables U and z , the performance index and collision avoidance constraints can be stated as
Lager Image
Lager Image
Q J , b J , c J , Q lm , blm , clm are founded by reconstructing G and H lm with boundary conditions and M way-points. As the algorithm is described in Section 3, the performance index and collision avoidance constraints, which are represented as variables, create the optimal variables that do not incurcollision.
The unconstrained solutions between two way-points are first obtained from the analytic solution of energyoptimal control problemby Lee & Park (2011) as the initial solution of the problem with collision avoidance constraints:
Lager Image
If the distances between satellites are smaller than the safe limit distance, satellites are considered to collide and violate the collision avoidance constraints. At this time, calculate the difference between the square of safe limit distance and the square of minimum distance between colliding satellites and define the penalty function P(z) as the sum of satellites violating collision avoidance constraints.
Lager Image
When the penalty function, which is described as the variable z, is positive, some collision arises. That means that the variable z which makes penalty function less than or equal to 0is the solution that does not cause collisions. Thus, when some satellites violateconstraints, update the variable z repeatedly using a gradient method to make penalty function negative or 0 by Eq. (15):
Lager Image
When the updated z satisfies the collision avoidance constraints, the next process is to determine the variable minimizing the performance index. Because the performance index J(z) is a function of variable z, update z again using a gradient method to minimize J(z) according to Eq. (16).
Lager Image
The final solution going through the upper two steps satisfies the collision avoidance and minimizes the performance index at the same time (Sultan et al. 2006). This solution is a set of states of way-points. Therefore applying the calculated state to Eqs. (7) and (8) and connecting reconfiguration subinterval divided by way-points generate the collision-free reconfiguration trajectories for the entire maneuver time. The gravitational field is incorporated as the coefficient matrix R j (t), S j (t), P j (t) and Q j (t), and are estimated from the Hill’s dynamics.
This paper focuses on developing a collision-free reconfiguration algorithm under the Hill’s dynamics without perturbation. Thus, the ‘swapping cube maneuver’ simulation, identical with the simulation in Sultan et al. (2006), is conducted to objectively verify the algorithm.
The total of 8 satellites are initially placed on each vertex
Lager Image
Relative trajectories of satellites for unconstrained reconfiguration problem.
Lager Image
Histories of relative distances between satellites for unconstrained reconfiguration problem.
of a cube whose side length is 10 m, with one vertex located on a circular reference orbit of 700 km in altitude. Then each satellite swaps their position diagonally during 740.80 s.
Fig. 1 shows the relative trajectories without collision avoidance constraints. Whether collisions may or may not occur can be observed by checking distances between satellites. Here the radius of buffer region is 1 m and the safe limit distance is 2 m. Without collision avoidance constraints, distances between satellites under the safe limit distance take place 12 times in 370.50 s from the start of reconfiguration ( Fig. 2 ).
To prevent such collisions, the algorithm described in Section 3 is applied. Distances between satellites must be larger than the safe limit distance of 2 m. Fig. 3 shows the relative trajectories, and Fig. 4 shows the time history of relative distances after applying collision avoidance
Lager Image
Relative trajectories of satellites for the constrained reconfiguration problem.
Lager Image
Histories of relative distances between satellites for the constrained reconfiguration problem.
constraints. Fig. 4 confirms that the resultant relative trajectories are safe reconfiguration trajectories without collisions. Fig. 5 shows time histories of control on each axis when there are collision avoidance constraints. While the performance index is 4.3679 × 10 -8 m 2 /s 4 without considering collision avoidance, the performance index is 4.7869 × 10 -8 m 2 /s 4 with collision avoidance constraints. The performance index increases by 9.5636% for 8 satellites and 1.1955% for each satellite by average to avoid collision.
A collision-avoidance reconfiguration algorithm under the Earth’s gravitational field has been developed by extending a collision-free reconfiguration method in gravity-free space. In
Lager Image
Control histories of satellites for the constrained reconfiguration problem.
the algorithm, the way-points from analytic solution of energy optimal control problem under the Hill’s dynamics without collision avoidance constraintswere introduced as the initial solution of the constrained problem. Then, the collision- freestates and controls were developed, while minimizing the performance index. Through a simple simulation, it was confirmed that safe, collision-free trajectories was able to be generated for the linearized central gravitational field. The energy consumption for collision avoidance is minimized by trying to minimizethe distances between satellites. Because the way-points are introduced as variables, the dimension of collision avoidance constraints is restricted. It makes the algorithm useful in applying to a large group of formation flying.
As the Hill’s dynamics does not exactly represent the nonlinear gravity fieldnear a central body, it is necessary to extend the proposed approach into more general dynamic environments where a reference orbit is elliptic and possibly includes a variety of perturbations.
This work was supported by Global Surveillance Research Center (GSRC) program funded by the Defense Acquisition Program Administration (DAPA) and Agency for Defense Development (ADD).
Clohessy WH , Wiltshire RS (1960) Terminal guidance system for satellite rendezvous J. Aerosp 27 653 - 658    DOI : 10.2514/8.8704
Katz JG , Saenz-Otero A , Miller DW 2011 Development and Demonstration of an Autonomous Collision Acoidance Algorithm aboard the ISS in Aerospace Conference 5-12 March
Lee S , Park SY (2011) Approximate Analytical Solution to Optimal Reconfiguration Problems in Perturbed Satellite Relative Motion JGCD 34 1,097 - 1,111    DOI : 10.2514/1.52283
Min H , Guoqiang Z , Junling S 2010 Optimal Collision Avoidance Maneuver for Formation Flying Satellites Using Relative Orbital Elements in Chinese control conference Beijing, China 29-31 July
Sauter L , Palmer P (2012) Analytic Model Predictive Controller for Collision-Free Relative Motion Reconfiguration JGCD 35 1069 - 1079    DOI : 10.2514/1.56521
Scharf DP , Acikmese AB , Ploen SR , Hagaegh FY 2006 A Direct Solution for Fuel-Optimal Reactive Collision Avoidance of Collaborating Spacecraft in American Control Conference 14-16 Jun
Sultan C , Seereram S , Mehra Rk (2006) Energy Suboptimal Collision-Free Reconfiguration for Spacecraft Formation Flying JGCD 29 190 - 192    DOI : 10.2514/1.10781
Sun ZW , Deng H , Zhong WC , Wu XD (2012) Attacking Satellite Path Planning Based on Genetic Algorithm J. Aerosp. Eng. 25 32 - 38    DOI : 10.1061/(ASCE)AS.1943-5525.0000110