Method and system for dynamic estimation and predictive route generation

• US 7,565,155 B2
• Filed: 04/10/2003
• Issued: 07/21/2009
• Est. Priority Date: 04/10/2002
• Status: Expired due to Fees

• Current Assignee: Bluestone Ventures, Inc.
• Original Assignee: Networks In Motion Incorporated (Comtech Telecommunications Corporation)
• Inventors: Sheha, Michael A., Sheha, Angie, Petilli, Stephen, Yarlagadda, Arun
• Primary Examiner(s): PHAM, TUAN
• Application Number:
  US10/410,740
• Publication Number:
  US 20050075119A1
• Time in Patent Office: 2,294 Days
• Field of Search: 4554561-4567, 701/201, 701/204, 701/208, 701/209, 701/211, 340/992, 340/993, 340/994
• US Class Current: 455/456.1
• CPC Class Codes: G01C 19/42 for indicating rate of turn; for integrating rate of turn
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3676 Overview of the route on the road map
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: G08G 1/205 Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental

Abstract

The preferred embodiments of the present invention are directed to methods and systems for dynamic route estimation and prediction using discrete sampled location updates from various mobile devices for the purpose of providing a graphical representation of a mobile device'"'"'s route along a known network path of map data. The embodiments also provide supplemental route metrics, such as traveled distance, elapsed time, etc., and the capability to assign destination points for the purpose of providing the ability to modify location update points in an application, such as a route planner, and/or to store the dynamically generated route based on various preferences for later retrieval.

Claims

1. A method of providing predictive position information for a mobile communication device, said method comprising the steps of:

receiving position information of the mobile communication device, said position information indicating a first position of the mobile communication device;

receiving updated position information of the mobile communication device, said updated position information indicating a second position of the mobile communication device;

accessing a map database, said map database containing mapping information for a geographical area;

using the mapping information, displaying a graphical representation of a map, said map including routes of travel;

using the position information and the updated position information, determining a speed of travel of said mobile communication device;

using said determined speed of travel, calculating a predictive position of the mobile communication device at a point in time ahead of the real time;

displaying, on the graphical representation of the map, the predictive position of the mobile communication device at said point in time ahead of the real time;

calculating an alternative predictive position of the mobile communication device; and

displaying, on the graphical representation of the map, the alternative predictive position of the mobile communication device.

2. The method according to claim 1, further comprising the step of displaying, on the graphical representation of the map, the first and the second positions of the mobile communication device.

3. The method according to claim 1, further comprising the step of receiving destination information of the mobile communication device.

4. The method according to claim 1, further comprising the step of transmitting the predictive position information.

5. The method according to claim 1, wherein the mapping information includes position information of a plurality of points of interest located within the geographical area.

6. The method according to claim 1, wherein the position information and the updated position information are received in real time, and wherein the predictive position information is calculated and displayed in real time.

7. The method according to claim 1, wherein the position information and the updated position information is received from a satellite.

8. The method according to claim 1, wherein the mapping information includes route information of the geographical area, said route information including a plurality of routes of travel.

9. The method according to claim 8, further comprising the steps of:

generating an adjusted predictive position by correlating the predictive position of the mobile communication device with a position on a route of travel nearest to the predictive position; and

displaying the adjusted predictive position.

10. The method according to claim 8, further comprising the step of transmitting the adjusted predictive position.

11. The method according to claim 5, further comprising the steps of transmitting position information of one of said plurality of points of interest.

12. The method according to claim 11, wherein said one point of interest is, relative to the other points of interests, nearest to the predictive position of the mobile communication device.

13. The method according to claim 8, further comprising the step of receiving user preference information, said user preference information includes the user preferred routes of travel.

14. The method according to claim 13, further comprising the step of using the user preference information to generate an adjusted predictive position.

15. The method according to claim 1, further comprising the step of displaying an estimate time of arrival at the predictive position.

16. The method according to claim 8, wherein the route information includes one of speed limit information for the routes of travel and traffic stop information for the routes of travel.

17. The method according to claim 16, further comprising the step of calculating an estimate time of arrival at the predictive position, wherein said estimated time of arrival is calculated using one of the speed limit information and the traffic stop information for the routes of travel.

18. The method according to claim 1, wherein the map database is stored within the mobile communication device.

53. The method of claim 1, wherein the predictive position and the alternative predictive position are displayed at the same time.

19. A computer-readable medium encoded with a computer program for causing a computer processor to generate predictive position information for a mobile communication device by causing the processor to execute the steps of:

receiving position information of the mobile communication device, said position information indicating a first position of the mobile communication device;

