Path planning, terrain avoidance and situation awareness system for general aviation

• US 6,401,038 B2
• Filed: 05/18/2001
• Issued: 06/04/2002
• Est. Priority Date: 06/28/1999
• Status: Expired due to Term

• Current Assignee: Min-Chung Gia
• Original Assignee: Min-Chung Gia
• Inventors: Gia, Min-Chung
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US09/859,407
• Publication Number:
  US 20010023390A1
• Time in Patent Office: 382 Days
• Field of Search: 701/300, 701/301, 701/302, 701/4, 701/9, 701/10, 701/14, 342/357.08, 342/357.14, 342/64, 342/65
• US Class Current: 701/301
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01S 13/935 for terrain-avoidance

Abstract

A number of navigation functions are performed on terrain navigation space. One function is to define a dynamic dangerous zone based on flight altitude by locating and aggregating a set of nodes of terrain height over a minimum flight altitude. Algorithms such as collision check, mountainous area boundary and region growing techniques are developed as basic operations for this terrain model. In addition, a visibility graph approach for dynamic route selection may be adapted to reduce the real-time computational requirements. This approach reduces the size of the search space by establishing a partial visibility graph of terrain and avoids details of the terrain, which do not influence the choice of flight path, independent of the size of the navigation space. By exploiting the multiple and variable resolution properties of Oct-tree terrain models, a series of CFIT warning functions using terrain data as reference are implemented efficiently with existing on-board terrain data resources.

Claims

1. A method of performing a real-time dynamic collision check comprising the steps of:

using Digitized Terrain Elevation Data (DTED) to generate a terrain model, said terrain model containing a set of nodes, each of the nodes containing four parameters I,J,K,S, the four parameters I,J,K,S being obtained by mapping each elevation peak point I,J,K of a DTED file into a 3-D locational code of a corresponding Oct-tree, parameters I,J,K defining 3-D coordinates of a space location, a scaling factor of the elevation being introduced with divides the terrain elevation into bands, and parameter K representing scaled elevation, wherein the nodes of said Oct-tree with equal scaled value of elevation occurring in a same quadrant of a corresponding quad-tree are merged and the scaling factor is non-linear or, beginning with a baseline instead of mean sea level, parameter S is a coverage area of a node and is added to represent the size of a respective node, said bit positions of the four parameters I,J,K,S being interleaved to form an integer representation of the respective node;

using the terrain model to provide a navigation space;

accessing and retrieving the terrain model to generate a terrain map;

identifying a list of the nodes in the navigation space based on flight altitude;

establishing a ground track for a flight path segment, said ground track including a list of the nodes on the terrain map; and

determining whether a flight path segment is in conflict with a dangerous zone by searching each of the nodes of the ground track for the flight path segment against the list of nodes in the navigation space.

2. The method of claim 1 wherein the collision check is performed by checking common nodes appearing in both of the node lists.

3. A method of performing a real-time dynamic weather condition avoidance comprising the steps of:

using Digitized Terrain Elevation Data (DTED) to generate a terrain model, said terrain model containing a set of nodes, each of the nodes containing four parameters I,J,K,S, the four parameters I,J,K,S being obtained by mapping each elevation peak point I,J,K of a DTED file into a 3-D locational code of a corresponding Oct-tree, parameters I,J,K defining 3-D coordinates of a space location, a scaling factor of the elevation being introduced with divides the terrain elevation into bands, and parameter K representing scaled elevation, wherein the nodes of said Oct-tree with equal scaled value of elevation occurring in a same quadrant of a corresponding quad-tree are merged and the scaling factor is non-linear or, beginning with a baseline instead of mean sea level, parameter S is a coverage area of a node and is added to represent the size of a respective node, said bit positions of the four parameters I,J,K,S being interleaved to form an integer representation of the respective node;

using the terrain model to provide a navigation space;

accessing and retrieving the terrain model to generate a terrain map;

establishing a start point and a goal point in the navigation space to determine a ground track for a direct flight path on the terrain map;

identifying a dangerous zone based on the ground track and flight altitude;

establishing a weather condition coverage area and representing the weather coverage area by a list of the nodes;

adding the list of nodes of the weather coverage area to a list of the nodes of the dangerous zone to obtain a new dangerous zone;

using said new dangerous zone to allocate a set of way-points for avoidance;

constructing a visibility graph for a new navigation space, in which is a set of collision free path segments;

linking the start point to the goal point by a flight path searching algorithm; and

obtaining the terrain profile of the flight path from the terrain model.

4. The method of claim 3, wherein:

the weather condition coverage area is a set of locational codes overlaying said terrain map; and

weather conditions to be avoided include thunderstorms, windshear and any meteorological situations that appear in airspace.

5. A method of performing real-time dynamic obstacles avoidance comprising the steps of:

using Digitized Terrain Elevation Data (DTED) to generate a terrain model, said terrain model containing a set of nodes, each of the nodes containing four parameters I,J,K,S, the four parameters I,J,K,S being obtained by mapping each elevation peak point I,J,K of a DTED file into a 3-D locational code of a corresponding Oct-tree, parameters I,J,K defining 3-D coordinates of a space location, a scaling factor of the elevation being introduced with divides the terrain elevation into bands, and parameter K representing scaled elevation, wherein the nodes of said Oct-tree with equal scaled value of elevation occurring in a same quadrant of a corresponding quad-tree are merged and the scaling factor is non-linear or, beginning with a baseline instead of mean sea level, parameter S is a coverage area of a node and is added to represent the size of the node, said bit positions of the four parameters I,J,K,S being interleaved to form an integer representation of a respective node;

using the terrain model to provide a navigation space;

accessing and retrieving the terrain model to generate a terrain map;

establishing a start point and a goal point in the navigation space to determine a ground track for a direct flight path on the terrain map;

identifying a dangerous zone based on the ground track and flight altitude;

establishing an obstacles coverage area and representing the obstacles coverage area by a list of the nodes;

adding the list of nodes of the obstacles coverage area to a list of the nodes of the dangerous zone to obtain a new dangerous zone;

using said new dangerous zone to allocate a set of way-points for avoidance;

constructing a visibility graph for a new navigation space, in which is a set of collision free path segments;

linking the start point to the goal point by a flight path searching algorithm; and

obtaining the terrain profile of the flight path from the terrain model.

6. The method of claim 5, wherein:

the obstacles coverage area is a set of locational codes overlaying said terrain map; and

the obstacles include terrain, peak, and any man-made obstacles.