Lane-level vehicle navigation for vehicle routing and traffic management

• US 9,964,414 B2
• Filed: 03/14/2014
• Issued: 05/08/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Caliper Corporation
• Original Assignee: Caliper Corporation
• Inventors: Slavin, Howard, Yang, Qi, Morgan, Daniel, Rabinowicz, Andres, Brandon, Jonathan, Balakrishna, Ramachandran
• Primary Examiner(s): Shaawat, Mussa A
• Assistant Examiner(s): Kerrigan, Michael V
• Application Number:
  US14/210,673
• Publication Number:
  US 20140278052A1
• Time in Patent Office: 1,516 Days
• 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: G01C 21/3658 Lane guidance
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0145 for active traffic flow control
• CPC Class Codes: G08G 1/096716 where the received information does not generate an automatic action on the vehicle control
• CPC Class Codes: G08G 1/096741 where the source of the transmitted information selects which information to transmit to each vehicle
• CPC Class Codes: G08G 1/096775 where the origin of the information is a central station

Abstract

A lane-level vehicle routing and navigation apparatus includes a simulation module that performs microsimulation of individual vehicles in a traffic stream, and a lane-level optimizer that evaluates conditions along the candidate paths from an origin to a destination as determined by the simulation module, and determines recommended lane-level maneuvers along the candidate paths. A link-level optimizer may determines the candidate paths based on link travel times determined by the simulation module. The simulation may be based on real-time traffic condition data. Recommended candidate paths may be provided to delivery or service or emergency response vehicles, or used for evacuation planning, or to route vehicles such as garbage or postal trucks, or snowplows. Corresponding methods also may be used for traffic planning and management, including determining, based on microsimulation, at least one of (a) altered road geometry, (b) altered traffic signal settings, such as traffic signal timing, or (c) road pricing.

Claims

1. A lane-level vehicle routing and navigation apparatus comprising:

a simulation module that performs microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream to predict travel times;

a link-level optimizer that determines candidate paths based on link travel times predicted by said simulation module; and

a lane-level route optimizer that evaluates predicted conditions along candidate paths from an origin to a destination as determined by said simulation module, and determines recommended lanes to use and the associated lane-level maneuvers along the candidate paths;

wherein;

said apparatus provides lane use recommendations from said lane-level route optimizer to a vehicle operator via a user communication device.

2. The lane-level vehicle routing and navigation apparatus of claim 1 wherein:

said simulation module performs multiple simulation runs for at least some of said candidate paths as part of said microsimulation-based dynamic traffic assignment; and

said link-level optimizer is utilized to identify time-efficient and reliable routes and route guidance.

3. The lane-level vehicle routing and navigation apparatus of claim 2 wherein said simulation module performs said multiple simulation runs at intervals of up to 1 second.

4. The lane-level vehicle routing and navigation apparatus of claim 3 wherein said simulation module performs said multiple simulation runs at intervals of between 0.1 second and 1 second.

5. The lane-level vehicle routing and navigation apparatus of claim 4 wherein said simulation module performs said multiple simulation runs at intervals of 0.1 second.

6. The lane-level vehicle routing and navigation apparatus of claim 1 wherein the recommended lanes to use and the associated lane-level maneuvers take into account driver route preferences.

7. The lane-level vehicle routing and navigation apparatus of claim 6 wherein said driver route preferences comprise lane preferences.

8. The lane-level vehicle routing and navigation apparatus of claim 1 wherein said lane-level route optimizer takes account of the operation of traffic controls along the candidate paths.

9. The lane-level vehicle routing and navigation apparatus of claim 8 wherein said operation of said traffic controls is simulated by said simulation module.

10. The lane-level vehicle routing and navigation apparatus of claim 8 wherein said operation of said traffic controls is evaluated based on real-time traffic control data.

11. The lane-level vehicle routing and navigation apparatus of claim 1 further comprising:

inputs for real-time traffic condition data;

wherein;

said simulation module bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

12. The lane-level vehicle routing and navigation apparatus of claim 1 wherein said lane-level optimizer takes account of future downstream lane conditions.

13. The lane-level vehicle routing and navigation apparatus of claim 1 wherein models used in said microsimulation, and said lane-level optimizer, take account of effects of obstacles to traffic flow.

14. The lane-level vehicle routing and navigation apparatus of claim 13 wherein said obstacles to traffic flow comprise one or more of (a) work zones, or (b) traffic accidents.

15. The lane-level vehicle routing and navigation apparatus of claim 1 wherein different routings are provided to different vehicles traveling from said origin to said destination.

16. The lane-level vehicle routing and navigation apparatus of claim 1 wherein said simulation module is at least one of (a) multi-threaded, or (b) distributed.

17. A lane-level vehicle routing and navigation apparatus comprising:

