System, module, and method of constructing a flight path used by an avionics system

• US 8,234,068 B1
• Filed: 01/15/2009
• Issued: 07/31/2012
• Est. Priority Date: 01/15/2009
• Status: Active Grant

• Current Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Original Assignee: Rockwell Collins, Inc. (Raytheon Technologies Corporation d/b/a RTX)
• Inventors: Young, Shih-Yih, Jerome, Kristen M.
• Primary Examiner(s): Elchanti, Hussein
• Assistant Examiner(s): Khatib, Rami
• Application Number:
  US12/321,112
• Time in Patent Office: 1,293 Days
• Field of Search: 701/3, 701/4, 701 9- 11, 701/14, 701/17, 701 23- 28, 701/201, 701/202, 701/205, 701/209, 701/210, 701/213, 701/214, 701/218, 701/219, 701/300, 701/301, 701/400, 701/408, 701/409, 701/410, 701/411, 701/416, 701/423, 701/448, 701/528, 701/533, 701/302, 340/945, 340/953, 340961-967, 340/970, 340974-976, 340/979, 342 27- 32, 342/38, 342/46, 342/47, 342/65, 342118-123, 342/357.2, 342/357.23, 342/357.25, 342/455, 342/456, 342/462, 244/75.1, 244/76.R, 244/175, 244185-188, 244/194, 244/195
• US Class Current: 701/528
• CPC Class Codes: G05D 1/0202 specially adapted to aircraft
• CPC Class Codes: G08G 5/0008 with other aircraft
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0056 in an emergency situation, e.g. hijacking
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/0078 for monitoring traffic from the aircraft radar or analogous systems specially adapted for traffic control G01S13/91
• CPC Class Codes: G08G 5/0086 for monitoring terrain radar or analogous systems specially adapted for terrain avoidance G01S13/935
• CPC Class Codes: G08G 5/0091 for monitoring atmospheric conditions radar or analogous systems specially adapted for meteorological use G01S13/95; meteorology G01W

Abstract

A present novel and non-trivial system, module, and method for constructing a flight path used by an avionics system are disclosed. A processor receives flight plan data and object data associated with terrain and obstacles. Free cells are extracted above the objects using a recursive space decomposition technique, and a reference path is formed through traversable free space determined from the availability of free cells. In an additional embodiment, threat data associated with hostile military weaponry and significant meteorological conditions could affect the availability of free cells. A genetic algorithm applying genetic operators which include mutators is employed with aircraft kinematic constraints to refine the reference path used to form a population of best path candidates. When a best path is reached after cycling through a re-generation process of path candidates, flight path data representative of the best path is generated and provided to at least one avionics system.

Claims

1. A system of constructing a flight path used by an avionics system, said system comprising:

a source for providing flight plan data;

a source for providing object data;

a processor configured to

receive data representative of a flight plan of an aircraft,

receive data representative of objects,

define a plurality of pre-processing boxes, where

at least one pre-processing box corresponds to a current position of the aircraft along the flight plan, and

at least one pre-processing box corresponds to a future position of the aircraft along the flight plan,

extract free cells that are located vertically above objects corresponding to the flight plan, where

the free cells are three-dimensional, and

the extraction of free cells employs a recursive space decomposition technique within the plurality of pre-processing boxes,

define traversable free space based upon availability of free cells, where

the traversable free space is three-dimensional,

construct a reference path traversing through the traversable free space between two points on the flight plan,

refine the reference path using a genetic algorithm, and

provide flight path data to at least one avionics system, wherein

such flight path data is representative of at least the refined reference flight path between the two points on the flight plan; and

at least one avionics system configured to receive the flight path data.

2. The system of claim 1, further comprising:

a source for providing threat data, and

the processor is further configured to

receive threat data,

extract pseudo-free cells above objects corresponding to the threat data, where the pseudo-free cells are three-dimensional,

identify each pseudo-free cell as either a free cell or a full cell, where a pseudo-free cell is identified as a full cell when

terrain masking is not applied, or

at least one line of sight vector in the pseudo-free cell does not penetrate through terrain when terrain masking is applied,

eliminate full cells from the availability of free cells, and

determine the location of deviation and re-entry points based upon the threat data, whereby

such deviation and re-entry points are used as the two points on the flight plan.

