Learning road navigation paths based on aggregate driver behavior

• US 8,738,285 B2
• Filed: 03/11/2011
• Issued: 05/27/2014
• Est. Priority Date: 03/11/2010
• Status: Expired due to Fees

• 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:
  US13/046,644
• Publication Number:
  US 20110224898A1
• Time in Patent Office: 1,173 Days
• Field of Search: 701117-119, 701/400, 701/410, 701/411, 701/414, 701/416, 701423-425, 340/995.13, 34099521-99523
• US Class Current: 701/410
• 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 programmed computing systems, information about a plurality of prior vehicle trips along a plurality of roads in a geographic area, the plurality of prior vehicle trips involving a plurality of drivers of vehicles and each reflecting actual prior behavior of one of the plurality of drivers in traveling between a starting location in the geographic area and an ending location in the geographic area, the received information including, for each of the prior vehicle trips, indications of multiple data samples reported by a device in the vehicle as the vehicle travels between the starting and ending locations for that vehicle trip, each of the data samples indicating a road location and an associated time when the vehicle is at the indicated road location;

automatically analyzing, by at least one of the one or more programmed computing systems, the received information about the plurality of prior vehicle trips to determine multiple compound links that each represents a preferred path between two locations in the geographic area based on actual prior behavior of the plurality of drivers, the automatic analyzing including;

determining based on the plurality of prior vehicle trips multiple decision points along the plurality of roads that each corresponds to a connection of multiple roads which at least some of the plurality of prior vehicle trips arrive at and continue past during those at least some prior vehicle trips, the at least some prior vehicle trips that arrive at each of the determined multiple decision points being part of at least one of traffic diverging among the multiple roads of the connection for the decision point and of traffic converging from the multiple roads of the connection for the decision point;

identifying multiple pairs of the determined decision points, each of the identified decision point pairs including one of the determined decision points as a starting point and including another of the determined decision points as an ending point, each of the identified decision point pairs further having multiple alternative paths along the plurality of roads from the starting determined decision point to the ending determined decision point and having multiple associated prior vehicle trips from the plurality of prior vehicle trips that each include one of those multiple alternative paths, each of the multiple alternative paths being traveled by at least one of the associated prior vehicle trips; and

selecting multiple of the identified decision point pairs to represent the determined multiple compound links, the selecting of the multiple identified decision point pairs including excluding at least one of the identified decision point pairs based at least in part on a determined amount of traffic diverging at an additional intermediate decision point between the decision points of the excluded at least one identified decision point pair, each of the selected decision point pairs having a preferred one of the multiple alternative paths for that decision point pair that is used by a majority of the multiple associated prior vehicle trips for that selected decision point pair such that at most a specified amount of those multiple associated prior vehicle trips use an alternative path other than the preferred one path, the determined multiple compound links being the preferred one paths for the selected decision point pairs;

providing, by at least one of the one or more programmed computing systems, information about the determined compound links to enable future routing decisions for other vehicles to use the determined compound links as part of preferred routes; and

after the determining of the multiple compound links, automatically using, by at least one of the one or more programmed computing systems, the determined compound links to improve routing of additional vehicle trips through the geographic area, the using of the determined compound links including, for each of multiple requests for a route between two indicated locations in the geographic area;

selecting one of multiple alternative paths between the two indicated locations for the request based at least in part on the selected one alternative path including at least one of the determined compound links; and

providing the selected alternative path as the route for the request.

2. The method of claim 1 wherein the determined multiple decision points each further have at least one of (a) multiple of the at least some prior vehicle trips for the determined decision point incoming to the determined decision point along a single first one of the multiple roads of the connection for the determined decision point and departing from the determined decision point by being split among those multiple roads and of (b) multiple of the at least some prior vehicle trips for the determined decision point incoming to the determined decision point along those multiple roads by being split among each of those multiple roads and departing from the determined decision point by joining along a single second one of those multiple roads, and wherein the determining of the multiple decision points includes identifying a plurality of decision points along the plurality of roads and selecting a subset of the plurality of decision points to be the determined multiple decision points based at least in part on an assessed amount of at least one of the traffic diverging and of the traffic converging at each of the determined multiple decision points.

3. The method of claim 1 wherein the determining of the multiple compound links further includes, for each of one or more of the multiple compound links:

determining multiple different time periods of interest; and

for each of the multiple different time periods, selecting a subset of the multiple associated prior vehicle trips for the decision point pair corresponding to the compound link based on the selected subset of prior vehicle trips corresponding to the time period of interest, and identifying a determined compound link for the time period by identifying a preferred one of the multiple alternative paths for that decision point pair based on the selected subset of prior vehicle trips, and wherein the identified determined compound links for the multiple different time periods include multiple differing alternative paths.

