Computation-time-optimized route planning for aircraft

• US 8,639,397 B2
• Filed: 10/08/2009
• Issued: 01/28/2014
• Est. Priority Date: 10/10/2008
• Status: Active Grant

• Current Assignee: Airbus Defence and Space GmbH (Airbus SE)
• Original Assignee: EADS Deutschland GmbH (Airbus SE)
• Inventors: Verlut, Gregoire, Lohmiller, Winfried
• Primary Examiner(s): Nguyen, Kim T
• Application Number:
  US12/575,938
• Publication Number:
  US 20100094485A1
• Time in Patent Office: 1,573 Days
• Field of Search: 701/3, 701/5, 701/7, 701/30.2, 701/533
• US Class Current: 701/3
• 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: G05D 1/0005 with arrangements to save energy
• CPC Class Codes: G05D 1/0646 to follow the profile of undulating ground
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A process and system for the planning a cost-minimized aircraft flight route between a starting point and end point takes into account costs associated with the flight route, no-fly zones and flight corridors, and aircraft limitations. A raster set is determined which comprises topographical points between the starting and end points, and costs associated with the respective raster points are determined. N nodes are determined for each raster point of at least one subset of the raster set, such nodes being associated with approach directions of the raster point by the aircraft. Possible take-off directions of the raster point are defined, taking into account the minimum turning radius of the aircraft, as a function of the approach direction. A cost-minimized flight route is determined by means of a shortest path algorithm, taking into account only the k most cost-effective nodes (k<N) for a raster point.

Claims

1. A process for determining a cost-minimized flight route for an aircraft between a starting point and an end point, taking into account costs associated with the flight route and limitations of the flight route caused by the aircraft, the process comprising:

determining, by a processor, a raster set which comprises topographical raster points between the starting point and the end point;

determining, by the processor, costs associated with respective raster points of the raster set;

determining, by the processor, N nodes for each raster point of at least one subset of the raster set;

wherein

i) the N nodes are associated with approach directions of the aircraft to the raster point;

ii) possible take-off directions of the raster point are determined as a function of the approach directions; and

iii) said possible take-off directions are defined taking into account a turning radius of the aircraft; and

determining, by the processor, the cost-minimized flight route between the starting point and the end point by means of a shortest path algorithm;

wherein

x) for a particular raster point, only k most cost-effective nodes are taken into account; and

y) k≧

3 and k is less than N.

2. The process according to claim 1, wherein a raster point is defined by geographic area coordinates and topological altitude of a point on the earth'"'"'s surface.

3. The process according to claim 1, wherein the costs take into account a threat risk of the aircraft.

4. The process according to claim 3, wherein the threat risk takes into account at least one of:

a line of sight starting from a raster point;

presence of surface-to-air missiles;

presence of radar stations;

“

no-fly”

zones; and

flight corridors.

5. The process according to claim 1, wherein the costs take into account flight altitude of the aircraft.

6. The process according to claim 5, wherein a minimal flight altitude possible at a topographical height of a raster point is taken into account for computing the costs.

7. The process according to claim 5, wherein a minimal flight altitude possible at the topographical height of a raster point and a possible rate of descent of the aircraft are taken into account for computing the costs.

8. The process according to claim 1, wherein a number of raster points in the raster set depends on a minimum turning radius of the aircraft.

9. The process according to claim 1, wherein:

each of the N nodes defines an approach direction of the raster point by the aircraft; and

the N approach directions are uniformly distributed on a circle.

10. The process according to claim 1, wherein said possible take-off directions define a transition from a current raster point to a raster point that follows.

11. The process according to claim 10, wherein costs of the transition depend on costs of the raster points adjoining the transition, and on a time in which the aircraft flies through the transition.

12. The process according to claim 10, wherein the nodes associated with the raster points, the transitions between these nodes and the costs of the transitions define a weighted graph.

13. The process according to claim 1, wherein only geographical coordinates of a raster point and the raster point'"'"'s associated approach directions, but not the flight altitude of the aircraft, define nodes for determination of the cost-minimized flight route by means of the shortest path algorithm.

14. The process according to claim 1, wherein three possible take-off directions are defined for the nodes, including a straight-line take-off direction, a take-off direction extending leftward and a take-off direction extending rightward.

15. The process according to claim 1, wherein N is equal to 16 and k is equal to 3.

16. The process according to claim 1, wherein the shortest path algorithm is one of a Dijkstra algorithm, an A* algorithm, and a Bellmann-Ford algorithm.

17. An onboard computer of an aircraft which implements the process according to claim 1.

18. A system for determining a cost-minimized flight route for an aircraft between a starting point and an end point, taking into account costs associated with the flight route and limitations of the flight route caused by the aircraft, the system comprising:

computation means for determining a raster set which comprises topographical raster points between the starting point and the end point;

computation means for determining costs associated with respective raster points of the raster set;

computation means for determining N nodes to each raster point of at least one subset of the raster set;

wherein

i) the N nodes are associated with approach directions of the aircraft to the raster point;

ii) possible take-off directions of the raster point are determined as a function of the approach directions; and

iii) said possible take-off directions are defined, taking into account a turning radius of the aircraft; and

computation means for determining the cost-minimized flight route between the starting point and the end point by means of a shortest path algorithm;

wherein

x) for a particular raster point, only k most cost-effective nodes are taken into account; and

y) k≧

3 and k is less than N.

19. An air control system for aircraft which comprises the system according to claim 18.