3. The system of claim 2, wherein the source for providing threat data comprises at least one of the following:

an aircraft defense system, a weather radar system, a weather awareness and warning system, and an airspace awareness and warning system.

4. The system of claim 2, further comprising:

a crew alerting system configured to receive a threat alert signal, where

the processor is further configured to

generate the threat alert signal based upon the threat data, and provide the threat alert signal to the crew alerting system.

5. The system of claim 1, wherein the source for providing object data includes a terrain database, an obstacle database, a non-terrain and/or obstacle acquisition system, or a combination thereof.

6. The system of claim 1, wherein the objects includes terrain, obstacles, or both.

7. The system of claim 1, wherein the processor is a processor of an avionics system.

8. The system of claim 7, wherein the processor is a processor of a flight management system, a vision system, an autoflight system, or a display unit system.

9. The system of claim 1, wherein the genetic algorithm comprises:

generating a plurality of path candidates from the reference path to form a population;

evaluating a fitness value for each path candidate;

performing a generation cycle, wherein the generation cycle comprises

selecting parent path candidates from best path candidates,

generating a plurality of offspring path candidates from parent path candidates,

evaluating a fitness value for each offspring path candidate,

adding the offspring path candidates to the population, and

selecting best path candidates to form a population;

repeating the generation cycle on the formed population when an exit condition has not been reached; and

generating flight path data from the data representative of the best path candidate from the formed population when an exit condition has been reached.

10. The system of claim 9, wherein

the plurality of path candidates and a plurality of offspring path candidates are generated using a plurality of genetic operators, and

the fitness value of each path candidates and the fitness value of each offspring path candidate are evaluated using at least one aircraft kinematic constraint.

11. The system of claim 10, wherein an aircraft kinematic constraint comprises at least one aircraft performance constraint, at least one flight operational constraint, or at least one aircraft performance constraint and at least one flight operational constraint.

12. The system of claim 10, further comprising:

a source for providing input factor data, and

the processor is further configured to receive input factor data, whereby

such input factor data is applied to at least one aircraft kinematic constraint.

13. The system of claim 1, wherein the avionics system receiving the flight path data includes at least one of the following:

a flight management system, a vision system, an autoflight system, or a display unit system.

14. The system of claim 1, wherein the flight path data includes flight plan data not affected by the construction and refinement of the reference path.

15. A module for constructing a flight path used by an avionics system, said module comprising:

an input communications interface to facilitate the receiving of data by a processor from at least one data source;

a processor configured to

receive data representative of a flight plan of an aircraft,

receive data representative of objects,

define a plurality of pre-processing boxes, where

at least one pre-processing box corresponds to a current position of the aircraft along the flight plan, and

at least one pre-processing box corresponds to a future position of the aircraft along the flight plan,

extract free cells that are located vertically above objects corresponding to the flight plan, where

the free cells are three-dimensional, and

the extraction of free cells employs a recursive space decomposition technique within the plurality of pre-processing boxes,

define traversable free space based upon availability of free cells, where

the traversable free space is three-dimensional,

construct a reference path traversing through the traversable free space between two points on the flight plan,

refine the reference path using a genetic algorithm, and

provide flight path data to at least one avionics system, wherein

such flight path data is representative of at least the refined reference flight path between the two points on the flight plan; and

an output communications interface to facilitate the providing of the flight plan data to at least one avionics system.

16. The module of claim 15, wherein

the processor is further configured to

receive threat data;

extract pseudo-free cells above objects corresponding to the threat data, where the pseudo-free cells are three-dimensional;

identify each pseudo-free cell as either a free cell or a full cell, where a pseudo-free cell is identified as a full cell when

terrain masking is not applied, or

at least one line of sight vector in the pseudo-free cell does not penetrate through terrain when terrain masking is applied;

eliminate full cells from the availability of free cells; and

determine the location of deviation and re-entry points based upon the threat data, whereby

such deviation and re-entry points are used as the two points on the flight plan.

17. The module of claim 16, wherein

the processor is further configured to

generate a threat alert signal based upon the threat data, and

provide the threat alert signal to the crew alerting system.

18. The module of claim 15, wherein the objects includes terrain, obstacles, or both.

19. The module of claim 15, wherein the module is a module of an avionics system.

