System for processing digital map data

• US 7,248,184 B2
• Filed: 08/05/2004
• Issued: 07/24/2007
• Est. Priority Date: 08/05/2003
• 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: Gelhar, Jens, Lussen, Harald, Nagel, Philipp Harald
• Primary Examiner(s): NGUYEN, TAI T
• Application Number:
  US10/912,881
• Publication Number:
  US 20050107950A1
• Time in Patent Office: 1,083 Days
• Field of Search: 340/995.19, 340/995.1, 340/995.13, 340/990, 340/995, 340/539.11, 340/5.61, 701/203, 701/208, 701/211, 701/210, 701/29, 701/32, 701/34
• US Class Current: 340/990
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A method for processing digital map data for route determination is provided that includes dividing a region into a plurality of zones, and for the zones, automatically determining at least one cost value for at least one direction of travel of the zone based on the digital map data of the zone and a predetermined cost criterion. A method for determining a route between two points is provided that includes dividing a region into a plurality of zones, for the zones, automatically determining at least one cost value for at least one direction of travel of the zone based on the digital map data of the zone and a predetermined cost criterion, and automatically determining at least one sequence of zones connecting the two points, where each zone of the sequence may be adjacent to another zone of the sequence, such that the sum of the cost values of the zones of the sequence may be optimized.

Claims

1. A method for determining a route between two points, comprising:

a) dividing a region into at least two zones;

b) automatically determining at least one cost value for at least one direction of travel of a zone from digital map data of the zone and a predetermined cost criterion;

c) automatically determining a sequence of zones connecting the two points, where each zone of the sequence of zones is adjacent to another zone of the sequence of zones such that the overall cost value of the sequence of zones is optimized; and

d) determining a route of travel between the two points based on the sequence of zones.

2. The method of claim 1, further comprising, automatically determining all sequences of zones connecting the two points, where the overall cost value of the sequences of zones does not differ from the overall cost value of an optimal sequence by more than a predetermined threshold.

3. The method of claim 1, further comprising determining for a zone, a difference between the overall cost value of a sequence of zones comprising the zone and the overall cost value of an optimal sequence of zones.

4. The method of claim 1, further comprising automatically re-determining the at least one sequence of zones connecting the two points on a periodic basis.

5. The method of claim 1, further comprising automatically re-determining the at least one sequence of zones connecting the two points upon occurrence of a predetermined event.

6. The method of claim 1, where one of the two points is a current position and the other point is a destination point.

7. The method of claim 1, where the overall cost value of each sequence is optimized under at least one predetermined constraint.

8. The method of claim 7, where the constraint is the exclusion of a zone from the sequence of zones.

9. The method of claim 1, further comprising determining the route based on the digital map data for the zones of a determined sequence of zones connecting the two points.

10. The method of claim 1, where a computer program product comprising software code that is directly loadable into an internal memory of a digital computer performs the method.

11. The method of claim 1, where a computer program product that is stored in a medium readable by a computer system comprises computer readable program means for causing a computer to perform the steps of the method.

12. A method for processing digital map data to determine a route of travel, comprising:

dividing a region represented by digital map data into a plurality of zones;

determining one or more cost values corresponding to at least one direction of travel within each of the plurality of zones;

analyzing the cost values to determine a sequence of zones within the plurality of zones connecting two points; and

identifying a route of travel between the two points based on the sequence of zones.

13. The method of claim 12, where the cost values are determined from a travel distance for the at least one direction of travel within each of the plurality of zones.

14. The method of claim 13, where the cost values are proportional to the travel distance.

15. The method of claim 12, where the cost values are determined from a travel time for the at least one direction of travel within each of the plurality of zones.

16. The method of claim 15, where the cost values are proportional to the travel time.

17. The method of claim 12, where the cost values are determined from a combination of a travel distance and a travel time for the at least one direction of travel within each of the plurality of zones.

18. The method of claim 17, where the cost values are proportional to a combination of the travel distance and the travel time.

19. The method of claim 12, where the cost values include information relating to a predetermined part of an adjacent zone.

20. The method of claim 12, where each of the plurality of zones has a polygonal shape.

21. The method of claim 20, where the polygonal shape is selected from squares, rectangles, or hexagons.

22. The method of claim 12, further comprising periodically tiling the region.

23. The method of claim 20, further comprising determining one or more cost values for traversing a zone within the plurality of zones from one edge to at least one other edge of the zone.

24. The method of claim 20, further comprising determining one or more cost values for traversing a zone within the plurality of zones from one corner to at least one other corner of the zone.

25. The method of claim 20, further comprising determining one or more cost values for traversing a zone within the plurality of zones from one edge to at least one other edge and from one corner to at least one other corner of the zone.

26. The method of claim 12, further comprising determining a time dependent cost value for each of the plurality of zones.

27. The method of claim 12, further comprising automatically re-determining one or more cost values of a zone within the plurality of zones on a regular basis.

28. The method of claim 12, further comprising automatically re-determining one or more cost values of a zone within the plurality of zones upon occurrence of a predetermined event.

29. The method of claim 28, where the predetermined event relates to a traffic condition.

30. The method of claim 12, further comprising storing the one or more cost values for each of the plurality of zones.

31. The method of claim 30, where the storing comprises storing adjacency information for each of the plurality of zones.

32. The method of claim 12, where a computer program product comprising software code that is directly loadable into an internal memory of a digital computer performs the method.

33. The method of claim 12, where a computer program product that is stored in a medium readable by a computer system comprises computer readable program means for causing a computer to perform the steps of the method.

34. A method for assisting navigation, comprising:

dividing a region into a plurality of zones;

automatically determining one or more cost values for a direction of travel within each of the plurality of zones from digital map data of the zone and a predetermined cost criterion;

analyzing the cost values to automatically determine a sequence of zones within the plurality of zones connecting two points, where each zone of the sequence of zones is adjacent to another zone of the sequence of zones such that the overall cost value of the sequence of zones is optimized;

determining a route between the two points based on the sequence of zones; and

providing acoustic and or video output of route information.

35. The method of claim 34, where a computer program product comprising software code that is directly loadable into an internal memory of a digital computer performs the method.

36. The method of claim 34, where a computer program product that is stored in a medium readable by a computer system comprises computer readable program means for causing a computer to perform the steps of the method.