Route Navigation via a Proximity Point

• US 20100076674A1
• Filed: 09/22/2008
• Published: 03/25/2010
• Est. Priority Date: 09/22/2008
• Status: Active Grant

• Current Assignee: MiTAC International Corporation (MiTAC Holdings Corp.)
• Original Assignee: Magellan Navigation Incorporated (MiTAC Holdings Corp.)
• Inventors: Louvet, Simon, Berot, Olivier
• Granted Patent: US 8,219,317 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A system and method is provided that uses one or more points, e.g., “smart via” input points, e.g., a center of a city such as a large city, to determine one or more points, e.g., smart via output points. A smart via output point determined from a smart via input point can be used, together with origination and destination points, to identify an optimal navigational route between the origination and destination points. A navigational route generated using the smart via output point, an origination point and a destination point travels in proximity to the smart via input point.

Claims

1. A computer-implemented method for generating a navigational route, said method comprising:

determining a smart via output point using origination, destination and smart via input points, the origination point corresponding to a starting point for a navigational route, the destination point corresponding to a destination point for the route, and the smart via output point is a point for the navigational route that is identified to be an optimal point and that is in proximity to, and different from, the smart via input point; and

generating the navigational route using the origination, destination and smart via output points.

2. The method of claim 1, wherein said smart via output point corresponds to a point of a segment of a road identified using the original, destination and smart via input points.

3. The method of claim 2, wherein the segment of the road comprises a root of a segment tree identified using the original, destination and smart via input points.

4. The method of claim 1, said determining a smart via output point further comprising:

creating one or more segment trees comprising at least one node, each node corresponding to a segment of a road, each road segment having a starting and ending point;

estimating a value for each of the one or more segment trees;

selecting one of the one or more segment trees using the estimated at least one value; and

using the starting point of the selected segment tree'"'"'s root node as the smart via output point.

5. The method of claim 4, wherein the estimated value for a segment tree comprises an optimal aggregate value selected from one or more aggregate values determined for the segment tree, each aggregate value for the segment tree corresponding to a traversal path of nodes from the segment tree'"'"'s root node to a leaf node of the segment tree and comprising a weighted sum of values assigned to each of the nodes of the traversal path.

6. The method of claim 5, the value assigned to a node being determined using speed and angle coefficients determined for the node.

7. The method of claim 4, said creating one or more segment trees further comprising:

determining a geographic area about the smart via input point;

identifying a plurality of segments using the determined geographic area;

for each of the one or more segment trees;

identifying one of the plurality of segments as a root node of the segment tree using a determined distance of the segment from the destination point; and

identifying one or more nodes for the segment tree, each identified node corresponding to one of the plurality of segments having an aggregate direction to the destination point that satisfies an aggregate direction threshold.

8. The method of claim 7, wherein each segment of road has a ranking corresponding to a level of a road, said determining a geographic area about the smart via input point further comprising:

determining a segment density for at least one of a plurality of levels of road and an initial geographic area about the smart via input point, the determined segment density for a level of road corresponding to a number of segments associated with the initial geographic area and having a ranking corresponding to the road level;

selecting a highest one of the levels of roads for which the determined segment density satisfies a density threshold corresponding to the level of road; and

determining a segment density for each of a plurality of zone-determination geographic areas about the smart via input point, the segment density for a zone-determination geographic area corresponding to the number of segments associated with the zone-determination geographic area and having a ranking corresponding to the selected level of road; and

determining the geographic area about the smart via input point using the zone-determination geographic areas that have a determined segment density that satisfies a zone-determination density threshold.

9. A computer-readable medium embodying program code for generating a navigational route, said program code comprising code to:

determine a smart via output point using origination, destination and smart via input points, the origination point corresponding to a starting point for a navigational route, the destination point corresponding to a destination point for the route, and the smart via output point is a point for the navigational route that is identified to be an optimal point and that is in proximity to, and different from, the smart via input point; and

generate the navigational route using the origination, destination and smart via output points.

10. The computer-readable medium of claim 9, wherein said smart via output point corresponds to a point of a segment of a road identified using the original, destination and smart via input points.

11. The computer-readable medium of claim 10, wherein the segment of the road comprises a root of a segment tree identified using the original, destination and smart via input points.

12. The computer-readable medium of claim 9, said code to determine a smart via output point further comprising code to:

create one or more segment trees comprising at least one node, each node corresponding to a segment of a road, each segment having a starting and ending point;

estimate a value for each of the one or more segment trees;

select one of the one or more segment trees using the estimated at least one value; and