receiving updated position information of the mobile communication device, said updated position information indicating a second position of the mobile communication device;

accessing a map database, said map database containing mapping information for a geographical area;

using the mapping information, displaying a graphical representation of a map, said map including routes of travel;

using the position information and the updated position information, determining a speed of travel of said mobile communication device;

using said determined speed of travel, calculating a predictive position of the mobile communication device at a point in time ahead of the real time;

displaying, on the graphical representation of the map, the predictive position of the mobile communication device at said point in time ahead of the real time;

calculating an alternative predictive position of the mobile communication device; and

displaying, on the graphical representation of the map, the alternative predictive position of the mobile communication device.

20. The computer-readable medium according to claim 19, wherein the medium includes further instructions for causing the processor to execute the step of displaying, on the graphical representation of the map, the first and the second positions of the mobile communication device.

21. The computer-readable medium according to claim 19, wherein the medium includes further instructions for causing the processor to execute the step of receiving destination information of the mobile communication device.

22. The computer-readable medium according to claim 19, wherein the medium includes further instructions for causing the processor to execute the step of transmitting the predictive position information.

23. The computer-readable medium according to claim 19, wherein the mapping information includes position information of a plurality of points of interest located within the geographical area.

24. The computer-readable medium according to claim 19, wherein the position information and the updated position information are received in real time, and wherein the predictive position information is calculated and displayed in real time.

25. The computer-readable medium according to claim 19, wherein the position information and the updated position information are received from a satellite.

26. The computer-readable medium according to claim 19, wherein the mapping information includes route information of the geographical area, said route information including a plurality of routes of travel.

27. The computer-readable medium according to claim 26, wherein the program causes the processor to further execute the steps of:

generating an adjusted predictive position by correlating the predictive position of the mobile communication device with a position on a route of travel nearest to the predictive position; and

displaying the adjusted predictive position.

28. The computer-readable medium according to claim 26, wherein the program causes the processor to further execute the step of transmitting the adjusted predictive position.

29. The computer-readable medium according to claim 23, wherein the program causes the processor to execute the further steps of transmitting position information of one of said plurality of points of interest.

30. The computer-readable medium according to claim 29, wherein said one point of interest is, relative to the other points of interests, nearest to the predictive position of the mobile communication device.

31. The computer-readable medium according to claim 26, wherein the program causes the processor to execute further the step of receiving user preference information, said user preference information includes the user preferred routes of travel.

32. The computer-readable medium according to claim 19, wherein the program causes the processor to execute the further step of using the user preference information to generate an adjusted predictive position.

33. The computer-readable medium according to claim 19, wherein the program causes the processor to execute the further step of displaying an estimate time of arrival at the predictive position.

34. The computer-readable medium according to claim 26, wherein the route information includes one of speed limit information for the routes of travel and traffic stop information for the routes of travel.

35. The computer-readable medium according to claim 34, wherein the medium includes further instructions for causing the processor to execute the step of calculating an estimate time of arrival at a final destination position, wherein said estimated time of arrival is calculated using one of the speed limit information and the traffic stop information for the routes of travel.

36. The computer-readable medium according to claim 19, wherein the map database is stored within the mobile communication device.

54. The computer-readable medium of claim 19, wherein the predictive position and the alternative predictive position are displayed at the same time.

37. A method for providing predictive travel information for a plurality of mobile devices, said method comprising the steps of:

receiving real-time position information from each of said plurality of mobile devices, said real-time position information including at least one positional information of the corresponding mobile device;

accessing a map database, said map database including map data of a geographical area;

displaying a graphical mapping representation of the geographical area, said graphical mapping representation including a network of known paths of travel;

displaying, on the graphical mapping representation, at least one real-time position of each of said plurality of mobile devices along said network of known paths;

determining a speed of travel for each of said plurality of mobile devices;

using the determined speeds of travel, calculating a predictive position along said network of known paths for each of said plurality of mobile devices for a point in time ahead of the real time;

displaying, on the graphical mapping representation, the predictive position for each of said plurality of mobile devices along said network of known paths at said point in time,

wherein the at least one real-time position of each of said plurality of mobile devices and the predictive position for each of said plurality of mobile devices are displayed along said network of known paths at the same time.

38. The method according to claim 37, further comprising the step of calculating a predictive route of travel for each of said plurality of mobile device, said predictive route of travel originating from a real-time position of the mobile device and terminating at a central destination position.

39. The method according to claim 38, further comprising the step of estimating a time of arrival by each of the mobile device to the central destination.

