Method and system for using real-time traffic broadcasts with navigation systems

• US 6,438,561 B1
• Filed: 11/19/1998
• Issued: 08/20/2002
• Est. Priority Date: 11/19/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Fernekes, Robert, Lampert, David, Jaugilas, John M., Israni, Vijaya S., Ashby, Richard A.
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/196,409
• Time in Patent Office: 1,370 Days
• Field of Search: 707/5, 707/6, 707/104, 707/100, 707/3-4, 707/104.1, 701/200, 701/201, 701/202, 701/203, 701/208-210, 701/213, 701/117, 701/118, 340/990, 340/955, 340/996, 455/456, 455/457
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096866 where the complete route is shown to the driver
• CPC Class Codes: G08G 1/096872 where instructions are given per voice
• CPC Class Codes: Y10S 707/92 Navigation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method are disclosed that allow a navigation system that uses a geographic database to also use the data in traffic messages broadcast by a traffic broadcast system. One aspect of a present system and method includes the formation, storage, and use of location reference data records in a geographic database used by a navigation system. These location reference data records identify certain other kinds of data records that represent physical geographic features, such as data records that represent segments of roads, as being associated with certain location reference numbers. These location reference records may be included in a geographic database installed in the vehicle or may be provided to vehicles via a wireless communication link. Another aspect of a present system and method includes the formation, storage, and use of one or more indices that relate location reference numbers used by a traffic broadcast system to location reference records in a geographic database used by the navigation system. Another aspect of a present system and method is the formation, storage, and use of data that identify, for each location reference number, the immediately previous and the immediately next location reference number. Still another aspect of a present system and method includes the programming, and methods of use thereof, that query the geographic database and return the data entities associated with certain identified location reference numbers.

Claims

1. A method of operating a navigation application program comprising:

receiving broadcast traffic messages that include data that indicate traffic conditions at locations on roads in a geographic area, wherein each of said traffic messages includes

data that indicates a starting location of a reported traffic condition, wherein said starting location is a location selected from an ordered sequence of designated locations along a road to which location reference numbers have been assigned, and

data that indicates an extent of the reported traffic condition, wherein said extent is expressed as a number of adjacent locations in said ordered sequence of designated locations extending from the starting location;

extracting from each of said traffic messages the data that indicates the staring location and the data that indicates the extent;

using a geographic database to identify affected road segments that extend from the starting lotion and from each of the adjacent locations in said ordered sequence of designated locations extending from starting location indicated by the extent;

associating traffic conditions contained in the traffic messages with the affected road segments; and

using the geographic database to calculate a route to a selected destination along roads taking into account the traffic conditions associated with the affected road segments.

2. The method of claim 1 further comprising the step of:

associating the data in said traffic messages that indicate traffic conditions at locations to those data entities in said geographic database which had been identified in said step of searching as corresponding to said locations.

3. The method of claim 2 wherein said step of associating the data in said traffic messages to data entities in said geographic database is performed prior to performing a route calculation function.

4. The method of claim 2 wherein said steps of extracting, searching, and associating are performed until all pertinent traffic messages have been processed.

5. The method of claim 2 wherein said step of associating the data in said traffic messages to data entities in said geographic database is performed as part of a route calculation function of said navigation application program.

6. The method of claim 2 wherein said steps of extracting, searching, and associating are updated as new traffic messages are received that indicate changed traffic conditions.

7. The method of claim 1 further comprising the step of:

after finding data entities in said geographic database that represent geographic features that correspond to said locations, weighting said data entities according to the data that indicates traffic conditions.

8. The method of claim 1 wherein said geographic database is located in an on-board navigation system.

9. The method of claim 1 wherein said navigation application program is installed in a navigation system installed in a vehicle.

10. The method of claim 1 wherein said traffic messages are broadcast on the Radio Data System-Traffic Message Channel.

11. The method of claim 1 wherein said traffic messages conform to a standard format for ALERT-C messages established in the RDS-TMC system.