4. The method of claim 1 wherein the receiving of the information about the plurality of prior vehicle trips along the plurality of roads includes receiving a plurality of data samples that are generated by a plurality of vehicles, the received plurality of data samples including the multiple data samples for each of the plurality of prior vehicle trips, and includes analyzing the received plurality of data samples to identify at least the plurality of prior vehicle trips for use in the determining of the multiple compound links.

5. The method of claim 1 wherein the at least one programmed computing systems that perform the automatic analyzing of the received information about the plurality of prior vehicle trips to determine the multiple compound links are part of an automated driver behavior analysis system, and wherein the at least one programmed computing systems that perform the automatic using of the determined compound links to improve routing of additional vehicle trips through the geographic area are part of an automated route selection system.

6. A computer-implemented method comprising:

receiving, by one or more programmed computing systems, information about a plurality of prior vehicle trips that involve a plurality of vehicles being driven by a plurality of drivers along a plurality of roads in a geographic area;

automatically analyzing, by the one or more programmed computing systems, the received information about the plurality of prior vehicle trips to determine one or more compound links that each represents a preferred path between locations in the geographic area based on actual prior behavior of the plurality of drivers, the automatic analyzing including;

determining multiple decision points along the plurality of 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;

identifying multiple pairs of the determined decision points, each of the identified decision point pairs having multiple alternative paths along the plurality of roads from a starting one of the determined decision points to an ending one of the determined decision points and having multiple associated vehicle trips from the plurality of prior vehicle trips that each includes one of those multiple alternative paths; and

selecting one or more of the identified decision point pairs to represent the determined one or more compound links, each of the selected decision point pairs having a preferred one of the multiple alternative paths for that decision point pair that is used by a majority of the multiple associated prior vehicle trips for that selected decision point pair; and

identifying, for each of the selected decision point pairs, the preferred one path for the selected decision point part as one of the determined compound links; and

providing, by the one or more programmed computing systems, information about the determined compound links to enable future routing decisions for other vehicles to use the determined compound links as part of preferred routes.

7. The method of claim 6 wherein the providing of the information about the determined compound links includes using the determined compound links as part of generating one or more alternatives for a route in the geographic area, at least one of the one or more alternatives including at least one of the determined compound links.

8. The method of claim 7 wherein the method further comprises evaluating the determined compound links with respect to a specified traffic measure by assessing a value for the specified traffic measure for each of the determined compound links based at least in part on the plurality of prior vehicle trips, and wherein the generating of the one or more alternatives for the route includes using the assessed value for the specified traffic measure for the at least one determined compound links.

9. The method of claim 8 wherein the specified traffic measure is an average traversal time, and wherein the assessed value for each of the determined compound links is based on multiple of the plurality of prior vehicle trips that each includes that determined compound link.

10. The method of claim 8 wherein the specified traffic measure is variability of traversal time, and wherein the assessed value for each of the determined compound links is based on multiple of the plurality of prior vehicle trips that each includes that determined compound link.

11. The method of claim 8 wherein the specified traffic measure is an average speed of travel, and wherein the assessed value for each of the determined compound links is based on multiple of the plurality of prior vehicle trips that each includes that determined compound link.

12. The method of claim 6 wherein the one or more programmed computing systems are part of an automated driver behavior analysis system, and wherein the providing of the information about the determined compound links includes sending the provided information to one or more other programmed computing systems that are part of an automated route selection system distinct from the driver behavior analysis system.

13. The method of claim 6 wherein the determining of the multiple decision points along the plurality of roads includes analyzing the received information about the plurality of prior vehicle trips to identify 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.

14. The method of claim 13 wherein the received information about the plurality of prior vehicle trips includes, for each of the prior vehicle trips, a plurality of data samples that each reports an indicated associated road location of the vehicle for that vehicle trip at an indicated time, wherein the identifying of the locations at which the plurality of prior vehicle trips perform at least one of the diverging and the converging includes using the plurality of data samples for each of the plurality of prior vehicle trips to determine paths of the vehicles for the plurality of prior vehicle trips, and includes using the determined vehicle paths to determine that some of the vehicles at each of the identified locations have different travel paths than other of the vehicles at those identified locations, and wherein the determining of the multiple decision points further includes selecting a subset of the identified locations to be the determined multiple decision points based on the identified locations of the subset each having at least a minimum amount of traffic on each of multiple different travel paths that include the identified location.

15. The method of claim 13 wherein the determining of the multiple decision points further includes selecting a subset of the identified locations to be the determined multiple decision points based on the identified locations of the subset each satisfying one or more specified criteria.

