Method of terrain following

FIELD AND BACKGROUND OF THE INVENTION

The present invention relates to terrain following and, more particularly, to real-time methods for designing a terrain-following flight profile.

A combat air vehicle, for example a bomber, must fly close to the ground in order to reach its target without being detected and intercepted by the enemy. The general problem of flying as close as possible to the ground along a given flight path is known as the "terrain-following" problem. Early terrain following systems used active on-board sensors to determine the aircraft's position and terrain clearance. Radiation emitted by such active sensors could be detected by the enemy. As early as 1981, Alson C. Woodward and Wayne M. Hoover ("Passive terrain following using stored map and global positioning system", <i>IEEE</i> NAECON 0547-3578/81/0000-0079) recognized that an aircraft with an on-board GPS receiver could follow a pre-stored reference terrain profile while using the GPS receiver to measure its own position. The aircraft actually follows a pre-stored reference flight profile that corresponds to the terrain profile. The design of the flight profile is an optimization problem: within the constraints of the aircraft's performance limitations, how close can the aircraft fly to the ground while following the flight path? See, for example, Ping Lu and Bion L. Pierson, "Optimal aircraft terrain-following analysis and trajectory generation", <i>Journal of Guidance, Control and Dynamics</i> vol. 18 no. 3, May-June 1995. Usually, this optimization problem is solved iteratively.

One problem with the use of a pre-stored reference flight profile is that the actual flight profile followed by the aircraft usually deviates from the reference flight profile because of navigational uncertainties. These navigational uncertainties could be accounted for by computing the reference flight profile with respect to an "inflated" reference terrain profile, as described below; but at the cost of obtaining a suboptimal flight profile. The flight profile would be suboptimal because inflation in advance of the reference terrain profile necessarily would have to be based on "worst case" navigational uncertainties. There is thus a widely recognized need for, and it would be highly advantageous to have, a method for real time computation of a reference flight profile that would account for actual navigational uncertainties and so be less suboptimal than a reference flight profile computed in advance.

DEFINITIONS

The present invention relates to terrain-following guidance of an <i>air vehicle.</i> The term <i>air vehicle</i> is understood herein to include any vehicle capable of flight, including in particular manned aircraft and unmanned aerial vehicles (UAVs).

The <i>trajectory</i> followed by an air vehicle is a line in three-dimensional (<i>x, y, z</i>) space. The <i>flight path</i> of the air vehicle is a projection of the trajectory onto a horizontal (<i>x, y</i>) plane. The <i>flight profile</i> of the air vehicle is the vertical (<i>z</i>) coordinate of the trajectory as a function of distance <i>s</i> along the flight path.

The problem of optimal design of the trajectory as a whole is the <i>terrain avoidance</i> problem. This problem is more general than and beyond the scope of the present invention, although the present invention could be used as a component of the solution of the terrain avoidance problem. As discussed above, the problem addressed by the present invention is the <i>terrain following</i> problem: given an <i>a priori</i> flight path, what is the optimal flight profile?

A <i>terrain profile</i> is an estimate of the ground elevation as a function of <i>s</i> along the flight path. The flight profile is designed with reference to the corresponding terrain profile. Typically, the terrain profile is <i>inflated</i> to provide a safety margin. The present invention is directed towards methods of transforming a terrain profile into a flight profile. That the flight profile is a <i>terrain-following</i> flight profile means that the flight profile is designed to parallel the terrain as closely as possible within the relevant constraints.

The terrain profile that is transformed to the desired flight profile is defined with reference to a given flight path. More generally, to allow a manned air vehicle freedom of horizontal maneuver around the given flight path, the terrain profile is defined, with reference to a <i>flight corridor</i> of a given finite horizontal width about the flight path, as an estimate, as a function of <i>s</i>, of the maximum ground elevation along and to the sides of the flight path. The process of inflating the terrain profile takes into account the uncertainty in the lateral displacement of the air vehicle from the nominal flight path. Note that a flight path can be viewed as a special case of a flight corridor, to wit, a flight corridor of infinitesimal width.

Given a function <i>f</i>(<i>s</i>), an <i>envelope</i> of the function is a function <i>g</i>(<i>s</i>) that is equal to <i>f</i>(<i>s</i>) at selected points s and otherwise is greater than <i>f</i>(<i>s</i>). In the discussion below, the filtered terrain profile is an envelope of the inflated terrain profile and the flight profile is constructed by constructing successive envelopes of the filtered terrain profile.

Comparisons of quantities herein are algebraic comparisons. That a negative slope tanγ is at most about as small as a minimum slope tanγ_<i>min</i> means that tanγ is substantially bounded from below by tanγ_<i>min</i>. Similarly, that a negative vertical acceleration <i>a</i>_<i>Z</i> is at most about as small as a minimum negative vertical acceleration <i>a</i>_<i>Zmin</i> means that <i>a</i>_<i>Z</i> is substantially bounded from below by <i>a</i>_<i>Zmin</i>.

The terms "elevation" and 'altitude" are used interchangeably herein.

SUMMARY OF THE INVENTION

The present invention provides a direct, non-iterative method of terrain-following flight profile design that is fast enough to be implemented in real time and so to be based on actual navigational uncertainties and on instantaneous values of air vehicle performance parameters rather than on worst case navigational uncertainties and on worst case values of air vehicle performance parameters. Because the present invention operates in real time, the present invention can take into account the changes in the performance characteristics of the air vehicle as the air vehicle flies along the trajectory whose altitude is defined by the flight profile.

The computations of the present invention do not require the fitting of a functional approximation to a discrete digital terrain map.

The present invention allows a tradeoff, in flight profile design, between the closeness with which the air vehicle follows the terrain and the gentleness of the maneuvers executed by the air vehicle.

According to the present invention there is provided a method of designing a terrain-following flight profile for an air vehicle, including the steps of: (a) providing a terrain profile; and (b) transforming the terrain profile into the terrain-following flight profile in accordance with at least one performance parameter of the air vehicle.

According to the present invention there is provided a method of designing a terrain-following flight profile for an air vehicle, including the steps of: (a) defining a terrain profile with reference to a flight corridor; (b) inflating the terrain profile, thereby providing an inflated terrain profile; (c) filtering the inflated terrain profile, thereby providing a filtered terrain profile; (d) constructing a first envelope for the filtered terrain profile, the first envelope being constrained so that every positive slope of the first envelope is at most about as great as a maximum climb slope of the air vehicle and every negative slope of the first envelope is at most about as small as a minimum dive slope of the air vehicle; (e) constructing a second envelope for the first envelope, the second envelope being constrained so that if the air vehicle flies at a given speed according to the second envelope, every negative vertical acceleration of the air vehicle is at most about as small as a minimum negative vertical acceleration of the air vehicle; and (f) constructing a third envelope for the second envelope, the third envelope being constrained so that if the air vehicle flies at the given speed according to the third envelope, every positive vertical acceleration of the air vehicle is at most about as great as a maximum positive vertical acceleration of the air vehicle.

According to the present invention there is provided a method of designing a terrain-following flight profile for an air vehicle, including the steps of: for each of a plurality of frames: (a) providing a respective terrain profile; and (b) transforming the respective terrain profile into at least a portion of the terrain-following flight profile in accordance with at least one performance parameter of the air vehicle.

According to the present invention there is provided a method of designing a terrain-following flight profile for an air vehicle, including the steps of: (a) providing a terrain profile; and (b) filtering the terrain profile by steps including: (i) selecting a filter length, and (ii) constructing an envelope of the terrain profile in accordance with the filter length, the terrain-following flight profile then being based on the envelope.

According to the present invention there is provided a method of navigating an air vehicle within a flight corridor, including the steps of: (a) partitioning the flight corridor among a set of at least one frame; and (b) as the air vehicle enters each of the at least one frame: (i) defining a respective terrain profile with respect to a respective portion of the flight corridor that lies within the each frame, and (ii) transforming the respective terrain profile into a respective flight profile for the each frame in accordance with at least one performance parameter of the air vehicle.

