This paper proposes a linear system control algorithm with collision avoidance in multiple satellites. Consideration of collision avoidance is augmented by adding a weighting term in the cost function of the original tracking problem in linear quadratic control (LQC). Because the proposed algorithm relies on a similar solution procedure to the original LQC, its inherent advantages,including gainrobustness and optimality, are preserved. To confirm and visualize the derived algorithm, a simple example of twovehicle motion in the twodimensional plane is illustrated. In addition, the proposed collision avoidance control is applied to satellite formation flying, and verified by numerical simulations.
1. Introduction
Linear quadratic control (LQC) is a wellknown control algorithm in the area of linear systems control. LQC originated from meansquare filtering, researched by Wiener in 1940s (Wiener, 1948). The LQC problem is based upon linear systems, and the cost function of the performance is constructed in the form of quadratic terms which track performance and control efforts. An objective in LQC entails cost minimizing, and the corresponding control input solution can be obtained by the wellknown Riccati equation.In the solution procedure, various methods can be used; the HamiltonJacobi optimization equation is used to derive the Riccati equation.
The obtained solution provides gainrobustness and global optimality performance (Dorato et al., 1995). Additionally,because of such advantages, the LQC algorithm has been applied to various areas such as groundvehicles, missions,aircraft, and spacecraft (Fravolini et al., 2003; Gribble, 1993;Lovren and Tomic, 1994; Plumlee and Bevly, 2004; Psiaki,2001; Ridgely et al., 1987).
The LQC solution was originally derived in a regulating problem, which is called the linear quadratic regulator(LQR). The regulating problem specifies that the desired state is zero, and the corresponding controller maintains the vehicle state at zero. To apply the LQC solution in a tracking problem, which has a nonzero desired trajectory, the disturbancerejection problem was considered by modifying system dynamics (Anderson and Moore, 1990; Dorato et al.,1995).
This study proposes a control algorithm that adds collision avoidance to the original LQC tracking problem. To achieve this goal, an additional term is inserted into the cost function to account for a collision avoidance effect. A detailed derivation of the proposed algorithm is introduced in Section 3. One of the important changes in the new approach is the offdiagonal term of the weight matrix on state. This term is not zero, which is a measure taken in order to implement the collision avoidance constraint. To prevent equalization of the position between vehicles, the cost function should consider the correlation and dependency between state variables. As a result, the weight matrix on states becomes a nondiagonal matrix, which is easy to implement by using commercial software tools such as MATLAB.
After performing the derivation of the optimal control history for a multiplevehicle case, the proposed algorithm is applied to a satellite formation flying (SFF) mission. SFF is a combined phrase consisting of the words satellite and formation flying. SFF has recently received much attention(Clohessy and Wiltshire, 1960; Hadaegh et al., 2000;McCambish et al., 2009; Speyer, 1979; Xing et al., 2000).As with other concerning satellite missions, all guidance,navigation, and control theories are necessary for SFF.Additionally, among guidance and control parts, the collision avoidance problem is an important issue because multiple satellites are operating.
Many researchers have studied the collision avoidance problem in SFF. Slater et al. (2006) referred to the collision probability function, and used an impulsive control to maintain a safe distance between spacecrafts. Wang and Schaub (2008) attempted to avoid collision using electrostatic (coulomb) forces with a Lyapunovbased control law. And, Lim et al. (2005) used potential functions to prevent collision. This paper proposes a collision avoidance algorithm by modifying the original LQC tracking problem.The conventional LQC provides desirable qualities such as gainrobustness and optimality; these properties can be preserved in the proposed algorithm because the proposed algorithm is based on the LQC problem. In addition, an optimal solution can be obtained by simple numerical integration only.
This paper is presented in the following manner. In Section 2, introductory material of LQR is presented. The main control algorithm and its derivation are introduced in Section 3. Finally, the algorithm’s application to SFF with numerical simulation is discussed in Section 4.
2. Linear Quadratic Control Algorithm
In this chapter, the LQC problem is briefly reviewed.Before proceeding, the general LQR algorithm including disturbance rejection will be introduced. In the next chapter,a collision avoidance measurement term is augmented to the linear control framework introduced here.
 2.1 Linear quadratic regulator