12. The method of claim 1 wherein said navigation application program is installed in a non-vehicle.

13. The method of claim 1 wherein said step of receiving is performed in a receiver, and wherein said step of searching a geographic database is performed in a navigation system which is separate from said receiver.

14. A method of operating a navigation system comprising:

in an in-vehicle navigation system, receiving a plurality of broadcast traffic messages from a traffic broadcast system that broadcasts said traffic messages,

wherein each of said traffic messages includes a plurality of data components including;

a first data component that identifies a starting location of traffic congestion, wherein said starting location is a location selected from an ordered sequence of designated locations along a road to which location reference numbers have been assigned,

a second data component that indicates a severity level of traffic congestion extending from said starting location, and

a third data component that indicates an extent of the traffic congestion, wherein said extent is expressed as a number of adjacent locations in an ordered sequence of designated locations extending from the starting location;

in said in-vehicle navigation system, using a geographic database to identity affected road segments that extend from the starting location and from each of the adjacent locations in said ordered sequence of designated locations extending from starting location indicated by the extent;

associating said affected road segments with the severity level of said second data component; and

using said geographic database to calculate a route to a selected destination taking into account the traffic conditions associated with the affected road segments.

15. The method of claim 14 wherein said first data component is comprised of a location reference number that identifies said location.

16. The method of claim 14 further comprising the step of:

after receiving said plurality of broadcast traffic messages, extracting first data components and second data components from said traffic messages.

17. The method of claim 14 wherein said data components include data that indicate successive adjacent locations to which reference numbers have been assigned.

18. A geographic database used by a navigation system for route calculation in conjunction with traffic messages broadcast by a traffic condition broadcast system wherein each of said traffic messages includes

a location reference number that indicates a starting location of a reported traffic condition, wherein said location reference number identifies a designated location selected from an ordered sequence of designated locations along a road to which location reference numbers have been assigned, and

data that indicates an extent of the reported traffic condition, wherein said extent is expressed as a number of adjacent locations in said ordered sequence of designated locations extending from the starting location,

said geographic database comprising:

data entities of a first type that represent geographic features in a geographic region, including portions of a road network; and

data entities of a second type each of which associates a location reference number to data entities of said first type that represent road segments that extend therefrom,

whereby the navigation system using said geographic database in conjunction with traffic messages broadcast by the tic condition broadcast system can incorporate information from said traffic messages when using said geographic database for route calculation purposes.

19. The invention of claim 18 wherein said data entities of said first type and said data entities of said second type are organized into a plurality of parcels each of which includes a plurality of data entities of said respective types.

20. The invention of claim 18 wherein said geographic database is separated into parcels each of which includes a plurality of data entities.

21. The invention of claim 18 wherein said geographic database is comprised of separate types of geographic data.

22. The invention of claim 21 wherein said separate types of geographic data include routing and cartographic.

23. The invention of claim 18 wherein said geographic database is stored on a computer readable medium.

24. The invention of claim 18 wherein said geographic database is stored on one of a CD-ROM disk, a DVD disk, and a hard disk.

25. The invention of claim 18 wherein said data entities of said first type represent segments of roads.

26. The invention of claim 18 wherein said data entities of said first type represent segments of roads, including segments of roads that lead into locations along said road network that are represented by said location references in said traffic messages.

27. The invention of claim 18 further comprising:

an index that relates location references to said data entities of said second type.

28. The invention of claim 18 wherein said data entities of said second type are arranged numerically in a plurality of parcels and wherein said geographic database further comprises:

an index that identifies, for a first data entity of said second type in each of said plurality of parcels, the one of said plurality of parcels in which said first data entity of said second type is located.

29. The invention of claim 18 wherein said location references included in said traffic messages represent along roads.

30. The invention of claim 18 wherein at last part of said geographic database is located remotely.

31. The invention of claim 18 wherein said data entities of a second type are located remotely.

32. The invention of claim 18 wherein said data entities of a second type are downloaded to the navigation system from a remote location.