Method and apparatus for determining a route and correction values for heuristic values

• US 10,145,695 B2
• Filed: 12/18/2015
• Issued: 12/04/2018
• Est. Priority Date: 06/20/2013
• Status: Active Grant

• Current Assignee: Bayerische Motoren Werke AG
• Original Assignee: Bayerische Motoren Werke AG
• Inventors: Tava, Marcello
• Primary Examiner(s): Tissot, Adam D
• Assistant Examiner(s): Pipala, Edward J
• Application Number:
  US14/973,851
• Publication Number:
  US 20160102989A1
• Time in Patent Office: 1,082 Days
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

The route from a prescribed starting node to a prescribed destination node is determined on the basis of digital map data stored in a memory unit such that, for possible expansion of a respective current node, total costs are determined for the current node on the basis of a sum of edge costs for an optimum route from the starting node to the current node and a destination-node-related heuristic value for the current node and a prescribed destination-node-related correction value. The destination-node-related correction value is in this case representative of a mean value for cost ratios for respective nodes in a prescribed set, wherein the respective cost ratios are dependent on the edge costs of the connections that are situated between the current node and the respective node in the set and that represent an optimum route between the current node and this node in the set and on a heuristic value for the current node in relation to this node in the set.

Claims

1. A method for determining a route for at least one of a navigation system and a driver assistance system with an associated storage unit in a vehicle for storing digital map data for at least one of a route network and a path network in a predefined area, the digital map data comprising:

respective nodes in the predefined area and connections between the respective nodes in the predefined area,

respective edge costs for the respective connections between the nodes, and

predefined correction values for the respective nodes,

wherein the method comprises the acts of;

determining, by an apparatus including a processor programmed to determine the route, the route from a predefined starting node to a predefined destination node on the basis of the digital map data stored in the storage unit wherein, for a possible expansion of a respective current node, total costs are determined for the current node based on;

(i) a sum of edge costs (g) of an optimum route from the starting node to the current node and a destination-node-based heuristic value (h) for the current node, which represents respectively estimated costs from the current node to the destination node, and

(ii) a predefined destination-node-based correction value (k) which is representative of a mean value of cost ratios (Cost) of respective nodes in a predefined set, wherein the respective cost ratios (Cost) are dependent on;

the edge costs of the connections, which lie between the current node and the respective node in the set and represent an optimum route between the current node and the respective node in the set, and

a heuristic value for the current node with respect to the respective node in the set; and

forwarding the determined route to the at least one of the navigation system and the driver assistance system for at least one of indicating the determined route and controlling the vehicle.

2. The method according to claim 1, wherein the digital map data comprise the respective positions of the nodes, and the method further comprises the act of:

determining the destination-node-based heuristic value on the basis of the position of the current node and the position of the destination node.

3. The method according to claim 1, wherein

the digital map data comprise predefined heuristic values for the respective nodes with respect to respective other nodes in the predefined area, which each represent estimated costs from one node in each case to the other node in each case, and the destination-node-based heuristic value is therefore predefined.

4. The method according to claim 1, wherein:

the respective destination-node-based heuristic value represents a Euclidean distance between the current node and the destination node.

5. The method according to claim 1, wherein the heuristic value for the current node with respect to the respective node in the set represents a Euclidean distance between the current node and the respective node in the set.

6. The method according to claim 1, wherein:

the predefined area is subdivided into a plurality of segment regions, and

the respective nodes in the predefined set comprises selected nodes which are arranged in a destination node segment region which comprises at least the destination node.

7. The method according to claim 1, wherein

the mean value of the cost ratios of the respective nodes in the predefined set represents an arithmetic mean value of the cost ratios.

8. The method according to claim 6, wherein

the respective segment region of the predefined area comprises a predefined radius region starting from the current node and a predefined angle region around the current node.

9. The method according to claim 7, wherein

the respective segment region of the predefined area comprises a predefined radius region starting from the current node and a predefined angle region around the current node.

10. A method for determining correction values for a route calculation algorithm based on digital map data for at least one of a route network and a path network in a predefined area, the digital map data comprising:

respective nodes in the predefined area and connections between the respective nodes in the predefined area, and

respective edge costs for the respective connections between the nodes,

the method comprising the acts of;

predefining, by an apparatus including a processor programmed to determine a route, at least one reference set of nodes for at least some of the nodes in the predefined area for the respective node, and

for the at least one predefined reference set of nodes;

determining, by the apparatus including the processor programmed to determine the route, a cost ratio for the respective node in the reference set based on;