The LQC problem originated from a meansquare filtering algorithm by Wiener. The LQC algorithm manages a linear system, and its performance is measured in quadratic form.A linear system is a system in which the system equation is constructed by linear operators. Quadratic form indicates cost terms, like the tracking performance of states and control effort of an actuator, are represented by the quadratic errors.
where
V
is a performance measure, x and u are the state and control input of corresponding linear system x˙=
Ax
+
Bu
,
Q
and R are the weight matrix to performance. An optimal control input history
u
(τ) which minimizes the performance measure can be found using an optimality principle also referred to as the dynamic programming approach (Bellman,1952).
The above equation is the HamiltonJacobi optimization equation. Additionally,
l(x, u, t)
is a cost function which is integrated along time V=∫
_{t}
^{T}
l(x, u, t)
d
τ for obtaining the performance measure, and
f(x, u, t)
represents the differential state x˙. In addition,
V
*(
x, t
) is a minimum value of the performance measure obtained by the optimal input history.
V
*(
x, t
) may have various forms for different system equations
f(x)
and cost functions
l(x, u, t)
.
Firstly, we will consider a simple case, where
l(x, u, t)
=x
^{T}
Qx+
u
^{T}
Ru and
f(x, u, t)
=
Ax+Bu
. In this case, the optimal control input is solved as a state feedback control,
u*(t)
=
−Kx(t)
, and the minimum performance measure can be represented as
V*(x, t)
=
x^{T}
P(t)x. By substituting the derived forms into HamiltonJacobi optimization equation, the Riccati equation and the corresponding optimal control law are obtained.
 2.2 Disturbance rejection problem
Disturbance rejection problems are characterized by an additional disturbance term
w(t)
in a differential state equation, i.e.,
f(x, u, t)
=
Ax+Bu+w(t)
. Thus, the LQR solution previously introduced is a special solution to the disturbance rejection problem with
w(t)
=0. As previously noted, the minimum performance measure
V* (x, t)
takes a different form. Linearly statedependent terms and stateindependent terms are augmented, as
V
*=
x^{T}
P(t)x+2bT
(t)x+c(t)
. By substituting the new performance measure form into the HamiltonJacobi equation, one can obtain the following differential equations.
In addition, the disturbance rejection problem is similar to the tracking problem. The tracking problem requires a nonzero desired state,
x_{d}(t)
≠0. To formulate the tracking problem as a regulating problem, one can use an additional term ξ
(t)=x(t)x_{d}(t)
, which represents tracking errors. In addition, through the following procedure, the tracking problem can be reduced to a disturbancerejection regulating problem (Dorato et al., 1994).
3. Collision Avoidance Consideration
In multiple vehicles control, such as airplanes and spacecrafts, collision between each vehicle should be avoided. This avoidance guidance is known as ‘Collision Avoidance’, and associated research has been conducted for many years. In this chapter, an additional cost term will be added to the predefined cost function
l(x, u, t)
in order to consider collision avoidance. First, our analysis focuses solely on regulating problem, which is described as
x_{d}(t)
=0. Then, in the following subchapter, a general tracking problem is introduced, which is the
x_{d}(t)
≠0 case for linear optimal control.
 3.1 Regulating problem
