System, method and apparatus for searching geographic area using prioritized spatial order Number:7,386,373 from the United States Patent and Trademark Office (PTO) owispatent

Title: System, method and apparatus for searching geographic area using prioritized spatial order

Abstract: A spatial data search method, system and apparatus for identifying particular data of significance around a reference vector through the spatial data. The method involves determining a reference vector within a spatial region for which spatial data exists, loading a portion of the spatial data including the data around the reference vector into a memory buffer, and searching the spatial data in a prioritized order. The method, system and apparatus have particular utility in searching geographic data for a terrain awareness and warning system ("TAWS") and display in an aircraft. Embodiments of the present invention provide advantages over existing sequential and radial search methods, significantly reducing the processing and calculations required and providing faster alerts to pilots.

Patent Number: 7,386,373 Issued on 06/10/2008 to Chen,   et al.

---

Inventors:	Chen; Susan S. (Chandler, AZ), Barber; Clayton E. (Independence, MO)
Assignee:	Garmin International, Inc. (Olathe, KS)
Appl. No.:	10/720,371
Filed:	November 24, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	10337598	Jan., 2003	6745115

---

Current U.S. Class:	701/9 ; 340/961; 340/971; 701/301
Field of Search:	701/9,10,14,13,15,16,120,301 244/158R,75R 340/945,815.4,947,951,948,961,971,963 342/64 707/3 375/240.16

---

References Cited [Referenced By]

---

U.S. Patent Documents

3668623	June 1972	Caaposs
4071843	January 1978	Marien
4224669	September 1980	Brame
4319218	March 1982	Bateman
4433323	February 1984	Grove
4484192	November 1984	Seitz et al.
4495483	January 1985	Bateman
4567883	February 1986	Langer et al.
4639730	January 1987	Paterson et al.
4646244	February 1987	Bateman et al.
4675823	June 1987	Noland
4684948	August 1987	Bateman
4792799	December 1988	Grove
4818992	April 1989	Paterson
4849756	July 1989	Bateman
4857923	August 1989	Bateman
4894655	January 1990	Joguet et al.
4903212	February 1990	Yokouchi et al.
4914436	April 1990	Bateman et al.
4916448	April 1990	Thor
4939513	July 1990	Paterson et al.
4940987	July 1990	Frederick
4951047	August 1990	Paterson et al.
4980684	December 1990	Paterson et al.
4987413	January 1991	Grove
5001476	March 1991	Vermilion et al.
5038141	August 1991	Grove
5075685	December 1991	Vermilion et al.
5086396	February 1992	Waruszewski, Jr.
5136512	August 1992	Le Borne
5140532	August 1992	Beckwith, Jr. et al.
5153588	October 1992	Muller
5166682	November 1992	Bateman
5187478	February 1993	Grove
5192208	March 1993	Ferguson et al.
5196847	March 1993	Bateman
5202690	April 1993	Frederick
5220322	June 1993	Bateman et al.
5265025	November 1993	Hirata
5293318	March 1994	Fukushima
5369589	November 1994	Steiner
5389712	February 1995	El Sayed et al.
5392048	February 1995	Michie
5410317	April 1995	Ostrom et al.
5414631	May 1995	Denoize et al.
5420582	May 1995	Kubbat et al.
5442556	August 1995	Boyes et al.
5448233	September 1995	Saban et al.
5448241	September 1995	Zeoli et al.
5485156	January 1996	Manseur et al.
5488563	January 1996	Chazelle et al.
5495249	February 1996	Chazelle et al.
5511153	April 1996	Azarbayejani et al.
5519392	May 1996	Oder et al.
5638282	June 1997	Chazelle et al.
5661486	August 1997	Faivre et al.
5677842	October 1997	Denoize et al.
5781126	July 1998	Paterson et al.
5798712	August 1998	Coquin
5839080	November 1998	Muller et al.
5884223	March 1999	Tognazzini
5892462	April 1999	Tran
5936552	August 1999	Wichgers et al.
6002347	December 1999	Daly et al.
6038498	March 2000	Briffe et al.
6043758	March 2000	Snyder, Jr. et al.
6076042	June 2000	Tognazzini
6088634	July 2000	Muller et al.
6088654	July 2000	Lepere et al.
6092009	July 2000	Glover
6122570	September 2000	Muller et al.
6125432	September 2000	Hanami et al.
6127944	October 2000	Daly et al.
6138060	October 2000	Conner et al.
6154151	November 2000	McElreath et al.
6216064	April 2001	Johnson et al.
6219592	April 2001	Muller et al.
6233522	May 2001	Morci
6292721	September 2001	Conner et al.
6304800	October 2001	Ishihara et al.
6347263	February 2002	Johnson et al.
6433729	August 2002	Staggs
6456940	September 2002	Higgins
6489916	December 2002	Block
6690298	February 2004	Barber et al.
6745115	June 2004	Chen
6765965	July 2004	Hanami et al.
6778605	August 2004	Hamanaka
6793173	September 2004	Salesse-Lavergne
6879280	April 2005	Bull et al.
6995690	February 2006	Chen et al.
7064680	June 2006	Reynolds et al.
2001/0056316	December 2001	Johnson et al.
2002/0041631	April 2002	Arita et al.
2002/0089432	July 2002	Staggs et al.
2002/0131500	September 2002	Gandhi et al.
2003/0063673	April 2003	Riemens et al.
2003/0107499	June 2003	Lepere et al.
2003/0225489	December 2003	Tsao
2005/0007270	January 2005	Block
2005/0105616	May 2005	Kim et al.