According to the present invention there is provided an air vehicle including: (a) a memory for storing a map; (b) a processor for: (i) partitioning a flight corridor among a set of at least one frame, and (ii) as the air vehicle enters each of the at least one frame: (A) based on the map, providing a respective terrain profile for a respective portion of the flight corridor that lies within the each frame, and (B) transforming the respective terrain profile into a respective terrain-following flight profile for the each frame in accordance with at least one performance parameter of the air vehicle; and (c) a propulsion and guidance system for flying the air vehicle within the flight corridor in accordance with the at least one respective flight profile.

According to the present invention there is provided a method of designing a terrain-following flight path for an air vehicle, including the steps of: (a) providing a terrain profile; and (b) transforming the terrain profile into the terrain-following flight path in accordance with a desired tradeoff between a closeness with which the terrain-following flight path tracks the terrain profile and an ease of maneuver of the air vehicle.

The present invention has two principle aspects. The first aspect is the non-iterative transformation of a terrain profile into a terrain-following flight profile, in accordance with one or more air vehicle performance parameters. The second aspect is low-pass spatial filtering of the terrain profile prior to the construction of the flight profile. Together, these two aspects of the present invention provide the ability to trade off between the closeness with which the air vehicle follows the terrain and the gentleness of the maneuvers executed by the air vehicle.

Preferably, the terrain profile is defined with reference to a flight corridor. Indeed, the first aspect of the present invention can be viewed as a method of navigating the air vehicle within a given flight corridor. As noted above, in the case of an unmanned air vehicle; the "flight corridor" is actually a flight path.

Preferably, the terrain profile is transformed into the flight profile in a manner that directly adapts the terrain profile to the performance parameters of the air vehicle. This is in contrast to prior art methods that obtain a flight profile by fitting functions such as polynomials to the terrain profile. The difference between the direct adaptation of the present invention and the indirect adaptation of those prior art methods can be appreciated by considering what kind of flight profile is produced from a flat or gently varying terrain profile. The prior art methods produce a flight profile whose shape reflects both the shape of the terrain profile and the shapes of the functions that are fitted to the terrain profile. The method of the present invention produces a flight profile that is exactly parallel to the terrain profile.

Preferably, the flight profile is constructed as an envelope of the terrain profile that is constrained in accordance with at least one performance parameter of the air vehicle. Preferably, four performance parameters are accounted for: a maximum allowed climb slope, a minimum allowed dive slope, a minimum allowed negative vertical acceleration as the air vehicle flies at a given speed, and a maximum allowed positive vertical acceleration as the air vehicle flies at the given speed. Preferably, the flight profile is constructed in three steps. In the first step, a first envelope of the terrain profile is constructed subject to the constraints that every positive slope of the first envelope is at most about as great as the maximum allowed climb slope and that every negative slope of the first envelope is at most about as small as the minimum allowed dive slope. In the second step, a second envelope is constructed as an envelope of the first envelope, subject to the same constraints as the first envelope, and also to the constraint that if the air vehicle were to fly at the given speed according to the second envelope as the flight profile, every negative vertical acceleration of the air vehicle would be at most about as small as the minimum allowed negative vertical acceleration. In the third step, a third envelope is constructed as an envelope of the second envelope, subject to the same constraints as the first envelope and also to the constraint that if the air vehicle were to fly at the given speed according to the third envelope as the flight profile, every positive vertical acceleration of the air vehicle would be at most about as great as the maximum allowed positive vertical acceleration. The third envelope is the desired flight profile.

Preferably, the flight profile is constructed in real time, in the sense that the flight profile is constructed while the air vehicle flies along a flight path corresponding to at least a portion of the terrain profile.

Preferably, the terrain profile is an inflated terrain profile.

Preferably, the terrain profile is filtered prior to the construction of the flight profile, also in real time, in the sense that the filtering is done while the air vehicle flies along a flight path corresponding to at least a portion of the terrain profile. As noted above, the preferred filtering method is itself an independent aspect of the present invention. A filter length is selected, and an envelope of the terrain profile is constructed in accordance with the filter length and is substituted for the terrain profile in the construction of the flight profile. Preferably, this envelope is piecewise linear. More preferably, this envelope is constructed by selecting a plurality of points of the terrain profile and connecting neighboring pairs of points with straight line segments. Most preferably, the points are selected, starting with a first point of the terrain profile as a pivot point, by downwardly pivoting a filtering line segment, whose horizontal extent is equal to the filter length, _about the pivot point until the filtering line segment contacts the terrain profile, selecting the last point at which the filtering line segment contacts the terrain profile, moving the pivot point to the last point at which the filtering line segment contacts the terrain profile, and repeating the process until the last point at which the filtering line segment contacts the terrain profile is the last point of the terrain profile.

From another point of view, the two aspects of the present invention can be considered to be stages in the transformation of a terrain profile into a terrain-following flight path in accordance with a desired tradeoff between the closeness with which the flight path tracks the terrain profile and the ease of maneuver of the air vehicle as the air vehicle attempts to fly according to the flight path. In particular, the filter length of the second aspect preferably is selected in accordance with the desired tradeoff,

Most commonly, the flight path is partitioned among a plurality of frames, a respective terrain profile is provided for each frame as the air vehicle enters the frame, and a corresponding respective flight profile is constructed as described above for each frame. The overall flight profile then is a concatenation of the individual respective flight profiles. Typically, the frames overlap, and this "concatenation" actually is a concatenation of the initial portions of the individual respective flight profiles, until the last frame is reached, at which point the entire respective flight profile of the last frame is concatenated to the overall composite flight profile. The air vehicle then is flown in accordance with the concatenated flight profile.

Preferably, the providing of the respective terrain profile of each frame is done by providing a digital terrain map that includes a plurality of elevations and then, at each of a plurality of points along a nominal flight path within the frame, determining a maximum elevation within an uncertainty interval around that point. The resulting set of maximum elevations, as a function of the points along the nominal flight path, is the desired terrain profile.

An air vehicle of the present invention includes an on-board memory, an on-board processor, and a propulsion and guidance system. The memory is used to store a map. The processor partitions the flight path among a set of frames. As the air vehicle enters each frame, the processor provides a respective terrain profile for the respective portion of a flight corridor that lies within the frame. This terrain profile is based on the map that is stored in the memory. Then the processor transforms the respective terrain profile into a respective flight profile for the frame in accordance with at least one performance parameter of the air vehicle. The propulsion and guidance system then is used to fly the air vehicle along the flight path in accordance with the flight profile until the next frame is reached.

Preferably, the map is a digital terrain map.

Preferably, each flight profile is a terrain-following flight profile.

Preferably, for example if the air vehicle is unmanned, the "flight corridor" is actually a flight path.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein: <ul id="ul0001" list-style="none" compact="compact"><li>FIGs 1A and 1B illustrate the coordinate system used herein to describe the method of the present invention;</li><li>FIGs. 2A-2C illustrate the geometric construction that is used to filter a terrain profile;</li><li>FIG. 2D shows a terrain profile before and after filtering;</li><li>FIGs. 3A-3D show the templates that are used to construct the flight profile shaping envelopes;</li><li>FIG. 4A illustrates the replacement of overly steep negative slopes with negative slopes that are consistent with a minimum dive slope;</li><li>FIG. 4B illustrates the replacement of overly steep positive slopes with positive slopes that are consistent with a maximum climb slope;</li><li>FIGs. 5A and 5B illustrate the replacement of excessive downward curvatures with downward curvatures that are consistent with a minimum vertical acceleration;</li><li>FIG. 6 illustrates the launching of a piecewise linear approximation of the template of FIG. 3D;</li><li>FIGs. 7A and 7B illustrate the replacement of excessive upward curvatures with upward curvatures that are consistent with a maximum upward acceleration;</li><li>FIG. 8 illustrates a problematic boundary condition that creates a fictitious local elevation maximum;</li><li>FIG. 9 illustrates a problematic interaction, between two successive frames, that is accounted for by an appropriate choice of frame length;</li><li>FIGs. 10A-10C show respective portions of a terrain profile and three corresponding flight profiles computed for a terrain profile filtered with filters of various lengths;</li><li>FIG. 11 shows plots of mean clearances vs. filter length for the terrain profile of FIGs. 10A-10C;</li><li>FIG. 12 is a schematic diagram of an air vehicle of the present invention.</li></ul>

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention is of a method of designing a terrain-following flight profile.

