Introduction

Global optimization algorithms and space pruning methods represent a recent new paradigm for spacecraft trajectory design. They promise an automated and unbiased search of different trajectory options, freeing the final user from the need for caring about implementation details. In this chapter we provide a unified framework for the definition of trajectory problems as pure mathematical optimization problems highlighting their common nature. We then present the detailed definition of two popular typologies, the Multiple Gravity Assist (MGA) and the Multiple Gravity Assist with single Deep Space Manouver (MGA-1DSM). Later we describe in detail the instantiation of four particular problems proposing them as a test set to benchmark the performances of different algorithms and pruning solutions. We take inspiration from real interplanetary trajectories such as Cassini, Rosetta, and the proposed TandEM mission, considering a large search space in terms of possible launch windows and transfer times, but also from rather academic cases such as that of the First Global Trajectory Optimisation Competition (GTOC). We test four popular heuristic paradigms on these problems (differential evolution, particle swarm optimization, simulated annealing with adaptive neighborhood, and genetic algorithm) and note their poor performances both in terms of reliability and solution quality, arguing for the need to use more sophisticated approaches, for example, pruning methods, to allow finding better trajectories. We then introduce the cluster pruning method for the MGA-1DSM problem and we apply it, in combination with the simulated annealing with adaptive neighborhood algorithm, to the TandEM test problem finding a large number of good solutions and a new putative global optima.

Introduction

This chapter presents the main elements associated with a general spacecraft trajectory design and optimization software system. A unified framework is described that facilitates the modeling and optimization of spacecraft trajectories that may operate in complex gravitational force fields, use multiple propulsion systems, and involve multiple spacecraft. The ideas presented are simple and practical and are based in part on the existing wealth of knowledge documented in the open literature and the author's experience in developing software systems of this type.

The goal of any general trajectory design and optimization system is to facilitate the solution to a wide range of problems in a robust and efficient manner. A trade off exists between scope and depth. An attempt is made to strike a balance between the two and describe an approach that has proven to be robust and useful for a broad range of spacecraft trajectory design problems. The ideas and techniques presented here have been implemented in a working operational system known as Copernicus. This system has been used to support the detailed and comprehensive mission design studies associated with NASA's Constellation program. It has also been used to design and optimize the LCROSS mission trajectory which was launched on June 18, 2009.

Introduction and Background

It is well known that spacecraft propelled by low-thrust electric propulsion (EP) can potentially deliver a greater payload fraction compared to vehicles propelled by conventional chemical propulsion. The increase in payload fraction for EP systems is due to its much higher specific impulse (Isp) or engine exhaust velocity, which is often an order of magnitude greater than the Isp for a chemical system. However, optimizing low-thrust orbit transfers is a challenging problem due to the low control authority of the EP system and the existence of long powered arcs and subsequent multiple orbital revolutions. Therefore, obtaining optimal transfers is sometimes tedious and time consuming. In his seminal paper, Edelbaum presented analytical solutions for optimizing continuous-thrust transfers between inclined circular Earth orbits. These results serve as an excellent preliminary design tool for estimating ΔV and transfer time for low-thrust missions with continuous thrust and quasi-circular transfers. Real solar electric propulsion (SEP) spacecraft, however, experience periods of zero thrust during passage through the Earth's shadow, and this major effect is not accommodated in Edelbaum's analysis. Colasurdo and Casalino have extended Edelbaum's analysis and developed an approximate analytic technique for computing optimal quasi-circular transfers with the inclusion of the Earth's shadow. Only coplanar transfers are considered, and the thrust-steering is constrained so that the orbit remains circular in the presence of the Earth's shadow.

Introduction