a simulation module that performs microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream, along candidate paths determined by link-level optimization, to predict travel times and to make lane use recommendations; and

inputs for real-time traffic condition data;

wherein;

said simulation module bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data;

said apparatus further comprising;

a user communication device that provides said lane use recommendations to a vehicle operator.

18. The lane-level vehicle routing and navigation apparatus of claim 17 wherein said real-time traffic condition data are available for at least one of (a) one or more vehicles, or (b) one or more road segments.

19. The lane-level vehicle routing and navigation apparatus of claim 17 wherein said real-time traffic condition data are available at lane level.

20. The lane-level vehicle routing and navigation apparatus of claim 17 wherein said simulation module performs microsimulations for said microsimulation-based dynamic traffic assignment at intervals of up to 1 second.

21. The lane-level vehicle routing and navigation apparatus of claim 20 wherein said simulation module performs said microsimulations for said microsimulation-based dynamic traffic assignment at intervals of between 0.1 second and 1 second.

22. The lane-level vehicle routing and navigation apparatus of claim 21 wherein said simulation module performs said microsimulations for said microsimulation-based dynamic traffic assignment at intervals of 0.1 second.

23. A lane-level vehicle routing and navigation method comprising:

performing microsimulation-based dynamic traffic assignment, in a simulation engine, of individual vehicles in a traffic stream to predict travel times;

determining, in a link-optimizing engine, candidate paths from an origin to a destination based on predicted link travel times determined by said performing;

evaluating, in a lane-optimizing engine, predicted conditions along said candidate paths from said origin to said destination as determined by said performing, and determining recommended lane-level maneuvers along said candidate paths; and

providing lane use recommendations, from said evaluating in said lane-optimizing engine, to a vehicle operator via a user communication device.

24. The lane-level vehicle routing and navigation method of claim 23 wherein:

said performing comprises performing multiple simulation runs for at least some of said candidate paths as part of said microsimulation-based dynamic traffic assignment; and

said determining comprises identifying time-efficient and reliable routes and route guidance.

25. The lane-level vehicle routing and navigation method of claim 24 further comprising:

inputting real-time traffic condition data;

wherein;

said performing bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

26. The lane-level vehicle routing and navigation method of claim 24 wherein said microsimulations for performing microsimulation-based dynamic traffic assignment occur at intervals of up to 1 second.

27. The lane-level vehicle routing and navigation method of claim 26 wherein said microsimulations for performing microsimulation-based dynamic traffic assignment occur at intervals of between 0.1 second and 1 second.

28. The lane-level vehicle routing and navigation method of claim 27 wherein said microsimulations for performing microsimulation-based dynamic traffic assignment occur at intervals of 0.1 second.

29. The lane-level vehicle routing and navigation method of claim 23 wherein the determining takes into account driver route preferences.

30. The lane-level vehicle routing and navigation method of claim 29 wherein said driver route preferences comprise lane preferences.

31. The lane-level vehicle routing and navigation method of claim 23 wherein said determining takes account of the operation of traffic controls along the candidate paths.

32. The lane-level vehicle routing and navigation method of claim 31 wherein said performing comprises simulating said operation of said traffic controls.

33. The lane-level vehicle routing and navigation method of claim 31 wherein said simulating said operation of said traffic controls is based on real-time traffic control data.

34. The lane-level vehicle routing and navigation method of claim 23 wherein said determining takes account of predicted downstream lane conditions.

35. The lane-level vehicle routing and navigation method of claim 23 wherein models used in said performing, and said determining, take account of effects of obstacles to traffic flow.

36. The lane-level vehicle routing and navigation method of claim 35 wherein said obstacles to traffic flow comprise one or more of (a) work zones, or (b) traffic accidents.

37. The lane-level vehicle routing and navigation method of claim 23 wherein different routings are provided to different vehicles from said origin to said destination.

38. A lane-level vehicle routing and navigation method comprising:

performing, in a simulation engine, microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream, to predict travel times along candidate paths determined by link-level optimization, and to make lane use recommendations;

inputting real-time traffic condition data; and

providing said lane use recommendations, from said performing microsimulation-based dynamic traffic assignment in said simulation engine, to a vehicle operator via a user communication device;

wherein;

said performing bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

39. The lane-level vehicle routing and navigation method of claim 38 wherein said real-time traffic condition data are available for at least one of (a) one or more vehicles, or (b) one or more road segments.

40. The lane-level vehicle routing and navigation method of claim 38 wherein said real-time traffic condition data are available at lane level.

41. The lane-level vehicle routing and navigation method of claim 38 wherein microsimulations for said performing microsimulation-based dynamic traffic assignment occur at intervals of up to 1 second to make said lane use recommendations.