The principles and-operation of terrain following according to the present invention may be better understood with reference to the drawings and the accompanying description.

Referring now to the drawings, Figures 1A and 1B illustrate the coordinate systems used herein. Figure 1A shows a trajectory <b>10</b> of an air vehicle flying in a three-dimensional space defined by Cartesian coordinates <b><i>x, y</i></b> and <i><b>z. z</b></i> is the altitude coordinate. <b><i>x</i></b> and <b><i>y</i></b> are geographic coordinates, for example north and east as in the Universal Transverse Mercator grid. Note that this coordinate system is a left-handed coordinate system. The corresponding flight path <b>12</b> is the projection of trajectory <b>10</b> onto the <b><i>x</i>,<i>y</i></b> plane. Figure 1B shows the corresponding flight profile <b>14:</b> the <b><i>z</i>-</b> coordinate of trajectory <b>10</b> as a function of horizontal distance <b><i>s</i></b> along flight path <b>12</b>. The air vehicle flies in the direction of increasing <b><i>s</i></b>, which in the relevant Figures is from left to right.

Typically, the various profiles (terrain profiles, flight profile) considered herein are sampled at discrete sample points <b><i>s</i></b>_{<b><i>i</i></b>} along flight path <b>12.</b> In the subsequent discussion, these sample points usually are assumed to be a constant interval <b><i>ds</i></b> apart. It will be clear to those ordinarily skilled in the art how to modify the subsequent discussion to account for irregular sampling of the distance coordinate <b><i>s</i></b>.

Figure 1B also shows that flight path <b>12</b> is partitioned among a set of overlapping frames <b><i>F</i></b>_<b>1</b> through <b><i>F</i></b>_{<b><i>N</i></b>}. As the air vehicle flies along flight path <b>12,</b> the air vehicle first enters frame <b><i>F</i></b>_<b>1</b>, then frame <b><i>F</i></b>_<b>2</b>, etc. In the subsequent discussion, the air vehicle is considered to be flying in the local frame with the highest index. So, for example, after the air vehicle enters frame <b><i>F</i></b>_<b>2</b>, the air vehicle is considered to be flying in frame <b><i>F</i></b>_{<b><i>2</i></b>} even though the <b><i>s</i></b>-coordinate of the air vehicle is still within frame <b><i>F</i></b>_<b>1</b>.

Typically, the interval between the left end of a frame and the left end of the next frame is a constant distance Δ<b><i>s</i></b> along flight path <b>12.</b> Alternatively, the interval between the left end of every frame (other than the last frame) and the left end of the next frame is chosen so that the air vehicle spends the same time interval <b><i>Δt</i></b> flying from the left end of one frame to the left end of the next frame. <b><i>Δs</i></b> is selected in accordance with factors that include terrain complexity, the computational power available to the air vehicle, the rate of increase of navigational uncertainty and the frequency of navigational updates. As discussed below, all the frames except for the frames at the end of flight path <b>12</b> are given a common length chosen in advance in accordance with regional terrain roughness.

The problem addressed herein is the terrain-following problem: given a terrain profile, <i>i</i>.<i>e</i>., an estimate of terrain altitude along flight path <b>12,</b> design a trajectory <b>10</b> for an air vehicle to fly as close as is feasible to the terrain along flight path <b>12.</b> Because flight path <b>12</b> is given in advance (and indeed is fixed <i>a priori</i> if the air vehicle is unmanned), this is equivalent to designing a flight profile <b>14</b> for the air vehicle.

More specifically, the present invention addresses the real-time terrain-following problem. Flight path <b>12</b> is a <i>reference</i> flight path, i.e., a nominal flight path that the air vehicle attempts to follow. Because of navigational uncertainties and similar sources of error, the actual flight path followed by the air vehicle, <i>i</i>.<i>e</i>., the projection to a horizontal plane of the actual trajectory flown by the air vehicle, only approximates the reference flight path. Similarly, the flight profile provided to the air vehicle by the present invention is a <i>reference</i> flight profile that is only approximated by the altitude coordinate of the actual trajectory flown by the air vehicle. The present invention provides the air vehicle with a reference flight profile that is adapted in real time to the contingencies of flight. This is accomplished in three phases: terrain profile inflation, terrain profile filtering and flight profile shaping. For each frame, all three phases are effected as soon as the air vehicle enters the frame, to provide a reference flight profile that the air vehicle attempts to follow until the air vehicle enters the next frame.

Phase I: Terrain Profile Inflation

The input to this phase is the reference flight path, a digital terrain map of the region that includes the reference flight path, and, for a manned air vehicle, the width of the allowed flight corridor to the sides of the reference flight path. If it could be guaranteed that both the altitude and the geographical coordinates of the air vehicle were always known with perfect accuracy, and that the digital terrain map was perfectly accurate, then the terrain altitude along the reference flight path could be used as the terrain profile that is input to the second and third phases. Because neither the altitude of the air vehicle nor the geographic coordinates of the air vehicle nor the terrain altitude are known with perfect accuracy, this nominal terrain profile must be "inflated" to guarantee that the air vehicle does not hit the ground.

The inflated terrain profile is constructed in two steps. The first step accounts for errors in lateral position. The second step accounts for altitude errors.

In the first step, a horizontal corridor is defined along the reference flight path. The width of the horizontal corridor is the root-mean-square sum of all the errors that contribute to the lateral positional uncertainty of the air vehicle, plus, in the case of a manned air vehicle, the width of the allowed flight corridor. At each one of a set of equally spaced points s along the reference flight path, the digital terrain map is sampled in a region (usually a rectangular or elliptical region) centered on at that point <i>s</i>. The maximum value of the digital terrain map within this region is taken as the terrain altitude at point <i>s</i>.

In the second step, at each point <i>s</i>, the root-mean-square sum, of all the errors that contribute to the vertical positional uncertainty of the air vehicle, is added to the terrain altitude from the first step. The resulting terrain profile is the "inflated" terrain profile that is input to the second phase.

The terrain profile is inflated in real time to exploit the following feature of air vehicle navigation. Generally, the contribution of navigational uncertainty to the width of the horizontal corridor of the first step tends to grow with time. Therefore, the width of the horizontal corridor of the first step also tends to grow with time. Occasionally, the air vehicle receives a relatively accurate navigational update that reduces the lateral navigational uncertainty of the air vehicle. For example, the air vehicle may use, for navigation, an on-board self-contained navigational instrument such as an inertial measurement unit, supplemented by occasional updates from a navigational instrument such as a GPS receiver that relies on external signals. When the accurate navigational update is received, the width of the horizontal corridor shrinks accordingly, as does the range of digital terrain map altitudes that contributes to the calculation of maximum terrain altitude at each point s in the first step. As a result, the inflation of the terrain profile becomes less severe, and the air vehicle is enabled to follow the terrain more closely than would have been possible without real-time inflation.

The relatively accurate navigational update often indicates that the air vehicle is farther from the reference flight path than was indicated by the self-contained navigational instrument. When this occurs, the aircraft is flown so as to approach the reference flight path. The horizontal corridor also is modified to account for the deviation of the actual lateral position of the air vehicle from the reference flight path.

Phase II: Terrain Profile Filtering

