Computing-time-efficient route determination along several preset path points with given connecting routes in-between

• US 8,401,790 B2
• Filed: 10/08/2009
• Issued: 03/19/2013
• 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: Lohmiller, Winfried, Noetzold, Dieter, Eisele, Matthias, Verlut, Gregoire
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US12/575,923
• Publication Number:
  US 20100106398A1
• Time in Patent Office: 1,258 Days
• Field of Search: 701/528, 701/410, 701/420, 701/465, 701/3, 340/995.19, 340/995.23
• US Class Current: 701/528
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/24 specially adapted for cosmonautical navigation
• CPC Class Codes: G08G 5/0052 for cruising combined instruments indicating more than one navigational value G01C23/00
• CPC Class Codes: G08G 5/006 in accordance with predefined flight zones, e.g. to avoid prohibited zones

Abstract

A process for determining a route along more than two mutually consecutive preset path points with given connecting routes in-between. In this case, a plurality of connecting routes is given between at least one pair of two mutually consecutive path points. Respective costs and preferably also a respective time duration are assigned to each connecting route. In a first step of the process, a tree is generated which comprises edges and nodes connected by edges. Each node is assigned to a defined path point and each edge corresponds to a connecting route. The route is determined based on a selection of edges of the tree.

Claims

1. A process for determining a route along at least three mutually consecutive preset path points with connecting routes in-between;

wherein a plurality of connecting routes is given between at least a pair of mutually consecutive path points, and respective costs are assigned to each connecting route;

said method comprising;

generating a tree comprising edges, as well as nodes that are connected by edges, each node being assigned to a defined path point and each edge corresponding to a connecting route; and

determining the route based on a selection of edges of the tree,

wherein

said tree has a plurality of tree levels on which the nodes are distributed;

the nodes of a tree level are assigned to a common path point; and

different nodes of a tree level are assigned to different values of a characteristic of a path point.

2. The process according to claim 1, wherein:

each connecting route has a time duration assigned thereof; and

different nodes of a tree level are assigned to different time data.

3. The process according to claim 2, wherein, for at least a plurality of nodes in each case, a node-specific time indication, node-specific costs and a reference to a node preceding in the tree are stored.

4. The process according to claim 3, wherein, for at least a plurality of nodes, in each case, the following are stored:

a total time duration from a reference point to the respective node as a node-specific time indication; and

the total costs from the reference point to the respective node as node-specific costs.

5. The process according to claim 3, wherein the stored reference references refers to a preceding node by which the time indication is reached at the lowest cost.

6. The process according to claim 5, wherein the reference comprises a connecting route index.

7. The process according to claim 1, wherein the tree is generated iteratively.

8. The process according to claim 1, wherein:

the tree is generated iteratively; and

in an iteration, combinations of the individual node-specific time indications of a path point and the connecting routes to a following path point in the tree are determined which have the lowest node-specific costs in the case of identical resulting time indications.

9. The process according to claim 1, wherein:

the tree is generated iteratively; and

in an iteration, nodes of a path point following in the tree are determined by combining the nodes of a path point with the connecting routes to form the path point that follows;

wherein the nodes of the path point that follows have the lowest node-specific costs for the individual time indications.

10. The process according to claim 1, wherein a time demand exists for at least one of the path points.

11. The process according to claim 2, wherein:

a time demand exists for at least one of the path points; and

at least one node of a path point, which is characterized by its time indications, is selected as a function of time demand.

12. The process according to claim 11, wherein the tree is continued only by the selected at least one node of a path point.

13. The process according to claim 3, wherein the step of determining the route comprises:

selecting a node of a level of the tree which is the last for which there is a time demand;

wherein the selection takes place by comparing the time demand with time indications of the nodes.

14. The process according to claim 13, wherein the step of determining the route further comprises selecting the edges from the selected node to the root node, utilizing stored references.

15. The process according to claim 1, wherein the route of a vehicle is determined.

16. A system for determining a route along at least three mutually consecutive preset path points with connecting routes in-between;

wherein a plurality of connecting routes is given between at least a pair of mutually consecutive path points, and respective costs are assigned to each connecting route, said system comprising;

means for generating a tree comprising edges and nodes connected by edges, wherein each node is assigned to a defined path point and each edge corresponds to a connecting route; and

means for determining the route based on a selection of edges of the tree,

wherein

said tree has a plurality of tree levels on which the nodes are distributed;

the nodes of a tree level are assigned to a common path point; and

different nodes of a tree level are assigned to different values of a characteristic of a path point.

17. An onboard computer of a vehicle comprising the system according to claim 16.

18. A process for determining a route along at least three mutually consecutive preset path points;

said process comprising;

determining connecting routes between a first pair of path points independently of a determination of other connecting routes between other pairs of path points; and

determining the route based on the connecting routes of the at least three mutually consecutive path points, wherein the first pair of path points each comprise a plurality of nodes of a tree level of a tree that includes the connecting routes and the first and other pair of path points.

19. The process according to claim 18, further comprising:

newly determining connecting routes between the first pair of path points; and

newly determining the route based on the newly determined connecting routes.