To: CMU Autonomous Machine Learning Group , cga@cc.gatech.edu, dilello@cs.cmu.edu, gboone@cs.cmu.edu, jab@cs.cmu.edu, schneide@cs.cmu.ed, scottd@cs.cmu.edu, carlos@cc.gatech.edu cc: Gary Noel Boone Subject: Are all mimimum time controllers bang-bang? Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII I've been thinking about the recent example systems suggested by Chris showing that optimal controllers for minimum time systems may not be bang-bang. Here's what I found. Comments and corrections are welcome. =) Gary ----------------------- Gary N. Boone gboone@cc.gatech.edu Georgia Tech http://www.cc.gatech.edu/grads/b/Gary.N.Boone/Gary.N.Boone.html Time Optimal Problems, Bang-Bang Control and Singularities 1. Bang-Bang Control and Pontryagin's Minimum Principle 2. Singular Control 3. Minimum Time Example 4. Conditions for Bang-Bang Control 5. Solving Singular Problems 6. Example Code The Calculus of Variations provides a suite of analytical techniques that allow the solution of optimal control problems. Developed over the past thirty years, its theorems and procedures describe the conditions in which controllers are optimal, and often specify their forms and design methodology. One class of controllers that has received considerable attention in the literature is the bang-bang controller, so called because it switches the control inputs between admissible extremes. Bang-bang controllers are chiefly of interest because their simple design greatly reduces the effort required to find the optimal control function. Bang-bang controllers can be shown to be optimal for several types of problems, including minimum-time and minimum effort problems. However, there are specific conditions which must be met; not all minimum time problems are bang-bang. 1. Bang-Bang Control and Pontryagin's Minimum Principle Bang-Bang control arises because the admissible controls are constrained and the Hamiltonian is linear in the control. Given a plant, x_dot = f(x, u, t), and a final state constraint, psi(x(T), T), we want to minimize a performance criterion, J(t0) = phi(x(T), T) + integral_t0^T L(x, u, t) dt, where phi is a final cost. It is useful to define the Hamiltonian, H(x, u, p, t) = L(x, u, t) + p' f(x, u, t). Note that H is a scalar, p and f are a vectors. Then, to minimize L it is necessary to minimize H, that is, find u such that: x_dot = H_p = f (state equations) p_dot = - H_x = L_x + f_x' p (costate equations) 0 = H_u = L_u + f_u' p (stationarity condition) where the subscripts indicate derivatives. These equations, with their boundary conditions, can often be solved to provide the optimal controller. However, if the control magnitudes are limited, it may not be possible to satisfy the stationarity condition. The stationarity condition, H_u = 0, should be replaced with Pontryagin's minimum principle: H(x*, u*, p*, t) <= H(x*, u, p*, t), which says that the constrained controls, u, will increase the Hamiltonian over the value for the optimal, unconstrained, controls, u*. Therefore, if our controls are constrained, the best we can is choose the admissible control that most minimizes the Hamiltonian. This is Pontryagin's minimum principle. It applies to all time and _all_ admissible controls. Note, however, that some controls may not affect the value of the Hamiltonian. Suppose the state equations and performance index are linear in u. Then the Hamiltonian will be linear in u. x_dot = a(x, t) = f(x, t) + Bu L(x, u, t) = g(x, t) + C'u H(x, u, p, t) = g(x, t) + C'u + p' f(x, t) + p' Bu. Then the stationary condition, H_u = L_u + a_u' p = 0 = C + B'p = 0 (H_u is not a scalar) does not depend on u! That means we can choose u to be as small as possible, -inf, to most minimize the Hamiltonian. However, the controls are constrained and p, which is a function of time, may change sign. Therefore, we will operate the controls at their extremes, switching according to the sign of p. Thus, the optimal control is bang-bang. Another way to see this is to use Pontryagin: g(x*, t) + Cu* + p*' f(x*, t) + p*' Bu* <= g(x*, t) + Cu + p*' f(x*, t) + p*' Bu or Cu* + p*' Bu* <= Cu + p*' Bu Thus, u will switch with p* to keep (C+p*'B)u as small as possible. So far, we have two conditions for bang-bang control: - The control inputs are limited. - The state equations and performance index are linear in the controls. Note that we have not required that the problem be minimum time to enable bang-bang control. However, in practice, there are few problems which are linear on u and whose performance metric has a linear or no dependence on u. Minimum fuel problems use |u| and minimum energy problems use u^2 as performance indexes. Time minimal problems use L = 1; if the control is linear, then they may be bang-bang. 2. Singular Control The optimal control for a bang-bang controller switches according to the sign of p. Note that p may equal 0, at which the switching function is undefined. If p equals 0 only instantaneously, then the controller is bang-bang. However, there are many problems in which p = 0 for some period of time. These problems are called singular. Formally, a problem is said to be normal if there exists a countable set of times at which p = 0. If there is any time interval for which p=0, the problem is singular. Consider a system that is linear in the controls has a performance index that does not depend on u. Note that this does not have to be minimum time problem. x_dot = a(x, t) = f(x, t) + Bu, L(x, u, t) = g(x, t). The Hamiltonian is: H(x, u, p, t) = g(x, t) + p' f(x, t) + p' Bu. If p = 0, then the Hamiltonian becomes H(x, u, p, t) = g(x, t), which says nothing about the optimal control! Another condition that leads to singularity occurs if the stationarity condition for unconstrained controls is true although the control magnitudes are indeed constrained. That is, the trajectory achieves the global minima of H. Then H_u = 0. However, in the above case, the Hamilton becomes H_u = B'p = 0, which indicates that the Hamiltonian, the adjoint equations, and the Pontryagin minimum principal no longer define the optimal control by a relationship between u, p, x, and t. It must be emphasized that the singular condition does not mean that an optimal control does not exist or is unknown. 3. Minimum Time Example For the system: State: Initial Cond. Constraints x1_dot = 1/((x2)^2 + 1) x1(0) = 0 -1 < u < 1 x2_dot = u x2(0) = 1 x1 > 1 is the goal Because the performance index is minimal time, the Hamiltonian is given by H = 1 + p1 / (x2^2 + 1) + p2 u Then the costate equations are p1_dot = 0 p2_dot = -2 p1 x2 (x2^2 + 1)^-2 The boundary conditions are given by the stationarity condition and by the boundary condition equation: (phi_x + psi_x'v - p)'|_T dx(T) + (phi_t + psi_t'v + H)|_T dT = 0 which for problems that have both final times and final positions free and independent becomes (phi_x + psi_x'v - p)'|_T = 0 (phi_t + psi_t'v + H)|_T = 0 (phi is the final cost and psi is the final state.) v is a new constant Lagrange multiplier that is introduced. Thus, we have 2n differential equations which can be solved as a two point boundary problem. Note that they are coupled and must be integrated with respect to time. We know that by Pontryagin, 1 + p1* / (x2*^2 + 1) + p2* u* <= 1 + p1* / (x2*^2 + 1) + p2* u which implies that p2* u* <= p2* u. So the optimal u is a switching function on p2. The controller is bang-bang, provided that the problem is not singular. Are there any trajectories for which p2 = 0 for any interval? Looking at the costate equation, p2_dot = 0 if x2 /(x2^2 + 1)^2 = 0 or p1 = 0. But p1 is constant because p1_dot = 0. If p1(0) = 0, then p2_dot = 0. If p2(0) = 0, then it will remain 0. Therefore, for the initial conditions p1(0) = p(1) = 0, this problem is singular. 4. Conditions for Bang-Bang Control We have three general conditions for bang-bang control. - The control inputs are limited. - The state equations and performance index are linear in the controls. - The problem is normal. Note, however, a couple of caveats. Other singular points may also exist. For example, the state equations may define trajectories that are discontinuous, not unique, or do not exist. This discussion has assumed continuous systems. An optimal control may not exist. The set of states achievable in finite time by admissible controls is called the reachable set. If the target surface of a time-optimal problem and the reachable set have an empty intersection, then no time-optimal control exists. If a system is completely controllable, then all states are reachable. To check controllability, one can build [b|Ab|A^2b|...|A^(n-1)b]; if it is nonsingular, then the system is completely controllable. The strongest results pertain to linear systems. For linear, time-invariant, controllable, normal systems, if all of the eigenvalues of A have nonpositive real parts, then an optimal control exists. Further, the control is unique and extremal, switching at most n-1 times for an nth order system. 5. Solving Singular Problems There are few formal results for the necessary and sufficient conditions for singular problems. However, it is known that if the determinant of the matrix H_uu vanishes at any point along an extremal arc, the problem is singular. H_uu is defined as a matrix whose ijth entry is (H_i)_j. However, there are a number of tricks and techniques that can be used to solve the resulting equations. For example, if p = 0, then p_dot = 0. The derivative with respect to time of the Hamilton is zero. If the final time is free, then the variations of dt and dx in the variational approach are independent. Then, if the system is time invariant, it must be true that the Hamiltonian equals 0. These techniques may allow relationships to be worked through to determine an optimal control. However, these manipulations are only practical for small problems. 6. Example Code Here's Mathematica code to verify the operation of the optimal controller and experiment with the relationships between the state and adjoint equations. NDSolve[{x1'[t] == 1/(x2[t]^2 + 1), x2'[t] == If[x2[t]>0,-1,0], x1[0] == 0, x2[0] == 1}, {x1[t], x2[t]}, {t, 0, 1.7}]; Plot[Evaluate[x1[t] /. %], {t, 0, 1.7}] NDSolve[{x1'[t] == 1/(x2[t]^2 + 1), x2'[t] == -If[p2[t]<0,-1,1], p1'[t] == 0, p2'[t] == - 2 p1[t] x2[t] (x2[t]^2 + 1)^(-2), x1[0] == 0, x2[0] == 1, p1[0] == 0, p2[0] == 0}, {x1[t], x2[t], p1[t], p2[t]}, {t, 0, 1.7}]; Plot[Evaluate[x1[t] /. %], {t, 0, 1.7}] Athans, M., and Falb, P. (1966) "Optimal Control: An Introduction to the Theory and Its Applications". McGraw-Hill, New York, NY. Bell, D. J. (1975) "Singular Problems in Optimal Control--A Survey". International Journal of Control. Vol. 21, No. 2, pp. 319--331. Johnson, C. D. (1965) "Singular Solutions in Problem of Optimal Control." In _Advances in Control Systems_, Ed. C. T. Leondes. Vol. 2, pp. 209--267. Kirk, D. (1970) "Optimal Control Theory: An Introduction" Prentice-Hall, Englewood Cliffs, NJ. Lewis, F., and Syrmos, V. (1995) "Optimal Control" John Wiley & Sons, New York, New York. Sage, A., and White, C. (1977) "Optimum Systems Control". Prentice-Hall, Englewood Cliffs, NJ.