The regulating problem, which is when
x_{d}(t)
=0, regulates a vehicle’s position to the zero state, generally represented by zero position and zero velocity. In a strict sense, the regulating problem has a paradox for the collision avoidance concept because a vehicle’s position travels toward the same position at the final time
x_{pos}(T)=0, x_{1}(T)=x_{2}(T)
, and collision eventually occurs. However, as a subwork for simple derivation of the case, we will first study the regulating problem.
To add the collision avoidance effect into multiple vehicle guidance, we will augment additional cost terms to the cost function,
where
l_{CA} (x, u, t)
is a modified cost function which considers the collision avoidance issue from the original cost function
l(x, u, t)
by adding the second terms on the R.H.S. in the above equation. The
(xixj)^{T}(xixj)
term indicates the square of distance between vehicles, and the term qCA, ij is used as a weighted term for collision avoidance.
For a simple case, the number of vehicles is assumed to be two, which means
N
=2; and, the vehicles are considered to be moving along a onedimensional axis. The necessary information can be summarized as four state variables, x
(t)
=[x
_{1}
x
_{2}
x˙
_{1}
x˙
_{2}
]T. Finally, we add collision avoidance terms to the cost function using Eq. (8),
where
A_{1}, A_{2}
and
A_{3}
are weight terms for each cost. A1 is a weight that regulates the performance of vehicle 1,
A_{2}
is a weight that regulates the performance of vehicle 2, and
A_{3}
is a weight term that considers the collision avoidance between the vehicles. Note that in the above equation we do not consider the weight terms of the velocities, such as
A_{x1}
x˙
_{1}
^{2}
. We also omit a cost for the control quantity uT Ru for simplicity. In addition, the above equation can be represented in matrix notation,
where
Q_{no}
is a weight matrix for regulating, which is an original weight matrix of LQR with no collision avoidance,
QCA
is a weight matrix for avoiding collision avoidance. We can see that offdiagonal entries of original weight matrix become nonzero after collision avoidance is considered. Finally, after this matrix formulation, the optimal input history
u*(t)
can be obtained by using the HamiltonJacobi optimization equation as given in Eqs. (3) and (4).
 3.2 Tracking problem