the edge costs of the connections, which lie between the node, for which a correction value is determined, and the respective node in the reference set and represent an optimum route between the node, for which the correction value is determined, and the node in the reference set, and

a heuristic value for the node, for which the correction value is determined, with respect to the node in the reference set,

determining, by the apparatus including the processor programmed to determine the route, a mean value based on the determined cost ratios of the nodes in the reference set, and

determining, by the apparatus including the processor programmed to determine the route a correction value based on the mean value.

11. The method according to claim 10, wherein the digital map data comprise the respective positions of the nodes, wherein the act of determining the heuristic value for the node, for which the correction value is determined, with respect to the respective node in the reference set is based on the position of the node, for which the correction value is determined, and the position of the respective node in the reference set.

12. The method according to claim 10, wherein the digital map data comprise predefined heuristic values for the respective nodes with respect to the respective other nodes in the predefined area, which each represent estimated costs from one node in each case to the other node in each case, and the heuristic value for the node, for which the correction value is determined, with respect to the respective node in the reference set is therefore predefined.

13. The method according to claim 10, wherein

the heuristic value for the node, for which the correction value is determined, with respect to the node in the reference set represents a Euclidean distance between the node, for which the correction value is determined, and the node in the reference set.

14. The method according to claim 10, wherein:

the predefined area is subdivided into a plurality of segment regions starting from the respective node for which the correction values are calculated, and

selected nodes in the respective segment regions each form one of the predefined reference sets of nodes.

15. The method according to claim 14, wherein

the predefined segment regions in the predefined area each comprise a predefined radius region starting from the respective node, for which the correction value is determined, and a predefined angle region around this node for which the correction value is determined.

16. An apparatus for determining a route for at least one of a navigation system and a driver assistance system with an associated storage unit for storing digital map data for at least one of a route network and a path network in a predefined area, the digital map data comprising:

respective nodes in the predefined area and connections between the respective nodes in the predefined area,

respective edge costs for the respective connections between the nodes, and

predefined correction values for the respective nodes,

wherein the apparatus comprises a processor that executes a program to;

determine the route from a predefined starting node to a predefined destination node on the basis of the digital map data stored in the storage unit such that, for a possible expansion of a respective current node, total costs are determined for the current node based on;

(i) a sum of edge costs (g) of an optimum route from the starting node to the current node and a destination-node-based heuristic value (h) for the current node, which represents respectively estimated costs from the current node to the destination node, and

(ii) a predefined destination-node-based correction value (k) which is representative of a mean value of cost ratios (Cost) of respective nodes in a predefined set, wherein the respective cost ratios (Cost) are dependent on;

the edge costs of the connections, which lie between the current node and the respective node in the set and represent an optimum route between the current node and the respective node in the set, and

a heuristic value for the current node with respect to the respective node in the set.

17. A system, comprising:

a storage unit that stores digital map data for at least one of a route network and a path network in a predefined area, the digital map data comprising;

respective nodes in the predefined area and connections between the respective nodes in the predefined area,

respective edge costs for the respective connections between the nodes, and

predefined correction values for the respective nodes;

an apparatus for determining a route, the apparatus being coupled with the storage unit and being configured to read the digital map data from the storage unit, wherein the apparatus comprises;

a processor that executes program code to;

determine the route from a predefined starting node to a predefined destination node on the basis of the digital map data stored in the storage unit such that, for a possible expansion of a respective current node, total costs are determined for the current node based on;

(i) a sum of edge costs (g) of an optimum route from the starting node to the current node and a destination-node-based heuristic value (h) for the current node, which represents respectively estimated costs from the current node to the destination node, and

(ii) a predefined destination-node-based correction value (k) which is representative of a mean value of cost ratios (Cost) of respective nodes in a predefined set, wherein the respective cost ratios (Cost) are dependent on

the edge costs of the connections, which lie between the current node and the respective node in the set and represent an optimum route between the current node and the respective node in the set, and

a heuristic value for the current node with respect to the respective node in the set.

18. The system according to claim 17, wherein the digital map data comprise the respective positions of the nodes, and the processor further executes program code to:

determine the destination-node-based heuristic value on the basis of the position of the current node and the position of the destination node.

19. The system according to claim 17, wherein

the digital map data comprise predefined heuristic values for the respective nodes with respect to respective other nodes in the predefined area, which each represent estimated costs from one node in each case to the other node in each case, and the destination-node-based heuristic value is therefore predefined.

20. The system according to claim 17, wherein

the respective destination-node-based heuristic value represents a Euclidean distance between the current node and the destination node.