# Optimal Soaringwith Hamilton-Jacobi-Bellman Equations

## Robert Almgren and Agnes Tourin

Competition glider flying, like other outdoor sports, is a game of stochastic optimization, in which mathematics and quantitative strategies have historically played an important role. We address the problem of uncertain future atmospheric conditions by constructing a nonlinear Hamilton-Jacobi-Bellman equation for the optimal speed to fly, with a free boundary describing the climb/cruise decision. This equation comes from a singular stochastic exit time control problem and involves a gradient constraint, a state constraint and a weak Dirichlet boundary condition. An accurate numerical solution requires robust monotone numerical methods. The computed results are of direct applicability for glider flight.

## Web resources

Soaring Society of America
John Cochrane's publications, including his paper "MacCready theory with uncertain lift and limited altitude". His paper studies a discrete-space model, which was the motivation for our continuous model.
A mesmerizing Java simulation of cross-country glider flying.
A nice Java animation of sailboat racing, which uses the same techniques as our paper (in a discrete state space).

## First section of the paper

1. Introduction Competition glider flying, like other outdoor sports such as sailboat racing, is a game of probabilities, and of optimization in an uncertain environment. The pilot must make a continuous series of strategic decisions, with imperfect information about the likely conditions to be encountered futher along the course and later in the day. In a competition, these decisions are made in order to maximize cross-country speed, and hence final score in the contest; even in noncompetition flying the pilot is under pressure to complete the chosen course before the end of the day.

Optimal control under uncertainty is, of course, an area of extremely broad application, not only of sport competition, but for many practical problems, in particular in the general area of finance and investments.

Another area of broad mathematical interest is that of free boundary problems. These are common in optimal control problems, where the boundary delineates a region of state space where it is optimal to take a different action: exercise an option, sell an asset, etc. This problem also has an optimal exercise boundary, corresponding to the decision whether to stop and climb in a thermal.

An entire area of mathematical research -- viscosity solutions -- has been developed in order to solve these problems with various forms of nonsmooth constraints. The results available provide important insight into this problem, which in turns, gives a very concrete example to illustrate the techniques and the theory in practice. For a detailed introduction to the theory and its applications, we recommend Barles (1994), Bardi, Capuzzo, and Dolcetta (1997), Capuzzo, Dolcetta, and Lions (1997), Crandall, Evans, and Lions (1984), Crandall, Ishii, and Lions (1982), Fleming and Soner (1993), and Lions (1982).

1.1 How a glider flies. A modern glider, or sailplane, is a remarkably sophisticated machine. It has a streamlined fiberglass fuselage, and carefully shaped wings, to cruise at speeds in the range of 100-150 km/hr, with a glide ratio approaching 40: with 1000 meters of altitude the aircraft can glide 40 km in still air. Cross-country flights of 300-500 km are routinely attained in ordinary conditions. With this level of performance human intuition and perception are not adequate to make strategic decisions, and today most racing gliders carry sophisticated computer and instrument systems to help optimize in-flight decisions. But the inputs to these systems still come largely from the pilot's observations of weather conditions around him and conditions to be expected on the course ahead.

The glider is launched into the air by a tow from a powered airplane (most frequently---launching on a ground-based cable is also possible). Once aloft, the pilot needs to find rising air in order to stay up, and to progress substantial distances cross-country. In the most common type of soaring, this rising air is generated by thermal convection in the atmospheric boundary layer: no hills and no wind is necessary. (Soaring on ridges, and on mountain waves, is also possible but is not discussed here.)

