OPTIMUM ROUTE DETERMINATION WITH TILING

• US 20110301837A1
• Filed: 06/02/2011
• Published: 12/08/2011
• Est. Priority Date: 11/09/2005
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Inventors: Wellmann, Harald
• Granted Patent: US 9,279,692 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G08G 1/0968 Systems involving transmission of navigation instructions to the vehicle
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated

Abstract

An optimum route search may be conducted through the use of a tiling overlay on the network of road segments. Overlaying the tiling (grid) over the road segments allows for a reduction of the number of road segments considered for an optimum path as road segments can be evaluated on whether the road segment is part of an optimal path to the borders of a first tile and then successively larger frames of tiles around the initial tile. By reducing the number of road segments considered for the optimum route search to road segments that are part of optimal routes to various tile boundary edges, the computation of the optimum route for the route of interest may be quicker and less resource intensive than efforts to determine optimum routes through other methods.

Claims

1. A system for pre-processing road segment data, comprising:

a first storage unit containing road segment data;

a second storage unit containing tiling definition data;

a working memory unit for storing a subset of the road segment data and a subset of the tiling definition data; and

a processing unit adapted to process data stored in the working memory unit and to determine a rank information of a road segment based on the tiling, where the rank information quantifies the relevance of the road segment for optimum routes connecting tiles of the tiling.

2. The system for pre-processing road segment data of claim 1 where the system is adapted to perform pre-processing road segment data by including utilizing a combination of the tiling and the road segment data defined such that each one of the road segments is contained in at most one tile of the tiling.

3. The system for pre-processing road segment data of claim 1 where the system includes an additional working memory unit coupled to the processing unit and adapted to store a determined rank information.

4. The system for pre-processing road segment data of claim 3 where the processing unit is adapted to process data stored in the additional working memory unit for determining the rank information.

5. The system for pre-processing road segment data of claim 1 where the working memory unit has a storage capacity sufficient to store a subset of road segment data required for an optimum route search for determining the rank information.

6. The system for pre-processing road segment data of claim 1 where the system includes an output unit for outputting a determined rank information.

7. The system for pre-processing road segment data claim 1, where the system includes a third storage unit for storing a determined rank information.

8. The system for pre-processing road segment data claim 1, where the system includes at least one additional processing unit adapted to determine a rank information of a road segment based on the tiling, and where the processing unit and the additional processing unit are adapted to determine road segment rank information in parallel.

9. A system for optimum route determination, comprising:

a first storage unit containing road segment data;

a second storage unit containing rank information data;

a working memory unit for storing a subset of the road segment data; and

a processing unit coupled to the working memory unit and adapted to determine an optimum route from a start point to a destination based on rank information data;

where in that the rank information data is determined in dependence on the tiling and the rank information quantifies the relevance of a road segment for optimum routes connecting tiles of the tiling.

10. The system for optimum route determination of claim 9 where the system includes an additional processing unit adapted to manage the data stored in the working memory unit based on the rank information data.

11. The system for optimum route determination of claim 9, where the system includes a third storage unit containing tiling definition data.

12. The system for optimum route determination claim 9 where the working memory unit has a storage capacity sufficient to store a subset of the road segment data required for optimum route determination.

13. A navigation system for use in providing guidance on a suitable route for a vehicle comprising:

an output unit;

a position detection unit;

a system for computing an optimum route from a start point to a destination through a use of a tiling applied to a network of road segments, the system for computing an optimum route utilizing a pre-processing step that determines a rank information value for a road segment based on a relevance of that road segment to an optimum route passing through that road segment from a point on a border of a tile in the tiling containing the road segment to another point on the border of the tile in the tiling containing the road segment.

14. The navigation system of claim 13 where the position detection unit is adapted to provide a set of data sufficient to define a current position of the navigation system to be used as the start point.