The determination of optimal (either minimum-time or minimum-propellant-consumption) space trajectories has been pursued for decades with different numerical optimization methods. In general, numerical optimization methods can be classified as deterministic or stochastic methods. Deterministic gradient-based methods assume the continuity and differentiability of the objective function to be minimized. In addition, gradient-based methods are local in nature and require the identification of a suitable first-attempt “solution” in the region of convergence, which is unknown a priori and strongly problem dependent. These circumstances have motivated the development of effective stochastic methods in the last decades. These algorithms are also referred to as evolutionary algorithms and are inspired by natural phenomena. Evolutionary computation techniques exploit a population of individuals, representing possible solutions to the problem of interest. The optimal solution is sought through cooperation and competition among individuals. The most popular class of these techniques is represented by the genetic algorithms (GA), which model the evolution of a species based on Darwin's principle of survival of the fittest. Differential evolution algorithms represent alternative stochastic approaches with some analogy with genetic algorithms, in the sense that new individuals are generated from old individuals and are eventually preserved after comparing them with their parents. Ant colony optimization is another method, inspired by the behavior of ants, whereas the simulated annealing algorithm mimics the equilibrium of large numbers of atoms during an annealing process.

Introduction

The subject of spacecraft trajectory optimization has a long and interesting history. The problem can be simply stated as the determination of a trajectory for a spacecraft that satisfies specified initial and terminal conditions, that is conducting a required mission, while minimizing some quantity of importance. The most common objective is to minimize the propellant required or equivalently to maximize the fraction of the spacecraft that is not devoted to propellant. Of course, as is common in the optimization of continuous dynamical systems, it is usually necessary to provide some practical upper bound for the final time or the optimizer will trade time for propellant. There are also spacecraft trajectory problems where minimizing flight time is the important thing, or problems, for example those using continuous thrust, where minimizing flight time and minimizing propellant use are synonymous.

Except in very special (integrable) cases, which reduce naturally to parameter optimization problems, the problem is a continuous optimization problem of an especially complicated kind.

Introduction

The analysis of optimal low-thrust orbit transfer using averaging methods has benefited from the contributions in. In particular the minimum-time transfer between inclined circular orbits was solved in by rotating the orbit plane around the relative line of nodes of initial and final orbits using a piecewise-constant out-of-plane thrust angle switching signs at the relative antinodes while simultaneously changing the orbit size from its initial to its final required value. The original analysis in was further reformulated in in order to arrive at expressions that depict the evolutions of the transfer parameters in a uniform manner valid for all transfers. Further contributions using both analytic and numerical approaches were also carried out in and to solve increasingly more difficult problems, such as by considering realistic constraints and orbit precession due to the important second zonal harmonic J2, while also considering various averaging schemes for rapid computation of the solutions.

The first part of this chapter presents the reformulated Edelbaum problem of the minimum-time low-thrust transfer between inclined circular orbits by further extending it in order to constrain the intermediate orbits during the transfer to remain below a given altitude. The minimum-time problem involving an inequality constraint on the orbital velocity is shown to be equivalent to one involving an equality constraint in terms of the thrust yaw angle representing the control variable that is optimized resulting in the minimum-time solution.

Introduction

A spacecraft in flight is a dynamical system. As dynamical systems go, it is comparatively straightforward; the equations of motion are continuous and deterministic, for the unforced case they are essentially integrable, and perturbations, such as the attractions of bodies other than the central body, are usually small. The difficulties arise when the complete problem, corresponding to a real space mission, is considered. For example, a complete interplanetary flight, beginning in Earth orbit and ending with insertion into Mars orbit, has complicated, time-dependent boundary conditions, straightforward equations of motion but requires coordinate transformations when the spacecraft transitions from planet-centered to heliocentric flight (and vice versa), and likely discrete changes in system states as the rocket motor is fired and the spacecraft suddenly changes velocity and mass. If low-thrust electric propulsion is used, the system is further complicated as there no longer exist integrable arcs and the decision variables, which previously were discrete quantities such as the times, magnitudes and directions of rocket-provided impulses, now also include continuous time histories, that is, of the low-thrust throttling and of the thrust pointing direction. In addition, it may be optimizing to use the low-thrust motor for finite spans of time and “coast” otherwise, with the optimal number of these thrust arcs and coast arcs a priori unknown.

Since the cost of placing a spacecraft in orbit, which is usually the first step in any trajectory, is so enormous, it is particularly important to optimize space trajectories so that a given mission can be accomplished with the lightest possible spacecraft and within the capabilities of existing (or affordable) launch vehicles.

Introduction

