Method and apparatus for route calculation considering potential mistakes

• US 10,209,088 B2
• Filed: 06/03/2016
• Issued: 02/19/2019
• Est. Priority Date: 06/03/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Cheng, Wanli
• Primary Examiner(s): Patel, Shardul D
• Application Number:
  US15/172,909
• Publication Number:
  US 20170350717A1
• Time in Patent Office: 991 Days
• Field of Search: 701400, 701533
• 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/3453 Special cost functions, i.e. other than distance or default speed limit of road segments

Abstract

An approach is provided for route calculation using a navigation system by considering potential mistakes. Using the navigation system, at least one route is calculated. A map database is queried to identify intersections along the at least one route. A predicted probability of a user making a routing mistake at the intersections is calculated. A travel time, travel distance, or a combination thereof that is predicted to result from the routing mistake is calculated. The travel time, the travel distance, or a combination thereof represents a predicted severity of the routing mistake. At least one route is recalculated to accept or avoid the intersections based on the predicted probability and the predicted severity of the routing mistake. The recalculated route is presented in a user interface as an optimal route.

Claims

1. A computer-implemented method for performing a route calculation using a navigation system by considering potential mistakes, comprising:

calculating, using the navigation system, at least one route between a starting point and a destination;

querying a map database to identify an intersection along the at least one route;

calculating a predicted probability of a user making a routing mistake at the intersection;

calculating a travel time, a travel distance, or a combination thereof that is predicted to result from the user making the routing mistake, wherein the travel time, the travel distance, or a combination thereof represents a predicted severity of the routing mistake;

determining a cost value of the routing mistake as a product of the predicted probability and the predicted severity;

recalculating the at least one route to avoid the intersection when the cost value is above a threshold value; and

presenting the recalculated at least one route in a user interface of the navigation system as an optimal route.

2. The method of claim 1,

wherein the predicted severity of the routing mistake is calculated based on the travel time and the travel distance.

3. The method of claim 1, further comprising:

accepting the intersection as a part of the at least one route, when the cost value is below the threshold value;

recursively calculating a cost value of a subsequent routing mistake for a subsequent intersection along the at least one route until reaching the destination; and

designating the calculated at least one route resulting from the recursive calculating as the optimal route.

4. The method of claim 3, further comprising:

calculating a predicted probability and a predicted severity for each subsequent intersection to determine a respective cost value.

5. The method of claim 4, further comprising:

calculating the predicted probability for the subsequent intersection as a product of a conditional probability of the subsequent routing mistake occurring at the subsequent intersection and a previously calculated probability of a previous routing mistake occurring at a previous intersection along the at least one route.

6. The method of claim 1, further comprising:

retrieving a predictive driving behavior model personalized for the user based, at least in part, on a routing mistake history of the user,

wherein the predicted probability of the user making the routing mistake is calculated using the predictive driving behavior model.

7. The method of claim 1, wherein the routing mistake is a deviation from the at least one route that is detectable using a plurality of sensors of the navigation system, wherein one of the plurality of sensors is configured to communicate with a traffic related object to collect data.

8. The method of claim 7, wherein other ones of the plurality of sensors are correspondingly configured to collect data from a vehicle, a device within a premise, or a mobile device.

9. The method of claim 1, further comprising:

retrieving a general predictive driving behavior model associated with a plurality of users from a general population of drivers,

wherein the predicted probability of the user making the routing mistake is calculated using the general predictive driving behavior model.

10. An apparatus for performing a route calculation using a navigation system by considering potential mistakes, comprising:

a processor; and

a memory including computer program code for a program,

the memory and the computer program code configured to, with the processor, cause the apparatus to perform at least the following,

calculate, using the navigation system, at least one route between a starting point and a destination;

query a map database to identify an intersection along the at least one route;

calculate a predicted probability of a user making a routing mistake at the intersection;

calculate a travel time, a travel distance, or a combination thereof that is predicted to result from the user making the routing mistake, wherein the travel time, the travel distance, or a combination thereof represents a predicted severity of the routing mistake;

determine a cost value of the routing mistake as a product of the predicted probability and the predicted severity;

recalculate the at least one route to avoid the intersection when the cost value is above a threshold value; and

present the recalculated at least one route in a user interface of the navigation system as an optimal route.

11. The apparatus of claim 10,

wherein the predicted severity of the routing mistake is calculated based on the travel time and the travel distance.

12. The apparatus of claim 10, wherein the apparatus is further caused to:

accept the intersection as a part of the at least one route, when the cost value is below the threshold value;

recursively calculate a cost value of a subsequent routing mistake for a subsequent intersection along the at least one route until reaching the destination; and

designate the calculated at least one route resulting from the recursive calculating as the optimal route.

13. The apparatus of claim 10, wherein the apparatus is further caused to:

calculate a predicted probability and a predicted severity for each subsequent intersection to determine a respective cost value.

14. The apparatus of claim 13, wherein the apparatus is further caused to:

calculate the predicted probability for the subsequent intersection as a product of a conditional probability of the subsequent routing mistake occurring at the subsequent intersection and a previously calculated probability of a previous routing mistake occurring at a previous intersection along the at least one route.

15. The apparatus of claim 10, wherein the apparatus is further caused to:

retrieve a predictive driving behavior model personalized for the user based, at least in part, on a routing mistake history of the user,

wherein the predicted probability of the user making the routing mistake is calculated using the predictive driving behavior model.

16. The apparatus of claim 10, wherein the routing mistake is a deviation from the at least one route that is detectable using one or more sensors of the navigation system.

17. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

calculating, using the navigation system, at least one route between a starting point and a destination;

querying a map database to identify an intersection along the at least one route;

calculating a predicted probability of a user making a routing mistake at the intersection;

calculating a travel time, a travel distance, or a combination thereof that is predicted to result from the user making the routing mistake, wherein the travel time, the travel distance, or a combination thereof represents a predicted severity of the routing mistake;

determining a cost value of the routing mistake as a product of the predicted probability and the predicted severity;

recalculating the at least one route to avoid the intersection when the cost value is above a threshold value; and

presenting the recalculated at least one route in a user interface of the navigation system as an optimal route.

18. The non-transitory computer-readable storage medium of claim 17,

wherein the predicted severity of the routing mistake is calculated based on the travel time and the travel distance.

19. The non-transitory computer-readable storage medium of claim 18, wherein the apparatus is caused to further perform:

accepting the intersection as a part of the at least one route, when the cost value is below the threshold value;

recursively calculating a cost value of a subsequent routing mistake for a subsequent intersection along the at least one route until reaching the destination; and

designating the calculated at least one route resulting from the recursive calculating as the optimal route.

20. The non-transitory computer-readable storage medium of claim 17, wherein the apparatus is caused to further perform:

calculating a predicted probability and a predicted severity for each subsequent intersection to determine a respective cost value.