LEARNING ROAD NAVIGATION PATHS BASED ON AGGREGATE DRIVER BEHAVIOR

• US 20140309914A1
• Filed: 04/09/2014
• Published: 10/16/2014
• 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
• Granted Patent: US 9,299,251 B2
• Time in Patent Office: Days
• US Class Current: 701/119
• 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-42. -42. (canceled)

43. A computer-implemented method comprising:

receiving, by one or more configured computing systems, information relating to a plurality of prior vehicle trips along one or more roads by a plurality of vehicles;

automatically analyzing, by the one or more configured computing systems, the received information to determine a compound link representing a preferred path between two locations on at least one of the one or more roads, wherein the automatic analyzing includes selecting one of multiple alternative paths over the one or more roads between the two locations based at least in part on an assessed value of an indicated traffic measure for each of the multiple alternative paths, the assessed value for each alternative path being based at least in part on at least one of the plurality of prior vehicle trips that include that alternative path; and

providing, by the one or more configured computing systems, an indication of the determined compound link.

44. The computer-implemented method of claim 43 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.

45. The computer-implemented method of claim 44 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.

46. The computer-implemented method of claim 45 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.

47. The computer-implemented method of claim 44 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.

48. The computer-implemented method of claim 43 wherein the indicated traffic measure is one of an average traversal time, a variability of traversal time, and an average speed of travel.

49. The computer-implemented method of claim 43 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.

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

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

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

53. The computer-implemented method of claim 43 wherein the providing of the determined compound link includes using the determined compound link as part of generating multiple alternatives for a route along the one or more roads, at least one of the multiple alternatives including using the determined compound link.

54. The computer-implemented method of claim 43 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

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

55. The computer-implemented method of claim 43 wherein the information relating to the plurality of prior vehicle trips includes a plurality of data samples that each reflects an associated road location of one of the plurality of vehicles at an indicated time, the plurality of data samples being generated by devices associated with the plurality of vehicles.

56. 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.

57. The non-transitory computer-readable storage medium of claim 56 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.

58. The non-transitory computer-readable storage medium of claim 57 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.

59. The non-transitory computer-readable storage medium of claim 58 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.

60. The non-transitory computer-readable storage medium of claim 57 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.

61. The non-transitory computer-readable storage medium of claim 56 wherein the indicated measure is based at least in part on one or more of an average traversal time, a variability of traversal time, and an average speed of travel.

62. The non-transitory computer-readable storage medium of claim 56 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.

63. The non-transitory computer-readable storage medium of claim 62 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.

64. The non-transitory computer-readable storage medium of claim 56 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.

65. 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 one or more compound links that each represent a preferred path between two locations on one or more roads and provide an indication of at least one of the determined one or more compound links, the automatic determining of the one or more compound links including, for each compound link;

analyzing information regarding a plurality of prior vehicle trips along the one or more roads by a plurality of vehicles; and

selecting one of multiple alternative paths between the two locations for the compound link based at least in part on an assessed value of a traffic measure for each of the multiple alternative paths, the assessed value for each alternative path being based at least in part on one or more of the plurality of prior vehicle trips that include that alternative path.

66. The computing system of claim 65 wherein the traffic measure reflects one or more of an average traversal time, a variability of traversal time, and an average speed of travel.

67. The computing system of claim 65 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 regarding the plurality of prior vehicle trips for each determined compound link includes selecting a subset of the plurality of prior vehicle trips that correspond to the associated aggregation category for that determined compound link.