Navigation system

• US 6,950,745 B2
• Filed: 05/16/2001
• Issued: 09/27/2005
• Est. Priority Date: 05/16/2000
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Yeoman Group Plc (Vontier Corp.)
• Inventors: Hancock, Simon Geoffery, Geake, Vincent, Agnew, Hugh John
• Primary Examiner(s): Camby, Richard M.
• Application Number:
  US10/276,718
• Publication Number:
  US 20030187573A1
• Time in Patent Office: 1,595 Days
• Field of Search: 701/23, 701/24, 701/25, 701/202, 701/207, 701/208, 701/209, 701/210, 707/10, 707/102, 707/104
• US Class Current: 701/210
• 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/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096872 where instructions are given per voice
• CPC Class Codes: G08G 1/096888 where input information is obtained using learning systems, e.g. history databases

Abstract

A navigation guidance system (1) is provided which provides direction information from a remote server (11) to a mobile user unit (2) for guiding user to a desired destination. The navigation guidance system (1) maintains time-related models for traffic speeds expected on road segments of a road database. By maintaining such time-related models, the system can more accurately provide the user with road guidance instructions to arrive at a chosen destination by a given time. The system can also provide more accurate route guidance information to a destination over different routes, even during rush hour or at off peak times. These time related models can be changed as a result of changing traffic patterns or as a result of an incident on a road segment. In a preferred embodiment, therefore, the system continuously monitors each calculated route and advises the users of alternative routes or of updated departure or arrival times as appropriate.

Claims

1. A navigation guidance system comprising;

means for storing data defining a road network within a geographical area;

means for storing data defining speed-time characteristics for roads of the road network, which speed-time characteristics define traffic speeds along the roads in the network at different times;

means for receiving data from a user defining a travel plan including a source location, a destination location and a proposed travel time; and

route determining means comprising;

(i) means for determining traffic speeds for the roads of the road network at the proposed travel time using said data defining said speed-time characteristics; and

(ii) means for calculating a quickest route from the source location to the destination location defined in the travel plan at the proposed travel time using the data defining the road network and the determined traffic speeds for the roads of the road network.

2. A system according to claim 1, wherein said proposed time of travel specifies a desired arrival time at the destination and wherein said route determining means is operable to calculate the required departure time from the source location in order to arrive at the destination at the desired arrival time.

3. A system according to claim 2, further comprising means for updating the data defining the speed time characteristics for the roads of the road network.

4. A system according to claim 3, further comprising means for monitoring the calculated route using the updated road speed data in order to determine whether or not a new departure time from the source location is required in order to arrive at the destination at the desired arrival time.

5. A system according to claim 4, wherein said monitoring means is operable to calculate the expected arrival time of the user at the destination based on the original departure time, the calculated route and the updated road speed data and is operable to recalculate a new departure time if said expected arrival time is a predetermined amount before or after the desired arrival time.

6. A system according to claim 4, wherein said monitoring means is operable to recalculate the departure time in reverse time starting from the destination at the required arrival time using the calculated route and the updated road speed data and is operable to advise the user of the new departure time if the new departure time has changed by a predetermined amount from the originally calculated departure time.

7. A system according to any of claims 4 to 6, wherein said monitoring means is operable to perform said determination at predetermined time intervals, until the user arrives at the destination location.

8. A system according to claim 7, wherein said monitoring means is arranged so that said predetermined time intervals vary depending on a time difference between a current time and the calculated departure time.

9. A system according to any of claims 4 to 6, wherein if said monitoring means determines that a new departure time is required after the user has set off from the source location, then said monitoring means is operable to cause said route determining means to try to find a quicker route to the destination.

10. A system according to claim 1, wherein said proposed time of travel is defined as a specified departure time and wherein said route determining means is operable to track time from the indicated departure time and to use road speed values for each road along the calculated route corresponding to the time at which the user is expected to travel on the road as calculated from the specified departure time.

11. A system according to claim 1, further comprising means for outputting the calculated route and/or the determined departure time to the user.

12. A system according to claim 1, wherein said data defining said road network comprises data defining the location of nodes corresponding to road junctions and data defining links connecting the nodes representing road segments between the road junctions.

13. A system according to claim 12, wherein at least one speed-time characteristic is stored for each road segment.

14. A system according to claim 12 or 13, wherein each road segment is stored with a segment identification number and wherein said calculating means is operable to output a list of road segment identification numbers corresponding to the route to be traversed from the source location to the destination location.

15. A system according to claim 14, further comprising means for converting said sequence of road segment identification numbers into a sequence of driving instructions defining the road names and road intersection points to be traversed along the calculated route.

16. A system according to claim 15, further comprising means for outputting said driving instructions to the user as a set of spoken or text instructions.

17. A system according to claim 16, wherein said receiving means is operable to receive said travel plan from the user via a telephone connection and wherein said calculated route is output to the user through said telephone connection.

18. A system according to claim 1, wherein a different speed-time characteristic for each road of the road network is stored for each day of the week.

19. A system according to claim 1, wherein a different speed-time characteristic for each road of the road network is stored for each day of the year.

20. A system according to claim 1, further comprising means for generating map data for the calculated route and means for outputting the map data to the user.