This subchapter investigates the tracking problem. As noted before, the tracking problem has a nonzero desired state
x_{d}(t)
≠0, which is different from the regulating problem in which
x_{d}(t)
=0. Because of this change, a simple Riccati equation cannot be used, and its optimal control solution has a similar form to the disturbance rejection problem given in Eqs. (5) and (6). The detailed derivation procedure of the optimal control history is explored.
Firstly, for simplicity, it is assumed again that there are two vehicles, and they move along a onedimensional axis. Four state variables represent the system status as before. However, the vehicles’ tracking errors from the desired trajectory ξ
(t)=x(t)x_{d}(t)
is adopted as state variables, rather than the vehicles’ positions and velocities directly. The tracking problem can then be converted into a regulating problem as given by Eq. (7). And, a new state representing the tracking error becomes ξ
(t)=[x_{1}x_{1d} x_{2}x_{2d} x˙_{1}x˙_{1d} x˙_{2}x˙_{2d}]^{T}
.
However, the vehicles’ tracking errors from the desired trajectory ξ(t)=x(t)xd(t) is adopted as state variables, rather than the vehicles’ positions and velocities directly. The tracking problem can then be converted into a regulating problem as given by Eq. (7). And, a new state representing the tracking error becomes ξ(t)=[x1x1d x2x2d x˙1x˙1d x˙2x˙2d]T .
Because state variables are different, the cost function
l(ξ, u, t)
should also be changed
where x
_{1d}
(t)
and x
_{2d}
(t)
are the desired trajectories of each vehicle.
In Eq. (11), it should be noted that the last term, which is used to prevent collision avoidance, has a quadratic form with a negative sign. This form is must be applied to the original LQC algorithm which is derived in a quadratic manner. In general collision avoidance research, rather than a quadratic term, an inverse of the distance term like (x
_{i}
−x
_{j}
)
^{−1}
or a potential function with an exponential term is used to prevent collision. In this manner, collision could be avoided regardless of the shape of the desired trajectory. However, an optimal property such as the minimizing control effort is hard to obtain when those terms are used. In addition, if optimal equations could be constructed, the equations are not easily solved. In this paper, the proposed algorithm does not guarantee collision avoidance for some cases in which different trajectories or systems are desired, and confirmation of the obtained control input could be needed. However, the proposed algorithm is based on the conventional LQC problem, so the proposed algorithm inherently preserves gainrobustness and optimality, and an optimal solution can be obtained by simple numerical integration.
We can see that Eq. (11) is similar to Eq. (9) which was derived in the regulating problem. But, different in state variables exist. The x
_{1}
, x
_{2}
terms in Eq. (9) are replaced by ξ
_{1}
=x
_{1}
−x
_{1d}
, ξ
_{2}
=x
_{2}
−x
_{2d}
in Eq. (11). Because of this change, the cost function with tracking problem, Eq. (11), cannot be formed with quadratic terms, ξ
^{T}
Q
ξ, while it was possible in Eqs. (9) and (10). Thus, additional terms are needed in the tracking problem to generalize the cost function.
where
r(t)
and
s(t)
terms are added. The unknown timeindependent matrix
Q
, timevarying terms
r(t)
, and
s(t)
can be obtained by expanding and comparing the first and the third lines of the above equations,
From Eq. (12) and Eq. (13), one can express the collision avoidance effect as a combination of a matrix and vector. Finally, the optimal input history is derived using the HamiltonJacobi optimization equation, Eq. (2). Because this problem manages the tracking problem, the following form for the performance measure is introduced, i.e.,
V
*(ξ,
t
)=ξ
T
P
(t)
+2
b^{T} (t)
ξ+
c(t)
. By substituting all of the terms into Eq. (2), the following equations are derived.
After expanding the above equations and collecting the quadratic terms, linear terms and stateindependent terms respectively, the results can be summarized as,
where
w(t)
comes from a desired trajectory produced by converting the tracking problem into the regulating problem,
w(t)=A_{xd}−x_{d}
. And, the corresponding optimal control
u*(t)
is equivalent to the original tracking problem solution.
Eq. (15) shows similar results to the original disturbance rejection solution, Eq. (5). A comparison of the two results is summarized in Table 1. One can see that there is an additional term −
r(t)
in the
b(t)
equation for the solution of collision avoidance considered cell. This term changes the b(t) history, consequently affecting the control history
u*(t)
.
 3.3 Multiple vehicle case
Until now, cases involving twovehicles have only been considered, rather than the multiplevehicle cases in which N≥3. However, we can generalize the results of the above subchapters into a multiple vehicle case without complex derivation.
Firstly, note that the solution for the performance measure coefficients
P(t), b(t)
, and
c(t)
in Eq. (15) are not changed, as the number of vehicles change. The weight matrix and coefficients of the cost function
l(ξ, u)
, which are
Q, r(t)
and
s(t)
in Eq. (13), are changed.
To visualize the tendency of the change in
Q, r(t), s(t)
, a threevehicle case solution is represented in Eq. (17). We can see that Eq. (13) and Eq. (17) exhibit similarities in the results.
Finally, a generalized form of the multiplevehicle case can be obtained, as shown in Eqs. (18) and (19).
where,
 3.4 Example: simple 2dimensional tracking problem
Before applying the derived control algorithm to real practical problems, such as SFF, a simple problem is analyzed to demonstrate the validity of the control law. In a twodimensional space, twovehicles are used, requiring no additional forces except control acceleration
u(t)
. Then, the system kinematics equations are formulated as given by Eq. (20).
where x=[x
_{1}
x
_{2}
y
_{1}
y
_{2}
x˙
_{2}
x˙
_{2}
y˙
_{1}
y˙
_{2}
]
^{T}
and
u=[u_{x1} u_{x2} u_{y1} u_{y2}]
. In the problem formulation, the cost function coefficients and initial conditions are defined in
Table 2
.
Figures 1