42. The lane-level vehicle routing and navigation method of claim 41 wherein said microsimulations for performing microsimulation-based dynamic traffic assignment occur at intervals of between 0.1 second and 1 second.

43. The lane-level vehicle routing and navigation method of claim 42 wherein said microsimulations for performing microsimulation-based dynamic traffic assignment occur at intervals of 0.1 second.

44. A lane-level vehicle routing and navigation apparatus comprising:

a simulation module that performs microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream at intervals of up to 1 second to predict travel times;

a link-level optimizer that determines candidate paths from an origin to a destination based on link travel times predicted by said simulation module; and

a lane-level route optimizer that evaluates predicted conditions along said candidate paths from said origin to said destination as determined by said simulation module, and determines recommended lanes to use and the associated lane-level maneuvers along said candidate paths;

wherein;

said apparatus provides lane use recommendations from said lane-level route optimizer to a vehicle operator via a user communication device.

45. The lane-level vehicle routing and navigation apparatus of claim 44 wherein said simulation module performs microsimulations for said microsimulation-based dynamic traffic assignment at intervals of between 0.1 second and 1 second.

46. The lane-level vehicle routing and navigation apparatus of claim 45 wherein said simulation module performs said microsimulations for said microsimulation-based dynamic traffic assignment at intervals of 0.1 second.

47. The lane-level vehicle routing and navigation apparatus of claim 44 wherein:

said simulation module performs multiple simulation runs for at least some of said candidate paths for said microsimulation-based dynamic traffic assignment; and

said link-level optimizer is utilized to identify time-efficient and reliable routes and route guidance.

48. The lane-level vehicle routing and navigation apparatus of claim 44 wherein the recommended lanes to use and the associated lane-level maneuvers take into account driver route preferences.

49. The lane-level vehicle routing and navigation apparatus of claim 48 wherein said driver route preferences comprise lane preferences.

50. The lane-level vehicle routing and navigation apparatus of claim 44 wherein said lane-level route optimizer takes account of the operation of traffic controls along the candidate paths.

51. The lane-level vehicle routing and navigation apparatus of claim 50 wherein said operation of said traffic controls is simulated by said simulation module.

52. The lane-level vehicle routing and navigation apparatus of claim 50 wherein said operation of said traffic controls is evaluated based on real-time traffic control data.

53. The lane-level vehicle routing and navigation apparatus of claim 44 further comprising:

inputs for real-time traffic condition data;

wherein;

said simulation module bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

54. The lane-level vehicle routing and navigation apparatus of claim 44 wherein said lane-level optimizer takes account of future downstream lane conditions.

55. The lane-level vehicle routing and navigation apparatus of claim 44 wherein models used in said microsimulation-based dynamic traffic assignment, and said lane-level optimizer, take account of effects of obstacles to traffic flow.

56. The lane-level vehicle routing and navigation apparatus of claim 55 wherein said obstacles to traffic flow comprise one or more of (a) work zones, or (b) traffic accidents.

57. The lane-level vehicle routing and navigation apparatus of claim 44 wherein different routings are provided to different vehicles traveling from said origin to said destination.

58. The lane-level vehicle routing and navigation apparatus of claim 44 wherein said simulation module is at least one of (a) multi-threaded, or (b) distributed.

59. A lane-level vehicle routing and navigation apparatus comprising:

a simulation module that performs microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream, at intervals of up to 1 second, along candidate paths determined by link-level optimization, to predict travel times and to make lane use recommendations; and

inputs for real-time traffic condition data;

wherein;

said simulation module bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data;

said apparatus further comprising;

a user communication device that provides said lane use recommendations to a vehicle operator.

60. The lane-level vehicle routing and navigation apparatus of claim 59 wherein said simulation module performs said microsimulation-based dynamic traffic assignment at intervals of between 0.1 second and 1 second.

61. The lane-level vehicle routing and navigation apparatus of claim 60 wherein said simulation module performs said microsimulation-based dynamic traffic assignment at intervals of 0.1 second.

62. The lane-level vehicle routing and navigation apparatus of claim 59 wherein said real-time traffic condition data are available for at least one of (a) one or more vehicles, or (b) one or more road segments.

63. The lane-level vehicle routing and navigation apparatus of claim 59 wherein said real-time traffic condition data are available at lane level.

64. A lane-level vehicle routing and navigation method comprising:

performing, in a simulation engine, at intervals of up to 1 second, microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream to predict travel times;

determining, in a link-optimizing engine, candidate paths from an origin to a destination based on link travel times predicted by said performing;

evaluating, in a lane-optimizing engine, predicted conditions along said candidate paths from said origin to said destination as determined by said performing, and determining recommended lane-level maneuvers along the candidate paths; and

providing lane use recommendations, from said evaluating in said lane-optimizing engine, to a vehicle operator via a user communication device.

