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

摘要

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.

主权项

1. A method 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 method comprises the acts of: determining 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.