Primary Examiner: To; Tuan C
Attorney, Agent or Firm: West; Kevin E. Korte; Samuel M.

---

Parent Case Text

---

RELATED APPLICATIONS

The present application is a continuation-in-part and claims priority benefit, with regard to all common subject matter, of an earlier-filed U.S. patent application entitled "System, Method and Apparatus for Searching Geographic Area Using Prioritized Spatial Order", Ser. No. 10/337,598, filed Jan. 7, 2003 now U.S. Pat. No. 6,745,115.

---

Claims

---

The invention claimed is:

1. A method of searching geographic data for a terrain awareness warning system, the method comprising a plurality of alert cycles, wherein a first alert cycle of the plurality comprising: identifying a first search vector for the geographic data based upon at least a first direction of travel and a first location of the aircraft at a first time, the search vector having a first length representing a look-ahead distance, the first search vector dependent upon a vertical velocity of the aircraft at the first time and independent of the flight angle of the aircraft at the first time; locating the first location of the aircraft in the geographic data; copying into a memory buffer having cells, a first subset of the geographic data corresponding to and encompassing cells corresponding to a geographic region through which the search vector extends; and searching a portion of the memory buffer cells according to a first predetermined prioritized search order.

2. The method of claim 1, wherein searching comprises searching the memory buffer cells in a non-linear prioritized search order.

3. The method of claim 1, wherein a second alert cycle of the plurality comprising: identifying a second search vector for the geographic data based upon at least a second direction of travel and a second location of the aircraft at a second time, the second search vector dependent upon a vertical velocity of the aircraft at the second time and independent of the flight angle of the aircraft at the second time; locating the second location of the aircraft in the geographic data; copying a second subset of the geographic data corresponding to the second location of the aircraft and second direction of travel for the aircraft into the memory buffer; searching the portion of the memory buffer cells according to a second predetermined search order.

4. The method of claim 1, wherein the predetermined prioritized search order is a search order predetermined with regard to its relation to the search vector.

5. The method of claim 1, wherein each alert cycle among the plurality searches the memory buffer cells according to at least first and second predetermined prioritized search orders depending upon an external factor.

6. The method of claim 1, wherein searching comprises comparing data relative to an elevation value stored in a memory cell with a projected aircraft safety altitude for the memory cell.