65. The lane-level vehicle routing and navigation method of claim 64 wherein said performing comprises performing said microsimulation-based dynamic traffic assignment at intervals of between 0.1 second and 1 second.

66. The lane-level vehicle routing and navigation method of claim 65 wherein said performing comprises performing said microsimulation-based dynamic traffic assignment at intervals of 0.1 second.

67. The lane-level vehicle routing and navigation method of claim 64 wherein:

said performing comprises performing multiple simulation runs for at least some of said candidate paths for said microsimulation-based dynamic traffic assignment; and

said determining comprises identifying time-efficient and reliable routes and route guidance.

68. The lane-level vehicle routing and navigation method of claim 64 wherein the determining takes into account driver route preferences.

69. The lane-level vehicle routing and navigation method of claim 68 wherein said driver route preferences comprise lane preferences.

70. The lane-level vehicle routing and navigation method of claim 64 wherein said determining takes account of the operation of traffic controls along the candidate paths.

71. The lane-level vehicle routing and navigation method of claim 70 wherein said performing comprises simulating said operation of said traffic controls.

72. The lane-level vehicle routing and navigation method of claim 70 wherein said simulating said operation of said traffic controls is based on real-time traffic control data.

73. The lane-level vehicle routing and navigation method of claim 64 further comprising:

inputting real-time traffic condition data;

wherein;

said performing bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

74. The lane-level vehicle routing and navigation method of claim 64 wherein said determining takes account of future downstream lane conditions.

75. The lane-level vehicle routing and navigation method of claim 64 wherein models used in said performing, and said determining, take account of effects of obstacles to traffic flow.

76. The lane-level vehicle routing and navigation method of claim 75 wherein said obstacles to traffic flow comprise one or more of (a) work zones, or (b) traffic accidents.

77. The lane-level vehicle routing and navigation method of claim 64 wherein different routings are provided to different vehicles from said origin to said destination.

78. A lane-level vehicle routing and navigation method comprising:

performing, in a simulation engine, at intervals of up to 1 second, microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream, along candidate paths determined by link-level optimization, to predict travel times and to make lane use recommendations;

inputting real-time traffic condition data; and

providing said lane use recommendations, from said performing microsimulation-based dynamic traffic assignment in said simulation engine, to a vehicle operator via a user communication device;

wherein;

said performing bases said simulation at least in part on said real-time traffic condition data.

79. The lane-level vehicle routing and navigation method of claim 78 wherein said performing comprises performing said microsimulation-based dynamic traffic assignment at intervals of between 0.1 second and 1 second.

80. The lane-level vehicle routing and navigation method of claim 79 wherein said performing comprises performing said microsimulation-based dynamic traffic assignment at intervals of 0.1 second.

81. The lane-level vehicle routing and navigation method of claim 78 wherein said real-time traffic condition data are available for at least one of (a) one or more vehicles, or (b) one or more road segments.

82. The lane-level vehicle routing and navigation method of claim 78 wherein said real-time traffic condition data are available at lane level.

83. A lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle, the apparatus comprising:

a simulation module that performs microsimulation-based dynamic traffic assignment for individual vehicles in a traffic stream to predict travel times;

a link-level optimizer that determines candidate paths based on link travel times predicted by said simulation module; and

a lane-level route optimizer that evaluates predicted conditions along candidate paths from an origin to a destination as determined by said simulation module, and determines recommended lanes to use and the associated lane-level maneuvers along the candidate paths;

wherein;

said self-driving automated vehicle makes lane changes based on lane-use recommendations from said lane-level route optimizer.

84. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 wherein:

said simulation module performs multiple simulation runs for at least some of said candidate paths as part of said microsimulation-based dynamic traffic assignment; and

said link-level optimizer is utilized to identify time-efficient and reliable routes and route guidance.

85. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 wherein said lane-level route optimizer takes account of the operation of traffic controls along the candidate paths.

86. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 85 wherein said operation of said traffic controls is simulated by said simulation module.

87. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 85 wherein said operation of said traffic controls is evaluated based on real-time traffic control data.

88. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 further comprising:

inputs for real-time traffic condition data;

wherein;

said simulation module bases said microsimulation-based dynamic traffic assignment at least in part on said real-time traffic condition data.

89. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 wherein said lane-level optimizer takes account of future downstream lane conditions.

90. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 wherein models used in said microsimulation, and said lane-level optimizer, take account of effects of obstacles to traffic flow.

91. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 90 wherein said obstacles to traffic flow comprise one or more of (a) work zones, or (b) traffic accidents.

92. The lane-level vehicle routing and navigation apparatus for a self-driving automated vehicle of claim 83 wherein said simulation module is at least one of (a) multi-threaded, or (b) distributed.