METHOD AND SYSTEM FOR ROUTING USING UNCERTAINTY DATA

• US 20130204525A1
• Filed: 02/08/2012
• Published: 08/08/2013
• Est. Priority Date: 02/08/2012
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Pfeifle, Martin
• Granted Patent: US 9,057,622 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• 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 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.

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. A computer-implemented method for route calculation, the method comprising:

receiving an origin and a destination; and

calculating a route from the origin and the destination using a probability-based routing algorithm based on uncertainty cost; and

providing probability information regarding the route.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

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

15. The method of claim 11, wherein the route is a multi-modal route.

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

17. The method of claim 11, wherein the probability information includes a distribution function.

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

19. A navigation system, comprising:

a processor;

a geographic database that includes uncertainty data associated attributes stored in node and segment records that represent a road network; and

data storage containing instructions executable by the processor for carrying out route calculation functions, the functions including;

receiving an origin and a destination;

selecting a current node closest to the origin;

retrieving a current node cost for the current node from the geographic database;

identifying a neighbor node nearest to the current node and with a highest probability of being included in a route from the origin to the destination;

retrieving a segment cost for a segment connecting the current node and the neighbor node from the geographic database;

calculating a neighbor node cost by adding the current node cost and the segment cost; and

continuing to calculate a route from the origin to the destination, wherein the current node cost, the segment node cost, and the neighbor node costs are distribution functions.

20. The system of claim 19, wherein if the neighbor node has two costs after calculating the neighbor node cost, calculating a cumulative distribution function for each of the costs and evaluating the cumulative distribution functions at an allowed overall cost value to select one of the two costs.