7. The method of claim 6, further comprising storing in an alert list an identity of each memory cell having a data value exceeding the projected aircraft safety altitude.

8. The method of claim 7, further comprising calculating an alert status for each entry in the alert list when a predetermined number of memory cell values exceed the predetermined alert elevation value during the first alert cycle.

9. The method of claim 8, wherein calculating the alert status comprises determining a travel time for the aircraft to reach the geographic region represented by the memory cell value, determining a first pull-up time for a pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell, and comparing the travel time to a time relative to the first pull-up time.

10. The method of claim 9, wherein calculating the alert status further comprises determining a second pull-up time for the pilot of the aircraft to pull-up to an altitude above the elevation value stored in the cell plus a clearance value, and comparing the travel time to a time relative to the second pull-up time.

11. The method of claim 10, wherein each alert cycle comprises searching at least one memory cell on the search vector followed by searching at least one memory cell adjacent to the search vector followed by searching at least one unsearched memory cell on the search vector.

12. The method of claim 1, further comprising determining a terrain alert and displaying images on a terrain display, the images representative of terrain and an associated terrain alert level.

---

Description

---

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention generally relates to searching data relating to a spatial region using a prioritized search order, and more particularly to a Terrain Awareness Warning System ("TAWS") for use by an aircraft for searching terrain elevation data for a geographic area to determine aircraft terrain clearance.

2. Background Art

Various systems are known in the art that provide warnings and advisory indications of hazardous flight conditions. Among such systems are systems generally known as Ground Proximity Warning Systems ("GPWS") which monitor the flight conditions of an aircraft and provide a warning if flight conditions are such that inadvertent contact with terrain is imminent. Among flight conditions normally monitored by such systems are radio altitude and rate, barometric altitude and rate, air speed, and flap and gear positions. These parameters are monitored and an advisory signal and/or warning signal is generated when the relationship between the parameters is such that terrain impact is likely to occur.

Other systems improve upon earlier GPWS by utilizing ground-based navigational information. Monitoring stored terrain data and providing modified ground proximity warnings may provide more accurate warnings. U.S. Pat. Nos. 4,646,244, and 4,675,823 each disclose terrain advisory systems that utilize ground-based navigational systems and stored terrain data to provide various ground proximity warnings in relation to the position of the aircraft. U.S. Pat. No. 5,839,080 discloses a Global Positioning System ("GPS") and stored terrain data to provide warning indications.

Satellite-based navigational systems, such as GPS, which can track longitude, latitude, altitude, groundtrack, and ground speed, are becoming an important and reliable source of information for aircraft. An aircraft's Forward Looking Terrain Avoidance ("FLTA") system looks ahead of the aircraft during flight along and below the aircraft's lateral and vertical flight path to provide suitable alerts if a potential threat exists of the aircraft colliding or coming too close to terrain. The computation involves searching through a terrain database for terrain cells that are within the search area and violate the Required Terrain Clearance ("RTC"). The RTC is the value set by the Federal Aviation Administration as the permitted flight "floor" for various phases of aircraft flight. The RTC indicates the clearance distance from terrain below which the aircraft should not fly. Searching the search area and finding the cells in violation is expensive in both processor and memory resources.

Two common methods of searching terrain data are sequential and radial. Both of these methods suffer from the deficiency that they expend precious processor and memory resources. For the sequential search method, some common deficiencies include: First, every cell in a rectangular area encompassing the search area is searched, even those cells that are outside the search area boundary. This requires a determination of whether a cell is within the search area or not, which could be complicated and expensive. Second, a large data buffer is needed to store the cells found during the search, the dimension of the buffer needed is difficult to determine accurately because the upper bound could equal the size of the search area which varies by the speed of the plane. Third, sorting the cells in the result buffer by distance to the aircraft position is expensive, especially if a large number of cells are returned in the search and if both distance and bearing are considered.

