Trajectory optimization
Encyclopedia
Trajectory optimization is the process of designing a trajectory
that minimizes or maximizes some measure of performance
within prescribed constraint boundaries. While not exactly the same, the goal of solving a trajectory optimization problem is essentially the same as solving an optimal control
problem.
The selection of flight profiles that yield the greatest performance plays a substantial role in the preliminary design of flight vehicles, since the use of ad-hoc profile or control policies to evaluate competing configurations may inappropriately penalize the performance of one configuration over another. Thus, to guarantee the selection of the best vehicle design, it is important to optimize the profile and control policy for each configuration early in the design process.
Consider this example. For tactical missiles, the flight profiles are determined by the thrust and load factor
(lift) histories. These histories can be controlled by a number of means including such techniques as using an angle of attack
command history or an altitude/downrange schedule that the missile must follow. Each combination of missile design factors, desired missile performance, and system constraints results in a new set of optimal control parameters.
approaches which grew out of the calculus of variations
developed at the University of Chicago in the first half of the 20th century most notably by Gilbert Ames Bliss
. Pontryagin in Russia and Bryson in America were prominent researchers in the development of optimal control.
Early application of trajectory optimization had to do with the optimization of rocket thrust profiles in:
From the early work, much of the givens about rocket propulsion optimization were discovered. Another successful application was the climb to altitude trajectories for the early jet aircraft. Because of the high drag associated with the transonic drag region and the low thrust of early jet aircraft, trajectory optimization was the key to maximizing climb to altitude performance. Optimal control based trajectories were responsible for some of the world records. In these situations, the pilot followed a Mach versus altitude schedule based on optimal control solutions.
In the early phase of trajectory optimization; many of the solutions were plagued by the issue of singular subarcs. For such problems, the term in the Hamiltonian linearly multiplying the control variable goes to zero for a finite time and it becomes impossible to directly solve for the optimal control. The Hamiltonian is of the form:
and the control is restricted to being between an upper and a lower bound: 
. To minimize 
, we need to make 
as big or as small as possible, depending on the sign of 
, specifically:
If
is positive at some times, negative at others and is only zero instantaneously, then the solution is straightforward and is a bang-bang control
that switches from
to 
at times when 
switches from negative to positive.
The case when
remains at zero for a finite length of time 
is called the singular control
case and the optimal trajectory follows the singular subarc.
In this case, one is left with a family of feasible solutions. At that point, the investigators had to numerically evaluate each member of the family to determine the optimal solution. A breakthrough occurred with a condition sometimes referred to as the Kelley condition. While not a sufficient condition, this provided an additional necessary condition that allowed downselection to a trajectory that is usually the optimal singular control
.
An example of a problem with singular control is the optimization of the thrust of a missile flying at a constant altitude and which is launched at low speed. Here the problem is one of a bang-bang control at maximum possible thrust until the singular arc is reached. Then the solution to the singular control provides a lower variable thrust until burnout. At that point bang-bang control provides that the control or thrust go to its minimum value of zero. This solution is the foundation of the boost-sustain rocket motor profile widely used today to maximize missile performance.
Many of the early triumphs of trajectory optimization have moved into the background knowledge of the modern flight mechanicist and the origins of these discoveries are not widely known.
The techniques available to solve optimization problems
fall into two broad categories: the optimal control methodology that allows solution by either analytical or numerical procedures, and an approximation to the optimal-control problem through the use of nonlinear programming
that allows solution by numerical procedures. The former technique is "indirect" in that it finds a solution where the total differential of the performance measure is zero. The latter technique is "direct" in that it finds a solution where the performance measure is smaller (or greater) than that of any other solution in the neighborhood.
The optimal control problem is an infinite dimensional problem while the nonlinear programming approach approximates the problem by a finite dimensional problem. Trajectory optimization shares the same optimization algorithms as other optimization problems. The numerical optimal control methodology can produce the best answers but converging to a solution is difficult. Convergence is rapid when the initial guess is good, otherwise the search may fail. The ascent trajectories for the US space program (Gemini and Apollo) were designed using numerical optimal control. The very tight tolerances associated with space launchers allowed optimal control to be a useful tool. For systems with less controlled environments such as missiles, numerical optimal control would not prove as useful.
The analytic solution of the optimal control often involves extensive approximations but can still produce useful algorithms. An example is given in Ohlmeyer & Phillips . In this example, linear assumptions are made and yet the algorithm can produce near optimal trajectories. Another example of an analytic solution is the "Iterative Guidance Mode (IGM)", the guidance algorithm used by the two exo-atmospheric stages of the Saturn V rocket. The IGM algorithm is an analytical calculus-of-variations solution of the two-point boundary value problem posed by the ascent of the rocket to prescribed orbit-injection conditions. The analytical solution requires that gravitational acceleration
be approximated as a constant vector, and an iteration of the solution is required to improve the accuracy of this approximation.
Many numerical procedures exist to solve parameter optimization problems. The simplest procedures use the gradient descent
technique, sometimes also known as the method of steepest descent. Second-order methods are also available to improve the rate of convergence, for example, the Newton–Raphson iteration, which requires the evaluation of the Hessian matrix
. Quasi-Newton or variable-metric methods avoid the evaluation of the Hessian matrix by using iterative evaluation of first-order information to approximate the Hessian matrix. The nonlinear programming methods such as BFGS and SQP
may be used to solve the finite dimensional problem. An effective and robust nonlinear programming method employing the Simplex algorithm
was developed in the 1970's. It was first used to determine quasi-optimum reentry trajectories for the Space Shuttle and has subsequently been used to solve a wide variety of rocket trajectory optimization problems. The nonlinear programming approach is generally more robust in terms of finding a solution than numerical optimal control, but many of the gradient or Newton-Raphson methods require "smoothness" in the function algorithms to be successful. Smoothness is continuity in the first derivative. The smoothness requirement imposes a burden on flight trajectory analysts in that most highly detailed trajectory simulations do not exhibit smoothness. This restriction was a problem in the early days of trajectory optimization when computer computation speed was an issue. Often, special approximate trajectory models had to be used to work with non-linear programming models. As computation time has become cheap compared to manpower, direct sample methods have evolved as the optimization algorithms of choice. These algorithms may require orders of magnitude increases in the number of functional samples but exhibit robustness to non-smoothness in the trajectory code. Examples include: genetic algorithms , stochastic sampling methods, and hill climbing
algorithms. An overview of the state of the art in numerical methods is given in Betts.
A collection of low thrust trajectory optimization tools can be found at http://www.grc.nasa.gov/WWW/InSpace/LTTT/index.html.
Trajectory
A trajectory is the path that a moving object follows through space as a function of time. The object might be a projectile or a satellite, for example. It thus includes the meaning of orbit—the path of a planet, an asteroid or a comet as it travels around a central mass...
that minimizes or maximizes some measure of performance
Figure of merit
A figure of merit is a quantity used to characterize the performance of a device, system or method, relative to its alternatives. In engineering, figures of merit are often defined for particular materials or devices in order to determine their relative utility for an application...
within prescribed constraint boundaries. While not exactly the same, the goal of solving a trajectory optimization problem is essentially the same as solving an optimal control
Optimal control
Optimal control theory, an extension of the calculus of variations, is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and his collaborators in the Soviet Union and Richard Bellman in the United States.-General method:Optimal...
problem.
The selection of flight profiles that yield the greatest performance plays a substantial role in the preliminary design of flight vehicles, since the use of ad-hoc profile or control policies to evaluate competing configurations may inappropriately penalize the performance of one configuration over another. Thus, to guarantee the selection of the best vehicle design, it is important to optimize the profile and control policy for each configuration early in the design process.
Consider this example. For tactical missiles, the flight profiles are determined by the thrust and load factor
Load factor
Load factor may refer to:* Load factor , the ratio of the lift of an aircraft to its weight* Load factor , the ratio of the number of records to the number of addresses within a data structure...
(lift) histories. These histories can be controlled by a number of means including such techniques as using an angle of attack
Angle of attack
Angle of attack is a term used in fluid dynamics to describe the angle between a reference line on a lifting body and the vector representing the relative motion between the lifting body and the fluid through which it is moving...
command history or an altitude/downrange schedule that the missile must follow. Each combination of missile design factors, desired missile performance, and system constraints results in a new set of optimal control parameters.
History
Trajectory optimization began in earnest in the 1950s as digital computers became available for the computation of trajectories. The first efforts were based on optimal controlOptimal control
Optimal control theory, an extension of the calculus of variations, is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and his collaborators in the Soviet Union and Richard Bellman in the United States.-General method:Optimal...
approaches which grew out of the calculus of variations
Calculus of variations
Calculus of variations is a field of mathematics that deals with extremizing functionals, as opposed to ordinary calculus which deals with functions. A functional is usually a mapping from a set of functions to the real numbers. Functionals are often formed as definite integrals involving unknown...
developed at the University of Chicago in the first half of the 20th century most notably by Gilbert Ames Bliss
Gilbert Ames Bliss
Gilbert Ames Bliss, , was an American mathematician, known for his work on the calculus of variations.-Life:...
. Pontryagin in Russia and Bryson in America were prominent researchers in the development of optimal control.
Early application of trajectory optimization had to do with the optimization of rocket thrust profiles in:
- a vacuum and
- in an atmosphere.
From the early work, much of the givens about rocket propulsion optimization were discovered. Another successful application was the climb to altitude trajectories for the early jet aircraft. Because of the high drag associated with the transonic drag region and the low thrust of early jet aircraft, trajectory optimization was the key to maximizing climb to altitude performance. Optimal control based trajectories were responsible for some of the world records. In these situations, the pilot followed a Mach versus altitude schedule based on optimal control solutions.
In the early phase of trajectory optimization; many of the solutions were plagued by the issue of singular subarcs. For such problems, the term in the Hamiltonian linearly multiplying the control variable goes to zero for a finite time and it becomes impossible to directly solve for the optimal control. The Hamiltonian is of the form:
and the control is restricted to being between an upper and a lower bound: . To minimize , we need to make as big or as small as possible, depending on the sign of , specifically:
If
is positive at some times, negative at others and is only zero instantaneously, then the solution is straightforward and is a bang-bang controlBang-bang control
In control theory, a bang–bang controller , also known as a hysteresis controller, is a feedback controller that switches abruptly between two states. These controllers may be realized in terms of any element that provides hysteresis...
that switches from
to at times when switches from negative to positive.The case when
remains at zero for a finite length of time is called the singular controlSingular control
In optimal control, problems of singular control are problems that are difficult to solve because a straightforward application of Pontryagin's minimum principle fails to yield a complete solution. Only a few such problems have been solved, such as Merton's portfolio problem in financial economics...
case and the optimal trajectory follows the singular subarc.
In this case, one is left with a family of feasible solutions. At that point, the investigators had to numerically evaluate each member of the family to determine the optimal solution. A breakthrough occurred with a condition sometimes referred to as the Kelley condition. While not a sufficient condition, this provided an additional necessary condition that allowed downselection to a trajectory that is usually the optimal singular control
Singular control
In optimal control, problems of singular control are problems that are difficult to solve because a straightforward application of Pontryagin's minimum principle fails to yield a complete solution. Only a few such problems have been solved, such as Merton's portfolio problem in financial economics...
.
An example of a problem with singular control is the optimization of the thrust of a missile flying at a constant altitude and which is launched at low speed. Here the problem is one of a bang-bang control at maximum possible thrust until the singular arc is reached. Then the solution to the singular control provides a lower variable thrust until burnout. At that point bang-bang control provides that the control or thrust go to its minimum value of zero. This solution is the foundation of the boost-sustain rocket motor profile widely used today to maximize missile performance.
Many of the early triumphs of trajectory optimization have moved into the background knowledge of the modern flight mechanicist and the origins of these discoveries are not widely known.
Solution techniques
The techniques available to solve optimization problems
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
fall into two broad categories: the optimal control methodology that allows solution by either analytical or numerical procedures, and an approximation to the optimal-control problem through the use of nonlinear programming
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
that allows solution by numerical procedures. The former technique is "indirect" in that it finds a solution where the total differential of the performance measure is zero. The latter technique is "direct" in that it finds a solution where the performance measure is smaller (or greater) than that of any other solution in the neighborhood.
The optimal control problem is an infinite dimensional problem while the nonlinear programming approach approximates the problem by a finite dimensional problem. Trajectory optimization shares the same optimization algorithms as other optimization problems. The numerical optimal control methodology can produce the best answers but converging to a solution is difficult. Convergence is rapid when the initial guess is good, otherwise the search may fail. The ascent trajectories for the US space program (Gemini and Apollo) were designed using numerical optimal control. The very tight tolerances associated with space launchers allowed optimal control to be a useful tool. For systems with less controlled environments such as missiles, numerical optimal control would not prove as useful.
The analytic solution of the optimal control often involves extensive approximations but can still produce useful algorithms. An example is given in Ohlmeyer & Phillips . In this example, linear assumptions are made and yet the algorithm can produce near optimal trajectories. Another example of an analytic solution is the "Iterative Guidance Mode (IGM)", the guidance algorithm used by the two exo-atmospheric stages of the Saturn V rocket. The IGM algorithm is an analytical calculus-of-variations solution of the two-point boundary value problem posed by the ascent of the rocket to prescribed orbit-injection conditions. The analytical solution requires that gravitational acceleration
Gravitational acceleration
In physics, gravitational acceleration is the acceleration on an object caused by gravity. Neglecting friction such as air resistance, all small bodies accelerate in a gravitational field at the same rate relative to the center of mass....
be approximated as a constant vector, and an iteration of the solution is required to improve the accuracy of this approximation.
Many numerical procedures exist to solve parameter optimization problems. The simplest procedures use the gradient descent
Gradient descent
Gradient descent is a first-order optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient of the function at the current point...
technique, sometimes also known as the method of steepest descent. Second-order methods are also available to improve the rate of convergence, for example, the Newton–Raphson iteration, which requires the evaluation of the Hessian matrix
Hessian matrix
In mathematics, the Hessian matrix is the square matrix of second-order partial derivatives of a function; that is, it describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named...
. Quasi-Newton or variable-metric methods avoid the evaluation of the Hessian matrix by using iterative evaluation of first-order information to approximate the Hessian matrix. The nonlinear programming methods such as BFGS and SQP
Sequential quadratic programming
Sequential quadratic programming is an iterative method for nonlinear optimization. SQP methods are used on problems for which the objective function and the constraints are twice continuously differentiable....
may be used to solve the finite dimensional problem. An effective and robust nonlinear programming method employing the Simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
was developed in the 1970's. It was first used to determine quasi-optimum reentry trajectories for the Space Shuttle and has subsequently been used to solve a wide variety of rocket trajectory optimization problems. The nonlinear programming approach is generally more robust in terms of finding a solution than numerical optimal control, but many of the gradient or Newton-Raphson methods require "smoothness" in the function algorithms to be successful. Smoothness is continuity in the first derivative. The smoothness requirement imposes a burden on flight trajectory analysts in that most highly detailed trajectory simulations do not exhibit smoothness. This restriction was a problem in the early days of trajectory optimization when computer computation speed was an issue. Often, special approximate trajectory models had to be used to work with non-linear programming models. As computation time has become cheap compared to manpower, direct sample methods have evolved as the optimization algorithms of choice. These algorithms may require orders of magnitude increases in the number of functional samples but exhibit robustness to non-smoothness in the trajectory code. Examples include: genetic algorithms , stochastic sampling methods, and hill climbing
Hill climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
algorithms. An overview of the state of the art in numerical methods is given in Betts.
Multi-level optimization
When dealing with complex payoff functions that are pertinent to realistic engineering problems, an alternative method is one of the multi-level techniques. These approaches allow models to be used in the optimization in a tiered approach by the passing of constraints to the lower levels and selecting the optimal value of the constraint value in the upper levels. An early paper in this area presents this idea for the optimization of the performance of a missile.Software
Examples of trajectory optimization programs include:- Copernicus Trajectory Design and Optimization System http://research.jsc.nasa.gov/PDF/Eng-12.pdf
- GMAT (General Mission Analysis Tool)
- JModelica.orgJModelica.orgJModelica.org is a free and open source platform based on the Modelica modeling language for modeling, simulation, optimization and analysis of complex dynamic systems. The platform is maintained and developed by Modelon AB in collaboration with academic and industrial institutions, notably Lund...
(Modelica-based open source platform for dynamic optimization) - OTIS (Optimal Trajectories by Implicit Simulation) http://otis.grc.nasa.gov/background.html
- POST (Program to Optimize Simulated Trajectories) https://post2.larc.nasa.gov/, http://www.sierraengineering.com/Post3d/post3d.html
- SORT (Simulation and Optimization of Rocket Trajectories)
- ASTOSAstosASTOS is a Trajectory optimization and simulation tool for launch and re-entry missions, orbit transfers, design optimization and for re-entry safety assessments. It solves Aerospace problems with a data driven interface and automatic initial guesses...
(AeroSpace Trajectory Optimization and Simulation - ZOOM, Conceptual Design and Analysis of Rocket Configurations and Trajectories) http://trajectorysolution.com/ZOOM%20Program.html
A collection of low thrust trajectory optimization tools can be found at http://www.grc.nasa.gov/WWW/InSpace/LTTT/index.html.