Thermal lift happens when a cold air mass comes in over warm ground. Instability in the air is triggered by local hot spots, and once released, the air parcels continue to rise until they meet a thermal inversion layer. If the air contains moisture, the water vapor condenses at an altitude determined by the initial humidity and the temperature profile; this condensation forms the puffy cumulus clouds typical of pleasant spring and summer days. From the pilot's point of view, these clouds are useful as markers of the tops of thermals, and they also impose an upper altitude limit since flight in clouds is illegal. This altitude is typically 1-2000 m above ground in temperate regions, and as much as 3-4000 m in the desert. By flying in circles within the rising air, the glider can climb right up to this maximum altitude, although of course while climbing no cross-country progress is being made. Clearly, in order to complete a 300 km flight, the glider will need to climb in many different thermals, and one of the biggest determinants of cross-country speed is the proper choice of thermals to use: different individual thermals have different strengths.

 Fig. 1.1. Gliding between thermals. Four gliders leave the thermal on the right at the same time; the trajectories shown cover the same length of elapsed time. Glider A stops in every weak thermal; he has low probability of landout but achieves a low total speed. Glider B heads toward the strong thermal at the speed of best glide angle, with minimum loss of height. Glider C flies faster: although he loses more height in the glide, the rapid climb more than compensates. Glider D flies even faster; unfortunately he is forced to land before he reaches the thermal. (Modeled on an original in Reichmann (1975).)

In such unstable conditions, nearly the entire air mass is in vertical motion of one sign or another; the organized structures described as thermals are only the largest and most conspicuous features. The air is of course moving down at some points in between the rising masses, but in addition, there are vertical motions of smaller magnitude both up and down. By exploiting these smaller motions during the "cruise" phase of flight, the pilot can greatly extend the distance of glide before it is again necessary to stop and climb. Generally speaking, the pilot slows down when passing through rising air and speeds up in sinking air; if the fluctuations are large enough then it can be possible to advance with almost no loss of altitude.

Since the air motion encountered in a particular flight is largely random, there is no guarantee that lift of the needed strength will be encountered soon enough. It is perfectly possible, and happens frequently, that the pilot will wind up landing in a farm field and will retrieve his aircraft by car. The probability of this happening is affected by the pilot's strategy: a cautious pilot can greatly reduce his risk of land-out, but at the cost of a certain substantial reduction in cross-country speed.

Soaring competitions are organized around the general objective of flying large distances at the fastest possible speed. Although the details of the rules are bewilderingly complex, for the mathematics it will be enough to assume that the task is to complete a circuit around a given set of turnpoints, in the shortest possible time. Furthermore, a penalty for landout is specified, which we crudely approximate in Section 3.1 below.

 Fig. 1.2. GPS trace from the 2001 Canadian Nationals competition, in xy projection. The course started at Rockton Airport, and rounded turnpoints at Tillsonburg, Waterford, and New Hamburg, before returning to Rockton. The glider does not follow precisely the straight lines of the course, but deviations are not too extreme (except on the last leg).
 Fig 1.3. The same trajectory as in Figure 1.2, with altitude. The horizontal axis x is distance remaining on course, around the remaining turnpoints. Vertical segments represent climbs in thermals; not all climbs go to the maximum alititude. In the cruise phases of flight, the trajectories are far from smooth, representing response to local up/down air motion.

1.2 Mathematics in soaring. Soaring is an especially fruitful area for mathematical analysis, much more than other sports such as sailing or sports that directly involve the human body, for two reasons: First, as mentioned above, the space and time scales are beyond direct human perception, and as a consequence the participants already carry computing equipment.

Second, the physical aspects can be characterized unusually well. Unlike a sailboat, a sailplane operates in a single fluid whose properties are very well understood. The performance of the aircraft at different speeds can be very accurately measured and is very reproducible. The largest area of uncertainty is the atmosphere itself, and the way in which this is modelled determines the nature of the mathematical problem to be solved.

Indeed, in addition to vast amounts of research on traditional aeronautical subjects such as aerodynamics and structures, there have been a few important contributions to the mathematical study of cross-country soaring flight itself.

In the 1950's, Paul MacCready, Jr., solved a large portion of the problem described above: in what conditions to switch from cruise to climb, and how to adjust cruise speed to local lift/sink. In 1956, he used this theory to become the first American to win a world championship. His theory was presented in a magazine article (MacCready 1958) and is extensively discussed and extended in many books (Reichmann 1975).

