Navigation system for estimating routes for users

• US 9,091,561 B1
• Filed: 10/28/2013
• Issued: 07/28/2015
• Est. Priority Date: 10/28/2013
• Status: Expired due to Fees

• Current Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Original Assignee: Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Inventors: Weir, David Frank Russell
• Primary Examiner(s): Cheung, Calvin
• Application Number:
  US14/065,170
• Time in Patent Office: 638 Days
• Field of Search: None
• US Class Current: 1/1
• 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

Abstract

The disclosure includes a system and method for generating a probability model used to estimate most likely routes for users. The system includes one or more processors configured to retrieve route data describing historical routes traveled by a group of users and map date describing a map, match the historical routes to the map, identify one or more intersections associated with the historical routes on the map, determine a maneuver ratio for one of the intersections based on the route data, and generate a probability model including one or more maneuver ratios for the one or more intersections. A maneuver ratio describes a ratio of a maneuver that the group of users has taken at the one of the intersections.

Claims

1. A computer-implemented method comprising:

retrieving, with one or more processors, route data describing historical routes traveled by a group of first users and map data describing a map;

matching, with the one or more processors, the historical routes to the map;

identifying, with the one or more processors, one or more intersections associated with the historical routes on the map;

determining, with the one or more processors, a maneuver ratio for one of the intersections based on the route data, the maneuver ratio describing a ratio of a maneuver that the group of first users has taken at the one of the intersections;

generating, with the one or more processors, a probability model including one or more maneuver ratios for the one or more intersections;

retrieving position data associated with a second user, the position data describing a position of the second user on the map;

estimating probabilities for a set of routes that the second user may take based on the probability model;

determining a most likely route for the second user from the set of routes based on the probabilities for the set of routes; and

providing useful information associated with the most likely route for display to the second user.

2. The method of claim 1, wherein the maneuver includes one or more of a right turn, a left turn, a U-turn and going straight.

3. The method of claim 1, further comprising:

determining one or more journey factors associated with the historical routes traveled by the group of first users and associated with the one or more intersections; and

determining the probability model based on the one or more journey factors, the probability model corresponding to the one or more journey factors and generated based on the historical routes characterized by the one or more journey factors.

4. The method of claim 3, wherein the one or more journey factors include one or more of a day of a week, a time of a day, weather of a day, whether a day is a national holiday, whether rain is present during a day, what a starting point of one of the historical routes is, what a destination of one of the historical routes is, what a stopping point along one of the historical routes is, an elapsed distance of one of the historical routes and an elapsed time of one of the historical routes.

5. The method of claim 1, further comprising:

identifying an intersection associated with the second user;

calculating probabilities of maneuvers that the second user may take at the intersection based on the probability model; and

determining a most likely maneuver that the second user may take at the intersection based on the probabilities of maneuvers.

6. The method of claim 1, further comprising:

determining one or more journey factors associated with the second user; and

calculating probabilities of maneuvers that the second user may take at the intersection based on the probability model and the one or more journey factors.

7. The method of claim 1, wherein the useful information associated with the most likely route includes information related to one or more of attractions, amenities, incidents, traffic delay, and road closure information along the most likely route.

8. A system comprising:

one or more processors, the processors being configured to;

retrieve route data describing historical routes traveled by a group of first users and map data describing a map;

match the historical routes to the map;

identify one or more intersections associated with the historical routes on the map;

determine a maneuver ratio for one of the intersections based on the route data, the maneuver ratio describing a ratio of a maneuver that the group of first users has taken at the one of the intersections;

generate a probability model including one or more maneuver ratios for the one or more intersections;

retrieve position data associated with a second user, the position data describing a position of the second user on the map;

estimate probabilities for a set of routes that the second user may take based on the probability model;

determine a most likely route for the second user from the set of routes based on the probabilities for the set of routes; and

provide useful information associated with the most likely route for display to the second user.

9. The system of claim 8, wherein the maneuver includes one or more of a right turn, a left turn, a U-turn and going straight.

10. The system of claim 8, wherein the processors are configured to also:

determine one or more journey factors associated with the historical routes traveled by the group of first users and associated with the one or more intersections; and

determine the probability model based on the one or more journey factors, the probability model corresponding to the one or more journey factors and generated based on the historical routes characterized by the one or more journey factors.

11. The system of claim 10, wherein the one or more journey factors include one or more of a day of a week, a time of a day, weather of a day, whether a day is a national holiday, whether rain is present during a day, what a starting point of one of the historical routes is, what a destination of one of the historical routes is, what a stopping point along one of the historical routes is, an elapsed distance of one of the historical routes and an elapsed time of one of the historical routes.

12. The system of claim 8, wherein the processors are configured to also:

identify an intersection associated with the second user;

calculate probabilities of maneuvers that the second user may take at the intersection based on the probability model; and

determine a most likely maneuver that the second user may take at the intersection based on the probabilities of maneuvers.

13. The system of claim 8, wherein the processors are configured to also:

determine one or more journey factors associated with the second user; and

calculate probabilities of maneuvers that the second user may take at the intersection based on the probability model and the one or more journey factors.

14. The system of claim 8, wherein the useful information associated with the most likely route includes information related to one or more of attractions, amenities, incidents, traffic delay, and road closure information along the most likely route.

15. A computer program product comprising a non-transitory computer usable medium storing a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

retrieve route data describing historical routes traveled by a group of first users and map data describing a map;

match the historical routes to the map;

identify one or more intersections associated with the historical routes on the map;

determine a maneuver ratio for one of the intersections based on the route data, the maneuver ratio describing a ratio of a maneuver that the group of first users has taken at the one of the intersections;

generate a probability model including one or more maneuver ratios for the one or more intersections;

retrieve position data associated with a second user, the position data describing a position of the second user on the map;

estimate probabilities for a set of routes that the second user may take based on the probability model;

determine a most likely route for the second user from the set of routes based on the probabilities for the set of routes; and

provide useful information associated with the most likely route for display to the second user.

16. The computer program product of claim 15, wherein the maneuver includes one or more of a right turn, a left turn, a U-turn and going straight.

17. The computer program product of claim 15, wherein the computer readable program is further configured to:

determine one or more journey factors associated with the historical routes traveled by the group of first users and associated with the one or more intersections; and

determine the probability model based on the one or more journey factors, the probability model corresponding to the one or more journey factors and generated based on the historical routes characterized by the one or more journey factors.

18. The computer program product of claim 17, wherein the one or more journey factors include one or more of a day of a week, a time of a day, weather of a day, whether a day is a national holiday, whether rain is present during a day, what a starting point of one of the historical routes is, what a destination of one of the historical routes is, what a stopping point along one of the historical routes is, an elapsed distance of one of the historical routes and an elapsed time of one of the historical routes.

19. The computer program product of claim 15, wherein the computer readable program is further configured to:

identify an intersection associated with the second user;

calculate probabilities of maneuvers that the second user may take at the intersection based on the probability model; and

determine a most likely maneuver that the second user may take at the intersection based on the probabilities of maneuvers.

20. The computer program product of claim 15, wherein the useful information associated with the most likely route includes information related to one or more of attractions, amenities, incidents, traffic delay, and road closure information along the most likely route.