Method and system for computer-supported determination of a route from a starting point to a destination point

• US 6,421,605 B1
• Filed: 04/19/2000
• Issued: 07/16/2002
• Est. Priority Date: 10/21/1997
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Burt, Alastair, Steiner, Donald, Dieterich, Hartmut, Lind, Jürgen
• Primary Examiner(s): Zanelli, Michael J.
• Assistant Examiner(s): Gibson, Eric M.
• Application Number:
  US09/529,785
• Time in Patent Office: 818 Days
• Field of Search: 701/201, 701/202, 701/206, 701/209, 701/210
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

In an iterative method and system, a route is determined from a starting point to a destination point. Sub-modules are supplied with digital messages that respectively contain at least one sub-starting point and one sub-destination point that are contained in a sub-route map that is allocated to the respective sub-module that receives the respective message. Each sub-module determines a sub-route between the respective sub-starting point and the respective sub-destination point. The route is formed from the sub-route.

Claims

1. A method for computer-supported determination of a route from a starting point to a destination point that respectively lie in different sub-route maps, the method comprising the steps of:

storing the sub-route maps in digital form;

allocating respective sub-modules to respective sub-route maps;

supplying the sub-modules with digital messages that respectively contain at least a sub-starting point and at least a sub-destination point that lie in the sub-route map of the sub-module that receives the respective digital message;

determining at least one sub-route, via the respective sub-module, between the respective sub-starting point and the sub-destination point; and

forming the route from the sub-routes.

2. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, wherein the sub-route maps are stored in the form of sub-route graphs with nodes and edges.

3. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 2, wherein the route is a set of interconnected nodes and edges between the starting point and the destination point.

4. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, further comprising the step of:

storing a data bank, on the basis of which possible chainings of sub-modules are determined, in a central module.

5. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, wherein the sub-modules are software agents.

6. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, further comprising the step of:

storing a sub-data bank in each sub-module, wherein at least one optimized route in the sub-module is determined with reference to the sub-data bank.

7. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, wherein the step of determining at least one sub-route includes determining shortest paths in the sub-route map allocated to the respective sub-module.

8. A method for computer-supported determination of a route from a starting point to a destination point as claimed in claim 1, wherein the determination of the sub-route occurs such that the sub-route is optimized in view of a cost function.

9. A system for computer-supported determination of a route from a starting point to a destination point that respectively lie in different sub-route maps, wherein the sub-route maps are stored in digital form, the system including at least one processor unit which comprises a plurality of sub-modules that are respectively allocated to a sub-route map, wherein each of the plurality of sub-modules are supplied with a digital message that respectively contains at least a sub-starting point and a sub-destination point that lie in the sub-route map of the respective sub-module that receives the respective digital message, wherein each sub-module determines at least one sub-route between the respective sub-starting point and the sub-destination point, and wherein the route is formed from the plurality of sub-routes.

10. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, wherein the processor unit is configured such that the sub-route maps are stored in the form of sub-route graphs which nodes and edges.

11. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 10, wherein the processor unit is configured such that the route is a set of interconnected nodes and edges between the starting point and the destination point.

12. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, the system further comprising:

a central module; and

a data bank with reference to which possible chainings of sub-modules are determined which is stored in the central module.

13. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, wherein the processor unit is configured such that the sub-modules are software agents.

14. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, wherein the processor unit is configured such that a sub-data bank with reference to which at least one optimized route in the sub-module is determined is stored in each sub-module.

15. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, wherein the processor unit is configured such that the determination of the at least one sub-route includes a determination of shortest paths in the sub-route map allocated to the respective sub-module.

16. A system for computer-supported determination of a route from a starting point to a destination point as claimed in claim 9, wherein the processor unit is configured such that the determination of the sub-route occurs such that the sub-route is optimized in view of a cost function.