Algebraic Approach to the Minimum-Cost Multi-Impulse Orbit-Transfer Problem

AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM M. AVENDA˜ NO Centro Universitario de la Defensa, Zaragoza, Spain V. MART´ IN-MOLINA Universidad de Sevilla, Sevilla, Spain J. MART´ IN-MORALES Centro Universitario de la Defensa, Zaragoza, Spain J. ORTIGAS-GALINDO Instituto de Educaci´on Secundaria ´ Elaios, Zaragoza, Spain Abstract. We present a purely algebraic formulation (i.e. polynomial equations only) of the minimumcost multi-impulse orbit transfer problem without time constraints, while keeping all the variables with a precise physical meaning. We apply general algebraic techniques to solve these equations (resultants, Gr¨obner bases, etc.) in several situations of practical interest of different degrees of generality. For instance, we provide a proof of the optimality of the Hohmann transfer for the minimum-fuel 2-impulse circular-to-circular orbit transfer problem. Finally, we also provide a general formula for the optimal 2-impulse in-plane transfer between two rotated elliptical orbits under a mild symmetry assumption on the two points where the impulses are applied (which we conjecture that can be removed). 1. Introduction Since the start of the space age with the first launch of a satellite to space (Sputnik in 1957), the interest in the study of space maneuvers that use the available resources like time and fuel efficiently has been growing steadily. In many real life cases, a satellite can serve multiple purposes, requiring for that a change of its orbit. Some maneuvering is also needed during the initial launch of a satellite, or when a spare satellite has to be brought to its intended orbit. Maneuvering a satellite can be done in two different ways: continuous thrust or a sequence of instantaneous and discrete impulses. This paper focuses on the latter. In theory, the solution using multiple discrete impulses should converge to the optimal continuous thrust maneuver, so our method could be applied to the continuous problem as well. However, the limitations imposed by the current hardware and software render this approach impractical. In this paper we have developed the theory allowing any finite number of impulses, but we have only solved for bi-impulse maneuvers. The orbit transfer problem with a fixed time of flight was studied by Lambert, who provided a solution in the case of two impulses. For a discussion of this problem, see [15]. However, the scarcest resource in space is fuel, since it represents a load on the spacecraft that cannot be too large to avoid launching problems and to uce costs. For this reason, we focus our attention on the minimum fuel transfer problem with unconstrained time. Using the well-known Tsiolkovsky rocket equation, we consider the sum of the individual impulses (difference between velocities before and after the thrust is applied) as the cost function. This usually appears in the literature as ∆v. The method we propose to obtain the minimum fuel transfer orbit with a fixed number of impulses uces the problem into a square system of algebraic equations in several unknowns. The resolution is 1 2 AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM done in two stages. In the first one, the equations are written symbolically in their most general form, i.e. leaving the data as unknown parameters. Then the system is solved using some computer algebra algorithm (Gr¨obner basis, resultants, elimination theory, etc.) and, as a result, the unknowns are written in terms of the data (usually as rational functions). Of course, this stage is the most time consuming but has to be solved only once for each type of orbit transfer problem. Any degenerate case that needs special treatment is detected at this stage. In the second stage, any particular instance of the problem is solved by substituting the real data into the general solution obtained in the first stage. In order to do this, some preprocessing might be needed. These computations are very fast, since they only consist in replacing values into simple formulas. Compa to other existing methods, ours is faster when a massively large number of instances have to be solved (to compensate for the time consumed in the first phase), or when a complete analytic understanding of the solution is needed (which numerical methods fail to provide). In terms of accuracy and range of input conditions, we can say that our method is exact, but we have not made any attempt to study its stability. In the case of a transfer between two circular coplanar orbits, Hohmann gave an explicit solution with two impulses in [8], which was later proven optimal analytically by Barrar [3]. For the case with three impulses, Hoelker and Silber [9] have shown that a bi-elliptical transfer has a lower fuel requirement than the Hohmann transfer for some special initial and final orbits. Roth [11] extended the notion of bi-elliptical transfer to the case of two inclined orbits. In this paper, we provide a detailed study of transfers between two circular orbits, including out-ofplane maneuvers and also the possibility that the initial and final angular momentum point in opposite directions. In all cases, we have proven algebraically that the Hohmann transfer is optimal for two impulses. Another problem of interest is transferring a satellite between petermined points in the initial and final orbits. This situation was studied by Avenda˜no and Mortari in [1], where they provided a closed-form solution. Here, we reobtain this solution algebraically, applying a much more efficient method. Previous attempts to solve this problem involved the use of iterative methods or an equation that needs to be solved numerically (see [2, 7, 10, 13, 14]). The last problem we study is the optimal transfer between two identical ellipses that are coplanar and rotated a fixed angle. This case was studied numerically by Bender in [4]. However, we provide an algebraic solution, which is fully explicit under a mild symmetry assumption. This paper is organized as follows. In Section 2, we present an algebraic approach to the multi-impulse minimum-cost orbit transfer problem. We have put special emphasis in explaining the physical meaning of all the variables involved. Three kinds of problems are studied: point to point, point to orbit and orbit to orbit. We also consider two possible cost functions. In Section 3, we present our solution to the general point-to-point problem with two impulses and cost function as in [1]. In Section 4, we provide a solution to a generalized version of the Hohmann transfer where out-of-plane maneuvers are allowed. The orbit-to-orbit problem between identical and coplanar orbits is studied in Section 5. The solution we obtain requires solving a large system of polynomial equations, which can be solved explicitly if we assume a symmetry condition. We have done extensive numerical tests showing that the symmetry condition is always satisfied in them. Finally, we have compiled in the Appendix all the equations of Celestial Mechanics that we will need in the paper. Although the three examples discussed in the paper seem simple and artificial, it should be noted that our solution of each of these problems is symbolic (except for a subcase of the last example), hence providing an exact solution for any instance of them almost instantly. Moreover, the example of the two rotated orbits is of remarkable importance given the number of times that this maneuver has to be done in real life situations, specially due to the precession of the perigee effect induced by the J2perturbation. 2. Multi-impulse orbit transfers In order to work with polynomial equations, we need to remove the divisions, the square roots and the constant µfrom some of the equations that describe the Keplerian motion, so we introduce the vectors ˆ r=r |r|,w=˙ r √µ,l=√µh |h|2,s=l×e. Note that land sare orthogonal, i.e. (1) l·s= 0, AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM 3 and that the angular momentum and eccentricity vectors can be simply recove as h=√µl |l|2,e=s×l |l|2. To avoid the extra complexity needed to handle parabolic and hyperbolic motions, as well as the degenerate case p= 0, we restrict our analysis to elliptic orbits, e < 1, and non-degenerate trajectories, h=0. Of course, the case l=0has to be excluded, and the condition e < 1 translates into |s|<|l|. Any unit vector ˆ rorthogonal to l, i.e. (2) ˆ r·ˆ r= 1,ˆ r·l= 0, determines a point on the orbit. The exact location can be obtained from Eq.(35), (3) 1 |r|=|l|2+ (s×l)·ˆ r, and the velocity of the particle at that point is, according to Eq.(36), (4) w=s+l׈ r. Finally, note that in the case of elliptic orbits (|s|<|l|), the right-hand side of Eq.(3) is always positive, so no extra inequalities are needed to guarantee a valid value of |r|−1. Figure 1. Ellipse with focus Fand a satellite Son it. An n-impulse orbit transfer is represented algebraically by the vectors l0,l1,...,ln,s0,s1,...,sn,ˆ r0,ˆ r1,...,ˆ rn−1 where the pair (li,si) determines the i-th orbit and ˆ ricorresponds to the point where the impulse is applied to change from the i-th to the (i+ 1)-th orbit. These vectors, according to Eqs.(1),(2) and (3), are constrained by li·si= 0,(5) li= 0,(6) |si|<|li|,(7) for i= 0, . . . , n, and li·ˆ ri= 0,(8) li+1 ·ˆ ri= 0,(9) |ˆ ri|2= 1,(10) |li|2+ (si×li)·ˆ ri,=|li+1|2+ (si+1 ×li+1)·ˆ ri,(11) for all i= 0, . . . , n −1. Conversely, any sequence of vectors satisfying all these restrictions represents a valid n-impulse transfer. Moreover, all the equations are invariant under rotation by a fixed angle and rescaling of the liand si. The following table shows the number of unknowns and algebraic equations that define the configuration space for each type of n-impulse transfer (n≥2). 4 AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM 3d-transfer 2d-transfer #unknowns #equations #unknowns #equations Point to Point 9n−12 5n−5 5n−7 2n−2 Point to Orbit 9n−9 5n−3 5n−5 2n−1 Orbit to Orbit 9n−6 5n−1 5n−3 2n In the orbit to orbit problem, the vectors l0,s0,ln,snare given and the remaining variables are conside unknowns. In the point to orbit, the initial point is given, so ˆ r0is also known, thus ucing the number of unknowns (and equations). Finally, in the point to point problem, the final point is also given, i.e. ˆ rn−1 is known. The two-dimensional version of these problems considers all orbits in the z= 0 plane, so li= (0,0, liz), si= (six, siy,0) and ˆ ri= (xi, yi,0), hence the uced number of variables and equations needed to handle them. The velocities wiand w∗ iare the velocities at the point ˆ riimmediately before and after the impulse is applied, respectively. It follows from Eq.(4) that wi=si+li׈ ri,(12) w∗ i=si+1 +li+1 ׈ ri.(13) The cost (fuel-wise) of such a transfer is proportional to the sum of ∆i=|wi−w∗ i|, denoted hereafter by f1. To avoid the square roots that are implicitly present in ∆i, we also consider a cost function f2 which is the sum of the squares of the ∆i: f1= n−1 X i=0 |wi−w∗ i|, f2= n−1 X i=0 |wi−w∗ i|2. If the vectors liand siare rescaled by a factor c, then f1and f2are multiplied by a factor |c|and |c|2, respectively. When the cost function f1is used, the trick to avoid the square roots consists of considering ∆ias a variable, efining the cost function as f1= n−1 X i=0 ∆i and adding the algebraic equations ∆2 i=|si−si+1|2+|li−li+1|2+ 2((si−si+1)×(li−li+1)) ·ˆ ri, for i= 0, . . . , n −1. The last equations can be obtained by substituting Eqs.(12) and (13) into the definition of ∆i: ∆2 i=|wi−w∗ i|2=|si+li׈ ri−si+1 −li+1 ׈ ri|2 =|si−si+1|2+|li−li+1|2+ 2((si−si+1)×(li−li+1)) ·ˆ ri. At this point we have a classical problem of constrained minimization, which we approach with Lagrange multipliers. Theorem 1 (Lagrange multipliers).Let q, q1, . . . , qm:Rk→Rin C∞and p∈Rka common zero of q1, . . . , qmbe such that the vectors ∇q1(p),...,∇qm(p)are linearly independent. Then pis a local extremum of qon the manifold defined by {q1=··· =qm= 0}if and only if there exists λ1, . . . , λm∈R such that ∇q(p) = λ1∇q1(p) + ···+λm∇qm(p). In our case, we have an algebraic variety V={q1=. . . =qm= 0} ⊆ Rk, defined by polynomials q1, . . . , qm∈R[x1, . . . , xk], and another polynomial function qthat we want to minimize on V. In order to apply Theorem 1, we need to exclude first the points where ∇q1(p),...,∇qm(p) are not linearly independent, which is, by definition, the set of singular points V∗of V. Computationally, V∗is the set of points of Vwhere all m×mminors of the matrix [∂qi/∂xj]1≤i≤m,1≤j≤khave zero determinant: V∗=p∈Rk:q1=··· =qm= 0 ∧ ∂(q1, . . . , qm) ∂(xj1, . . . , xjm) = 0,∀J={j1, . . . , jm}⊆{1, . . . , k}. These points have to be conside critical points (i.e. they are potential local extrema) and have to be evaluated separately. On the remaining points, V\V∗, the local extrema can be found directly by Theorem 1, solving the system of m+kequations q1=··· =qm= 0 and ∇q=λ1∇q1+···+λm∇qmin the m+kunknowns x1, . . . , xk, λ1, . . . , λm∈R, and disregarding the solutions with (x1, . . . , xk)∈V∗. Removing these AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM 5 solutions is actually not needed since they are always critical points. The set of solutions of the m+k equations described above and the set of all critical points of qare denoted Vqand Vcrit q, respectively: (14) Vq=(x1, . . . , xk, λ1, . . . , λm)∈Rm+k:q1=··· =qm= 0 ∧ ∇q=λ1∇q1+···+λm∇qm, Vcrit q=V∗∪πk(Vq)⊆Rk, where πk:Rm+k→Rkis the projection onto the first kcoordinates. Including the Lagrange multipliers, and the extra variables ∆ifor i= 0, . . . , n −1 when minimizing f1 instead of f2, we get the following total number of unknowns (which is equal to the number of equations): min(f1) min(f2) 3d-transfer 2d-transfer 3d-transfer 2d-transfer Point to Point 16n−17 9n−9 14n−17 7n−9 Point to Orbit 16n−12 9n−6 14n−12 7n−6 Orbit to Orbit 16n−7 9n−3 14n−7 7n−3 By using standard linear algebra, it is possible to eliminate all the Lagrange multipliers: (15) Vcrit q=V∗∪   q1=··· =qm= 0  ∂(q, q1, . . . , qm) ∂(xj1, . . . , xjm+1 ) = 0,∀J={j1, . . . , jm+1}⊆{1, . . . , k}   . The expression above shows that Vcrit qcan be written as the union of two algebraic varieties in Rk. 3. Minimum ∆v2Lambert problem In this problem, the vectors r0,r1,w0,w∗ 1are known, from which the vectors l0,l2,s0,s2can be computed directly. The unknowns are l1and s1, from which we can deduce w∗ 0and w1. There are two cases, depending on whether r0and r1are linearly independent or not. In the first case, we can assume without loss of generality that r0and r1both lie on the xy-plane, so the unknowns can be written l1= (0,0, l1z) and s1= (s1x, s1y,0). We can further assume that ˆ r0= (1,0,0) and ˆ r1= (x1, y1,0) with y1= 0 and x2 1+y2 1= 1. We will solve this problem in two stages: symbolical and numerical, as explained in the introduction. For the first one, we define k0=|r0|−1and k1=|r1|−1, we obtain the following two restrictions: q1:= l2 1z+l1zs1y−k0= 0,(16) q2:= l2 1z+l1z(x1s1y−y1s1x)−k1= 0.(17) From Eq.(4), the velocities w∗ 0and w1are w∗ 0=s1+l1׈ r0= (s1x, s1y+l1z,0),(18) w1=s1+l1׈ r1= (s1x−l1zy1, s1y+l1zx1,0),(19) and the impulses ∆0and ∆1are given by ∆0=|w∗ 0−w0|=|(s1x−w0x, s1y+l1z−w0y,−w0z)|,(20) ∆1=|w∗ 1−w1|=|(w∗ 1x−s1x+l1zy1, w∗ 1y−s1y−l1zx1, w∗ 1z)|,(21) so the cost function q=f2= ∆2 0+ ∆2 1is q:= (s1x−w0x)2+ (s1y+l1z−w0y)2+ (w0z)2+ (w∗ 1x−s1x+l1zy1)2+ (w∗ 1y−s1y−l1zx1)2+ (w∗ 1z)2. We compute the critical points of qusing Eq.(15). In this case, V∗=∅because  ∂(q1, q2) ∂(s1x, s1y) =l2 1zy1= 0 is impossible since l1z= 0 and y1= 0. Therefore, Eq.(15) uces to (22) Vcrit q=q1=q2= ∂(q, q1, q2) ∂(s1x, s1y, l1z) = 0. We will solve Eqs.(22) using the technique explained in [5, Ch.2]. In order to do that, we computed the Gr¨obner basis of Vcrit qin the polynomial ring K[s1x, s1y, l1z] over the field of fractions K= 6 AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM Frac Q[k0, k1, x1, y1,w0,w∗ 1]/⟨x2 1+y2 1−1⟩with respect to the lexicographic monomial order s1x> s1y> l1zusing the program Singular [6]. We obtained I=⟨p1, p2, p3⟩, where p1=k0y1·s1x−(k0x1−k1)·s1y−(k0−k1)·l1z p2= (2(k2 0−k2 1)2+ 8k2 0k2 1y2 1)·s1y + (4k3 0x1+ 2k3 0y2 1−4k3 0+ 4k2 0k1x1y2 1−8k2 0k1x1−8k2 0k1y2 1+ 8k2 0k1 + 4k0k2 1x1+ 2k0k2 1y2 1−4k0k2 1)·l3 1z + (k3 0x1y2 1w∗ 1y−k3 0x1y1w0x−k3 0x1y1w∗ 1x−k3 0y3 1w∗ 1x−k3 0y2 1w∗ 1y+k3 0y1w0x +k3 0y1w∗ 1x−2k2 0k1x1y3 1w∗ 1x−2k2 0k1x1y2 1w∗ 1y+ 2k2 0k1x1y1w0x+ 2k2 0k1x1y1w∗ 1x −2k2 0k1y4 1w∗ 1y+ 2k2 0k1y3 1w0x+ 2k2 0k1y3 1w∗ 1x+ 2k2 0k1y2 1w∗ 1y−2k2 0k1y1w0x −2k2 0k1y1w∗ 1x+k0k2 1x1y2 1w∗ 1y−k0k2 1x1y1w0x−k0k2 1x1y1w∗ 1x−k0k2 1y3 1w∗ 1x −k0k2 1y2 1w∗ 1y+k0k2 1y1w0x+k0k2 1y1w∗ 1x)·l2 1z + (2k4 0+ 8k2 0k2 1y2 1−4k2 0k2 1+ 2k4 1)·l1z −(k4 0x1y1w0x+k4 0x1y1w∗ 1x+k4 0y2 1w0y+k4 0y2 1w∗ 1y+ 2k3 0k1x1y2 1w0y+ 2k3 0k1x1y2 1w∗ 1y −2k3 0k1y3 1w0x−2k3 0k1y3 1w∗ 1x+k3 0k1y1w0x+k3 0k1y1w∗ 1x−k2 0k2 1x1y1w0x −k2 0k2 1x1y1w∗ 1x+k2 0k2 1y2 1w0y+k2 0k2 1y2 1w∗ 1y−k0k3 1y1w0x−k0k3 1y1w∗ 1x) p3= 2y4 1·l4 1z+ (x1y4 1w∗ 1y−x1y3 1w0x+x1y3 1w∗ 1x−y5 1w∗ 1x+y4 1w∗ 1y−y3 1w0x+y3 1w∗ 1x)·l3 1z −(k0x1y3 1w0x+k0x1y3 1w∗ 1x−2k0x1y2 1w0y−2k0x1y2 1w∗ 1y−2k0x1y1w0x −2k0x1y1w∗ 1x+k0y4 1w0y+k0y4 1w∗ 1y+ 2k0y3 1w0x+ 2k0y3 1w∗ 1x−2k0y2 1w0y −2k0y2 1w∗ 1y−2k0y1w0x−2k0y1w∗ 1x+ 2k1x1y1w0x+ 2k1x1y1w∗ 1x−k1y3 1w0x −k1y3 1w∗ 1x+ 2k1y1w0x+ 2k1y1w∗ 1x)·l1z −(4k2 0x1−2k2 0y2 1+ 4k2 0+ 4k0k1x1y2 1−8k0k1x1+ 8k0k1y2 1−8k0k1+ 4k2 1x1−2k2 1y2 1+ 4k2 1) The system of equations p1=p2=p3= 0 represent the symbolic solution to the problem. For the second stage of our approach to solving the problem, we will do the following: (1) Compute k0, k1, x1, y1,w0,w∗ 1from the real data provided. Some rotation might be needed to align the vector r0with the x-axis and vector r1with the xy-plane. (2) Solve equation p3for l1z. (3) Substitute l1zin p2and obtain s1y. (4) Substitute l1zand s1yin p1and solve for s1x. (5) Rotate back the vectors l1= (0,0, l1z) and s1= (s1x, s1y,0) to get the optimal transfer orbit. Steps 2–4 can be done since the leading coefficients in equations p1,p2and p3are not zero. Now we deal with the case when the vectors r0and r1are linearly dependent. We can uce to either ˆ r0=ˆ r1= (1,0,0) or ˆ r0=−ˆ r1= (1,0,0). There is no need to use all the machinery that we developed so far to handle these two degenerate cases. The following discussion shows how to solve both situations with simple geometric arguments. In the former case, i.e. ˆ r0=ˆ r1= (1,0,0), we must have k0=k1and w∗ 0=w1by Eqs.(16)–(19). The cost function f2can be expressed entirely in terms of the independent variables w∗ 0x,w∗ 0y,w∗ 0z, as follows: f2= (w0x−w∗ 0x)2+ (w0y−w∗ 0y)2+ (w0z−w∗ 0z)2+ (w∗ 1x−w∗ 0x)2+ (w∗ 1y−w∗ 0y)2+ (w∗ 1z−w∗ 0z)2. The critical points can be found by setting the partial derivatives of f2with respect to w∗ 0x,w∗ 0y,w∗ 0zto zero and solving the resulting system of equations. Doing so, only one solution appears: w∗ 0x=w1x=w0x+w∗ 1x 2, w∗ 0y=w1y=w0y+w∗ 1y 2, w∗ 0z=w1z=w0z+w∗ 1z 2. In the other case, i.e. ˆ r0=−ˆ r1= (1,0,0), the values of k0and k1are not necessarily equal, hence r0= (k−1 0,0,0) and r1= (−k−1 1,0,0), but w1can be expressed in terms of w∗ 0. Indeed, the conservation laws for the angular momentum hand eccentricity vector ein the intermediate orbit imply that r0×w∗ 0= r1×w1and w∗ 0×(r0×w∗ 0)−ˆ r0=w1×(r1×w1)−ˆ r1, respectively, from which it follows that: w1x=w∗ 0x, w1y=−k1 k0 w∗ 0y, w1z=−k1 k0 w∗ 0z. AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM 7 The cost function f2can be written in terms of the independent variables w∗ 0x,w∗ 0y,w∗ 0z, as follows: f2= (w0x−w∗ 0x)2+ (w0y−w∗ 0y)2+ (w0z−w∗ 0z)2+ (w∗ 1x−w∗ 0x)2+w∗ 1y+k1 k0 w∗ 0y2 +w∗ 1z+k1 k0 w∗ 0z2 . Taking partial derivatives and solving the resulting system of equations, we get the unique solution: w∗ 0x=w0x+w∗ 1x 2, w∗ 0y=k0 k0w0y−k1w∗ 1y k2 0+k2 1 , w∗ 0z=k0 k0w0z−k1w∗ 1z k2 0+k2 1 . 4. Optimality of the Hohmann transfer In this problem, we want to find the optimal 2-impulse transfer between concentric and coplanar circular orbits. Assuming that the plane that contains both initial and final orbits is orthogonal to (0,0,1) and that the initial point is on the x-axis, we can uce to the following situation: l0= (0,0, l0z),l2= (0,0, l2z),s0=s2= (0,0,0),ˆ r0= (1,0,0), where l0zand l2zare not zero. The nine unknowns are the components of the vectors l1= (l1x, l1y, l1z), s1= (s1x, s1y, s1z) and ˆ r1= (x1, y1, z1). The seven equations relating them are:                          l1xs1x+l1ys1y+l1zs1z= 0 l1x= 0 l1xx1+l1yy1+l1zz1= 0 l2zz1= 0 x2 1+y2 1+z2 1= 1 l2 0z=l2 1x+l2 1y+l2 1z+s1yl1z−s1zl1y l2 2z=l2 1x+l2 1y+l2 1z+x1(s1yl1z−s1zl1y) + y1(s1zl1x−s1xl1z) + z1(s1xl1y−s1yl1x) Since l2z= 0, we have that z1= 0. Substituting l1x= 0 and z1= 0 in the third equation, we get l1yy1= 0. We will discuss two cases: l1y= 0 and l1y= 0 (which means that y1= 0). Case l1y= 0. Here we can uce to l1= (0,0, l1z), s1= (s1x, s1y,0) and ˆ r1= (x1, y1,0), subject to the following conditions:      x2 1+y2 1= 1 l2 0z=l2 1z+s1yl1z l2 2z=l2 1z+x1s1yl1z−y1s1xl1z Since we want to minimize the function f1, we need to introduce the two extra variables ∆0and ∆1, which represent the magnitude of each impulse, and the following two restrictions: (∆2 0=s2 1x+ (s1y+l1z−l0z)2 ∆2 1= (s1x−l1zy1+l2zy1)2+ (s1y+l1zx1−l2zx1)2 Using Lagrange multipliers as in Eq.(14), we computed the uced Gr¨obner basis in the polynomial ring Q(l0z, l2z)[λ1, . . . , λ5,∆0,∆1, s1x, s1y, l1z, x1, y1] with respect to the lexicographic monomial order λ1> ··· > λ5>∆1>∆0> s1x> s1y> l1z> x1> y1, obtaining the following two solutions: x1=−1, y1= 0, l1z=±rl2 0z+l2 2z 2, s1x= 0, s1y=l2 0z−l2 2z l2 0z+l2 2z l1z. The cost function f1= ∆0+ ∆1at each of those solutions becomes: (23) f1= ±√2l2 0z pl2 0z+l2 2z−l0z + ±√2l2 2z pl2 0z+l2 2z−l2z . A simple computation shows that the sign of the optimum l1z(and also the sign of the numerators in the previous expression) coincides with the sign of l0z+l2z. This case corresponds to the classical Hohmann solution. Case l1y= 0. Since l1yy1= 0 and x2 1+y2 1= 1, this case is only possible when y1= 0 and x1=±1. When x1= 1, we have l2 0z=l2 2z, so the the orbits are of the same radius. If l0z=l2z, the initial and final orbits are exactly the same and no maneuver is needed. On the other hand, if l0z=−l2z, the 8 AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM satellite must change the direction of rotation in two impulses, both at the same point, so ˆ r0=ˆ r1and w∗ 0=w1. There are clearly infinitely many optimal solutions with f1= ∆1+ ∆2= 2|w0|. It only remains the case x1=−1. Here the unknowns are l1= (0, l1y, l1z) and s1= (s1x, s1y, s1z), subject to the equations      l1ys1y+l1zs1z= 0 l2 0z=l2 1y+l2 1z+s1yl1z−s1zl1y l2 2z=l2 1y+l2 1z−s1yl1z+s1zl1y. The impulses are (∆2 0=s2 1x+ (s1y+l1z−l0z)2+ (s1z−l1y)2 ∆2 1=s2 1x+ (s1y−l1z+l2z)2+ (s1z+l1y)2 and the cost function is f1= ∆0+ ∆1. We computed the Gr¨obner basis of Eq.(14) in the ring Q(l0z, l2z)[λ1, . . . , λ5,∆0,∆1, s1x, s1y, s1z, l1y, l1z] with respect to the lexicographic monomial order λ1> ··· > λ5>∆1>∆1> s1x> s1y> s1z> l1y> l1z, obtaining the following two optimal solutions: l1z=l5 0z+l4 0zl2z+ 4l3 0zl2 2z+ 4l2 0zl3 2z+l0zl4 2z+l5 2z 4l0zl2z(l2 0z+l0zl2z+l2 2z) l1y=±rl2 0z+l2 2z 2−l2 1z s1z=−l2 0z−l2 2z l2 0z+l2 2z l1y s1y=l2 0z−l2 2z l2 0z+l2 2z l1z s1x= 0 These solutions are defined only when a1<l2z l0z< a2, where a1and a2are the real roots of a4+ 2a3+ 2a+ 1 = 0. In particular, the sign of l2z l0zmust be negative. Substituting these solutions in the cost function f1and comparing with Eq.(23), it can be checked that the solution of the previous case is always better. 5. Two rotated ellipses In this orbit-to-orbit transfer problem, we will assume that the initial and final orbits are two identical ellipses rotated an angle α∈(0, π] lying on the same plane. We will restrict our optimization to intermediate orbits that also lie within the same plane, i.e. to a two-dimensional orbit transfer problem. Without loss of generality, we can assume that l0= (0,0, l0z), l2= (0,0, l2z), s0= (s0x, s0y,0), s2= (s2x, s2y,0) are given, and that we have to find ˆ r0= (x0, y0,0), ˆ r1= (x1, y1,0), l1= (0,0, l1z) and s1= (s1x, s1y,0). In order to guarantee that the initial and final orbits have the same eccentricity and semi-major axis, and to maximize the symmetry of the equations, we impose l2z=l0z= 1 (since the problem does not depend on the semi-major axis), s2x=−s0xand s2y=s0y. This ensures that the orbits are identical, but rotated an angle α= 2 arctan(s0x/s0y). Both orbits are also symmetric with respect to the x-axis. Finally, we need two extra variables ∆0and ∆1to represent the two impulses. For general ellipses, with arbitrary semi-latus rectum p, all the values l1,s1,w∗ 0,w1, ∆0and ∆1 calculated in this section have to be divided by √p. The discussion above uces the problem to two parameters s0x,s0y, nine unknowns x0,y0,x1,y1,s1x, s1y,l1z, ∆0, ∆1, six equations                        eq1:=x2 0+y2 0= 1 eq2:=x2 1+y2 1= 1 eq3:=l2 1z+l1z(x0s1y−y0s1x)−1−x0s0y+y0s0x= 0 eq4:=l2 1z+l1z(x1s1y−y1s1x)−1−x1s0y−y1s0x= 0 eq5:=∆2 0= (s0x−s1x)2+ (s0y−s1y)2+ (1 −l1z)2+ 2(1 −l1z)(x0(s0y−s1y)−y0(s0x−s1x)) eq6:=∆2 1= (s0x+s1x)2+ (s0y−s1y)2+ (1 −l1z)2+ 2(1 −l1z)(x1(s0y−s1y) + y1(s0x+s1x)) and a cost function f1= ∆0+ ∆1. AN ALGEBRAIC APPROACH TO THE MINIMUM-COST MULTI-IMPULSE ORBIT TRANSFER PROBLEM 9 5.1. Symbolic solutions. After introducing the Lagrange multipliers, the algebraic problem has 15 equations and 15 unknowns. Although such a system is expected to have a finite number of solutions, this is not true in our problem, so some special treatment is needed. We will divide the problem in several cases, which will be discussed below. Case 1: We impose the extra condition y0+y1= 0, which is done algebraically by introducing an additional variable kand adding the equation 1 −k(y0+y1) to the system. Geometrically, this new system looks for orbit transfers that are not symmetric with respect to the x-axis. We have no proof that the system has always a finite number of solutions, but we have collected extensive numerical evidence that this is indeed true. The best orbit transfer never happened to come from this case, as shown in Subsection 5.2. Case 2: Now we consider the remaining case, i.e. y0+y1= 0. It follows from eq1and eq2that x1=±x0, so we split the analysis again: x0=x1(case 2a) and x0=−x1(case 2b). The former represents transfers whose initial and final points are symmetric with respect the x-axis, and the latter is a degenerate case when the initial point, the final point and the origin are collinear. Both cases have a finite number of solutions, which we will compute explicitly below. Case 2a: We assume here that x1=x0and y1=−y0. Subtracting eq4from eq3, we obtain that y0s1x= 0. When y0= 0, we have x0=x1=±1 and the cost function can be written as f1= p(s1x−s0x)2+A+p(s1x+s0x)2+A, where Ais an expression that does not involve s1x. Since s1x vanishes from all the equations when y0= 0, we can consider it as a free variable. Setting the derivative of f1with respect to s1xto zero and solving the equation gives s1x= 0 after some algebraic manipulation. Now substituting x0=x1=±1, y0=y1= 0, s1x= 0 in the equations leaves us with only one restriction l2 1z±l1zs1y∓s0y= 1. By solving for s1yand substituting everything in the cost function f1, we get a minimization problem with only l1zas a free variable, which gives the following two solutions: (24) x0=x1=±1, y0=y1= 0, s1x= 0, s1y=s0y, l1z= 1, f1= 2|s0x|. It only remains to see what happens when s1x= 0 and y0= 0. Comparing eq5and eq6shows that ∆0= ∆1, so we can replace the cost function f1by 1 2f2= ∆2 0=s2 0x+ (s0y−s1y)2+ (1 −l1z)2+ 2(1 −l1z)(x0(s0y−s1y)−y0s0x). This uces the problem to four unknowns x0,y0,s1y,l1z, subject to two equations eq1and eq3. The case x0= 0 leads easily to the following two solutions: (25) x0=x1= 0, y0=±1, y1=∓1, s1x= 0, s1y=s0y, l1z=√1∓s0x, f1= 2|1∓s0x∓√1∓s0x|. A straightforward verification shows that |s0x|>2|1∓s0x∓√1∓s0x|for all s0x∈(−1,1), which means that the solution (25) is always better than (24). From now on, we assume that x0= 0. This allows us to express s1yin terms of x0,y0,l1zusing eq3, as follows: s1y=1 + x0s0y−y0s0x−l2 1z l1zx0 . Substituting the expression for s1yin the cost function 1 2f2, we obtain a rational function c(x0, y0, l1z). Therefore, we have to minimize csubject to x2 0+y2 0−1 = 0, which is equivalent to solving the equations              ∂c ∂l1z = 0 x0 ∂c ∂y0−y0 ∂c ∂x0 = 0 x2 0+y2 0−1=0 We can clear denominators, without losing any information, by multiplying the first equation by l3 1zx2 0 and the second one by l2 1zx3 0, since l1zand x0are both non-zero. We define the equations eq7:=l3 1zx2 0 ∂c ∂l1z = 0, eq8:=l2 1zx3 0x0 ∂c ∂y0−y0 ∂c ∂x0= 0,