The input to this phase is the inflated terrain profile that is output by phase I.

The purpose of this phase is to allow a tradeoff between close following of the terrain and ease of maneuver. For this purpose, the inflated terrain profile is filtered. The length of the filter determines the tradeoff, with a short filter favoring close following of the terrain and a long filter favoring ease of maneuver.

Figure 2A illustrates the geometric construction that is used to transform an inflated terrain profile into a filtered terrain profile. Figure 2A shows a 2 km long segment <b>22</b> of an inflated terrain profile <b><i>H(s)</i></b> along with a filtering line segment <b>24.</b> Filtering line segment <b>24</b> is constructed to have a horizontal extent equal to a preselected filter length, which in this example is 2 km. The left end of terrain profile segment <b>22</b> is used as a pivot point <b>26,</b> at which the left end of filtering line segment <b>24</b> is attached. Filtering line segment <b>24</b> is pivoted downward about pivot point <b>26,</b> as indicated by the arrow, while maintaining the 2 km horizontal extent of filtering line segment <b>24</b> at the preselected filter length, until filtering line segment <b>24</b> contacts terrain profile segment <b>22</b> to the right of pivot point <b>26</b>. The portion of filtering line segment <b>24</b> between pivot point <b>26</b> and the last point of contact <b>28</b> between terrain profile segment <b>22</b> and filtering line segment <b>24</b> then becomes a segment of a piecewise linear envelope of terrain profile <b><i>H</i></b>(<b><i>s</i></b>). In the example shown in Figure 2A, filtering line segment <b>24</b> first contacts terrain profile segment <b>22</b> at only one point to the right of pivot point <b>26.</b> Figure 2B shows a terrain profile segment <b>22'</b> such that when filtering line segment <b>24</b> first contacts terrain profile segment <b>22'</b>, this contact is at two points <b>30</b> and <b>32.</b> In this case, the portion of filtering line segment <b>24</b> between pivot point <b>26</b> and the rightmost point of contact (point <b>32)</b> is taken as the corresponding line segment of the piecewise linear envelope. Point <b>32</b> then becomes the next pivot point, for constructing the next line segment of the piecewise linear envelope. Figure 2C shows a terrain profile segment <b>22"</b> that is similar to terrain profile segment <b>22'</b> except that instead of point <b>32</b>, terrain profile segment <b>22"</b> has a point <b>32'</b> that is below filtering line segment <b>24</b> when filtering line segment <b>24</b> reaches point <b>30.</b> In this case, the portion of filtering line segment <b>24</b> between pivot point <b>26</b> and the single point of contact (point <b>30</b>) is taken as the corresponding line segment of the piecewise linear envelope; and point <b>30</b> then becomes the next pivot point.

In Figure 2D, solid line <b>40</b> is an inflated terrain profile <b><i>H(s)</i></b> of which terrain profile segment <b>22</b> is an initial portion. Dashed line segments <b>42, 44, 46, 48</b> and <b>50</b> are line segments of a piecewise linear envelope of terrain profile <b>40</b>, constructed as described above. Line segment <b>42</b> is constructed as described above in connection with Figure 2A. Line segment <b>44</b> is constructed by pivoting filtering line segment <b>24</b> downwards about point <b>28</b> as a pivot point until filtering line segment <b>24</b> contacts terrain profile <b>40</b> at point <b>34</b>. Line segment <b>46</b> is constructed by pivoting filtering line segment <b>24</b> downwards about point <b>34</b> as a pivot point until filtering line segment <b>24</b> lies tangent to terrain profile <b>40</b> between points <b>34</b> and <b>36</b> (line segment <b>46</b> is illustrated in Figure 2D as slightly displaced from terrain profile <b>40</b>, for clarity). Line segment <b>48</b> is constructed by pivoting filtering line segment <b>24</b> downwards about point <b>36</b> as a pivot point until filtering line segment <b>24</b> contacts terrain profile <b>40</b> at point <b>38.</b> Line segment <b>50</b> is constructed by pivoting filtering line segment <b>24</b> downwards about point <b>38</b> until filtering line segment <b>24</b> contacts terrain profile <b>40</b> at a point (not shown) to the right of the portion of terrain profile <b>40</b> that is illustrated in Figure 2D. The piecewise linear envelope defined by line segments <b>42, 44, 46, 48, 50</b> and other line segments (not shown) to the right of the portion of terrain profile <b>40</b> that is illustrated in Figure 2D constitute a filtered terrain profile.

For an inflated terrain profile that is defined as a set of discrete elevations {<b><i>H</i></b>_{<b><i>n</i></b>}} at a set of discrete sample points {<b><i>s</i></b>_{<b><i>n</i></b>}}, the filtering algorithm, given a filter length <b><i>L</i></b>, is as follows:

Starting at the first sample point (<b><i>n</i></b>=1), consider all sample points <b><i>s</i></b>_{<b><i>j&gt;n</i></b>} such that <b><i>s</i></b>_{<b><i>j</i></b>}<b><i>-s</i></b>_{<b><i>n</i></b>}<b><i>≤L</i></b>. At each such sample point <b><i>s</i></b>_{<b><i>j</i></b>}, compute the slope <b><i>m</i></b>_{<b><i>j</i></b>}=(<b><i>H</i></b>_{<b><i>j</i></b>}<b><i>-H</i></b>_{<b><i>n</i></b>})/(<b><i>s</i></b>_{<b><i>j</i></b>}<b><i>-s</i></b>_{<b><i>n</i></b>}). Let <b><i>jmax</i></b> be the index of the maximum slope. Draw a line segment from (<b><i>s</i></b>_{<b><i>n</i></b>},<b><i>H</i></b>_{<b><i>n</i></b>}) to (<b><i>s</i></b>_{<b><i>jmax</i></b>},<b><i>H</i></b>_{<b><i>jmax</i></b>}). This line segment is a segment of the piecewise linear envelope that is the desired filtered terrain profile. Replace <b><i>n</i></b> with <b><i>jmax</i></b> and continue until the end of the current frame is reached.

Terrain profile filtering is performed on a per-frame basis. To preserve continuity of the filtered terrain profile, upon entering a new frame, if the filtered terrain profile of the old frame is higher than the first point of the inflated terrain profile of the new frame (which first point otherwise would be used as the first pivot point of the new frame), the point at which the filtered terrain profile of the old frame enters the new frame is used as the first pivot point of the new frame.

Phase III: Flight Profile Shaping

The input to this phase is the filtered terrain profile that is output by phase II.

This phase consists of three subphases. In the first subphase, an envelope of the input filtered terrain profile is constructed. In the second and third subphases, respective envelopes of the envelopes from the immediately preceding subphases are constructed. The envelope constructed by the third subphase is the desired flight profile.

The three envelopes are constructed to adapt the respective inputs to real time performance parameters of the air vehicle. The first subphase adapts the filtered terrain profile to the maximum climb angle γ_{<b><i>max</i></b>} and the minimum dive angle γ_{<b><i>min</i></b>}, or equivalently, to the maximum climb slope tanγ_{<b><i>max</i></b>} and the minimum dive slope tanγ_{<b><i>min</i></b>} of the air vehicle. The second subphase adapts the output of the first subphase to the horizontal velocity component <b><i>V</i></b> of the air vehicle in the current frame and to the minimum negative vertical acceleration <b><i>a</i></b>_{<b><i>Zmin</i></b>} of the air vehicle, in a manner that guarantees that the air vehicle flies horizontally above significant local elevation peaks. The third subphase adapts the output of the second subphase to the horizontal velocity component <b><i>V</i></b> of the air vehicle in the current frame and to the maximum positive vertical acceleration <b><i>a</i></b>_{<b><i>Zmax</i></b>} of the air vehicle.

