METHOD AND APPARATUS OF VEHICLE NAVIGATION SYSTEM FOR DETECTING AND AVOIDING CITY WITH CROWDED STREETS

• US 20100088013A1
• Filed: 10/07/2008
• Published: 04/08/2010
• Est. Priority Date: 10/07/2008
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics of America Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Vu, Tien, Ta, Hong
• Granted Patent: US 8,165,802 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

A system for comparing various routes, identifying delays among the routes, and selecting a more desirable route, even if the desirable route is not the shortest distance, is described. In one embodiment, the more desirable route is the faster route. In one embodiment, the more desirable route is a route with fewer in-route delays. In one embodiment, the system loads a map from a memory and retrieves road level information based on position information of roads and delays. The roads in the map are described at various levels of detail, wherein lower levels contain more detail and relatively higher levels that contain less detail. One embodiment includes detecting a route having links with a substantially larger number of delays and adding an additional penalty cost for the links at higher levels based on penalties computed from the links at lower level road levels. If a current road level is not the highest, one embodiment include adding the additional penalty cost into a “penalty list” of a higher level link having the links of a current road level in order to detect the higher links with a large number of delays while calculating route at a higher level. When calculating a route (or portion of a route) at a higher road level, an additional penalty cost is added to the higher level links if based on the penalty list.

Claims

1. A method for selecting a route, comprising:

loading a map from a memory;

retrieving road-level information based on position information of roads and delays, wherein shorter links in the map are described at a lower road level and longer links in the map are described at a higher road level;

identifying a route comprising links with a larger number of potential delays;

adding an additional penalty cost for a first one or more links at a lower road level;

including said additional penalty cost into a penalty list of a first higher level link, said first higher level link comprising said first one or more links at a lower road level;

adding an additional cost to a calculation for a route using said first higher level link based on said additional penalty cost; and

selecting a final route with a relatively lower total penalty cost, wherein said lower total penalty cost comprises a sum of a penalty cost of links in said route.

2. The method of claim 1, further comprising:

comparing a length of a first link to a predetermined length;

marking said first link as a marked link if said length of the first link is less than the predetermined length;

identifying a link as a crowded link if said link comprises a specified number of consecutive marked links; and

setting a relatively high penalty cost for said crowded link.

3. The method of detecting the route of claim 1, further comprising:

computing a degree of regularity for each link; and

assigning a relatively higher penalty to a first link in accordance with a degree of regularity of said first link.

4. The method of detecting the route of claim 1, further comprising computing a cost of a link based, at least in part, on a length of a link.

5. The method of detecting the route of claim 1, further comprising computing a cost of a link based, at least in part, on a delay.

6. The method of detecting the route of claim 1, further comprising computing a cost of a link based, at least in part, on an intersection.

7. The method of detecting the route of claim 1, further comprising computing a cost of a link based, at least in part, on a stop sign.

8. The method of detecting the route of claim 1, further comprising computing a cost of a link based, at least in part, on a speed limit.

9. An apparatus for selecting a route, comprising:

a storage system configured to store a map;

a processor that identifies a route comprising links with a relatively larger number of delays while calculating a route, adds an additional penalty cost for the links at a low road level calculation, includes the additional penalty cost into a penalty list of a higher level link comprising one or more links of a current road level, and computes a cost for the higher level links if said higher level links are listed on the penalty list; and

a display for displaying a route selected by the processor.

10. The apparatus of claim 9, wherein the processor compares a length of a first link with a predetermined length, to mark the first link if the predetermined length is longer, identify a link as a crowded link if a number of consecutive marked links in the link is larger than a predetermined value.

11. The apparatus of claim 9, wherein the system is further configured to determine if link in a route are relatively regularly spaced and to assign a higher penalty to links that are less regularly spaced.

12. The apparatus of claim 9, wherein the system is further configured to compute a cost of a link.

13. A vehicle navigation apparatus, comprising:

a display configured to display a map and route information;

a plurality of input buttons configured to accept user instructions;

a storage system configured to store a map; and

a processor programmed to calculate a route using map information, to retrieve a road level information based on position information of roads and delays, wherein roads in the map are described by shorter links at lower road levels and wherein said roads are described by longer links at higher road levels, to identify routes comprising links with higher penalties by adding an additional penalty cost to into a penalty list for a higher level link and adding an additional cost for said route when said route includes said higher level link.

14. The apparatus of detecting the route of claim 13, wherein the processor is further configured to increase a penalty for a route comprising relatively larger number of shorter links.

15. The apparatus of detecting the route of claim 13, wherein the processor is further configured to increase a penalty for a route comprising relatively irregularly-spaced links.