Method and system for routing using uncertainty data

• US 9,057,622 B2
• Filed: 02/08/2012
• Issued: 06/16/2015
• Est. Priority Date: 02/08/2012
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Pfeifle, Martin
• Primary Examiner(s): Edwards, Jerrah
• Application Number:
  US13/368,934
• Publication Number:
  US 20130204525A1
• Time in Patent Office: 1,224 Days
• Field of Search: 701/400, 701/533, 701/439
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• 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/09626 where the origin of the information is within the own vehicle, e.g. a local storage device, digital map
• CPC Class Codes: G08G 1/096827 where the route is computed onboard

Abstract

A method and system for routing using uncertainty data is disclosed. The uncertainty data is associated with geographic data. The uncertainty data includes a distribution function that represents the probability that the geographic data is accurate. A routing application uses the uncertainty data during or after route calculation. The routing application provides one or more routes and information about the routes based on the uncertainty data.

Claims

1. A computer-implemented method for route calculation, the method comprising:

at a navigation system, receiving a destination;

the navigation system calculating a route from a current position to the destination, wherein the route is a sequence of road segments;

retrieving data indicative of a geographic position for at least one road segment from a geographic database associated with the navigation system;

retrieving a distribution function for an attribute describing the at least one road segment from the geographic database associated with the navigation system, wherein the attribute is different than the geographic position, wherein the distribution function represents uncertainty that the attribute is accurate; and

providing an output that includes information about the uncertainty in the route.

2. The method of claim 1, wherein the distribution function is a normal distribution function.

3. The method of claim 1, wherein the output includes a probability value of arriving at the destination before a certain time.

4. The method of claim 1, wherein the output includes a probability value that a first route is faster than a second route.

5. The method of claim 1, wherein the output includes a travel time estimate displayed as a distribution function.

6. The method of claim 1, wherein the output includes an estimated arrival time as a distribution function.

7. The method of claim 1, wherein the distribution function represents uncertainty in a slope value stored in the geographic database.

8. The method of claim 1, wherein the distribution function represents uncertainty in historic traffic data stored in the geographic database.

9. The method of claim 1, wherein the distribution function represents uncertainty in a public transportation schedule stored in the geographic database.

10. The method of claim 1, wherein the distribution function represents uncertainty in a speed category value stored in the geographic database.

11. The method of claim 1, wherein the distribution function represents uncertainty in traffic related data.

24. The method of claim 1, wherein the distribution function represents uncertainty in historical data stored in the geographic database.

12. A computer-implemented method for route calculation, the method comprising:

receiving an origin and a destination;

calculating a route from the origin and the destination using a probability-based routing algorithm based on geographic position data and an uncertainty cost that describes an accuracy of data for at least one attribute of a road segment, wherein the attribute is different than the geographic position data, along the route; and

providing probability information regarding the route.

13. The method of claim 12, wherein the routing algorithm calculates the uncertainty cost for a neighbor node by adding the uncertainty cost of a current node and the uncertainty cost of a segment connecting the neighbor node and the current node.

14. The method of claim 13, wherein the routing algorithm uses an allowed overall cost value to select an uncertainty cost when the neighbor node is associated with two uncertainty costs.

15. The method of claim 12, wherein the uncertainty cost includes a mean value and a variance value.

16. The method of claim 12, wherein the route is a multi-modal route.

17. The method of claim 12, wherein the probability information includes a probability that a vehicle can reach the destination without re-fueling or re-charging.

18. The method of claim 12, wherein the probability information includes a distribution function.

19. The method of claim 12, wherein the probability information includes a mean value and a standard deviation.

20. The method of claim 12, wherein the uncertainty cost represents uncertainty in a slope value stored in the geographic database, uncertainty in historic traffic data stored in the geographic database, uncertainty in a public transportation schedule stored in the geographic database, or uncertainty in a speed category value stored in the geographic database.

21. A computer-implemented method for route calculation, the method comprising:

receiving an origin and a destination;

calculating a route from the origin and the destination using a probability-based routing algorithm based on an uncertainty cost that describes an accuracy of data for at least one attribute of a road segment along the route; and

providing probability information regarding the route, wherein the uncertainty cost represents uncertainty in a slope value stored in a geographic database, uncertainty in historic traffic data stored in the geographic database, uncertainty in a public transportation schedule stored in the geographic database, or uncertainty in a speed category value stored in the geographic database.

22. A computer-implemented method for route calculation, the method comprising:

at a navigation system, receiving a destination;

the navigation system calculating a route from a current position to the destination, wherein the route is a sequence of road segments;

retrieving a distribution function for an attribute associated with a road segment from a geographic database associated with the navigation system, wherein the distribution function represents uncertainty; and

providing an output that includes information about the uncertainty in the route, wherein the distribution function represents uncertainty in a slope value stored in the geographic database, uncertainty in historic traffic data stored in the geographic database, uncertainty in a public transportation schedule stored in the geographic database, or uncertainty in a speed category value stored in the geographic database.

23. A method, further comprising:

receiving a destination;

calculating a route from a current position to the destination, wherein the route is a sequence of road segments;

retrieving geographic position data for at least one road segment from a geographic database associated with the navigation system;

retrieving a distribution function for an attribute associated with at least one road segment from the geographic database associated with the navigation system, wherein the distribution function represents uncertainty that the attribute is accurate; and

providing an output that includes information about the uncertainty in the route,

wherein the distribution function represents uncertainty in a slope value stored in the geographic database, uncertainty in historic traffic data stored in the geographic database, uncertainty in a public transportation schedule stored in the geographic database, or uncertainty in waiting time to cross an intersection.