This theory involves a single number, the "MacReady setting", which is to be set equal to the rate of climb anticipated in the next thermal along the course. By a simple construction described in Section 2.1 below, this gives the local speed to fly in cruise mode, and is simultaneously the minimum thermal strength that should be accepted for climb. MacCready showed how the necessary speed calculation could be performed by a simple ring attached to one of the instruments, and now of course it is done digitally. Indeed, modern flight computers have a knob for the pilot to explicitly set the MacCready value, and as a function of this setting and the local lift or sink a needle indicates the optimal speed.

The defect, of course, is that the strength of the next thermal is not known with certainty. Of course, one has an idea of the typical strength for the day, but it is not guaranteed that one will actually encounter such a thermal before reaching ground. As a result, the optimal setting depends on altitude: when the aircraft is high it is likely that it may meet a strong thermal before being forced to land. As altitude decreases, this probability decreases, and the MacCready setting should be decreased, both to lower the threshhold of acceptable thermals and to fly more conservatively and slower in the cruise.

Various attempts have been made to incorporate probability into MacCready theory. Edwards (1963) constructed an "efficient frontier" of optimal soaring. In his model, thermals were all of the same strength, and were independently distributed in location; air was still in between. As a function of cruise speed, he could evaluate the realized average speed, as well as the probability of completing a flight of a specified length. His conclusion was that by slowing down slightly from the MacCready-optimal speed, a first-order reduction in landout probability could be obtained with only a second-order reduction in speed.

Cochrane (1999) has performed the most sophisticated analysis to date, which was the inspiration for the present paper. He performs a discrete-space dynamic programming algorithm: the horizontal axis is divided into one-mile blocks, and in each one the lift is chosen randomly and independently. For each mile, the optimal speed is chosen to minimise the expectation of time to complete the rest of the course.

In this model, the state variables are only distance remaining and altitude; since the lift value is chosen independently in each block, the current lift has no information content for future conditions. MacCready speed optimization is automatically built in. Solving this model numerically, he obtains specific quantitative profiles for the optimum MacCready value as a function of altitude and distance: as expected, the optimal value increases with altitude.

1.3. Outline of this paper. Our model may be viewed as a continuous version of Cochrane's. We model the lift as a continuous Markov process in the horizontal position variable: the lift profile is discovered as you fly through it. As a consequence, the local value of lift appears as an explicit state variable in our model, and the MacCready construction is independently tested. We find that it is substantially verified, with small corrections which are likely an artifact of our model.

Of course, the use of a Markov process represents an extremely strong assumption, representing almost complete ignorance about the patterns to be encountered ahead. In reality, the pilot has some form of partial information, such as characteristic thermal spacings, etc. But this is extremely difficult to capture in a mathematical model. Further, our model has only a single horizontal dimension: it does not permit the pilot to deviate from the course line in search of better conditions. This is likely our largest source of unrealism.

In Section 2 we present our mathematical model. We explain the basic features of the aircraft performance, and the MacCready construction, which are quite standard and quite reliable. Then we describe our Markov atmosphere model, which is chosen for simplicity and robustness.

In Section 3 we consider an important simplification of this model, in which the entire lift profile is known in advance. This case represents the opposite extreme of our true problem; it yields a first-order PDE which gives important insight into the behavior of solutions to the full problem.

In Section 4 we solve the full problem: we define the objective, which is the expectation of time to complete the course and derive, using the Bellman Dynamic Programming Principle, a degenerate second-order parabolic partial differential equation (PDE) that describes the optimal value function and the optimal control. Boundary conditions at the ground come from the landout penalty and at cloud base a state constraint is necessary. This nonlinear Hamilton-Jacobi-Bellman equation is surprisingly difficult to solve numerically, but techniques based on the theory of viscosity solutions give very good methods (see Barles and Souganidis 1991)). We exhibit solutions and assess the extent to which MacCready theory is satisfied.

## References