The three envelopes are constructed using the templates illustrated in Figures 3A-3D. The first subphase uses templates <b>52</b> and <b>54.</b> Template <b>52</b> is a straight line with a slope tanγ_{<b><i>min</i></b>}. Template <b>54</b> is a straight line with a slope tanγ_{<b><i>max</i></b>}. The second subphase uses two templates <b>56</b> and <b>58</b> that are, respectively, the descending and ascending branches of a concave downward curve <b>60</b>. The central portion of curve <b>60</b> is the concave downward parabolic trajectory flown by the air vehicle as the horizontal component of the air vehicle's velocity is <b><i>V</i></b> and as the air vehicle accelerates downward with a constant vertical acceleration of <b><i>a</i></b>_{<b><i>Zmin</i></b>}. The parabola continues rightward until the slope of the parabola reaches tanγ_{<b><i>min</i></b>}. To the right of that point, the slope of the descending branch of curve <b>60</b> is a constant tanγ_{<b><i>min</i></b>}. The parabola continues leftward until the slope of the parabola reaches tanγ_{<b><i>max</i></b>}. To the left of that point, the slope of the ascending branch of curve <b>60</b> is a constant tanγ_{<b><i>max</i></b>}. The third subphase uses a template <b>62</b> that is a concave upward curve. The central portion of template <b>62</b> is the concave upward parabolic trajectory flown by the air vehicle as the horizontal component of the air vehicle's velocity is <b><i>V</i></b> and as the air vehicle accelerates upward with a constant vertical acceleration of <b><i>a</i></b>_{<b><i>Zmax</i></b>}. The parabola continues rightward until the slope of the parabola reaches tanγ_{<b><i>max</i></b>}. To the right of that point, the slope of the ascending branch of template <b>62</b> is a constant tanγ_{<b><i>max</i></b>}. The parabola continues leftward until the slope of the parabola reaches tanγ_{<b><i>min</i></b>}. To the left of that point, the slope of the descending branch of template <b>62</b> is a constant tanγ_{<b><i>min</i></b>}.

The performance parameters to which the subphases adapt their respective envelopes often vary in time. For example, as an air vehicle consumes fuel and so becomes lighter, its maximum climb slope tanγ_{<b><i>max</i></b>} and its maximum positive vertical acceleration <b><i>a</i></b>_{<b><i>Zmax</i></b>} may increase. The values of the performance parameters actually used to shape the flight profile of any given frame are the values of the performance parameters as the air vehicle enters the frame.

In the subsequent discussion, it will be assumed that the input filtered terrain profile and the various envelope functions are defined as a set of discrete elevations {<b><i>h</i></b>_{<b><i>n</i></b>}} at discrete sampling points {<b><i>s</i></b>_{<b><i>n</i></b>}} a fixed distance <b><i>ds</i></b> apart. It will be obvious to those skilled in the art how to generalize this discussion to irregularly spaced sample points and to other representations, for example piecewise continuous polynomial representations of higher order than first order, of the terrain profile and of the envelope functions.

In the first subphase, positive slopes that are steeper than the air vehicle's maximum climb slope tanγ_{<b><i>max</i></b>}, and negative slopes that are steeper (in absolute value) than the air vehicle's minimum dive slope tanγ_{<b><i>min</i></b>}, are replaced with slopes that are consistent with the air vehicle's maximum climb slope and minimum dive slope. This is done in two passes.

The input to the first pass is the filtered terrain profile. Conceptually, in the first pass, template <b>52</b> is swept across the filtered terrain profile in the direction of decreasing <b><i>s</i></b> (right to left), and whenever template <b>52</b> contacts the filtered terrain profile at two points, the portion of the filtered terrain profile between the two points is raised to match template <b>52</b>.

The corresponding algebraic algorithm is as follows. The slope to the right of each sample point <b><i>s</i></b>_{<b><i>n</i></b>} is <b><i>h'</i></b>_{<b><i>n</i></b>}=(<b><i>h</i></b>_{<b><i>n</i></b>}₊₁-<b><i>h</i></b>_{<b><i>n</i></b>})/<b><i>ds</i></b>, If <b><i>h'</i></b>_{<b><i>n</i></b>}&lt;tanγ_{<b><i>min</i></b>} then the elevations <b><i>h</i></b>_{<b><i>n+j</i></b>} to the right of sample point <b><i>s</i></b>_{<b><i>n</i></b>} are replaced with <b><i>h</i></b>_{<b><i>n</i></b>}<b>+<i>j</i></b>*<b><i>ds</i></b>*tanγ_{<b><i>min</i></b>} until a sample point <b><i>s</i></b>_{<b><i>n+k</i></b>} is found such that the input elevation <b><i>h</i></b>_{<b><i>n+k</i></b>} there is greater than the replacement value. Figure 4A shows a filtered terrain profile <b>64</b> with two elevations <b>66</b> and <b>68</b> such that the negative slopes immediately to the right of these elevations are less than tanγ_{<b><i>min</i></b>}. The elevations to the right of elevation <b>66</b> are replaced with the elevations marked by the triangles. Note that this construction need not be done for elevation <b>68</b> because the replacement elevations derived from elevation <b>66</b> are greater than the replacement elevations derived from elevation <b>68</b> in any case.

The input to the second pass is the output of the first pass. Conceptually, in the second pass, template <b>54</b> is swept across the output from the first pass in the direction of increasing <b><i>s</i></b> (left to right), and whenever template <b>54</b> contacts the output from the first pass at two points, the portion of the output from the first pass that lies between the two points is raised to match template <b>54</b>.

The algebraic algorithm of the second pass is similar to the algebraic algorithm of the first pass, but considers the slopes to the left of the sample points. The slope to the left of each sample point <b><i>s</i></b>_{<b><i>n</i></b>} is <b><i>h'</i></b>_{<b><i>n</i></b>}=(<b><i>h</i></b>_{<b><i>n</i></b>}<b><i>-h</i></b>_{<b><i>n</i></b>}_-1)/<b><i>ds</i></b>. If <b><i>h'</i></b>_{<b><i>n</i></b>}&gt;tanγ_{<b><i>max</i></b>} then the elevations <b><i>h</i></b>_{<b><i>n-j</i></b>} to the left of sample point <b><i>s</i></b>_{<b><i>n</i></b>} are replaced with <b><i>h</i></b>_{<b><i>n</i></b>}<b><i>-j*ds*</i></b> tanγ_{<b><i>max</i></b>} until a sample point <b><i>s</i></b>_{<b><i>n-k</i></b>} is found such that the input elevation <b><i>h</i></b>_{<b><i>n-k</i></b>} there is greater than the replacement value. Figure 4B shows the envelope <b>64'</b> of filtered terrain profile <b>64</b> that was constructed in Figure 4A, with two elevations <b>70</b> and <b>72</b> such that the positive slopes immediately to the left of these elevations are greater than tanγ_{<b><i>max</i></b>}. The elevations immediately to the left of elevations <b>70</b> and <b>72</b> are replaced with the elevations marked by the triangles.

In the second subphase, local downward curvatures that exceed the curvature associated with the combination of a horizontal velocity <b><i>V</i></b> and a minimum vertical acceleration <b><i>a</i></b>_{<b><i>Zmin</i></b>} are replaced with downward curvatures that are consistent with this combination. This, too, is done in two passes, to ensure that the final flight profile is horizontal above local elevation maxima.

The input to the first pass is the envelope derived in the first subphase. Conceptually, in the first pass, template <b>56</b> is swept across the envelope from the first subphase in the direction of decreasing <b><i>s</i></b> (right to left). When a values of <b><i>s</i></b> is found such that the envelope from the first subphase has excessive downward curvature, template <b>56</b> is made tangent there to the envelope from the first subphase, and the portion of the envelope from the first subphase, that lies between the target value of <b><i>s</i></b> and the next intersection, to the right of the target value of s, of template <b>56</b> and the envelope of the first subphase, is raised to match template <b>56.</b> Note that no negative slopes of the envelope from the first subphase are more negative than tanγ_{<b><i>min</i></b>}. Note also that in practice, the second derivative of the envelope from the first subphase is used as a proxy for the curvature.

