Trajectory optimization is the process of designing a trajectory that minimizes (or maximizes) some measure of performance while satisfying a set of constraints. Generally speaking, trajectory optimization is a technique for computing an open-loop solution to an optimal control problem. It is often used for systems where computing the full closed-loop solution is not required, impractical or impossible. If a trajectory optimization problem can be solved at a rate given by the inverse of the Lipschitz constant, then it can be used iteratively to generate a closed-loop solution in the sense of Caratheodory. If only the first step of the trajectory is executed for an infinite-horizon problem, then this is known as Model Predictive Control (MPC).
Although the idea of trajectory optimization has been around for hundreds of years (calculus of variations, brachistochrone problem), it only became practical for real-world problems with the advent of the computer. Many of the original applications of trajectory optimization were in the aerospace industry, computing rocket and missile launch trajectories. More recently, trajectory optimization has also been used in a wide variety of industrial process and robotics applications.
History Trajectory optimization first showed up in 1697, with the introduction of the brachystochrone problem: find the shape of a wire such that a bead sliding along it will move between two points in the minimum time.300 Years of Optimal Control: From The Brachystochrone to the Maximum Principle, Hector J. Sussmann and Jan C. Willems. IEEE Control Systems Magazine, 1997. The interesting thing about this problem is that it is optimizing over a curve (the shape of the wire), rather than a single number. The most famous of the solutions was computed using calculus of variations.
In the 1950s, the digital computer started to make trajectory optimization practical for solving real-world problems. The first optimal control approaches grew out of the calculus of variations, based on the research of Gilbert Ames Bliss and BrysonBryson, Ho, Applied Optimal Control, Blaisdell Publishing Company, 1969, p 246. in America, and PontryaginL.S. Pontyragin, The Mathematical Theory of Optimal Processes, New York, Intersciences, 1962 in Russia. Pontryagin's maximum principle is of particular note. These early researchers created the foundation of what we now call indirect methods for trajectory optimization.
Much of the early work in trajectory optimization was focused on computing rocket thrust profiles, both in a vacuum and in the atmosphere. This early research discovered many basic principles that are still used today. 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.
One of the important early problems in trajectory optimization was that of the singular arc, where Pontryagin's maximum principle fails to yield a complete solution. 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.
Applications
There are a wide variety of applications for trajectory optimization, primarily in robotics: industry, manipulation, walking, path-planning, and aerospace. It can also be used for modeling and estimation.
Robotic manipulators
Depending on the configuration, open-chain robotic manipulators require a degree of trajectory optimization. For instance, a robotic arm with 7 joints and 7 links (7-DOF) is a redundant system where one cartesian position of an end-effector can correspond to an infinite number of joint angle positions, thus this redundancy can be used to optimize a trajectory to, for example, avoid any obstacles in the workspace or minimize the torque in the joints. Computing the desired path for robotic manipulators is useful in industrial manufacturing.T. Chettibi, H. Lehtihet, M. Haddad, S. Hanchi, "Minimum cost trajectory planning for industrial robots" European Journal of Mechanics, 2004.
Manufacturing and processing
Trajectory optimization is used in manufacturing, particularly for controlling chemical processes.John W. Eaton and James B. Rawlings. "Model-Predictive Control of Chemical Processes" Chemical Engineering Science, Vol 47, No 4. 1992. It has also been proposed for liquids processing, such as for evaporators or for desalination.
Walking robots
There are a variety of different applications for trajectory optimization within the field of walking robotics. For example, one paper used trajectory optimization of bipedal gaits on a simple model to show that walking is energetically favorable for moving at a low speed and running is energetically favorable for moving at a high speed.Manoj Srinivasan and Andy Ruina. "Computer optimization of a minimal biped model discovers walking and running" Nature, 2006. Like in many other applications, trajectory optimization can be used to compute a nominal trajectory, around which a stabilizing controller is built.E.R. Westervelt, J.W. Grizzle, and D.E. Koditschek. "Hybrid Zero Dynamics of Planar Biped Walkers" IEEE Transactions on Automatic Control, 2003. Trajectory optimization can be applied in detailed motion planning complex humanoid robots, such as Atlas.Michael Posa, Scott Kuindersma, and Russ Tedrake. "Optimization and stabilization of trajectories for constrained dynamical systems." International Conference on Robotics and Automation, IEEE 2016. Finally, trajectory optimization can be used for path-planning of robots with complicated dynamics constraints, using reduced complexity models.Hongkai Dai, Andres Valenzuela, and Russ Tedrake. "Whole-body motion planning with Centroidal Dynamics and Full Kinematics" International Conference on Humanoid Robots, IEEE 2014.
Aerospace
Trajectory optimization is often used to compute trajectories for quadrotor helicopters. These applications typically used highly specialized algorithms.Daniel Mellinger and Vijay Kumar, "Minimum snap trajectory generation and control for quadrotors" International Conference on Robotics and Automation, IEEE 2011.Markus Hehn and Raffaello D'Andrea, "Real-Time Trajectory Generation for Quadrocopters" IEEE Transactions on Robotics, 2015. One interesting application shown by the U.Penn GRASP Lab is computing a trajectory that allows a quadrotor to fly through a hoop as it is thrown. Another, this time by the ETH Zurich Flying Machine Arena, involves two quadrotors tossing a pole back and forth between them, with it balanced like an inverted pendulum. The problem of computing minimum-energy trajectories for a quadcopter, has also been recently studied.Fabio Morbidi, Roel Cano, David Lara, "Minimum-Energy Path Generation for a Quadrotor UAV" in Proc. IEEE International Conference on Robotics and Automation, pp. 1492-1498, 2016.
For tactical missiles, the flight profiles are determined by the thrust and 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.Phillips, C.A, "Energy Management for a Multiple Pulse Missile", AIAA Paper 88-0334, Jan., 1988
Guidance strategies for spacecraft are normally determined through solving a trajectory optimization problem. A thrust profile, describing the variation of the magnitude and direction of the force exerted by an onboard thruster, is computed, typically with the goal of minimizing the propellant or time required to reach a destination.
Terminology
Decision variables The set of unknowns to be found using optimization.
Trajectory optimization problem A special type of optimization problem where the decision variables are functions, rather than real numbers.
Parameter optimization Any optimization problem where the decision variables are real numbers.
Nonlinear program A class of constrained parameter optimization where either the objective function or constraints are nonlinear.
Indirect method An indirect method for solving a trajectory optimization problem proceeds in three steps: 1) Analytically construct the necessary and sufficient conditions for optimality, 2) Discretize these conditions, constructing a constrained parameter optimization problem, 3) Solve that optimization problem.John T. Betts "Practical Methods for Optimal Control and Estimation Using Nonlinear Programming" SIAM Advances in Design and Control, 2010.
Direct method A direct method for solving a trajectory optimization problem consists of two steps: 1) Discretize the trajectory optimization problem directly, converting it into a constrained parameter optimization problem, 2) Solve that optimization problem.
Transcription The process by which a trajectory optimization problem is converted into a parameter optimization problem. This is sometimes referred to as discretization. Transcription methods generally fall into two categories: shooting methods and collocation methods.
Shooting method A transcription method that is based on simulation, typically using explicit Runge--Kutta schemes.
Collocation method (Simultaneous Method) A transcription method that is based on function approximation, typically using implicit Runge--Kutta schemes.
Pseudospectral method (Global Collocation) A transcription method that represents the entire trajectory as a single high-order orthogonal polynomial.
Mesh (Grid) After transcription, the formerly continuous trajectory is now represented by a discrete set of points, known as mesh points or grid points.
Mesh refinement The process by which the discretization mesh is improved by solving a sequence of trajectory optimization problems. Mesh refinement is either performed by sub-dividing a trajectory segment or by increasing the order of the polynomial representing that segment.Christopher L. Darby, William W. Hager, and Anil V. Rao. "An hp-adaptive pseudospectral method for solving optimal control problems." Optimal Control Applications and Methods, 2010.
Multi-phase trajectory optimization problem Trajectory optimization over a system with hybrid dynamics can be achieved by posing it as a multi-phase trajectory optimization problem. This is done by composing a sequence of standard trajectory optimization problems that are connected using constraints.
Trajectory optimization techniques
The techniques to any optimization problems can be divided into two categories: indirect and direct. An indirect method works by analytically constructing the necessary and sufficient conditions for optimality, which are then solved numerically. A direct method attempts a direct numerical solution by constructing a sequence of continually improving approximations to the optimal solution.