For the radial search method, some common deficiencies include: First, many possible flight directions are searched, even some of those that are highly unlikely. This requires expensive processing time to be spent on searching all flight directions even when the aircraft is flying straight. Second, because the search is performed in a plurality of radial arms originating at the same point and extending in a fan shape over the underlying data sectioned into a square grid, many cells near the origin of the arms are searched numerous times, and some cells farther from the origin are potentially missed if the radial arms become too far apart at their extents. Third, the position of each point on each radial arm is calculated and terrain data is searched throughout the full database. This is complicated and expensive. Fourth, a large data buffer is needed to store the cell identities found during the search, and the dimension of the buffer needed is difficult to determine accurately because the upper bound could equal the full number of the search points on all radial arms. Fifth, in systems which sort the results, sorting the cells in the result buffer by distance to the aircraft position is expensive, especially if a large number of cells is returned in the search and if both distance and bearing are considered.

Both conventional systems require extensive processor search time and memory storage for crucial Terrain Awareness and Warning systems ("TAWS"), for which the costs of developing, repairing and maintaining are increasing. The additional time required for these searches also reduces the time available for the processor to perform other tasks and lengthens the time in which search results can be made available to a pilot of the aircraft.

DISCLOSURE OF THE INVENTION

The present invention relates to methods, apparatus and a system for searching spatial data in a prioritized manner. In a general form of the invention, spatial data along and adjacent to a search vector is searched by storing a portion of a larger spatial information database into a smaller memory buffer and searching the buffer in a predetermined prioritized order. Different from conventional methods of searching spatial data, particular embodiments of the present invention search the data in the memory buffer in a non-linear order along and adjacent to a search vector, comparing spatial data values stored in select memory cells of the buffer with a predetermined search criteria. The identity of each cell searched which stores a value meeting the search criteria is included in an alert list which, when the length of the list equals a predetermined list length, is used to calculate an alert status for each cell on the list. Each cell in the memory buffer is searched no more than once for each alert cycle. Subsequent cycles may search using the same predetermined search order along the search vector, or a different predetermined search order.

Embodiments of the present invention are also particularly useful for searching geographic terrain data for use with TAWS for aircraft. By reference to a satellite navigation reference signal and possibly other signals that provide an indication of an aircraft's altitude, location and direction of travel, a processor determines a search vector in relation to the aircraft's coordinates. The processor accesses a geographic terrain information database and stores elevation data corresponding to the spatial area portion of the database representing the geography over which the aircraft is traveling in a memory buffer. Using a predetermined prioritized order for searching the cells of the memory buffer along the search vector, the processor compares the aircraft's projected altitude at each cell with the elevation value stored in the cell plus an appropriate RTC value for the flight phase (elevation+RTC="clearance elevation"). Particular embodiments of the invention employ a non-linear prioritized order. For all searched cells where the projected altitude of the aircraft is less than the clearance elevation at that cell, the identities of the cells are stored in an alert list until the list is full or the predetermined order is finished. When a predetermined number of alert list elements have been recorded, the processor, in association with a look-ahead warning generator, provides either caution or warning alert indicators to a pilot of the aircraft based upon a separate time-related analysis of the data. The alert indicators may be visual, aural, or both. Embodiments of the invention employ a select number of predetermined search patterns between which a selection is made and implemented for an alert cycle depending upon an exterior criteria such as a pilot's actions or the aircraft's movements. In particular embodiments of the invention, the predetermined search pattern searches a few cells in the direction of the flight path, then back-steps and searches unsearched cells adjacent the flight path, then returns to the flight path and searches at least one next unsearched cell in the flight path, then again searches unsearched cells adjacent the flight path.