The corresponding algebraic algorithm addresses the local second derivative <b><i>h</i>"</b> with respect to <b><i>s</i></b> of the envelope from the first subphase. The minimum allowed second derivative is <b><i>h"</i></b>_{<b><i>min</i></b>}=<b><i>a</i></b>_{<b><i>Zmin</i></b>}/[<b><i>V</i></b>²cos³γ(<b><i>s</i></b>)], where γ(<b><i>s</i></b>) is the arctangent of the slope of the envelope from the first phase at horizontal distance <b><i>s</i></b> along flight path <b>12.</b> The numerical approximation that is used to calculate the second derivative at <b><i>s</i></b>_{<b><i>n</i></b>} is <b><i>h"</i></b>_{<b><i>n</i></b>}<b><i>≈</i></b>(<b><i>h'</i></b>_{<b><i>n</i></b>}<b><i>-h'</i></b>_{<b><i>n</i></b>}_-1)/<b><i>ds</i></b>. For the envelope from the first subphase to be considered to have excessive downward curvature at a sample point <b><i>s</i></b>_{<b><i>n</i></b>} in the first pass, it must satisfy the following two conditions: <ul id="ul0002" list-style="none" compact="compact"><li>(a) <b><i>h"</i></b>_{<b><i>n</i></b>}<b><i>&lt;h"</i></b>_{<b><i>min</i></b>} and</li><li>(b) <b><i>h'</i></b>_{<b><i>n</i></b>}<b><i>&lt;h"</i></b>_{<b><i>min</i></b>}<b><i>*ds</i></b></li></ul> If <b><i>h'</i></b>_{<b><i>n</i></b>}_-1&lt;0, the first condition implies the second condition. The purpose of the second condition is to ensure that the final flight profile is flat at local maxima of the terrain profile, where <b><i>h'</i></b>_{<b><i>n</i></b>}_-1&gt;0. Starting from such a sample point <b><i>s</i></b>_{<b><i>n</i></b>} and proceeding rightwards, the slopes <b><i>h'</i></b>_{<b><i>n+j</i></b>}, <b><i>j</i></b>≥0 to the right of <b><i>s</i></b>_{<b><i>n</i></b>} are successively replaced by max[<b><i>h'</i></b>_{<b><i>n+j</i></b>}_-1+(<b><i>j</i></b>+1)*<b><i>h"</i></b>_{<b><i>min</i></b>}*<b><i>ds</i></b>, tanγ_{<b><i>min</i></b>}]. Then, again starting from this sample point <b><i>s</i></b>_{<b><i>n</i></b>}, proceeding rightwards, and using these replacement slopes, the elevations <b><i>h</i></b>_{<b><i>n+j</i></b>} to the right of this sample point <b><i>s</i></b>_{<b><i>n</i></b>} are successively replaced by <b><i>h</i></b>_{<b><i>n+j</i></b>}_-1+<b><i>h'</i></b>_{<b><i>n+j</i></b>}_-1*<b><i>ds</i></b>, until a sample point <b><i>s</i></b>_{<b><i>n+k</i></b>} is found such that the input elevation <b><i>h</i></b>_{<b><i>n+k</i></b>} there is greater than the replacement value. Figure 5A shows an envelope <b>74</b> derived in the first subphase, with two elevations <b>76</b> and <b>77</b> of excessive downward curvature according to the criteria of the first pass of the second subphase. The elevations to the right of elevation <b>76</b> are replaced with the elevations marked by the triangles. The elevation immediately to the right of elevation <b>77</b> would be replaced if not for the fact that the replacement elevation that is derived from elevation <b>76</b> is higher than the replacement elevation that would be derived from elevation <b>77.</b> Note that the replacement slopes to the right of the third replacement elevation are equal to tanγ_{<b><i>min</i></b>}.

The input to the second pass is the output of the first pass. Conceptually, in the second pass, template <b>58</b> is swept across the output of the first pass, in the direction of increasing <b><i>s</i></b> (left to right). When a value of <b><i>s</i></b> is found such that the output of the first pass has excessive downward curvature, template <b>58</b> is made tangent there to the output of the first pass and the portion of the output of the first pass that lies between the target value of s and the next intersection, to the left of the target value of <b><i>s</i></b>, of template <b>58</b> and the output of the first pass, is raised to match template <b>58.</b> Note that no positive slopes of the output of the first pass are more positive than tanγ_{<b><i>max</i></b>}. Note also that in practice, the second derivative of the output of the first pass is used as a proxy for the curvature.

As in the first pass, the corresponding algebraic algorithm also addresses the local second derivative <b><i>h</i>"</b> with respect <i>to</i><b><i>s</i></b> of the output of the first pass, but with a somewhat different condition for excessive downward curvature: <ul id="ul0003" list-style="none" compact="compact"><li>(a) <b><i>h"</i></b>_{<b><i>n</i></b>}<b><i>&lt;h"</i></b>_{<b><i>min</i></b>} and</li><li>(b) <b><i>h'</i></b>_{<b><i>n</i></b>}<b><i>&gt;h"</i></b>_{<b><i>min</i></b>}<b><i>*ds</i></b></li></ul> In other words, the second pass deals with the sample points, at which condition (a) is satisfied, that were not dealt with in the first pass. Starting from such a sample point <b><i>s</i></b>_{<b><i>n</i></b>} and proceeding leftwards, the slopes <b><i>h'</i></b>_{<b><i>n-j</i></b>}, <b><i>j</i></b>&gt;0, to the left of <b><i>s</i></b>_{<b><i>n</i></b>} are successively replaced by min[<b><i>h'</i></b>_{<b><i>n-j</i></b>}₊₁<b>-<i>j*h"</i></b>_{<b><i>min</i></b>}<b><i>*ds</i></b>, tanγ_{<b><i>max</i></b>}]. Then, again starting from the sample point <b><i>s</i></b>_{<b><i>n</i></b>}, proceeding leftwards, and using these replacement slopes, the elevations <b><i>h</i></b>_{<b><i>n-j</i></b>} to the left of this sample point <b><i>s</i></b>_{<b><i>n</i></b>} are successively replaced by <b><i>h</i></b>_{<b><i>n-j</i></b>}₊₁+<b><i>h'</i></b>_{<b><i>n-j</i></b>}<b><i>*ds</i></b>, until a sample point <b><i>s</i></b>_{<b><i>n-k</i></b>} is found such that the input elevation <b><i>h</i></b>_{<b><i>n-k</i></b>} there is greater than the replacement value. Figure 5B shows an envelope <b>78</b> from the first subphase that has been subjected to the first pass of the second subphase, with two elevations <b>80</b> and <b>82</b> of excessive downward curvature according to the criteria of the second pass of the second subphase. The elevations to the left of elevations <b>80</b> and <b>82</b> are replaced with the elevations marked by the triangles. Note that the replacement slopes to the left of the third replacement elevation to the left of elevation <b>80</b> are equal to tanγ_{<b><i>max</i></b>}.

In the third subphase, local upward curvatures that exceed the curvature associated with the combination of a horizontal velocity <b><i>V</i></b> and a maximum vertical acceleration <b><i>a</i></b>_{<b><i>Zmax</i></b>} are replaced with upward curvatures that are consistent with this combination. Because there is no associated constraint, related to local minima, that corresponds to the constraint of the second subphase that the flight profile must be horizontal at local maxima of the terrain profile, this replacement is done in a single pass.

The input to the third subphase is the envelope derived in the second subphase. Conceptually, template <b>62</b> is lowered as far as possible into the valleys of the envelope from the second subphase. Any valley in which template <b>62</b> contacts the two walls of the valley, instead of contacting the valley floor, has excessive upward curvature. The portion of the envelope from the second subphase that lies between the two contact points is raised to match template <b>62</b>.

