A computationally efficient algorithm for minimizing the flight time of an aircraft in a variable wind field has been invented. The algorithm, referred to as Neighboring Optimal Wind Routing (NOWR), is based upon neighboring-optimal- control (NOC) concepts and achieves minimum-time paths by adjusting aircraft heading according to wind conditions at an arbitrary number of wind measurement points along the flight route. The NOWR algorithm may either be used in a fast-time mode to compute minimum-time routes prior to flight, or may be used in a feedback mode to adjust aircraft heading in real-time. By traveling minimum-time routes instead of direct great-circle (direct) routes, flights across the United States can save an average of about 7 minutes, and as much as one hour of flight time during periods of strong jet-stream winds. The neighboring optimal routes computed via the NOWR technique have been shown to be within 1.5 percent of the absolute minimum-time routes for flights across the continental United States. On a typical 450-MHz Sun Ultra workstation, the NOWR algorithm produces complete minimum-time routes in less than 40 milliseconds. This corresponds to a rate of 25 optimal routes per second. The closest comparable optimization technique runs approximately 10 times slower.

ImageAirlines currently use various trial-and-error search techniques to determine which of a set of commonly traveled routes will minimize flight time.

These algorithms are too computationally expensive for use in real-time systems, or in systems where many optimal routes need to be computed in a . Instead of operating in real-time, airlines will typically plan a trajectory several hours in advance using wind forecasts. If winds change significantly from forecasts, the resulting flights will no longer be minimum-time. The need for a computationally efficient wind-optimal routing algorithm is even greater in the case of new air-traffic-control automation concepts. For air-traffic-control automation, thousands of wind-optimal routes may need to be computed and checked for conflicts in just a few minutes. These factors motivated the need for a more efficient wind-optimal routing algorithm. The NOWR algorithm is a special type of perturbation feed-back control as shown in the figure. The nominal winds are modeled as system states, and are considered to be zero magnitude so that the nominal trajectory solution is simply a great-circle route between origin and destination. The actual winds are input as perturbations to the nominal winds, multiplied by time-varying NOWR gains, and then fed back as heading command perturbations to achieve a minimum-time trajectory solution.

The NOWR gains are computed using techniques from the calculus of variations. Because the nominal route is a great circle, and because the nominal winds are zero magnitude, the NOWR feedback gains may be normalized and applied to flights at any airspeed between any origin and destination using coordinate rotations and simple time and distance scaling. This one-solution-fits-all aspect of NOWR makes it a very powerful and practical technique. The implementation procedure for NOWR is to either run a fast-time simulation to compute an optimal wind route, which can then be used as the basis for a filed flight plan, or one may use NOWR in real-time to achieve wind-optimal routes in a future free flight environment. The optimization process begins by first rotating coordinates so that the origin and destination points appear to be located along the equator of the rotated coordinate system. The distance unit is then scaled such that the distance from origin to destination is unity. The time unit is similarly scaled such that the airspeed of the aircraft is also unity. Because of this scaling, any flight between any two points appears to be mathematically similar.

The winds along the flight route are then obtained from the Rapid Update Cycle (RUC), a national gridded wind system developed at the National Oceanic and Atmospheric Administration. The NOWR algorithm may be adapted to use as many wind measurement points along the route as are desired, but in practice, about 10 or 15 points are sufficient. At each of these points, the predicted winds are multiplied by the NOWR gains to determine the optimal heading angles the aircraft should use to fly a minimum-time route. Once the optimal heading and the coordinates of the minimum-time route have been computed in the normalized coordinate system, the solution may be transformed back to real Earth coordinates through the inverse rotation equations. The reason why this perturbation scheme is so efficient is that it is a simple linear feedback algorithm involving just a few algebraic steps. The excellent performance of NOWR in practice is achieved because winds typically vary in a smooth manner and do not contain many sharp nonlinearities or discontinuities.

This work was done by Matthew R. Jardin of Ames Research Center. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.

Inquiries concerning rights for the commercial use of this invention should be addressed to the Patent Counsel, Ames Research Center, (650) 604-5104. Refer to ARC-14554.