use the starting point of the selected segment tree'"'"'s root node as the smart via output point.

13. The computer-readable medium of claim 12, wherein the estimated value for a segment tree comprises an optimal aggregate value selected from one or more aggregate values determined for the segment tree, each aggregate value for the segment tree corresponding to a traversal path of nodes from the segment tree'"'"'s root node to a leaf node of the segment tree and comprising a weighted sum of values assigned to each of the nodes of the traversal path.

14. The computer-readable medium of claim 13, the value assigned to a node being determined using speed and angle coefficients determined for the node.

15. The computer-readable medium of claim 12, said code to create one or more segment trees further comprising code to:

determine a geographic area about the smart via input point;

identify a plurality of segments using the determined geographic area;

for each of the one or more segment trees;

identify one of the plurality of segments as a root node of the segment tree using a determined distance of the segment from the destination point; and

identify one or more nodes for the segment tree, each identified node corresponding to one of the plurality of segments having an aggregate direction to the destination point that satisfies an aggregate direction threshold.

16. The computer-readable medium of claim 15, wherein each segment of road has a ranking corresponding to a level of a road, said code to determine a geographic area about the smart via input point further comprising code to:

determine a segment density for at least one of a plurality of levels of road and an initial geographic area about the smart via input point, the determined segment density for a level of road corresponding to a number of segments associated with the initial geographic area and having a ranking corresponding to the road level;

select a highest one of the levels of roads for which the determined segment density satisfies a density threshold corresponding to the level of road; and

determine a segment density for each of a plurality of zone-determination geographic areas about the smart via input point, the segment density for a zone-determination geographic area corresponding to the number of segments associated with the zone-determination geographic area and having a ranking corresponding to the selected level of road; and

determine the geographic area about the smart via input point using the zone-determination geographic areas that have a determined segment density that satisfies a zone-determination density threshold.

17. A system for generating a navigational route, the system comprising:

one or more processors configured to;

determine a smart via output point using origination, destination and smart via input points, the origination point corresponding to a starting point for a navigational route, the destination point corresponding to a destination point for the route, and the smart via output point is a point for the navigational route that is identified to be an optimal point and that is in proximity to, and different from, the smart via input point; and

generate the navigational route using the origination, destination and smart via output points.

18. The system of claim 17, wherein said smart via output point corresponds to a point of a segment of a road identified using the original, destination and smart via input points.

19. The system of claim 18, wherein the segment of the road comprises a root of a segment tree identified using the original, destination and smart via input points.

20. The system of claim 17, said one or more processors configured to determine a smart via output point being further configured to:

create one or more segment trees comprising at least one node, each node corresponding to a segment of a road, each road segment having a starting and ending point;

estimate a value for each of the one or more segment trees;

select one of the one or more segment trees using the estimated at least one value; and

use the starting point of the selected segment tree'"'"'s root node as the smart via output point.

21. The system of claim 20, wherein the estimated value for a segment tree comprises an optimal aggregate value selected from one or more aggregate values determined for the segment tree, each aggregate value for the segment tree corresponding to a traversal path of nodes from the segment tree'"'"'s root node to a leaf node of the segment tree and comprising a weighted sum of values assigned to each of the nodes of the traversal path.

22. The system of claim 21, the value assigned to a node being determined using speed and angle coefficients determined for the node.

23. The system of claim 20, said one or more processors configured to create one or more segment trees being further configured to:

determine a geographic area about the smart via input point;

identify a plurality of segments using the determined geographic area;

for each of the one or more segment trees;

identify one of the plurality of segments as a root node of the segment tree using a determined distance of the segment from the destination point; and

identify one or more nodes for the segment tree, each identified node corresponding to one of the plurality of segments having an aggregate direction to the destination point that satisfies an aggregate direction threshold.

24. The system of claim 23, wherein each segment of road has a ranking corresponding to a level of a road, said one or more processors configured to determine a geographic area about the smart via input point being further configured to:

determine a segment density for at least one of a plurality of levels of road and an initial geographic area about the smart via input point, the determined segment density for a level of road corresponding to a number of segments associated with the initial geographic area and having a ranking corresponding to the road level;

select a highest one of the levels of roads for which the determined segment density satisfies a density threshold corresponding to the level of road; and

determine a segment density for each of a plurality of zone-determination geographic areas about the smart via input point, the segment density for a zone-determination geographic area corresponding to the number of segments associated with the zone-determination geographic area and having a ranking corresponding to the selected level of road; and

determine the geographic area about the smart via input point using the zone-determination geographic areas that have a determined segment density that satisfies a zone-determination density threshold.