The corresponding algebraic algorithm addresses the local second derivative <b><i>h</i>"</b> with respect to s of the envelope from the second subphase. The maximum allowed second derivative is <b><i>h"</i></b>_{<b><i>max</i></b>}=<b><i>a</i></b>_{<b><i>Zmax</i></b>}/[<b><i>V</i></b>²cos³γ(<b><i>s</i></b>)]. The numerical approximation of the second subphase is used to calculate the second derivative at all sample points <b><i>s</i></b>_{<b><i>n</i></b>}, from left to right.

Figure 6 illustrates the geometric construction that is used to fit template <b>62</b> to the envelope from the second subphase. Considering the envelope to be a set of discrete points {(<b><i>s</i></b>_{<b><i>n</i></b>},<b><i>h</i></b>_{<b><i>n</i></b>})}, this construction is the "launch", towards the right of one of the points, of a continuous, piecewise linear approximation <b>100</b> of template <b>62</b> that is tangent to the envelope immediately to the left of a launch point <b>102.</b> If the slope of the envelope immediately to the left of launch point <b>102</b> is <b><i>h'</i></b>_{<b><i>n</i></b>}_<b>-1</b>, then the slope of segment <b>104</b> of approximation <b>100</b> that is tangent ta the envelope also is <b><i>h'</i></b>_{<b><i>n</i></b>}_<b>-1</b>. The slope of the next segment <b>106</b> of approximation <b>100</b> then is <b><i>h'</i></b>_{<b><i>n</i></b>}_<b>-1</b><b><i>+h"</i></b>_{<b><i>max</i></b>}<b><i>ds</i></b>, the slope of the segment immediately to the right of segment <b>106</b> is <b><i>h'</i></b>_{<b><i>n</i></b>}_<b>-1</b><b>+2<i>h"</i></b>_{<b><i>max</i></b>}<b><i>ds</i></b>, and so on until the slope reaches tanγ_{<b><i>max</i></b>}.

For each sample point <b><i>s</i></b>_{<b><i>n</i></b>} with an excessive second derivative, two such piecewise linear approximations of template <b>62</b> are launched from two adjacent points of the envelope from the second subphase. The first attempt to construct the piecewise linear approximations is made at sample points <b><i>s</i></b>_{<b><i>n</i></b>} and <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b>. Because sample point <b><i>s</i></b>_{<b><i>n</i></b>} has an excessive second derivative, the piecewise linear approximation that is launched from sample point <b><i>s</i></b>_{<b><i>n</i></b>} is guaranteed to be below the envelope from the second subphase, at least initially. If the piecewise linear approximation that is launched from sample point <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b> is tangent to the envelope from the second subphase at a sample point somewhere to the right of sample point <b><i>s</i></b>_{<b><i>n</i></b>}, and is above the envelope from the second subphase between sample point <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b> and the point of tangency, then the portion of this piecewise linear approximation between its launch point and its point of tangency defines the desired flight profile between those two points. If the piecewise linear approximation that is launched from sample point <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b> is entirely above the envelope from the second subphase, then the desired flight profile must lie somewhere between the "lower" piecewise linear approximation that is launched from sample point <b><i>s</i></b>_{<b><i>n</i></b>} and the "upper" piecewise linear approximation that is launched from point <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b>. A third polygonal approximation to template <b>62</b> is found that, having been launched from sample point <b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b> but with a slope intermediate between the first two piecewise linear approximations, is tangent to the envelope from the second subphase. The portion of the third polygonal approximation between its launch point and its point of tangency defines the desired flight profile between those two points. If the "upper" piecewise linear approximation intersects the envelope from the second subphase, then the construction is repeated for the pair of sample points (<b><i>s</i></b>_{<b><i>n</i></b>}_<b>-1</b>,<b><i>s</i></b>_{<b><i>n</i></b>}_<b>-2</b>), and so on, until a pair of sample points is found such that the piecewise linear approximation launched from the rightmost of the two sample points intersects the envelope from the second subphase and the piecewise linear approximation launched from the leftmost of the two sample points is tangent to or entirely above the envelope from the second subphase.