Particular advantages of the present invention are found in significantly reduced processing and computation requirements for system resources employing embodiments of the present invention for use in spatial data searching. By storing a relevant portion of the larger terrain information database in a smaller memory buffer, less data needs to be accessed and dismissed to find relevant data, significantly reducing the calculations needed. By searching the cells of the memory buffer no more than once per alert cycle and in a predetermined prioritized order, the alert list is automatically prioritized and cell data is not searched repeatedly. By searching each memory buffer cell using a single simple comparison, searching the search region only until the alert list reaches a predetermined number of cells, and performing a time-related analysis on the significantly shorter list of cells rather than the entire database, even further processing and calculation savings is achieved as well as providing and displaying relevant alert information to the pilots more quickly.

The foregoing and other features and advantages of the present invention will be apparent from the following more detailed description of the particular embodiments of the invention, as illustrated in the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flow diagram illustrating a general method of searching spatial data according to an embodiment of the present invention;

FIG. 2 is a representation of a spatial data grid indicating a vector and search area of interest;

FIG. 3 is a representation of a spatial data grid indicating a prioritized search order of the vector and search area according to an embodiment of the present invention;

FIG. 4 is a representation of a geographic information data grid indicating an aircraft flight path and area immediately adjacent to the flight path;

FIG. 5 is a flow diagram of a method of searching geographic information for a TAWS according to a particular embodiment of the present invention;

FIG. 6 is a side view of a flight path of an aircraft illustrating required terrain clearance boundaries for providing pilot alerts according to embodiments of the present invention;

FIG. 7 is a three-dimensional spatial data grid indicating a search vector;

FIG. 8 is a system diagram of a TAWS configured according to an embodiment of the present invention;

FIG. 9 is a curve diagram to assist in the description of time calculations for an aircraft achieving an additional altitude change; and

FIG. 10 is a plan view of a terrain display in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

As discussed above, embodiments of the present invention relate to searching spatial region data using a prioritized search order. One embodiment of the invention relates specifically to a Terrain Awareness Warning System ("TAWS") for use by an aircraft for searching terrain elevation data.

The purpose of a FLTA function of an aircraft is to predict whether the aircraft is heading toward terrain that will cause the terrain clearance to be less than the clearance required by federal guidelines. The Federal Aviation Administration ("FAA") establishes minimum terrain clearance levels that must be maintained for safety. The precise minimum clearance levels required for any given situation depends upon the type of aircraft, flight pattern, and the like. The FAA also determines minimum performance standards for TAWS equipment used by an aircraft. One example of FAA TAWS equipment standards may be found in the Technical Standard Order TSO-C151a issued in November 1999 by the FAA.

Embodiments of the present invention reduce the amount of data which must be stored by a TAWS to operate properly, and reduce the number of terrain data cells which must be searched for a useful result by focusing upon the cells containing data most important to the aircraft; those directly in front of and immediately adjacent to the aircraft's flight path. As is explained further herein, methods of searching spatial data according to embodiments of the present invention are also applicable to searching other spatial data sets where a primary area of importance is identified and a prioritized data search is desired.

Referring to FIGS. 1 and 2, a method of searching spatial data in a prioritized manner is shown. The method is useful for searching spatial data from a database including at least one value stored in association with each of a plurality of information records associated with a spatial region. A reference vector 20 within the spatial region 22 is determined (Step 2), and spatial data from a spatial database is accessed which corresponds to a starting point of the search. Spatial data corresponding to the determined spatial region 22 is loaded from the database to a spatial memory buffer based upon the starting reference position and primary search direction of the reference vector 20 (Step 4). By loading a smaller region of relevant data from the spatial information database into a separate memory buffer, the smaller relevant data region may be searched more quickly. In a first embodiment of the invention, the smaller region of relevant data is stored in the memory buffer according to its orientation with respect to the spatial information database. In this embodiment, while the general order of cells to be searched in relation to the search vector is predetermined, the specific order of cell identities to be searched depends upon the orientation of the search vector in relation to the spatial information database. This significantly reduces the amount of calculations necessary compared with conventional spatial or radial search systems which calculate the position of each desired search cell for each point to search and then locate that cell from the entirety of the database.