• M. Bardi and I. Capuzzo-Dolcetta (1997), Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Systems & Control: Foundations & Applications, Birkhäuser, Boston.
• G. Barles (1994), Solutions de Viscosité des Equations de Hamilton-Jacobi, Mathématiques & Applications, Springer-Verlag.
• G. Barles (1997), Convergence of numerical schemes for degenerate parabolic equations arising in finance theory, in Numerical Methods in Finance, L. C. G. Rogers and D. Talay, eds., Cambridge University Press, pp. 1-21.
• G. Barles, C. Daher, and M. Romano (1995), Convergence of numerical schemes for parabolic equations arising in finance theory, Math. Models Methods Appl. Sci., 5, pp. 125-143.
• G. Barles and B. Perthame (1988), Exit time problems in optimal control and vanishing viscosity method, SIAM J. Control Optim., 26, pp. 1133-1148.
• G. Barles and B. Perthame (1990), Comparison principle for Dirichlet type Hamilton-Jacobi equations and singular perturbations of degenerate elliptic equations, Appl. Math Optim., 21, pp. 21-44.
• G. Barles and E. Rouy (1998), A strong comparison result for the Bellman equation arising in stochastic exit time control problems and its applications, Comm. Partial Differential Equations, 23, pp. 1995-2033.
• G. Barles and P. E. Souganidis (1991), Convergence of approximation schemes for fully nonlinear second order equations, Asymptot. Anal., 4, pp. 271-283.
• A.-P. Blanc (1997), Deterministic exit time control problems with discontinuous exit costs, SIAM J. Control Optim., 35, pp. 399-434.
• I. Capuzzo Dolcetta and P.-L. Lions (1990), Hamilton-Jacobi equations with state constraints, Trans. Amer. Math. Soc., 318, pp. 643-683.
• I. Capuzzo Dolcetta and P. L. Lions, eds. (1997), Viscosity Solutions and Applications (Montecatini Terme 1995), Springer-Verlag.
• S. Chaumont (2004), A strong comparison result for viscosity solutions to Hamilton-Jacobi-Bellman equations with Dirichlet condition on a non-smooth boundary and application to parabolic problems. Preprint.
• J. H. Cochrane (1999), MacCready theory with uncertain lift and limited altitude, Technical Soaring, 23, pp. 88-96. Available at . http://gsbwww.uchicago.edu/fac/john.cochrane/research/Papers.
• M. G. Crandall, L. C. Evans, and P.-L. Lions (1984), Some properties of viscosity solutions of Hamilton-Jacobi equations, Trans. Amer. Math. Soc., 282, pp. 487-502.
• M. G. Crandall, H. Ishii, and P.-L. Lions (1992), User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc., 279, pp. 1-67.
• M. G. Crandall and P. L. Lions (1984), Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43, pp. 1-19.
• A. W. F. Edwards (1963), A stochastic cross-country or festina lente, Sailplane and Gliding, 14, pp. 12-14. Reprinted in Stochastic Geometry: A Tribute to the Memory of Rollo Davidson, E. F. Harding and D. G. Kendall, editors, John Wiley & Sons 1974.
• W. H. Fleming and H. M. Soner (1993), Controlled Markov Processes and Viscosity Solutions, Springer-Verlag.
• P. L. Lions (1982), Generalized solutions of Hamilton-Jacobi equations, Research Notes in Mathematics, Pitman, Boston.
• P. B. MacCready, Jr (1958), Optimum airspeed selector, Soaring, pp. 10-11.
• H. Reichmann (1978), Streckensegelflug, Motorbuch Verlag, 1975. Reprinted as Cross-Country Soaring by the Soaring Society of America.
• H. M. Soner (1986a), Optimal control with state-space constraint. I., SIAM J. Control Optim., 24, pp. 552-561.
• H. M. Soner (1986b), Optimal control with state-space constraint. II., SIAM J. Control Optim., 24, pp. 1110-1122.
• P. E. Souganidis (1985), Existence of viscosity solutions of Hamilton-Jacobi equations, J. Differential Equations, 56, pp. 345-390.
• A. Tourin and T. Zariphopoulou (1994), Numerical schemes for investment models with singular transactions, Comput. Econom., 7, pp. 287-307.