Route planning method for hierarchical map routing and apparatus therefor

• US 5,519,619 A
• Filed: 03/14/1994
• Issued: 05/21/1996
• Est. Priority Date: 03/14/1994
• Status: Expired due to Term

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Seda, Joseph W.
• Primary Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US08/209,590
• Time in Patent Office: 799 Days
• Field of Search: 364/444, 364/449, 340/988, 340/995
• 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

Abstract

A route planning method, and apparatus, for constructing a route connecting a given origin location and a given destination location from a hierarchical map database having more than one layer, where each layer represents a different level of detail. The method includes provision of a list of road segments extracted from an initial planning layer of the hierarchical map database, wherein each of the road segments in the list of road segments are connected to the given origin location. An alternative planning layer is selected dependent on exceeding a predetermined heading criteria measured between a heading associated with heading associated with one of the road segments in the list of road segments and a heading associated with the given destination location.

Claims

1. A route planning method for constructing a route connecting a given origin location and a given destination location from a hierarchical map database having a plurality of layers each layer representing a different level of detail, the method comprising the steps of:

providing a list of road segments extracted from an initial planning layer of the hierarchical map database, wherein each of the road segments in the list of road segments are connected to the given origin location; and

selecting an alternative planning layer dependent on exceeding a predetermined heading criteria measured between a heading associated with one of the road segments in the list of road segments and a heading associated with the given destination location.

2. A method in accordance with claim 1 further comprising a step of selecting the initial planning layer from the plurality of layers of the hierarchical map database, the selection dependent on a distance between the given destination location and a location associated with the one of the road segments.

3. A method in accordance with claim 1 wherein the predetermined heading criteria applied in said step of selecting an alternative planning layer is applied by projecting a heading envelope positioned normal to a projected heading at a termination location of the one of the road segments.

4. A method in accordance with claim 3 wherein the heading envelope is less than ±

145°

.

5. A method in accordance with claim 1 wherein the heading associated with the one of the road segments is derived from end point positions of the one of the road segments.

6. A method in accordance with claim 5 wherein the heading represents an average heading between the end point positions of the one of the road segments.

7. A method in accordance with claim 1 wherein the heading associated with the one of the road segments is a heading at a termination of the one of the road segments.

8. A method in accordance with claim 1 wherein the heading associated with the one of the road segments is a heading at a commencement of the one of the road segments.

9. A method in accordance with claim 1 further comprising a step of determining if any of the one of the road segments on the current planning layer are congested;

and

wherein said step of selecting an alternative planning layer further comprises selecting an alternative planning layer if any of the one of the road segments on the current planning layer are congested.

10. A route planning method for constructing a route connecting a given origin location and a given destination location from a hierarchical map database having a plurality of layers each layer representing a different level of detail, the method comprising the steps of:

providing a list of road segments extracted from an initial planning layer of the hierarchical map database, wherein each of the road segments in the list of road segments are connected to the given origin location;

selecting a candidate road segment from the list of road segments provided in said step of providing;

selecting another planning layer from the plurality of layers of the hierarchical map database, the selection dependent on a distance between the given destination location and a location associated with the candidate road segment;

extracting at least one successor road segment, connected to the candidate road segment, from a current planning layer corresponding one of the initial planning layer and the another planning layer;

determining if the at least one successor road segment provides a connection path to the given destination location; and

selecting an alternative planning layer dependent on exceeding a predetermined heading criteria measured between a heading associated with the at least one successor road segment and a heading associated with the given destination location.

11. A method in accordance with claim 10 wherein said step of selecting another planning layer is executed prior to said step of selecting an alternative planning layer.

12. A method in accordance with claim 11 wherein the alternative planning layer, selected in said step of selecting an alternative planning layer, is a layer having more road segments than the another planning layer selected in said step of selecting another planning layer.

13. A method in accordance with claim 10 wherein the predetermined heading criteria applied in said step of selecting an alternative planning layer is applied by projecting a heading envelope positioned normal to a projected heading at a termination location of the successor road segment.

14. A method in accordance with claim 13 wherein the heading envelope is less than ±

145°

.

15. A method in accordance with claim 10 wherein the heading associated with the successor road segment is derived from end point positions of the successor road segment.

16. A method in accordance with claim 15 wherein the heading represents an average heading between the end point positions of the successor road segments.

17. A method in accordance with claim 10 wherein the heading associated with the successor road segment is a heading at a commencement of the successor road segment.

18. A method in accordance with claim 10 wherein said step of selecting another planning layer comprises selecting another planning layer using an A* method.

19. A method in accordance with claim 10 further comprising a step of determining if any of the one of the successor road segments on the current planning layer are congested;

and

wherein said step of selecting an alternative planning layer further comprises selecting an alternative planning layer if any of the successor road segments on the current planning layer are congested.

20. An apparatus for constructing a route connecting a given origin location and a given destination location from a hierarchical map database having a plurality of layers each layer representing a different level of detail, the apparatus comprising:

means for providing a list of road segments extracted from an initial planning layer of the hierarchical map database, wherein each of the road segments in the list of road segments are connected to the given origin location; and

means for selecting an alternative planning layer dependent on exceeding a predetermined heading criteria measured between a heading associated with one of the road segments in the list of road segments and a heading associated with the given destination location.

21. An apparatus in accordance with claim 20 further comprising a means for selecting the initial planning layer from the plurality of layers of the hierarchical map database, the selection dependent on a distance between the given destination location and a location associated with the one road segment.

22. An apparatus in accordance with claim 20 wherein the predetermined heading criteria applied in said means for selecting an alternative planning layer is applied by projecting a heading envelope positioned normal to a projected heading at a termination location of a successor road segment.

23. A method in accordance with claim 22 wherein the heading envelope is less than ±

145°

.

24. An apparatus in accordance with claim 22 wherein the heading associated with one of the road segments represents an average heading between end point positions of the successor road segment.

25. An apparatus in accordance with claim 22 wherein the heading associated with the successor road segment is a heading at a termination position of the successor road segment.

26. An apparatus in accordance with claim 22 wherein the heading associated with the successor road segment is a heading at a commencement position of the successor road segment.