The general process for searching the spatial data once it is loaded into the memory buffer is to search along the vector in an order which focuses upon the most important and closest cells first, those being the cells along and adjacent to the search vector. In many cases, when searching data associated with spatial coordinates, data of interest relates to or is expected near a particular path through a spatial region. For these cases, search methods of the present invention are particularly useful. In simple terms, the method involves searching a few cells along a vector path, then back-stepping and searching a few cells immediately adjacent the vector path, then returning to the next one or two unsearched cells ahead along the vector path, then searching the next unsearched cells adjacent vector path. In this way, the order of the search through the cells, and thus the spatial region data stored in the buffer, may be numbered. Each sequential search cycle may be performed in the same order through the memory buffer data, each search computation relating only to the data value, search criteria and the cell location in relation to the originating cell. By searching in this manner, the most important cells, those along the vector path are searched first, but the cells adjacent the vector path are not left until last. The adjacent cells are intermixed in the search order with those cells immediately on the vector path to provide a prioritized search pattern. Those cells that are beyond a predetermined distance from the vector path 20 are not searched through this method.

Data from the first spatial cell is compared with the search criteria (Step 6). If the data meets the search criteria, the cell identity is stored in an alert list. Data from the second spatial cell is then compared with the search criteria (Step 8), and the cell identity is stored if the data meets the search criteria. This comparison process continues until a predetermined number of cell identities, or elements, have been identified and included in the alert list (Step 10).

FIG. 3 illustrates an exemplary prioritized search order for a 24.times.26 memory buffer cell array 30 for storing data associated with a spatial region. The numbers in the rows and columns indicate the order in which the cell 32 will be searched for data meeting the search criteria. Notice that the search pattern order searches along a primary search path for four cells, returns to search the two adjacent cells on either side of the first cell, returns to search the next unsearched cell along the primary search path, then returns to search the two adjacent cells on either side of the second searched cell. This pattern continues until the end of the memory buffer cell region is reached; adding additional searches to widen the search area for a section in the middle of the memory buffer. The widened search area in the middle of the buffer search is to account for some deviation in the vector, but still maintains a prioritized order for the search. The cells 32 which are outside the desired search region (element 22 from FIG. 2) are identified in FIG. 3 by a zero ("0") to indicate they are not searched. Each time data in a cell 32 is found to meet the search criteria, whatever it may be, the cell is included in an alert list. As will be clear to those of ordinary skill in the art, the alert list is prioritized as to its relevance to the search by virtue of the original search being a prioritized search. Thus, the alert list need not be reordered by a subsequent analysis. As explained previously, the spatial data stored in the memory buffer array 30 may be stored so that the path of the search vector through the buffer space differs by the direction of the search vector through the spatial region. Those of ordinary skill in the art will readily understand how to construct an appropriate search algorithm for data stored in the memory buffer by either order to search select cells by their positional relationship to the search vector regardless of the position or orientation of the vector. The cells listed in the alert list are already in priority order of those closest to the search vector origin, or some similar priority, depending upon the precise priority order in which the region is searched.

FIG. 4 illustrates a particular application of the general method of searching spatial data for use with searching geographic terrain data in a TAWS for an aircraft. Much like the spatial data search for the search method described with reference to FIGS. 1 3, a search vector is determined for searching data through a spatial region. For the present embodiment for use with a TAWS, a look-ahead distance is determined based upon the speed of the aircraft. For example, if at least 90 seconds of warning is desired, the speed of the aircraft would be multiplied by 90 seconds to provide an equivalent look-ahead distance. Based upon the flight direction of the aircraft, a look-ahead point location is calculated directly in front of the aircraft at the look-ahead distance. A search vector is established between the aircraft's current location and the look-ahead point. A subset of data from the geographic terrain database is then stored in a spatial data buffer for searching. The subset of data is selected to include at least a region of data encompassing the terrain data relevant to the terrain along and adjacent to the search vector.