The third polygonal approximation is found as follows, in the general case of the "upper" piecewise linear approximation emerging from the envelope from the second subphase at sample point <b><i>s</i></b>_{<b><i>n-j</i></b>} and the "lower" piecewise linear approximation emerging from the envelope from the second subphase at sample point <b><i>s</i></b>_{<b><i>n-j</i></b>}_<b>+1</b>. Denote the sample point immediately to the right of the intersection of the "lower" piecewise linear approximation with the envelope from the second subphase as "<b><i>s</i></b>_{<b><i>m</i></b>}". Then the slope of the first segment of the third piecewise linear approximation is given by<maths id="math0001" num=""><math display="block"><mrow><mtext mathvariant="italic">h</mtext><mtext>' = </mtext><msub><mrow><mtext mathvariant="italic">h'</mtext></mrow><mrow><mtext mathvariant="italic">L</mtext></mrow></msub><mtext> +Δ</mtext><mtext mathvariant="italic">h</mtext><mtext>/(</mtext><msub><mrow><mtext mathvariant="italic">s</mtext></mrow><mrow><mtext mathvariant="italic">m</mtext></mrow></msub><msub><mrow><mtext mathvariant="italic">-s</mtext></mrow><mrow><mtext mathvariant="italic">n-j</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1560096A2_D0001.tif" /></maths> where <b><i>h'</i></b>_{<b><i>L</i></b>} is the slope of the first segment of the "lower" piecewise linear approximation and Δ<b><i>h</i></b> is the depth of the "lower piecewise linear approximation below the envelope from the second subphase at sample point <b><i>s</i></b>_{<b><i>m</i></b>}.

Figure 7A shows an example of an envelope <b>84,</b> from the second subphase, that has an excessive second derivative at a point <b>86</b>. A "lower" piecewise linear approximation <b>88</b> to template <b>62</b> is launched from the point <b>94</b> immediately to the left of point <b>86</b> and intersects envelope <b>84</b> to the right of point <b>86</b>. An "upper" piecewise linear approximation <b>90</b> to template <b>62</b> is launched from the point <b>96</b> immediately to the left of point <b>94</b> and lies entirely above envelope <b>84.</b> A third piecewise linear approximation <b>92</b> to template <b>62</b> is found as described above that, having been launched from point <b>96,</b> is tangent to envelope <b>84</b> at a point <b>98</b> to the right of point <b>94.</b> Piecewise linear approximation <b>92</b> defines the desired flight profile between points <b>96</b> and <b>98</b>.

Figure 7B shows a similar envelope <b>84',</b> from the second subphase, in which piecewise linear approximation <b>88</b> to template <b>62</b> is tangent to envelope <b>84'</b> at a point <b>98'</b>. Piecewise linear approximation <b>88</b> defines the desired flight profile between points <b>94</b> and <b>98</b>. If piecewise linear approximation <b>88</b> were entirely above envelope <b>84'</b>, then the procedure described above would be used to find a piecewise linear approximation to template <b>62</b> that is below piecewise linear approximation <b>88</b>, and that is tangent to envelope <b>84'</b>, to serve as the desired flight profile between point <b>94</b> and the point of tangency.

Phase III: Boundary Conditions

The flight profile must connect smoothly to the "normal" trajectory along which the air vehicle flies before entering the terrain-following flight profile and after exiting the terrain-following flight profile. In addition, the flight profile computed for one frame must connect smoothly to the flight profile of the next frame. In practice, this means that the start of the third subphase envelope of a frame subsequent to the first frame must connect smoothly to the middle of the third subphase envelope of the immediately preceding frame, at the point in the immediately preceding frame where the new frame starts, because the final, composite flight profile is a concatenation of the initial parts of all the third subphase envelopes of all but the last frame, plus the entire third subphase envelope of the last frame. The initial altitude <b><i>h</i></b> and flight angle γ must be defined for all the frames, as must the final altitude <b><i>h</i></b> and flight angle γ of the last several frames. Usually, this is done by replacing the first two elevations of the inflated and filtered terrain profile, at the beginning of each frame, with the elevations <b><i>h</i></b>_<b>0</b> and <b><i>h</i></b>_<b>0</b>+tanγ_<b>0</b><b><i>ds</i></b>, respectively, where <b><i>h</i></b>_<b>0</b> is the altitude of the previous flight profile upon entry to the frame (as defined by the normal trajectory upon entering the first frame, or by the flight profile of the previous frame upon entering one of the other frames) and <b>γ</b>_<b>0</b> is the corresponding flight profile angle; and by replacing the last two elevations of the inflated and filtered profile of the last several frames with the elevations <b><i>h</i></b>_{<b><i>f</i></b>}-tanγ_{<b><i>f</i></b>}<b><i>ds</i></b> and <b><i>h</i></b>_{<b><i>f</i></b>}, where <b><i>h</i></b>_{<b><i>f</i></b>} is the desired altitude of the air vehicle upon leaving the flight profile and γ_{<b><i>f</i></b>} is the corresponding flight profile angle. The flight profile shaping algorithm presented above then is executed on the thus-adjusted inflated and filtered terrain profile.

There are two situations in which this default rule does not work.

The first situation is illustrated in Figure 8, which shows an inflated and filtered terrain profile <b><i>h</i>(<i>s</i>)</b>. γ_<b>0</b>&gt;0 and the third elevation <b><i>h</i>(<i>s</i></b>_<b>3</b><b>)</b> of inflated and filtered terrain profile <b><i>h</i>(<i>s</i>)</b> is lower than <b><i>h</i></b>_<b>0</b>+tanγ_<b>0</b><b><i>ds</i></b>. In that case, the default rule substitutes line segments <b>101</b> and <b>103</b> for the first two line segments of terrain profile h(s), thereby creating a fictitious local elevation maximum at the second sample point <b><i>s</i></b>_<b>2</b> of the frame, and the flight profile shaping algorithm seeks to create a flight profile that is horizontal at <b>s</b>_<b>2</b>. The solution to this problem is to create, instead, an <i>ad hoc</i> flight profile that starts from altitude <b><i>h</i></b>_<b>0</b> with the flight angle <b>γ</b>_<b>0</b> and flattens out to horizontal at the minimum allowed acceleration <b><i>a</i></b>_{<b><i>Zmin</i></b>}. An analogous procedure is followed at the end of the last frame if γ_<b>f</b>&lt;0 and the third from last elevation of the inflated and filtered profile is lower than <b><i>h</i></b>_{<b><i>f</i></b>}-tan<i>γ</i>_{<b><i>f</i></b>}<b><i>ds</i></b>.

The second situation is related to the third subphase. Recall that the "third" piecewise linear approximation, that defines the flight profile, is at the maximum allowed acceleration <b><i>a</i></b>_{<b><i>Zmax</i></b>}. If a frame, subsequent to the first frame, starts at a point in the previous frame at which the flight profile was defined in this way, then, because of numerical uncertainty, the flight profile computed for the previous frame is liable to intersect the envelope that is computed by the second subphase of the phase III algorithm, rather than be tangent to that envelope. The algorithm would then seek to back off (to the left) by another sample point; but because the algorithm is operating at the beginning of a frame, there is no sample point to back off to. Therefore, the initial flight slope is increased sufficiently to keep the flight profile from intersecting the envelope that is computed by the second subphase.

One more interaction between frames must be anticipated, as illustrated in Figure 9. Figure 9 shows two successive frames <b>110</b> and <b>112,</b> the associated terrain profile <b>114,</b> and the flight profile <b>116</b> computed as described above for frame <b>110</b>. Terrain profile <b>114</b> includes a cliff <b>120</b> in frame <b>112</b> but not in frame <b>110.</b> An extension <b>118</b> of flight profile <b>116</b> past the right end of frame <b>110</b> constrained by the maximum allowed upward acceleration <b><i>a</i></b>_{<b><i>Zmax</i></b>} and the maximum allowed climb angle γ_{<b><i>max</i></b>} intersects cliff <b>120,</b> so that an air vehicle flying according to flight profile <b>116</b> would crash into cliff <b>120.</b> This problem is handled by making the frames sufficiently long. The minimum frame length should be at least as great as the longest distance between two points, of the regional map from which the nominal terrain profile is obtained, such that the slope of the line of sight between the two points is greater than or equal to tanγ_{<b><i>max</i></b>}.

Example

The following Figures are taken from a study in which the method of the present invention was applied to a 110 Km long terrain profile.

Figures 10A, 10B and 10C show, respectively, three different portions of the terrain profile (marked with X's), along with three flight profiles. The flight profile marked with diamonds was computed without filtering the terrain profile. The flight profile marked with circles was computed after filtering the terrain profile with a 1 Km long filter. The flight profile marked with triangles was computed after filtering the terrain profile with a 3.5 Km long filter. Figure 10A shows the first 40 Km of the terrain profile and the three flight profiles. Figure 10B shows the next 40 Km of the terrain profile and the three flight profiles. Figure 10C shows the last 30 Km of the terrain profile and the three flight profiles. Overall, the flight profile that was computed using a relatively short 1-Km filter follows the terrain profile better than either the flight profile that was computed without filtering or the flight profile that was computed using a relatively long 3.5 Km filter. The 3.5 Km long filter, however, produces a flight profile that requires gentler maneuvers than the other two flight profiles.

Figure 11 shows three plots <b>130, 132</b> and <b>134</b> of the mean clearance of flight profiles above the inflated terrain profile as a function of the length of the filters that were used to filter the inflated terrain profile prior to computing the various flight profiles. Plot <b>130</b> refers to the entire 110 Km terrain profile. Plot <b>132</b> refers to the first 40 Km of the terrain profile, as shown in Figure 10A. Plot <b>134</b> refers to the last 30 Km of the terrain profile, as shown in Figure 10C. A 1 Km filter gives the closest terrain following for the terrain profile as a whole and also for the last 30 Km of the terrain profile. A 0.6 Km filter gives the closest terrain following for the first 40 Km of the terrain profile.

In general, the length of the filter that gives the closest terrain following depends on the nature of the terrain. It also should be remembered that terrain following is achieved at the expense of the increased fuel consumption needed to follow the terrain. Preferably, the terrain profile filter length is selected in advance of the mission assigned to the air vehicle, in accordance with these two criteria. The nature of the mission determines the relative importance of the two criteria (closeness of terrain following vs. gentleness of maneuver) that are used to select the terrain profile filter length.

Figure 12 is a schematic diagram of an air vehicle <b>150</b> of the present invention. On board air vehicle <b>150</b> are a memory <b>152</b> for storing a digital terrain map and (optionally, for an unmanned air vehicle <b>150</b>) a flight path within the digital terrain map, two navigational instruments (a self-contained navigational instrument <b>155</b> such as an inertial measurement unit, and a second navigational instrument <b>156</b>, such as a GPS receiver, that relies on external signals) for determining the position and velocity of the air vehicle in real time, and a processor <b>154</b> for implementing the method of the present invention to compute a reference flight profile for air vehicle <b>150</b> in real time, in accordance with the digital terrain map stored in memory <b>152</b>, optionally in accordance with the flight path stored in memory <b>152</b>, in accordance with the position of air vehicle <b>150</b> as measured by navigational instruments <b>155</b> and <b>156</b>, and in accordance with the time-varying performance parameters of air vehicle <b>150</b>. Air vehicle <b>150</b> also includes a propulsion and guidance system, represented in Figure 12 by jet engines <b>158</b> and control surfaces <b>160</b>, for flying air vehicle <b>150</b> along the flight path in accordance with the computed reference flight profile.

While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made.