Learning road navigation paths based on aggregate driver behavior

• US 9,299,251 B2
• Filed: 04/09/2014
• Issued: 03/29/2016
• Est. Priority Date: 03/11/2010
• Status: Active Grant

• Current Assignee: Inrix Incorporated
• Original Assignee: Inrix Incorporated
• Inventors: Scofield, Christopher L., Cahn, Robert, Wang, Weimin Mark, Barker, Alec, Leidle, Robert Frederick
• Primary Examiner(s): Keith, Jack W
• Assistant Examiner(s): Nguyen, Chuong P
• Application Number:
  US14/249,168
• Publication Number:
  US 20140309914A1
• Time in Patent Office: 720 Days
• Field of Search: 701117-119, 701/410, 701/411, 701/414, 701/423, 701/533, 340/995.13, 340/995.22, 340/995.23
• US Class Current: 1/1
• 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/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/0104 Measuring and analyzing of parameters relative to traffic conditions
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/052 with provision for determining speed or overspeed speed measuring in general G01P
• CPC Class Codes: G08G 1/096827 where the route is computed onboard

Abstract

Techniques are described for generating and using information regarding road traffic in various ways, including by obtaining and analyzing road traffic information regarding actual behavior of drivers of vehicles on a network of roads. Obtained actual driver behavior information may in some situations be analyzed to identify decision point locations at which drivers face choices corresponding to possible alternative routes through the network of roads (e.g., intersections, highway exits and/or entrances, etc.), as well as to track the actual use by drivers of particular paths between particular decision points in order to determine preferred compound links between those decision point locations. The identified and determined information from the analysis may then be used in various manners, including in some situations to assist in determining particular recommended or preferred routes of vehicles through the network of roads based at least in part on actual driver behavior information.

Claims

1. A computer-implemented method comprising:

receiving, by one or more configured computing systems, information that is gathered by a plurality of devices in a plurality of vehicles traveling on one or more roads and that reflects actual prior driver behavior during a plurality of prior vehicle trips along the one or more roads by the plurality of vehicles, wherein the actual prior driver behavior during the prior vehicle trips includes driver selections between multiple alternative choices at decision points along the one or more roads;

automatically analyzing, by the one or more configured computing systems and for multiple alternative paths between two locations on the one or more roads, the received information to determine a compound link representing a preferred path of the multiple alternative paths based at least in part on use of the preferred path from the actual prior driver behavior during the plurality of prior vehicle trips, wherein the automatic analyzing includes using values of an indicated traffic measure for the multiple alternative paths that are assessed from the received information; and

providing, by the one or more configured computing systems, an indication of the determined compound link, to enable future routine decisions using the determined compound link for vehicles on the one or more roads.

2. The computer-implemented method of claim 1, wherein the automatic analyzing further includes determining multiple decision points along the one or more roads based at least in part on the plurality of prior vehicle trips, each of the determined decision points corresponding to a connection of multiple roads which at least some of the plurality of vehicles travel past during at least some of the prior vehicle trips.

3. The computer-implemented method of claim 2 wherein the automatic analyzing further includes identifying multiple pairs of the determined decision points, each of the identified pairs of determined decision points having multiple alternative paths along the one or more roads from a starting one of the determined decision points of the pair to an ending one of the determined decision points of the pair and being associated with multiple of the plurality of prior vehicle trips that each includes one of those multiple alternative paths.

4. The computer-implemented method of claim 3 wherein the automatic analyzing further includes selecting one of the identified decision point pairs to represent the compound link, the selecting of the one decision point pair including excluding at least one other of the identified decision point pairs based at least in part on the at least one other decision point pair having more than a specified minimum amount of traffic passing one of the decision points of the pair and diverging at an additional intermediate decision point between the decision points of the pair.

5. The computer-implemented method of claim 2 wherein the automatic analyzing further includes identifying locations at which the plurality of prior vehicle trips perform at least one of diverging to multiple roads and of converging from multiple roads, the identified locations being candidates for the determined multiple decision points.

6. The computer-implemented method of claim 1 wherein the indicated traffic measure is a variability of traversal time, and wherein the automatic analyzing further includes determining the values of the indicated traffic measure based on the prior vehicle trips.

7. The computer-implemented method of claim 1 wherein the automatic analyzing is performed for each of multiple distinct aggregation categories by selecting a subset of the plurality of prior vehicle trips that correspond to the aggregation category and determining the preferred path with respect to the aggregation category based on the prior vehicle trips of the selected subset.

8. The computer-implemented method of claim 7 wherein the multiple distinct aggregation categories each includes one of multiple driver preferences.

9. The computer-implemented method of claim 7 wherein the multiple distinct aggregation categories each includes one of multiple vehicle types.

10. The computer-implemented method of claim 9 wherein the multiple distinct aggregation categories each further correspond to a distinct period of time.

11. The computer-implemented method of claim 1 further comprising, after determining the compound link, using the determined compound link as part of generating multiple alternatives for a route along the one or more roads, wherein at least one of the multiple alternatives includes using the determined compound link.

12. The computer-implemented method of claim 11 wherein the automatic analyzing further includes:

determining one or more additional compound links that each represents a preferred path of multiple alternative paths between distinct pairs of locations on the one or more roads; and