Multiple gravity assist (MGA) trajectories represent a particular class of space trajectories in which a spacecraft exploits the encounter with one or more celestial bodies to change its velocity vector. If deep space maneuvers (DSM) are inserted between two planetary encounters, the number of alternative paths can grow exponentially with the number of encounters and the number of DSMs. The systematic scan of all possible trajectories in a given range of launch dates quickly becomes computationally intensive even for moderately short sequences of gravity assist maneuvers and small launch windows. Thus finding the best trajectory for a generic transfer can be a challenge. The search for the best transfer trajectory can be formulated as a global optimization problem. An instance of this global optimization problem can be identified through the combination of a particular trajectory model, a particular sequence of planetary encounters, a number of DSMs per arc, a particular range for the parameters defining the trajectory model, and a particular optimality criterion. Thus a different trajectory model would correspond to a different instance of the problem even for the same destination planet and sequence of planetary encounters. Different models as well as different sequences and ranges of the parameters can make the problem easily solvable or NP-hard. However, the physical nature of this class of transfers allows every instance to be decomposed into subproblems of smaller dimension and smaller complexity.

It has been a very long time since the publication of any volume dedicated solely to space trajectory optimization. The last such work may be Jean-Pierre Marec's Optimal Space Trajectories. That book followed, after 16 years, Derek Lawden's pioneering Optimal Trajectories for Space Navigation of 1963. If either of these books can be found now, it is only at a specialized used-book seller, for “astronomical” prices.

In the intervening several decades, interest in the subject has only grown, with space missions of sophistication, complexity, and scientific return hardly possible to imagine in the 1960s having been designed and flown. While the basic tools of optimization theory – such things as the calculus of variations, Pontryagin's principle, Hamilton-Jacobi theory, or Bellman's principle, all of which are useful tools for the mission designer – have not changed in this time, there has been a revolution in the manner in which they are applied and in the development of numerical optimization. The scientists and engineers responsible have thus learned what they know about spacecraft trajectory optimization from their teachers or colleagues, with the assistance, primarily, of journal and conference articles, some of which are now “classics” in the field.

This volume is thus long overdue. Of course one book of ten chapters cannot hope to comprehensively describe this complex subject or summarize the advances of three decades. While it purposely includes a variety of both analytical and numerical approaches to trajectory optimization, it is bound to omit solution methods preferred by some researchers.

Introduction

The three-body system has been of interest to mathematicians and scientists for well over a century dating back to Poincaré. Much of the interest in recent years has focused on using the interesting dynamics present around libration points to create trajectories that can travel vast distances around the solar system for almost no fuel expenditure traversing the so-called “Interplanetary Super Highway” (IPS). It has also been proposed to use Lagrange points as staging bases for more ambitious missions.

Lagrange points are equilibrium points of the three-body system that describes the motion of a massless particle in the presence of two massive primaries in a reference frame that rotates with the primaries. There are five Lagrange points (labeled L1,…,L5), the three collinear points along the line of the two primaries, and the two equilateral points that form an equilateral triangle with the two primaries. It is the collinear points that are of the most interest and in particular the L1 point between the two primaries and the L2 point on the far side of the smaller primary. Since Poincaré, there has been much work on finding periodic solutions to the three-body problem. Early work was confined to analytic studies that are restricted to approximations as there exists no closed form analytical solution to the three-body system equations of motion.

Introduction

In this chapter we consider the problem of sequencing a given number of jobs on a single machine and devise methodologies and develop closed-form expressions (wherever possible) to compute the expectation and variance of various performance measures. Numerical illustrations indicating the significance and applicability of our work are also presented through example problems.

Besides being of significance in their own right, single-machine problems also constitute a good starting point for analyzing more complex scheduling environments of flow shop and job shop. The different performance measures that we consider for the single-machine case can be classified into two categories:

1. Completion-time-based, which includes total completion time (total flow time), total weighted completion time, and total weighted discounted completion time

2. Due-date-based, which includes total tardiness, total weighted tardiness, total number of tardy jobs, total weighted number of tardy jobs, mean lateness, and maximum lateness.

The processing time of a job is assumed to be a random variable that follows an arbitrary probability distribution.

First, we present the notation that is used in this chapter. Some of this notation has been introduced already in earlier chapters. However, we include it here for the sake of completeness.