The terrain data stored in the geographic terrain database is stored according to latitudinal and longitudinal positions. Accordingly, and because the earth is not a perfect sphere, the spatial area represented by each database subdivision is not exactly identical as far as its actual dimensions, and is not exactly a square or rectangular region. Thus, the geographic region represented by each cell in the memory buffer varies by region. Since the earth is approximately an ellipsoid, if the earth's surface is divided into latitude/longitude grids, the area that each grid represents will get smaller towards the pole. In an effort to keep the variation to a minimum, embodiments of the present invention divides the earth's surface into latitude bands. For example, 0 to N 60, N60 to N 71, N 71 to N 76, etc. to make groupings of longitude divisions. Even so, the size of the cell still varies to a degree, with a grid size of approximately 0.25 square nautical miles being around the equator. However, the size of the cells does not have significant effect on the searching method used herein. Other smaller and larger cell sizings and geographical representations known in the art may also be applied using embodiments of the present invention depending upon the particular TAWS application. The memory buffer cell 42 representations are shown, for illustrative purposes only, as identically sized and shaped squares.

The proportional spatial dimensions represented by the subset of terrain data from the geographic terrain database, which are dependent upon the length and direction of the search vector, are dependent upon the direction of travel for the aircraft and the aircraft speed. Larger proportional spatial dimensions will result in a larger subset of terrain data in the memory array 40 of the data buffer. The geographic dimensions of each subdivision of the geographic terrain database may be set to any scale by one of ordinary skill in the art.

After terrain data for an appropriate geographic region is copied into the spatial data buffer, each cell 42 of the memory array 40 contains elevation data for a corresponding subdivision of the geographic region. The cells 42 each include a maximum value of the terrain elevation within a geographic region corresponding to the cell for a search. The flight path for an aircraft 46, and search vector for the search, is shown as an arrow 44. The box 48 illustrates an approximate search width of interest around the primary flight path. Box 49 illustrates a list of cells, according to their position in the data array 40, which meet predetermined elevation search criteria. The cells may alternatively be identified in the list by other identifying indicia such as spatial coordinates, latitude and longitude, and the like.

FIG. 8 is a block diagram of a TAWS 80 for an aircraft configured according to an embodiment of the present invention. TAWS systems generally, their components and conventional avionics equipment are well known in the art and are governed by TSOs issued by the FAA. TAWS using satellite navigation information are also well known to those of ordinary skill in the art. The TAWS 80 of FIG. 8 includes a plurality of inputs to a central processor 82 where algorithms for methods of the present invention are executed. The central processor 82 may be a single processor with associated memory as is common in the art, or may be a plurality of processors associated with a number of different systems integral with or separate from the TAWS for performing all or a part of the processor function described herein. The inputs to the processor include signals from devices for collecting information relevant to the various calculations performed by the TAWS 80. Those inputs may include an altimeter 84, an airspeed indicator 86, a heading indicator 88, and a GPS receiver 90, all of which are common to conventional TAWS and are well known in the art. Alternatively, the GPS receiver 90 may be used to provide altitude, airspeed and heading indications. The system 80 also includes a geographic terrain information database 92 that includes at least elevation data for the geographic area over which the aircraft may fly. Embodiments of the present invention also include a terrain buffer space 94 comprising memory having data cells in which data associated with a portion of the geographic area may be stored. A look-ahead warning generator 96 evaluates the geographic locations identified as being of concern, and produces appropriate warnings by visual display 98 or aural warning 100. Visual display 98 may include display monitors, televisions, LED displays, blinking lights, digital and analog displays, and any other displays known for use with TAWS. Aural warnings 100 may include spoken recorded or synthesized voices, "beeps", or any other aural warnings known for use with TAWS.