4
display the simulation results of this condition.
Fig. 1
shows a vehicle trajectory from its initial position to the final position. The solid line represents a trajectory with the original tracking algorithm, and the dashed line represents the trajectory with the derived algorithm, considering collision avoidance between the vehicles. To prevent collision between vehicles, vehicles do not follow a predetermined desired trajectory. In
Fig. 2
, one can confirm that the distance between vehicles becomes larger when collision avoidance is added. In addition,
Figs. 3
and
4
show corresponding tracking errors between the present position and the desired trajectory.
Simulation parameters
Vehicle trajectory.
Figure 5
shows the change of vehicle trajectory as the collision avoidance weighting parameter
A
_{3}
increases. As the weighting parameter
A
_{3}
increases, collision avoidance between vehicles becomes more important than the tracking of a desired trajectory. Thus, the distance between the
Tracking error in Xaxis.
Distance between vehicles.
Tracking error in Yaxis.
Vehicle trajectory along various collision avoidance weighting A_{3}
vehicles tends to become longer in the time history.
4. Satellite Formation Flying
In this chapter, the control law derived in the previous chapter is applied to a SSF problem. SSF has been investigated for many years, and the Clohessy and Wiltshire (CW) equation is generally employed as the linearized equation for relative dynamics. By using the CW equation, an application of collision avoidance algorithm is demonstrated, and the corresponding simulation results are presented.
 4.1 Relative equations of motion
SSF is commonly constructed by a chief satellite and a deputy satellite. The amount of deputy satellites present can be more than one, and the actual number is determined by mission characteristics. The coordinated frame (localverticallocalhorizontal [LVLH] frame) has an origin at the center of the chief satellite and the direction of each axis is drawn in
Fig. 6
. The
(x, y)
axis together make an inplane motion, and z axis represents an outofplane motion of the deputy satellite. Eq. (21) shows the general nonlinear relative equations of motion.
Localverticallocalhorizontal frame.
Simulation parameters
where
(x, y, z
) are the components of the relative position of the deputy satellite in the LVLH frame, θc is the true latitude angle of the chief satellite, and rc stands for the radius of the chief satellite.
Eq. (21) has nonlinear terms such as a square term. CW developed a linearized equation of Eq. (21) using assumptions such that the chief satellite travels in a circular orbit (Clohessy and Wiltshire, 1960).
Eq. (22) is the CW equation, also known as Hill’s equation. In Eq. (22), the term stands for the angular rate of the chief satellite. Using the linear equation of SSF, CW equation, one can apply the derived linear control algorithm that were presented in the previous chapter.
 4.2 Simulation results
The application of the linear optimal control algorithm derived in the previous chapter is explored in this subchapter. A twodimensional space,
(x, y)
plane, is employed for the simulation. Because inplane motion
(x, y)
is decoupled from the outofplane motion z axis, the inplane motion only case is selected. Three satellites are assumed for the simulation, with final positions producing a circular formation around a chief satellite.
Satellite trajectory without collision avoidance.
Satellite trajectory with collision avoidance.
Distance between satellites.
Control acceleration of satellite No.1.
Details for the cost function coefficients and the initial condition of each satellite are presented in
Table 3
.
Figures 7

