US-12624953-B2 - Method and system of lane-level road congestion identification and forecasting for navigation application

Abstract

A method for lane-level road congestion identification and forecasting includes identifying lane-level road congestion using Gaussian mixture modeling, predicting lane-level road congestion using a 2D Markov chain, and identifying routes and route changes for a host vehicle and applying the route and route changes to improve a host vehicle estimated time of arrival (ETA) at a predetermined finish location such that the ETA is shorter than a predetermined threshold.

Inventors

• Fan Bai
• Michael Wahlstrom
• Donald K. Grimm
• Paul E. Krajewski
• Richard Gordon

Assignees

• GM Global Technology Operations LLC

Dates

Publication Date

20260512

Application Date

20230727

Claims (18)

1. 1 . A method for lane-level road congestion identification and forecasting, comprising: identifying lane-level road congestion comprising the steps of: developing a high-volume GPS trajectory trace set for vehicles traversing the predetermined segment of a road; conducting Gaussian mixture modeling (GMM) on the high volume GPS trajectory trace set; applying information to assist the GMM including a quantity of vehicle lanes of the predetermined segment of the road; performing an expectation maximization procedure to assist identification of a data convergence; comparing a Gaussian component due to GPS error to curves depicting a mixture of different Gaussian components; and isolating and distinguishing the Gaussian component from an overall Gaussian distribution; and predicting lane-level road congestion comprising the steps of: modeling a lane-level congestion evolution process as a 2-dimensional (2D) Markov chain having multiple vehicles moving through a predetermined segment of a road through horizontally and vertically adjacent road segments; aggregating a volume of the multiple vehicles over a predetermined unit of time moving through the predetermined segment; populating a lane congestion map identifying individual road lanes having differing levels of congestion; predicting a lane congestion map output and a lane congestion model output to a lane routing engine; identifying routes and route changes for a host vehicle and applying the route and route changes to improve a host vehicle estimated time of arrival (ETA) at a predetermined finish location such that the ETA is shorter than a predetermined threshold; and autonomously driving, via an automatic control system, the host vehicle along the identified routes and route changes.
2. 2 . The method of claim 1 , further including modeling lane level transition states through the use of Markov chains.
3. 3 . The method of claim 2 , further including: performing a 2D Markov chain dimension reduction; converting the 2D Markov chain to a one-dimensional (1D) Markov chain; and generating an error ε less than a predetermined percentage error.
4. 4 . The method of claim 3 , further including determining a 1D Markov chain error is satisfied and performing a 1D transition matrix generation, or determining the 1D Markov chain error is not satisfied and repeating a determination of the 1D Markov chain error.
5. 5 . The method of claim 4 , further including determining the 1D Markov chain error is satisfied and splitting the 1D transition matrix to form an iterative steady state estimation.
6. 6 . The method of claim 5 , further including: operating on the 1D transition matrix using a first iterative step applying a Jacobi iterative method to solve the 1D transition matrix; and identifying a system steady state estimation after the 1D matrix is solved.
7. 7 . The method of claim 5 , further including: operating on the 1D transition matrix using a first iterative step applying a Gauss-Seidel method to solve the 1D transition matrix; and identifying a system steady state estimation after the 1D transition matrix is solved.
8. 8 . The method of claim 1 , further including applying arrival and dissipative rates of vehicle motion to identify impacts of a behavior of individual ones of the multiple vehicles within the segment of the road while considering the vertically and horizontally adjacent road segments.
9. 9 . The method of claim 8 , further including identifying individual ones of the multiple vehicles having the differing levels of congestion, including non-congested lanes, busy or heavy traffic lanes and one or more congested lanes wherein traffic is stopped or slowed to a predetermined minimal speed.
10. 10 . The method of claim 1 , further including: predicting total of lane change count maneuvers made by the host vehicle until the predetermined finish location is reached; and conducting a trade-off analysis between minimizing the ETA of the host vehicle to the predetermined finish location and minimizing the total of the lane change count maneuvers to maximize a predetermined vehicle user comfort.
11. 11 . The method of claim 1 , wherein identifying lane-level road congestion further includes the step of performing a convergence test to identify individual vehicle traces.
12. 12 . The method of claim 11 , further including: identifying a lane assignment for the individual vehicle traces; and accumulating a current speed profile of the vehicles traveling in one of the vehicle lanes.
13. 13 . The method of claim 12 , further including comparing the current speed profile to a known, non-congested speed profile to determine if a current condition of the predetermined segment of any one of the vehicle lanes defines a congested condition or a non-congested condition.
14. 14 . The method of claim 11 , further including performing a lane assignment for the individual vehicle traces.
15. 15 . The method of claim 14 , further including: performing a first profile step to identify distributions of current lane-level speeds; conducting a second profile step in parallel with the first profile step to identify distributions of a non-congested lane-level speed; and comparing outputs from the first profile step and the second profile step.
16. 16 . The method of claim 1 , wherein identifying lane-level road congestion further includes the steps of: determining a volume of vehicles over a predetermined unit of time moving through the predetermined segment of the road; performing a lane assignment for individual vehicle traces of individual ones of the volume of vehicles; accumulating a current speed profile of a portion of the volume of vehicles traveling in one of multiple lanes of the road; comparing the current speed profile to a known, non-congested speed profile to determine if a current condition of the predetermined segment of any one of the multiple lanes defines a congested condition or a non-congested condition; and generating visual indications of multiple road image portions of the predetermined segment for presentation to an operator of a host vehicle identifying one of the congested condition or a non-congested condition.
17. 17 . The method of claim 16 , further including: obtaining a range of divergence values in terms of the speed profile; and establishing values of divergence congestion severity in the terms of the speed profile.
18. 18 . The method of claim 17 , further including varying one of a line width and a color of one of the multiple road image portions to distinguish between the values of divergence congestion severity.