In reference to FIG. 5, a flow chart of an exemplary embodiment of a method 50 of the present invention is disclosed for use with a TAWS to search altitude data with respect to a geographic area through which an aircraft is flying. Reference to FIG. 8 will be used to clarify the elements used in the system. Using inputs to the TAWS, the aircraft's current location over a geographic region as determined from the GPS receiver 90, the aircraft's ground speed and vertical velocity as determined from the airspeed indicator 86 and GPS receiver 90, and the aircraft's direction of travel as determined from the heading indicator 88 and GPS receiver 90, are determined (Step 52). The aircraft's altitude and an appropriate RTC are also determined and identified for comparison. The RTC appropriate for a given situation depends upon a number of factors including the flight pattern of the aircraft (cruising, landing, take-off, etc.), the vertical speed of the aircraft, the classification of the aircraft, and other factors. Those of ordinary skill in the art will be able to select an appropriate RTC based upon FAA guidelines.

In reliance upon the aircraft's location, air speed, and direction of travel, as discussed above, a portion of a terrain information database 92 is identified and loaded into the terrain buffer space 94 (Step 54). The full size of the terrain buffer space 94 is selected based upon a safe look-ahead distance for the maximum air speed at which the aircraft may travel. Each time data is loaded into the terrain buffer space 94 as buffer data, a portion of the terrain buffer space 94 is configured to receive a data set having a predetermined dimension based upon a safe look-ahead distance for the actual air speed and heading of the aircraft.

After the elevation data for the pertinent geographic region is loaded into the terrain buffer space 94, a search of the buffer space may begin in the primary flight path direction (Step 56) according to a predetermined path and cell order through the buffer space 94. The exact sequence of cell search is not crucial, only that the most important cells to the particular aircraft be searched first. However, it has been found that by following a search path which moves forward a few cells in the direction of the flight path, returns to search a few cells adjacent to the flight path, moves forward to search an unsearched cell in the direction of the flight path, then returns again to search more cells adjacent the flight path, such as that shown in FIG. 3, the most pertinent cells are searched first. How many cells away from the primary flight path the search incorporates depends upon what width of search area is considered important for the given situation. For example, it may be determined that a passenger carrier aircraft flying straight may need at most only 1 nautical mile clearance on either side of the aircraft for safety, but when the aircraft is turning, may need 2 nautical miles clearance on either side of the aircraft. It may also be determined, as partially shown with the search pattern of FIG. 3, that to widen the search boundary adjacent the search path for some or all of the search path, or to even fan out the search area as the search distance from the aircraft increases may be desired to account for the possibility of variance in the path of the aircraft. However, even with a fan search pattern, the prioritized order of searching cells may be used to ensure each cell is searched only once and that priority cells are searched first, resulting in a non-linear prioritized search order.

It is also contemplated that the algorithm followed to determine the precise path order may change during sequential alert cycles depending upon the actions of the pilot, the flight behavior of the aircraft, or any number of other criterion. Any number of prioritized search path orders is possible and contemplated for use with the TAWS of the present invention. Whatever the search pattern, however, it is followed by the algorithm controlled by the processor 82 (FIG. 8) to identify geographic regions having elevations too close to the aircraft flight path altitude. The frequency at which alert cycles are performed may also be increased or decreased based upon various criterion such as the speed of the aircraft, when the plane is turning or descending, or when greater risk factors exist near the aircraft, such as increased close terrain or a runway or airport, to provide the pilot with more relevant information in a timely manner.

In general terms, the search criteria for a cell may be any criteria relevant to the purpose for the search and the data contained in each cell. For a TAWS search, where each cell contains an elevation value, it is desirable to identify all cells having a clearance elevation value (elevation plus RTC), or alert value, greater than the aircraft's projected flight altitude for that cell. By establishing a clearance elevation value for each cell, a lower boundary is established. FIG. 6 is a graphical representation of this comparison showing an aircraft 102 flying on a projected flight path 104 through a spatial region subdivided into subdivisions A F. For purposes of this example, each subdivision corresponds to a cell of the terrain buffer along the flight path and is represented in each buffer cell as an elevation value illustrated in FIG. 6 as lines 108. The highest elevation of terrain 106 in each spatial subdivision is stored in each respective buffer cell. Of course, even those cells without noticeable terrain still have an appropriate ele