10
represent resultant plotting of the SSF control simulation.
Figure 7
presents satellite trajectories from initial positions to final mission destinations. No weighting term was added for the collision avoidance in the
Fig. 7
simulation, but
Fig. 8
considers collision avoidance for trajectory generation. In
Fig. 8
, satellites enter the final circular formation by detouring nondirect guidance as
Fig. 7
, to prevent collision between satellites.
Figures 9
and
10
present the corresponding distance between satellites as well as the acceleration input.
Figure 9
shows the distance between each satellite, which is
d
_{12}
,
d
_{23}
,
d
_{13}
. One can see that the distances became longer than the original tracking history case. Finally,
Fig. 10
displays the control acceleration input history in each axis for the first satellite.
Conclusions
In this paper, a linear control algorithm was derived for the tracking problem by solving the HamiltonJacobi optimization equation. To avoid collision between vehicles, an additional weighting term was introduced when constructing the cost function. The corresponding optimal control solution maintained a similar form as the original LQR tracking problem, which does not consider collision avoidance. The only difference was that extra terms were added in the differential equations of the performance measure coefficients. After deriving the control history solution, a simple example involving two vehicles was considered. In addition, the application of the control algorithm to SSF mission was analyzed, and numerical simulation was presented. Using this proposed algorithm, SSF problems as well as other problems involving multiplevehicles could consider collision avoidance in the tracking problems.
Acknowledgements
This research was supported by the NSL (National Space Lab) program through the Korea Science and Engineering Foundation funded by the Ministry of Education, Science and Technology (S1080100012308A010012310).
Anderson B. D. O
,
Moore J. B
1990
Optimal Control: Linear Quadratic Methods
Prentice Hall
Englewood Cliffs
Bellman R. E
1952
On the theory of dynamics programming.
Proceeding of the National Academy of Sciences
California
716 
719
Clohessy W. H
,
Wiltshire R. S
1960
Terminal guidance system for satellite rendezvous
Journal of the Aerospace Science
27
653 
658
Dorato P
,
Abdallah C. T
,
Cerone V
1995
LinearQuadratic Control: an Introduction.
Prentice Hall
Englewood Cliffs
Fravolini M. L
,
Ficola A
,
Napolitano M. R
,
Campa G
,
Perhinschi M. G
2003
Development of modeling and control tools for aerial refueling for UAVs
AIAA Guidance Navigation and Control Conference and Exhibit
Austin TX
AIAA2003 
5798
Gribble J. J
1993
Linear quadratic Gaussian/loop transfer recovery design for a helicopter in lowspeed flight
Journal of Guidance Control and Dynamics
16
754 
761
Hadaegh F. Y
,
Ghavimi A. R
,
Singh G
,
Quadrelli M
2000
A centralized optimal controller for formation flying spacecraft
International Conference of Intelligence and Technology
Lim H
,
Bang H
,
Kim H
2005
Sliding mode control for the configuration of satellite formation flying using potential functions
International Journal of Aeronautical and Space Sciences
6
56 
63
Lovren N
,
Tomic M
1994
Analytic solution of the Riccati equation for the homing missile linearquadratic control problem.
Journal of Guidance Control and Dynamics
17
619 
621
McCambish S. B
,
Romano M
,
Nolet S
,
Edwards C. M
,
Miller D. W
2009
Flight testing of multiplespacecraft control on SPHERES during closeproximity operations
Journal of Guidance Control and Dynamics
46
1202 
1213
Plumlee J. H
,
Bevly D. M
2004
Control of a ground vehicle using quadratic programming based control allocation techniques
Proceeding of the American Control Conference
Boston MA
4704 
4709
Psiaki M. L
2001
Magnetic torquer attitude control via asymptotic periodic linear quadratic regulation
Journal of Guidance Control and Dynamics
24
386 
394
Ridgely D. B
,
Banda S. S
,
McQuade T. E
,
Lynch P. J
1987
LinearquadraticGaussian with looptransfer recovery methodology for an unmanned aircraft
Journal of Guidance Control and Dynamics
10
82 
89
Slater G. L
,
Byram S. M
,
Williams T. W
2006
Collision avoidance for satellites in formation flight.
Journal of Guidance Control and Dynamics
29
1140 
1146
Speyer J. L
1979
Computation and transmission requirements for a decentralized linearquadraticGaussian control problem
IEEE Transactions and Automatic Control
24
262 
269
Xing G. Q
,
Parvez S. A
,
Folta D
2000
Design and implementation of synchronized autonomous orbit and attitude control for multiple spacecraft formation using GPS measurement feedback
Advances in the Astronautical Sciences
1051
115 
134
Wang S
,
Schaub H
2008
Spacecraft collision avoidance using coulomb forces with separation distance and rate feedback
Journal of Guidance Control and Dynamics
31
740 
750
Wiener N
1948
Cybernetics
John Wiley
New York