16. The method of claim 6 wherein the determining of the multiple decision points along the plurality of roads is performed based at least in part on map data obtained from an external source.

17. The method of claim 6 wherein the identifying of the multiple decision point pairs includes assessing a plurality of decision point pairs that each includes two of the determined decision points, and selecting a subset of the plurality of decision point pairs to be the identified multiple decision point pairs based at least in part on the decision point pairs of the selected subset each having multiple alternative paths that satisfy one or more specified criteria.

18. The method of claim 6 wherein the selecting of the one or more identified decision point pairs to represent the determined one or more compound links includes, for each of the one or more identified decision point pairs, evaluating the multiple alternative paths for that decision point pair with respect to a specified measure by assessing a value for the specified measure for each of the multiple alternative paths, the assessed values for the specified measure being based at least in part on the multiple associated vehicle trips for that decision point pair, and selecting the preferred one alternative path for that decision point pair from the multiple alternative paths for that decision point pair based in part on the assessed values for the specified measure.

19. The method of claim 6 wherein the selecting of the one or more identified decision point pairs to represent the determined one or more compound links includes excluding at least one of the identified decision point pairs based at least in part on the at least one decision point pairs each having an additional intermediate decision point that is between the pair of decision points and that has more than a specified minimum amount of traffic passing one of the decision points of the pair and diverging at the additional intermediate decision point so that it does not pass the other of the decision points of the pair.

20. The method of claim 6 wherein the selecting of the one or more identified decision point pairs to represent the determined one or more compound links is further performed for each of one or more distinct aggregation categories that each includes at least one of one or more time periods and of one or more non-time factors by, for one of the selected decision point pairs, selecting a subset of the multiple associated prior vehicle trips for that one selected decision point pair that correspond to the aggregation category, and determining a preferred one of the multiple alternative paths for that one selected decision point pair and for the aggregation category based on the prior vehicle trips of the selected subset that use the determined preferred alternative path satisfying one or more specified criteria, such that the determined preferred alternative path for each of the aggregation categories is a determined compound link for that aggregation category.

21. The method of claim 20 wherein the one or more distinct aggregation categories include multiple aggregation categories that each includes a distinct period of time, and wherein the determined preferred alternative paths for the one selected decision point pair and the multiple distinct aggregation categories include multiple distinct alternative paths.

22. The method of claim 20 wherein the one or more distinct aggregation categories include multiple aggregation categories that each includes one of multiple vehicle types, and wherein the determined preferred alternative paths for the one selected decision point pair and the multiple distinct aggregation categories include multiple distinct alternative paths.

23. The method of claim 20 wherein the one or more distinct aggregation categories include multiple aggregation categories that each includes one of multiple driver preferences, and wherein the determined preferred alternative paths for the one selected decision point pair and the multiple distinct aggregation categories include multiple distinct alternative paths.

24. The method of claim 6 wherein one or more of the determined multiple decision points each includes at least one of an intersection of two or more roads, of a split of one road into two or more roads, or of a merge of two or more roads into one road.

25. The method of claim 6 wherein the received information about the plurality of prior vehicle trips includes a plurality of data samples that each reports an indicated associated road location of one of the plurality of vehicle at an indicated time, the plurality of data samples being generated by devices associated with the plurality of vehicles, and wherein the method further comprises analyzing the plurality of data samples to identify the plurality of prior vehicle trips.

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

receiving, by the configured computing system, information about a plurality of prior vehicle trips along one or more roads by a plurality of vehicles that reflect actual prior behavior of a plurality of drivers;

automatically analyzing, by the configured computing system, the received information to determine a compound link that represents a preferred path between two locations on at least one of the one or more roads based on the actual prior behavior of the plurality of drivers, the automatic analyzing and including;

evaluating each of multiple alternative paths over the one or more roads between the two locations with respect to a specified measure by assessing a value for the specified measure for each of the multiple alternative paths, the assessed value for each alternative path being based at least in part on multiple of the plurality of prior vehicle trips that include that alternative path; and

selecting a preferred one of the multiple alternative paths to be the determined compound link based on the assessed value for the specified measure; and

indicating, by the configured computing system, the determined compound link.

27. The non-transitory computer-readable storage medium of claim 26, wherein the method further comprises determining multiple decision points along the plurality of roads based at least in part on the plurality of prior vehicle trips, each of the determined multiple decision points being a road location at which occurs at least one of traffic diverging to or converging from multiple roads, and selecting two of the determined multiple decision points as the two locations, such that the selected decision points respectively represent a starting point and an ending point on the one or more roads, the multiple alternative paths each including a distinct route between the starting point and the ending point.