assessing, for each of the determined compound link and at least one of the additional compound links, the value of the indicated traffic measure for at least the preferred paths of that compound link, and

wherein the using of the determined compound link as part of generating the multiple alternatives for the route includes using the assessed value of the indicated traffic measure for the preferred path of the determined compound link.

13. The computer-implemented method of claim 1 wherein the information gathered by the plurality of devices includes a plurality of data samples that each reflects an associated road location of one of the plurality of vehicles at an indicated time.

17. The non-transitory computer-readable storage medium of claim 3 wherein the determining of the one or more compound links further includes excluding at least one of the identified decision point pairs from use with any compound links, the excluding being based at least in part on an amount of traffic diverging at an intermediate decision point between the decision points of the excluded decision point pair.

14. A non-transitory computer-readable storage medium having stored contents that configure a computing system to perform a method, the method comprising:

receiving, by the configured computing system, one or more indications of multiple vehicle trips along one or more roads by multiple vehicles;

determining, by the configured computing system and based at least in part on the multiple vehicle trips, one or more compound links that each represents one of multiple alternative paths between two locations on at least one of the one or more roads, wherein the determining of each of the one or more compound links is based at least in part on an assessed value of an indicated measure for each of the multiple alternative paths for the compound link, the assessed value for each alternative path being based at least in part on some of the multiple vehicle trips that include that alternative path; and

providing, by the configured computing system, an indication of at least one of the determined one or more compound links.

15. The non-transitory computer-readable storage medium of claim 14 wherein the method further comprises determining multiple decision points on the one or more roads based at least in part on the multiple vehicle trips, each of the determined decision points corresponding to a connection of multiple roads which at least some of the multiple vehicles travel past during at least some of the multiple vehicle trips.

18. The non-transitory computer-readable storage medium of claim 15 wherein the determining of the one or more compound links further includes identifying locations at which at least some of the indicated multiple vehicle trips diverge to multiple roads and/or converge from multiple roads.

19. The non-transitory computer-readable storage medium of claim 14 wherein the receiving of the one or more indications of the multiple vehicle trips includes receiving a plurality of data samples that are gathered by multiple devices each located in one of the multiple vehicles and that reflect actual prior driver behavior during a plurality of prior vehicle trips along the one or more roads by the multiple vehicles and that each reflects an associated road location of one of the multiple vehicles at an indicated time, wherein the indicated measure is based at least in part on one or more of an average traversal time, a variability of traversal time, or an average speed of travel, and wherein the determining of each of the one or more compound links further includes determining the assessed value of the indicated measure for each of the multiple alternative paths for the compound link.

20. The non-transitory computer-readable storage medium of claim 19 wherein the providing of the indication of the at least one determined compound link includes using the determined one or more compound links in generating one or more alternatives for a route along the one or more roads.

21. The non-transitory computer-readable storage medium of claim 14 wherein the stored contents include software instructions that, when executed, further configure the computing system to determine multiple compound links that are each associated with one of multiple distinct aggregation categories, wherein each of the multiple distinct aggregation categories includes at least one of one or more time periods and of one or more non-time factors, and wherein the determining of each of the multiple compound links includes selecting a subset of the indicated multiple vehicle trips that correspond to the associated aggregation category for the compound link and includes selecting an alternative path for the associated aggregation category for the compound link based on the indicated vehicle trips of the selected subset.

22. The non-transitory computer-readable storage medium of claim 21 wherein the multiple distinct aggregation categories each correspond to one of multiple distinct periods of time, one of a plurality of distinct vehicle types, and/or one of a plurality of driver preferences.

16. The non-transitory computer-readable storage medium of claim wherein the determining of the one or more compound links further includes identifying multiple pairs of the determined decision points such that each identified pair has multiple alternative paths on the one or more roads between the pair of determined decision points and is included by at least some of the indicated multiple vehicle trips, and associating each of the one or more compound links with one of the identified multiple pairs.

23. A computing system, comprising:

one or more processors; and

a system that, when executed by at least one of the one or more processors, causes the at least one processor to automatically determine a compound links that represents a preferred path between two locations on one or more roads, and to provide an indication of the determined compound links, wherein the automatic determining of the compound links includes;

analyzing information that is gathered by a plurality of devices in a plurality of vehicles traveling on the one or more roads and that reflects actual prior driver behavior during a plurality of prior vehicle trips along the one or more roads by the plurality of vehicles; and

selecting, for one of multiple alternative paths between the two locations, t use the one alternative path for the compound link based at least in part on an amount of traffic diverging at an intermediate decision point along the one alternative path from the actual prior driver behavior during the plurality of prior vehicle trips.

24. The computing system of claim 23 wherein the selecting to use the one alternative path is further based in part on one or more assessed values for a traffic measure for the one alternative path, wherein the traffic measure reflects a variability of traversal time, and an average traversal time or an average speed of travel.

25. The computing system of claim 24 wherein the system includes software instructions that, when executed, further configure the system to automatically determine multiple compound links that are each associated with one of multiple distinct aggregation categories, and wherein the analyzing of the information is performed for each of the determined multiple compound links and includes selecting a subset of the plurality of prior vehicle trips that correspond to the associated aggregation category for that determined compound link.