Method for establishing optimized paths of movement of vehicles

• US 20080021635A1
• Filed: 07/18/2007
• Published: 01/24/2008
• Est. Priority Date: 07/19/2006
• Status: Abandoned Application

• Current Assignee: EADS Deutschland GmbH (Airbus SE)
• Original Assignee: EADS Deutschland GmbH (Airbus SE)
• Inventors: Lohmiller, Winfried, Loechelt, Sven, Henning, Ulrich, Batet, Monica
• Application Number:
  US11/826,793
• Publication Number:
  US 20080021635A1
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G05D 1/0005 with arrangements to save energy
• CPC Class Codes: G05D 1/0202 specially adapted to aircraft
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0052 for cruising combined instruments indicating more than one navigational value G01C23/00

Abstract

A method and apparatus for planning vehicle trajectories or routing in which a first optimized route between a starting point and a destination is established with regard to a first, relatively coarse node grid, using known techniques. In order to further refine route selection, a second relatively finer node grid is then established within a predeterminable area or volume that is adjacent yo the first optimized route, along its length. The latter finer node grid is then used to establish a second enhanced polygonal path from among the possible polygonal paths between the starting and destination points according to the finer node grid, once again using a known optimization technique.

Claims

1. A method for planning an optimized routing for a vehicle, said method comprising:

discretizing a region between a starting point and a destination by establishing a first node grid;

establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and

determining a predeterminable region around the first polygonal path;

establishing within said predeterminable region a more finely divided second node grid; and

from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid.

2. The method according to claim 1, wherein the second polygonal path is improved in a continuous optimization calculation or filtering/smoothing, taking account of flyable conditions, including at least one of maximum acceleration, minimum flight curve radius or the derivative.

3. The method according to claim 1, wherein a ratio of size of a cell formed by direct neighbors of a grid point in the first node grid to a size of a cell formed by direct neighbors of a grid point in the second node grid is at least 2.

4. The method according to claim 1, wherein the respective optimum paths are established from paths which extend from the starting point to the destination and have been calculated according to Dijkstra'"'"'s algorithm.

5. The method according to claim 1, wherein the respective optimum paths are established from paths which extend from the starting point to the destination and have been calculated according to Dijkstra'"'"'s dual algorithm.

6. The method according to claim 1, wherein a plurality of weightable optimization parameters are taken into account.

7. The method according to claim 6, wherein said weightable optimization parameters comprise at least one of minimum danger, speed or minimum danger and fuel consumption.

8. A computer readable medium encoded with a computer program that includes instructions which, when loaded into a computer, cause the computer to perform an optimized route selection for a vehicle, according to the following steps:

discretizing a region between a starting point and a destination by establishing a first node grid;

establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and

determining a predeterminable region around the first polygonal path;

establishing within said predeterminable region a more finely divided second node grid; and

from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid.

9. The method according to claim 8, wherein the second polygonal path is improved in a continuous optimization calculation or filtering/smoothing, taking account of flyable conditions, including at least one of maximum acceleration, minimum flight curve radius or the derivative.

10. The method according to claim 8, wherein a ratio of size of a cell formed by direct neighbors of a grid point in the first node grid to a size of a cell formed by direct neighbors of a grid point in the second node grid is at least 2.

11. The method according to claim 8, wherein a plurality of weightable optimization parameters are taken into account.

12. The method according to claim 11, wherein said weightable optimization parameters comprise at least one of minimum danger, speed or minimum danger and fuel consumption.

17. The method according to claim 12, wherein said weightable optimization parameters comprise at least one of minimum danger, speed or minimum danger and fuel consumption.

13. A system for planning an optimized routing for a vehicle, said system comprising:

a computer;

a memory contained in said computer and having stored therein data which are indicative of parameters that influence desirability of possible alternative routes; and

a computer readable medium which is accessible by said computer, and which has encoded therein a computer program which, when loaded into said computer, causes it to perform an optimized route selection for a vehicle, including

discretizing a region between a starting point and a destination by establishing a first node grid;

establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and

determining a predeterminable region around the first polygonal path;

establishing within said predeterminable region a more finely divided second node grid; and

from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid.

14. The method according to claim 13, wherein the second polygonal path is improved in a continuous optimization calculation or filtering/smoothing, taking account of flyable conditions, including at least one of maximum acceleration, minimum flight curve radius or the derivative.

15. The method according to claim 13, wherein a ratio of size of a cell formed by direct neighbors of a grid point in the first node grid to a size of a cell formed by direct neighbors of a grid point in the second node grid is at least 2.

16. The method according to claim 13, wherein a plurality of weightable optimization.