21. A system according to claim 20, wherein said map data comprises graphic map data illustrating the route to be taken and wherein said output means comprises a graphical display.

22. A system according to claim 1, wherein said receiving means is operable to receive data from a plurality of different users defining travel plans for each user and wherein said route determining means is operable to determine a route for each user based on the time of travel of each user.

47. A system according to claim 1, wherein said route determining means is operable to keep track of the time of day during the route calculation and is operable to update the appropriate traffic speeds for the roads for the time of day as it changes during the travel plan.

48. A system according to claim 47, wherein said proposed travel time defines a desired time of arrival at the destination location and wherein said route determining means is operable to perform the route calculation in reverse time starting from the destination at the desired arrival time.

23. A navigation guidance method comprising the steps of:

storing data defining a road network within a geographical area;

storing data defining speed-time characteristics for roads of the road network, which speed-time characteristics define traffic speeds along the roads in the network at different times;

receiving data from a user defining a travel plan including a source location, a destination location and a proposed travel time; and

determining a route comprising the steps of;

(i) determining traffic speeds for the roads of the road network at the proposed travel time using said data defining said speed-time characteristics; and

(ii) calculating a quickest route from the source location to the destination location defined in the travel plan at the proposed travel time using the data defining the road network and the determined traffic speeds for the roads of the road network.

24. A method according to claim 23, wherein said proposed time of travel specifies a desired arrival time at the destination and wherein said route determining step calculates the required departure time from the source location in order to arrive at the destination at the desired arrival time.

25. A method according to claim 24, further comprising the step of updating the data defining the speed time characteristics for the roads of the road network.

26. A method according to claim 25, further comprising the step of monitoring the calculated route using the updated road speed data in order to determine whether or not a new departure time from the source location is required in order to arrive at the destination at the desired arrival time.

27. A method according to claim 26, wherein said monitoring step calculates the expected arrival time of the user at the destination based on the original departure time, the calculated route and the updated road speed data and recalculates a new departure time if said expected arrival time is a predetermined amount before or after the desired arrival time.

28. A method according to claim 26, wherein said monitoring step recalculates the departure time in reverse time starting from the destination at the required arrival time using the calculated route and the updated road speed data and advises the user of the new departure time if the new departure time has changed by a predetermined amount from the originally calculated departure time.

29. A method according to any of claims 26 to 28, wherein said monitoring step perform said determination at predetermined time intervals, until the user arrives at the destination location.

30. A method according to claim 29, wherein said monitoring step is such that said predetermined time intervals vary depending on a time difference between a current time and the calculated departure time.

31. A method according to any of claims 26 to 28, wherein if said monitoring step determines that a new departure time is required after the user has set off from the source location, then said monitoring step causes said route determining step to try to find a quicker route to the destination.

32. A method according to claim 23, wherein said proposed time of travel is defined as a specified departure time and wherein said route determining step tracks time from the indicated departure time and uses road speed values for each road along the calculated route corresponding to the time at which the user is expected to travel on the road as calculated from the specified departure time.

33. A method according to claim 23, further comprising the step of outputting the calculated route and/or the determined departure time to the user.

34. A method according to claim 23, wherein said data defining said road network comprises data defining the location of nodes corresponding to road junctions and data defining links connecting the nodes representing road segments between the road junctions.

35. A method according to claim 34, wherein at least one speed-time characteristic is stored for each road segment.

36. A method according to claim 34 or 35, wherein each road segment is stored with a segment identification number and wherein said calculating step outputs a list of road segment identification numbers corresponding to the route to be traversed from the source location to the destination location.

37. A method according to claim 36, further comprising the step of converting said sequence of road segment identification numbers into a sequence of driving instructions defining road names and road intersection points to be traversed along the calculated route.

38. A method according to claim 37, further comprising the step of outputting said driving instructions to the user as a set of spoken or text instructions.

39. A method according to claim 38, wherein said receiving step receives said travel plan from the user via a telephone connection and wherein said calculated route is output to the user through said telephone connection.

40. A method according to claim 23, wherein a different speed-time characteristic for each road of the road network is stored for each day of the week.

41. A method according to claim 23, wherein a different speed-time characteristic for each road of the road network is stored for each day of the year.

42. A method according to claim 23, further comprising the step of generating map data for the calculated route and the step of outputting the map data to the user.

43. A method according to claim 42, wherein said map data comprises graphic map data illustrating the route to be taken and wherein said outputting step outputs the map data to a graphical display.

44. A method according to claim 23, wherein said receiving step receives data from a plurality of different users defining travel plans for each user and wherein said route determining step determines a route for each user based on the time of travel of each user.

45. A computer readable medium storing computer implementable instructions for controlling a processor to implement the method according to claim 23.

46. A computer implementable instructions product for controlling a processor to implement the method according to claim 23 when said instructions product is run on said processor.

49. A method according to claim 23, wherein said route determining step keeps track of the time of day during the route calculation and is operable to update the appropriate traffic speeds for the roads for the time of day as it changes during the travel plan.

50. A method according to claim 49, wherein said proposed travel time defines a desired time of arrival at the destination location and wherein said route determining step performs the route calculation in reverse time starting from the destination at the desired arrival time.