Method and Apparatus for Determining a Route and Correction Values for Heuristic Values

A method for determining correction values for a route calculation algorithm based on digital map data for a route network and/or 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 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 predefined reference set of nodes in each case:
• determining a cost ratio for the respective node in the reference set is based on:
• the edge costs of the connections, which lie between the node, for which the 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 a mean value based on the determined cost ratios of the nodes in the reference set, and
• determining a correction value based on the mean value.

An apparatus for determining a route for a navigation system and/or a driver assistance system with an associated storage unit for storing digital map data for a route network and/or 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:
• 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.

A system, comprising:

• a storage unit that stores digital map data for a route network and/or 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.