Route planning method for hierarchical map routing and apparatus therefor

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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

Claim 17

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.

Claim 18

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

Claim 19

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.

Claim 20

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

Claim 21

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.

Claim 24

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.

Claim 25

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.

Claim 26

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

Claim 27

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.

Claim 28

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.

Claim 29

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.