20. The module of claim 19, wherein the module is a module of a flight management system, a vision system, an autoflight system, or a display unit system.

21. The module of claim 15, wherein the genetic algorithm comprises:

generating a plurality of path candidates from the reference path to form a population evaluating a fitness value for each path candidate;

performing a generation cycle, wherein the generation cycle comprises

selecting parent path candidates from best path candidates,

generating a plurality of offspring path candidates from parent path candidates,

evaluating a fitness value for each offspring path candidate,

adding the offspring path candidates to the population, and

selecting best path candidates to form a population;

repeating the generation cycle on the formed population when an exit condition has not been reached; and

generating flight path data from the data representative of the best path candidate from the formed population when an exit condition has been reached.

22. The module of claim 21, wherein

the plurality of path candidates and a plurality of offspring path candidates are generated using a plurality of genetic operators, and

the fitness value of each path candidates and the fitness value of each offspring path candidate are evaluated using at least one aircraft kinematic constraint.

23. The module of claim 22, wherein an aircraft kinematic constraint comprises at least one aircraft performance constraint, at least one flight operational constraint, or at least one aircraft performance constraint and at least one flight operational constraint.

24. The module of claim 22, wherein the processor is further configured to receive input factor data, whereby such input factor data is applied to at least one aircraft kinematic constraint.

25. The module of claim 15, wherein the flight path data includes flight plan data not affected by the construction and refinement of the reference path.

26. A method of constructing a flight path used by an avionics system, said method comprising:

receiving data representative of a flight plan of an aircraft;

receiving data representative of objects;

defining a plurality of pre-processing boxes, where

at least one pre-processing box corresponds to a current position of the aircraft along the flight plan, and

at least one pre-processing box corresponds to a future position of the aircraft along the flight plan;

extracting free cells that are located vertically above objects corresponding to the flight plan, where

the free cells are three-dimensional, and

the extraction of free cells employs a recursive space decomposition technique within the plurality of pre-processing boxes;

defining traversable free space based upon availability of free cells;

constructing a reference path traversing through the traversable free space between two points on the flight plan;

refining the reference path using a genetic algorithm; and

providing flight path data to at least one avionics system, wherein

such flight path data is representative of at least the refined reference flight path between the two points on the flight plan.

27. The method of claim 26, further comprising:

receiving threat data;

extracting pseudo-free cells above objects corresponding to the threat data, where

the pseudo-free cells are three-dimensional;

identifying each pseudo-free cell as either a free cell or a full cell, where a pseudo-free cell is identified as a full cell when

terrain masking is not applied, or

at least one line of sight vector in the pseudo-free cell does not penetrate through terrain when terrain masking is applied;

eliminating full cells from the availability of free cells; and

determining the location of deviation and re-entry points based upon the threat data, whereby

such deviation and re-entry points are used as the two points on the flight plan.

28. The method of claim 27, further comprising:

generating a threat alert signal based upon the threat data, and

providing the threat alert signal to a crew alerting system.

29. The method of claim 26, wherein the genetic algorithm comprises:

generating a plurality of path candidates from the reference path to form a population;

evaluating a fitness value for each path candidate;

performing a generation cycle, wherein the generation cycle comprises

selecting parent path candidates from best path candidates,

generating a plurality of offspring path candidates from parent path candidates,

evaluating a fitness value for each offspring path candidate,

adding the offspring path candidates to the population, and

selecting best path candidates to form a population;

repeating the generation cycle on the formed population when an exit condition has not been reached; and

generating flight path data from the data representative of the best path candidate from the formed population when an exit condition has been reached.

30. The method of claim 29, wherein

the plurality of path candidates and a plurality of offspring path candidates are generated using a plurality of genetic operators, and

the fitness value of each path candidates and the fitness value of each offspring path candidate are evaluated using at least one aircraft kinematic constraint.

31. The method of claim 30, wherein an aircraft kinematic constraint comprises at least one aircraft performance constraint, at least one flight operational constraint, or at least one aircraft performance constraint and at least one flight operational constraint.

32. The method of claim 30, further comprising:

receiving input factor data, whereby such input factor data is applied to at least one aircraft kinematic constraint.

33. The method of claim 26, wherein the flight path data includes flight plan data not affected by the construction and refinement of the reference path.