28. The non-transitory computer-readable storage medium of claim 27 wherein the indicating of the determined compound link includes using the determined compound link as part of selecting one of multiple alternatives for a route, at least one of the multiple alternatives including the determined compound link.

29. The non-transitory computer-readable storage medium of claim 26 wherein the specified measure for the evaluating of the multiple alternative paths is popularity of use in the multiple associated vehicle trips such that the selected preferred one alternative path is used by at least a specified minimum amount of the multiple prior vehicle trips.

30. The non-transitory computer-readable storage medium of claim 26 wherein the specified measure for the evaluating of each of the multiple alternative paths is an average traversal time of the alternative path based on one or more of the multiple prior vehicle trips that include the alternative path.

31. The non-transitory computer-readable storage medium of claim 26 wherein the specified measure for the evaluating of each of the multiple alternative paths is variability of traversal time of the alternative path based on at least some of the multiple prior vehicle trips that include the alternative path.

32. The non-transitory computer-readable storage medium of claim 26 wherein the specified measure for the evaluating of each of the multiple alternative paths is an average speed of travel along the alternative path based on one or more of the multiple prior trips that include the alternative path.

33. The non-transitory computer-readable storage medium of claim 26 wherein the determining of the compound link that represents the preferred path between the two locations is further performed for each of one or more distinct aggregation categories that each includes at least one of one or more time periods and one or more non-time factors, by selecting a subset of the multiple associated vehicle trips that correspond to the aggregation category, and by selecting one of the multiple alternative paths to be a preferred compound link for that aggregation category based on the selected subset of prior vehicle trips.

34. The non-transitory computer-readable storage medium of claim 33 wherein the one or more distinct aggregation categories include multiple aggregation categories that each includes a distinct period of time, and wherein the preferred compound links for the multiple distinct aggregation categories include multiple distinct alternative paths.

35. The non-transitory computer-readable storage medium of claim 33 wherein the one or more distinct aggregation categories include multiple aggregation categories that each includes one or more non-time factors that include at least one of a vehicle type and of a driver preference, and wherein the preferred compound links for the multiple distinct aggregation categories include multiple distinct alternative paths.

36. The non-transitory computer-readable storage medium of claim 26 wherein the configured computing system is part of a driver behavior analysis system.

37. The non-transitory computer-readable storage medium of claim 26 wherein the computer-readable storage medium is a memory of the configured computing system, and wherein the contents are instructions that when executed program the configured computing system to perform the method.

38. A computing system, comprising:

one or more processors; and

a system that is configured to, when executed by at least one of the one or more processors, automatically determine a compound link that represents a preferred path between two locations on one or more roads based on actual prior behavior of a plurality of drivers on the one or more roads, the automatic determining of the compound link including;

receiving information about a plurality of prior vehicle trips along the one or more roads by a plurality of vehicles under control of the plurality of drivers, the received information including, for each of the prior vehicle trips, indications of multiple road locations of the vehicle during the vehicle trip;

identifying a pair of decision points along the one or more roads, each of the decision points being one of the two locations and corresponding to a connection of multiple roads which at least some of the plurality of prior vehicle trips travel past during those at least some prior vehicle trips, the identified decision point pair having multiple alternative paths between the pair of decision points and having multiple associated vehicle trips from the plurality of prior vehicle trips that each includes one of those multiple alternative paths;

selecting a preferred one of the multiple alternative paths to be the determined compound link, the preferred one alternative path being selected based on being used by at least a specified minimum amount of the multiple associated prior vehicle trips; and

indicating the determined compound link.

39. The computing system of claim 38 wherein the indicating of the determined compound link includes using the determined compound link as part of generating a route for a vehicle that includes at least a portion of the one or more roads.

40. The computing system of claim 39 wherein the one or more roads include a plurality of roads in a geographic area, and wherein the system is further configured to determine multiple decision points along the plurality of roads based at least in part on the plurality of prior vehicle trips, each of the determined multiple decision points being a road location at which occurs at least one of traffic along a single road splitting into traffic along each of multiple roads and of traffic along each of multiple roads joining into traffic along a single road, and to select the decision points of the identified pair from the determined multiple decision points such that the selected decision points represent a starting point and an ending point on the one or more roads, the multiple alternative paths each including a distinct route between the starting point and the ending point.

41. The computing system of claim 38 wherein the system is a driver behavior analysis system that includes software instructions for execution by the one or more processors.

42. The computing system of claim 38 wherein the system consists of a means for automatically determining the compound link that represents the preferred path between two locations on the one or more roads based on the actual prior behavior of the plurality of drivers on the one or more roads.