Description

The present disclosure relates to autonomous vehicle navigation and control systems. High fidelity lane congestion indicators are needed for many autonomous vehicle (AV) applications such as optimal lane selection over the course of a trip including to facilitate exit from a controlled access road or freeway. Present systems assess road network congestion but lack lane traffic distribution information to identify lane congestion in high fidelity. Thus, while current systems and methods for autonomous vehicle navigation achieve their intended purpose, there is a need for a new and improved system and method to identify lane-level road congestion. SUMMARY According to several aspects, a method to identify lane-level road congestion comprises: modeling a lane-level congestion evolution process as a 2-dimensional (2D) Markov chain having multiple vehicles moving through a predetermined segment of a road through horizontally and vertically adjacent road segments; aggregating a volume of the multiple vehicles over a predetermined unit of time moving through the predetermined segment; populating a lane congestion map identifying individual road lanes having differing levels of congestion; predicting a lane congestion map output and a lane congestion model output to a lane routing engine; and identifying routes and route changes for a host vehicle to apply to improve a host vehicle estimated time of arrival (ETA) at a predetermined finish location. In another aspect of the present disclosure, the method further includes modeling lane level transition states through the use of Markov chains. In another aspect of the present disclosure, the method further includes: performing a 2D Markov chain dimension reduction; converting the 2D Markov chain to a one-dimensional (1D) Markov chain; and conducting an error determination to identify if the 1D Markov chain is satisfied; and generating an error ε less than a predetermined percentage error. In another aspect of the present disclosure, the method further includes performing a 1D transition matrix generation if a 1D Markov chain error is satisfied, or repeating a determination of the 1D Markov chain error if the 1D Markov chain error is not satisfied. In another aspect of the present disclosure, the method further includes splitting the 1D transition matrix to form an iterative steady state estimation when the 1D Markov chain error is satisfied. In another aspect of the present disclosure, the method further includes: operating on the 1D transition matrix using a first iterative step applying a Jacobi iterative method to solve the 1D transition matrix; and identifying a system steady state estimation after the 1D matrix is solved. In another aspect of the present disclosure, the method further includes: operating on the 1D transition matrix using a first iterative step applying a Gauss-Seidel method.to solve the 1D transition matrix; and identifying a system steady state estimation after the 1D transition matrix is solved. In another aspect of the present disclosure, the method further includes applying arrival and dissipative rates of vehicle motion to identify impacts of a behavior of individual ones of the multiple vehicles within the segment of the road while considering the vertically and horizontally adjacent road segments. In another aspect of the present disclosure, the method further includes identifying individual ones of the multiple vehicles having differing levels of congestion, including non-congested lanes, busy or heavy traffic lanes and one or more congested lanes wherein traffic is stopped or slowed to a predetermined minimal speed. In another aspect of the present disclosure, the method further includes: predicting total lane change count maneuvers made by the host vehicle until the predetermined finish location is reached; and conducting a trade-off analysis between minimizing the ETA of the host vehicle to the predetermined finish location and minimizing total lane change count maneuvers to maximize a predetermined vehicle user comfort. According to several aspects, a method to identify lane-level road congestion comprises: developing a high-volume GPS trajectory trace set for vehicles traversing a predetermined segment of a road; conducting Gaussian mixture modeling (GMM) on the high-volume GPS trajectory trace set; applying information to assist the GMM including a quantity of vehicle lanes applied; performing an expectation maximization procedure to assist identification of a data convergence; comparing a Gaussian component due to GPS error to curves depicting a mixture of different Gaussian components; and isolating and distinguishing the Gaussian component from an overall Gaussian distribution. In another aspect of the present disclosure, the method further includes performing a convergence test to identify individual vehicle traces. In another aspect of the present disclosure, the method further includes: identifying a lane assignment for the in