US 2016/0102990 A1Published application

Method for Determining Correction Values for a Route Calculation Algorithm

AssigneeBayerische Motoren Werke Aktiengesellschaft

InventorMarcello TAVA

Life of this patent

Estimating the term…

Loading patent…

Abstract

A predefined area is divided into a plurality of tiles, a respective one of the tiles of the area being determined as a starting tile and the respective remaining tiles being determined as reference tiles, and special nodes, being predefined that are arranged in the starting tile or in the respective reference tile. For the respective starting tile, a correction value is determined, in each case in relation to one of the reference tiles, such that a respective cost ratio is determined for each special node of the respective starting tile in relation to each special node of the reference tile on the basis of the edge costs of the connections that are situated between the respective special node of the starting tile and the respective special node of the reference tile. The cost ratio is also determined on the basis of a heuristic value of the respective special node of the starting tile in relation to the respective special node of the reference tile. A mean value is determined on the basis of the determined cost ratios. The mean value is taken as a basis for determining the correction value of the starting tile in relation to the respective reference tile.

Claims12

Dependent claims

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:
subdividing the predefined area, in a predefined manner, into a plurality of tiles, for which the correction values are determined,
determining one of the tiles in the area respectively as a starting tile and the respective remaining tiles as reference tiles, first special nodes being predefined, which first special nodes are arranged in the starting tile and form a true or artificial subset of all nodes in the starting tile, and second special nodes being predefined, which second special nodes are arranged in the respective reference tile and form a true or artificial subset of all nodes in the respective reference tile,
determining the correction value for the respective starting tile with respect to one of the reference tiles in each case in such a manner that:
a cost ratio is respectively determined for each first special node in the respective starting tile with respect to each second special node in the respective reference tile based on:
(i) the edge costs of the connections, which lie between the respective first special node in the starting tile and the respective second special node in the respective reference tile and represent an optimum route between the first respective special node in the starting tile and the respective second special node in the respective reference tile, and (ii) a heuristic value for the respective first special node in the starting tile with respect to the respective second special node in the respective reference tile,
a mean value is determined based on the determined cost ratios, and
the correction value for the starting tile is determined with respect to the respective reference tile based on of the mean value.

7 more elements

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 in the predefined area, and
a set of correction values, wherein the correction values are determined via a processor executing a program to:
(i) subdivide the predefined area, in a predefined manner, into a plurality of tiles, for which the correction values are determined,
(ii) determine one of the tiles in the area respectively as a starting tile and the respective remaining tiles as reference tiles, first special nodes being predefined, which first special nodes are arranged in the starting tile and form a true or artificial subset of all nodes in the starting tile, and second special nodes being predefined, which second special nodes are arranged in the respective reference tile and form a true or artificial subset of all nodes in the respective reference tile,
(iii) determine the correction value for the respective starting tile with respect to one of the reference tiles in each case in such a manner that:
a cost ratio is respectively determined for each first special node in the respective starting tile with respect to each second special node in the respective reference tile based on:
(i) the edge costs of the connections, which lie between the respective first special node in the starting tile and the respective second special node in the respective reference tile and represent an optimum route between the respective first special node in the starting tile and the respective second special node in the respective reference tile, and (ii) a heuristic value for the respective first special node in the starting tile with respect to the respective second special node in the respective reference tile,
a mean value is determined based on the determined cost ratios, and
the correction value for the starting tile is determined with respect to the respective reference tile based on of the mean value;
and
an apparatus for determining a route for a navigation system and/or a driver assistance system, the apparatus being coupled to the storage unit and being configured to read the digital map data from the storage unit to determine the route by executing a program to:
determine the route from a predefined starting node to a predefined destination node based on a predefined route criterion and based on 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 of an optimum route from the starting node to the current node and a destination-node-based heuristic value for the current node, which represents respectively estimated costs from the current node to the destination node, and a destination-node-based correction value for the current node, which is selected from the set of correction values based on the current node and the destination node.

11 more elements

A computer product 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 area 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,
wherein the computer product comprises a computer readable medium having stored thereon executable program code segments to:
subdivide the predefined area, in a predefined manner, into a plurality of tiles, for which the correction values are determined,
determine one of the tiles in the area respectively as a starting tile and the respective remaining tiles as reference tiles, first special nodes being predefined, which first special nodes are arranged in the starting tile and form a true or artificial subset of all nodes in the starting tile, and second special nodes being predefined, which second special nodes are arranged in the respective reference tile and form a true or artificial subset of all nodes in the respective reference tile,
determine the correction value for the respective starting tile with respect to one of the reference tiles in each case in such a manner that:
a cost ratio is respectively determined for each first special node in the respective starting tile with respect to each second special node in the respective reference tile based on:
(i) the edge costs of the connections, which lie between the respective first special node in the starting tile and the respective second special node in the respective reference tile and represent an optimum route between the respective first special node in the starting tile and the respective second special node in the respective reference tile, and (ii) a heuristic value for the respective first special node in the starting tile with respect to the respective second special node in the respective reference tile,
a mean value is determined based on the determined cost ratios, and
the correction value for the starting tile is determined with respect to the respective reference tile based on the mean value.

7 more elements

Dependencies are inferred from the claim text.