40. The method according to claim 38, further comprising the step of estimating a position of intercept by each of said plurality of mobile devices with the central destination.

41. The method according to claim 40, further comprising the step of estimating a time of intercept by each of said plurality of mobile devices with the central destination.

42. The method according to claim 38, wherein said central destination is a stationary address.

43. The method according to claim 37, further comprising the step of receiving user travel preference information from each mobile device, said user travel preference information including user preferences for specific routes of travel within the network of known paths.

44. The method according to claim 37, wherein said map data further includes one of speed limits for each route of travel and traffic stop locations for each route of travel.

45. A computer-readable medium encoded with a program for causing a processor to providing predictive travel information for a plurality of mobile devices by executing the steps of:

receiving real-time position information from each of said plurality of mobile devices, said real-time position information including at least one positional information of the corresponding mobile device;

accessing a map database, said map database including map data of a geographical area;

displaying a graphical mapping representation of the geographical area, said graphical mapping representation including a network of known paths of travel;

displaying, on the graphical mapping representation, at least one real-time position of each of said plurality of mobile devices along said network of known paths;

determining a speed of travel for each of said plurality of mobile devices;

using the determined speeds of travel, calculating a predictive position alone said network of known paths for each of said plurality of mobile devices for a point in time ahead of the real time;

displaying, on the graphical mapping representation, the predictive position for each of said plurality of mobile devices along said network of known paths at said point in time,

wherein the at least one real-time position of each of said plurality of mobile devices and the predictive position for each of said plurality of mobile devices are displayed along said network of known paths at the same time.

46. The computer-readable medium according to claim 45, wherein the program causes the processor to execute the further step of calculating a predictive route of travel for each of said plurality of mobile device, said predictive route of travel originating from a real-time position of the mobile device and terminating at a central destination position.

47. The computer-readable medium according to claim 46, wherein the program causes the processor to execute the further step of estimating a time of arrival by each of the mobile device to the central destination.

48. The computer-readable medium according to claim 46, wherein the program causes the processor to execute the further step of estimating a position of intercept by each of said plurality of mobile devices with the central destination.

49. The computer-readable medium according to claim 48, wherein the program causes the processor to execute the further step of estimating a time of intercept by each of said plurality of mobile devices with the central destination.

50. The computer-readable medium according to claim 46, wherein said central destination is a stationary address.

51. The computer-readable medium according to claim 45, wherein the program causes the processor to execute the further step of receiving user travel preference information from each mobile device, said user travel preference information including user preferences for specific routes of travel within the network of known paths.

52. The computer-readable medium according to claim 45, wherein said map data further includes one of speed limits for each route of travel and traffic stop locations for each route of travel.

55. A mobile communication device comprising:

means for receiving position information of the mobile communication device, said position information indicating a first position of the mobile communication device;

means for receiving updated position information of the mobile communication device, said updated position information indicating a second position of the mobile communication device;

means for accessing a map database, said map database containing mapping information for a geographical area;

means for using the mapping information, displaying a graphical representation of a map, said map including routes of travel;

means for using the position information and the updated position information, determining a speed of travel of said mobile communication device;

means for using said determined speed of travel, calculating a predictive position of the mobile communication device at a point in time ahead of the real time;

means for displaying, on the graphical representation of the map, the predictive position of the mobile communication device at said point in time ahead of the real time;

means for calculating an alternative predictive position of the mobile communication device; and

means for displaying, on the graphical representation of the map, the alternative predictive position of the mobile communication device.

56. The mobile communication device of claim 55, wherein the predictive position and the alternative predictive position are displayed at the same time.

57. A mobile communication device for providing predictive travel information for a plurality of mobile devices, said method comprising the steps of:

means for receiving real-time position information from each of said plurality of mobile devices, said real-time position information including at least one positional information of the corresponding mobile device;

means for accessing a map database, said map database including map data of a geographical area;

means for displaying a graphical mapping representation of the geographical area, said graphical mapping representation including a network of known paths of travel;

means for displaying, on the graphical mapping representation, at least one real-time position of each of said plurality of mobile devices along said network of known paths;

means for determining a speed of travel for each of said plurality of mobile devices;

means for using the determined speeds of travel, calculating a predictive position along said network of known paths for each of said plurality of mobile devices for a point in time ahead of the real time;

means for displaying, on the graphical mapping representation, the predictive position for each of said plurality of mobile devices along said network of known paths at said point in time,

wherein the at least one real-time position of each of said plurality of mobile devices and the predictive position for each of said plurality of mobile devices are displayed along said network of known paths at the same time.