US6317690B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Path planning, terrain avoidance and situation awareness system for general aviation
Assignee: Individual
•
Filing: 1999-06-28
•
Granted: 2001-11-13
•
Expires: 2019-06-28
Abstract
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 technique are developed as basic operations for this terrain model. In addition a visibility graph approach for dynamic route selection may 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.
Inventors
- 👤 Min-Chung Gia
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 01:41
CPC Classifications
G; G01; G01S; G01S13/00; G01S13/88; G01S13/93; G01S13/933; G01S13/935; G01C; G01C21/00; G01C21/005; G01C21/20; G01C21/38; G01C21/3863; G01C21/387; G01C21/3881
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
301 words
A method of performing real-time flight path selection and path planning for general aviation, comprising the following steps: using Digitized Terrain Elevation Data (DTED) to generate a terrain model, said terrain model containing a set of nodes, each of said 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 the corresponding Oct-tree, parameters I, J defining the 2-D coordinates of planar location, with elevation K, the parameters I,J,K defining the 3-D coordinates of a space location, and a scaling factor of the elevation being introduced which divides the terrain elevation into bands, parameter K representing scaled elevation, the nodes of said Oct-tree with equal scaled value of elevation occurring in the same quadrant of the corresponding quad-tree being merged, the scaling factor also being non-linear, or beginning with a baseline instead of the mean sea level, parameter S being the coverage area of a node which is added to represent the size of a node, and bit positions of said four parameters I,J,K,S being interleaved to form an integer representation of a node; using this terrain model to provide a navigation space; accessing and retrieving terrain model to generate a terrain map; giving start and goal points on navigation space to determine a ground track of direct flight path on the terrain map; identifying a dangerous zone based on ground track and flight altitude; using said dangerous zone to allocate a set of way-points for avoidance; constructing a visibility graph of navigation space, in which is included a set of collision free path segments; linking start point to goal point by using a flight path searching algorithm; and obtaining the terrain profile of the flight path from the terrain model.
Claim 2
Independent Claim
301 words
A method of performing real-time flight path selection and path planning for general aviation, comprising the following steps: using Digitized Terrain Elevation Data (DTED) to generate a terrain model, said terrain model containing a set of nodes, each of said 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 the corresponding Oct-tree, parameters I, J defining the 2-D coordinates of planar location, with elevation K, the parameters I,J,K defining the 3-D coordinates of a space location, and a scaling factor of the elevation being introduced which divides the terrain elevation into bands, parameter K representing scaled elevation, the nodes of said Oct-tree with equal scaled value of elevation occurring in the same quadrant of the corresponding quad-tree being merged, the scaling factor also being non-linear, or beginning with a baseline instead of the mean sea level, parameter S being the coverage area of a node which is added to represent the size of a node, and bit positions of said four parameters I,J,K,S being interleaved to form an integer representation of a node; using this terrain model to provide a navigation space; accessing and retrieving terrain model to generate a terrain map; giving start and goal points on navigation space to determine a ground track of direct flight path on the terrain map; identifying a dangerous zone based on ground track and flight altitude; using said dangerous zone to allocate a set of way-points for avoidance; constructing a visibility graph of navigation space, in which is included a set of collision free path segments; linking start point to goal point by using a flight path searching algorithm; and obtaining the terrain profile of the flight path from the terrain model.
Claim 3
Dependent Claim
15 words
The method in claim 1 , wherein said terrain model is an Oct-tree terrain model.
Claim 4
Dependent Claim
18 words
The method in claim 1 , wherein said terrain model is a variant of quad-tree and Oct-tree structures.
Claim 5
Dependent Claim
14 words
The method in claim 1 , wherein each node is represented by an integer.
Claim 6
Dependent Claim
16 words
The method in claim 4 , wherein each terrain elevation data has a unique correspondent node.
Claim 7
Dependent Claim
54 words
The method in claim 1 , wherein said navigation space is defined as a region for allocating a possible flight path; said navigation space combines Oct-trees with quad-trees to provide both 3-D and 2-D operations on terrain elevation data; and a 2-D locational code is obtained by removing K-bits from a 3-D locational code.
Claim 8
Dependent Claim
91 words
The method of claim 5 , wherein said terrain map is obtained by the following steps: using an accessing algorithm to access said terrain model; accessing a node means which accesses a coverage area of a node; using a retrieving algorithm to retrieve parameters of a node of said terrain model, where the I,J,K parameters give the planar position and elevation of a node, different color codes from a mapping table are assigned to each elevation band, and S represents the coverage area of a node to form said terrain map.
Claim 9
Dependent Claim
95 words
The method in claim 1 , wherein the ground track is a straight line segment, formed as a list of nodes; the dangerous zone is a list of nodes obtained from a collision check of which elevations of the nodes conflict with flight altitude; each collision free path segment is a straight line segment, formed as a list of nodes; the way-points are represented in 2-D locational codes; and the visibility graph is constructed by performing the collision check on each segment between pairs of way-points to determine a set of collision free path segments.
Claim 10
Dependent Claim
29 words
The method in claim 1 , wherein due to the geometric region features of said dangerous zone in navigation space, path searching algorithms based on visibility graph are used.
Claim 11
Independent Claim
81 words
A method of performing real-time terrain masking for terrain awareness comprising: using Digitized Terrain Elevation Data (DTED) to generate a terrain model; using this terrain model to provide a navigation space; accessing and retrieving the terrain model to generate a terrain map; identifying a dangerous zone, peaks, and obstacles coverage area based on a selected flight altitude and heading; and computing a line-of-sight terrain masking of the dangerous zone, peaks, and obstacles with respect to a selected flight altitude and heading.
Claim 12
Independent Claim
81 words
A method of performing real-time terrain masking for terrain awareness comprising: using Digitized Terrain Elevation Data (DTED) to generate a terrain model; using this terrain model to provide a navigation space; accessing and retrieving the terrain model to generate a terrain map; identifying a dangerous zone, peaks, and obstacles coverage area based on a selected flight altitude and heading; and computing a line-of-sight terrain masking of the dangerous zone, peaks, and obstacles with respect to a selected flight altitude and heading.
Claim 13
Dependent Claim
20 words
The method in claim 10 , wherein said terrain model contains a set of nodes, each represented by an integer.
Claim 14
Dependent Claim
174 words
The method in claim 11 , wherein each of said nodes contains four parameters I,J,K,S; the four parameters I,J,K,S are obtained by mapping each elevation peak point I, J, K of a DTED file into a 3-D locational code of the corresponding Oct-tree; parameters I, J define the 2-D coordinates of planar location, with elevation K, and the parameters I,J,K define the 3-D coordinates of a space location; a scaling factor of the elevation is introduced which divides the terrain elevation into bands; parameter K represents a scaled elevation; the nodes of said Oct-tree with equal scaled value of elevation occur in the same quadrant of the corresponding quad-tree being merged; the scaling factor also is non-linear, or begin with a baseline instead of the mean sea level; parameter S is the coverage area of a node, and is added to represent the size of a node; bit positions of said four parameters I,J,K,S are interleaved to form an integer representation of a node; and each terrain elevation data has a unique correspondent node.
Claim 15
Dependent Claim
60 words
The method in claim 16 , wherein said computing line-of-sight terrain masking computes the line-of-sight terrain masking with respect to a selected flight altitude and heading using the same locational code representations; and the dangerous zone, peaks, and obstacles represent a subset of nodes of the terrain model and are obtained from collision checking and region finding with homogeneous nodes.
Claim 16
Independent Claim
211 words
A method of generating perspective images of a terrain model, comprising: using Digitized Terrain Elevation Data (DTED) to generate a terrain model said terrain model containing a set of nodes each of said 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 the corresponding Oct-tree, parameters I, J defining the 2-D coordinates of planar location, with elevation K, the parameters I,J,K defining the 3-D coordinates of a space location, and a scaling factor of the elevation being introduced which divides the terrain elevation into bands, parameter K representing scaled elevation, the nodes of said Oct-tree with equal scaled value of elevation occurring in the same quadrant of the corresponding quad-tree being merged the scaling factor also being non-linear, or beginning with a baseline instead of the mean sea level, parameter S being the coverage area of a node which is added to represent the size of a node, and bit positions of said four parameters I,J,K,S being interleaved to form an integer representation of a node; using this terrain model to provide a navigation space; and accessing and retrieving parameters I,J,K,S from the terrain model to generate a perspective image.
Claim 17
Independent Claim
211 words
A method of generating perspective images of a terrain model, comprising: using Digitized Terrain Elevation Data (DTED) to generate a terrain model said terrain model containing a set of nodes each of said 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 the corresponding Oct-tree, parameters I, J defining the 2-D coordinates of planar location, with elevation K, the parameters I,J,K defining the 3-D coordinates of a space location, and a scaling factor of the elevation being introduced which divides the terrain elevation into bands, parameter K representing scaled elevation, the nodes of said Oct-tree with equal scaled value of elevation occurring in the same quadrant of the corresponding quad-tree being merged the scaling factor also being non-linear, or beginning with a baseline instead of the mean sea level, parameter S being the coverage area of a node which is added to represent the size of a node, and bit positions of said four parameters I,J,K,S being interleaved to form an integer representation of a node; using this terrain model to provide a navigation space; and accessing and retrieving parameters I,J,K,S from the terrain model to generate a perspective image.
Claim 18
Dependent Claim
14 words
The method in claim 14 , wherein each node is represented by an integer.
Claim 19
Dependent Claim
16 words
The method in claim 15 , wherein each terrain elevation data has a unique correspondent node.
Claim 20
Dependent Claim
73 words
The method in claim 14 , wherein said step of accessing and retrieving parameters I,J,K,S comprises: using the terrain model directly as input data without accessing the original DTED file, where the I,J,K parameters give the planar position and elevation of a node, different color codes from a mapping table are assigned to each elevation band, and S represents a coverage area of a node to form said perspective images of said terrain.
References Cited (Backward Citations)
US5047916A
Cited
US5086396A
Cited
US5892462A
Cited
US6076042A
Cited
US6085147A
Cited
US6021374A
Cited
US5978715A
Cited
US6043756A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-11-12 | 2005-05-14 | 2005-11-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-11-12 | 2009-05-14 | 2009-11-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-11-12 | 2013-05-14 | 2013-11-13 | $7700.00 | Window Closed / Lapsed |