Computation-Time-Optimized Route Planning for Aircraft

• US 20100094485A1
• Filed: 10/08/2009
• Published: 04/15/2010
• Est. Priority Date: 10/10/2008
• Status: Active Grant

• Current Assignee: Airbus Defence and Space GmbH
• Original Assignee: EADS Deutschland GmbH (Airbus SE)
• Inventors: Lohmiller, Winfried, VERLUT, Gregoire
• Granted Patent: US 8,639,397 B2
• Time in Patent Office: Days
• 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 a raster set which comprises topographical raster points between the starting point and the end point;

determining costs associated with respective raster points of the raster set;

determining 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 direction; and

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

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 the k most cost-effective nodes are taken into account; and

y) k is smaller 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 the 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 1, wherein only geographical coordinates of a raster point and its 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.

13. 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.

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

15. 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.

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.

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

17. 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 direction; 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 the k most cost-effective nodes are taken into account; and

y) k is smaller than N.

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

20. A process for planning a cost-minimized flight route for low-flying aircraft between a starting point and an end point, taking into account costs dependent on the flight altitude and limitations of a climb rate caused by the aircraft, the process comprising:

determining a node set between the starting point and the end point;

determining topographical height of the nodes of the node set;

determining costs associated with the nodes of the node set, which costs depend on the flight altitude of the aircraft;

determining the cost-minimized route section between the starting point and a current node by means of a shortest path algorithm, wherein a minimum possible flight altitude is assumed at the nodes of a route section for determining the costs of the route section;

determining if the aircraft cannot reach the topographical height of the current node starting from the flight altitude at a preceding node of the route section;

determining corrected costs of the route section taking into account a climb rate of the aircraft and a minimum possible flight altitude at the current node; and

continuing the process, taking into account the corrected costs of a current route section until the current node corresponds to the end point.

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

22. The process according to claim 21, 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.

23. The process according to claim 20, wherein a node is defined by geographic area coordinates of a point on the earth'"'"'s surface.

24. The process according to claim 20, wherein geographic coordinates of a node, and not the flight altitude of the aircraft, define nodes for determining a cost-minimized route section by means of the shortest path algorithm.

25. The process according to claim 20, wherein the step of determining a node set comprises:

determining a raster set which comprises possible topographic points between the starting point and the end point; and

determining N nodes associated with a raster point of the raster set;

wherein

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

possible take-off directions of a raster point are defined as a function of the approach direction; and

the possible take-off directions are defined while taking into account a turning radius of the aircraft.

26. The process according to claim 25, wherein during the determination of the most cost-effective route section:

only the k most cost-effective nodes associated with a raster point are taken into account; and

k is smaller than N.

27. The process according to claim 20, wherein

the shortest path algorithm is either a Dijkstra algorithm, an A* algorithm, or a Bellmann-Ford algorithm.

28. The process according to claim 20, wherein the step of determining the corrected costs of the route section comprises:

determining corrected minimum possible flight altitudes of the aircraft at preceding nodes, taking into account the climb rate of the aircraft and the minimum possible flight altitude to be reached at the current node; and

determining costs associated with preceding nodes at the corrected minimum possible flight altitudes of the aircraft.

29. The process according to claim 28, wherein the minimum possible flight altitude at a node is obtained from minimum possible flight altitude at nodes that follow, minus a product of the climb rate and geometric distance of the two nodes.

32. An onboard computer of an aircraft, which carries out the process according to claim 20.

30. A system for determining a cost-minimized flight route for low-flying aircraft between a starting point and an end point taking into account costs dependent on the flight altitude and aircraft limitations climb rate, said system comprising:

means for determining a node set between the starting point and the end point;

means for determining topographical height of nodes of the node set;

means for determining costs associated with the nodes of the node set, which costs depend on flight altitude of the aircraft;

means for determining a cost-minimized route section between the starting point and a current node by means of a shortest path algorithm, wherein a minimum possible flight altitude is assumed at nodes of a route section, for determining the costs of the route section;

means for recognizing if the aircraft is unable to reach the topographical height of a current node, starting from a flight altitude at a preceding node of the route section; and

means for determining corrected costs of the route section, taking into account the climb rate of the aircraft and the minimum possible flight altitude to be reached at the current node.

31. A flight control system for aircraft which comprises the system according to claim 30.