Innovation: Self-driving cars in urban environments

Photo: chuyu/Getty Images

How Inertial Systems and GNSS Availability Will Help

Innovation Insights with Richard Langley

ARE WE THERE YET? This was a familiar refrain from the backseats of parents’ cars when traveling to a holiday destination or to grandparents when I was growing up. We didn’t have videos on a display attached to the seats in front of us or (who could imagine?) our own personal communication device on which we could call up games, movies or social media channels.

But I’m not talking about that complaint from our childhoods. I’m asking if we have arrived at the era of the self-driving car. The answer is yes and no. It all depends on what you mean by “self-driving.” We reviewed some of the technologies needed for self-driving or autonomous vehicles in this column in June 2019. And we indicated in the introduction to that column that vehicle autonomy has several levels. SAE International, formerly known as the Society of Automotive Engineers, has defined six levels of autonomy that can be briefly described as Level 0 – no automation; Level 1 – hands on/shared control; Level 2 – hands off; Level 3 – eyes off; Level 4 – mind off; and Level 5 – steering wheel optional.

Already, Level 1 automation is widely available in modern cars with adaptive cruise control, parking assistance, lane-keeping assistance and automatic emergency braking among the features being offered. Level 2 automation, where the automated system takes full control of the vehicle’s acceleration, braking and steering, is available in some production models, although the “hands-off” designation is not to be taken literally — most motor vehicle laws require drivers to keep their hands on the steering wheel. Between Level 2 and Level 3, we have conditional automation — the car can drive itself, but the driver must stay alert and be prepared to take over immediately. Level 3 is high automation, where a computer fully drives the car at certain times on certain routes such as a highway; while the driver can perform other tasks such as reading a book, they must be prepared to take over operation of the vehicle within a few seconds if alerted by the automated system. While test campaigns are still ongoing, some jurisdictions permit Level 3 operation by ordinary drivers on some roads, and customers will soon be able to buy vehicles with this level of automation. Widespread use of Level 4 and Level 5 automation is further off (some would say quite a way off) and remains in development. But famously, last year, Toyota operated Level 4 self-driving shuttle vehicles around the Tokyo 2020 Olympic Village.

A lot more work needs to be done before we will have arrived at the era of the fully self-driving car that will be able to travel on any road, anywhere in the world, all year around, in all weather conditions. In particular, self-driving cars in urban environments (as opposed to highway driving) can be problematic. The required multi-sensor automated systems will include GNSS, but buildings block and reflect GNSS signals, reducing system availability and accuracy. In “Innovation” this month, researchers from the Illinois Institute of Technology report on how inertial navigation systems coupled with wheel-speed sensors and vehicle dynamic constraints can help.

By Kana Nagai, Matthew Spenko, Ron Henderson and Boris Pervan

GNSS provides navigation services globally, but satellite visibility in urban areas is limited by high-rise buildings. This creates a mixture of GNSS available and denied environments (see FIGURE 1) — users do not generally know where the system can maintain sufficient levels of accuracy and integrity for a particular application. To begin to address the issue for self-driving cars, we evaluated GNSS-only availability in downtown Chicago.

FIGURE 1 .  The figure depicts three types of potential GNSS signal reception: direct LOS signals and blocked LOS signals (left) and reflected LOS signals (right). (Image: Authors)

GNSS signal prediction in urban environments has been conducted in previous work. For example, the concept of “shadow matching” was developed to identify GNSS signal blockages in urban canyons. Overlaying sky plots on a hemispherical sky view can be used to distinguish between line-of-sight (LOS) and non-line-of-sight (NLOS) signals (see FIGURE 2a). Reflected rays can be predicted using Householder transformations to reveal potential multipath conditions. Satellites producing blocked or reflected (NLOS) signals should be excluded to maintain integrity.

FIGURE 2. (a) A hemispherical sky view in an urban environment. (b) Illustration of a protection level and an alert limit. To ensure integrity, the protection level must not exceed an alert limit. (c) The allowable probability of exceedance is assumed to be 10−7 in this work. (Image: Authors)

When the number of visible satellites is greater than three, GNSS can resolve vehicle position. However, even in cases where enough satellites are visible, the satellite geometries are generally weak because the dilution of precision (DOP) is adversely affected by the buildings partially blocking the sky. Horizontal positioning error must be bounded by a protection level computed by the vehicle. Then, for navigation to be deemed available, the protection level must not exceed a required alert limit (see FIGURE 2b). The maximum allowed probability of exceedance (see FIGURE 2c) and the alert limit can together be used to determine the maximum allowable position error standard deviation.

Even if the protection level is far below the alert limit in an open-sky environment, it will frequently exceed the alert limit once the vehicle enters a city. GNSS alone is generally not able to maintain availability, so integration with other sensors is needed. Tightly coupling inertial navigation systems (INS) with GNSS using the extended Kalman filter (EKF) provides better estimation in urban environments. The EKF algorithm also enables integration of wheel-speed sensors and vehicle dynamic constraints. These integrated navigation systems will improve availability, but it is still unclear how long such a system can be expected to maintain fault-free integrity in a congested city.

Focusing on the problem of self-driving cars in urban environments, we evaluate protection levels of navigation with practical integrated sensors: GNSS, INS, a wheel-speed sensor (WSS) and vehicle dynamic constraints (VDC). The goal is to develop the means by which we can determine locations where external ranging sources (such as lidar) are needed to maintain continuous navigation with fault-free integrity.

GNSS-ONLY AVAILABILITY

For GNSS availability evaluation, we assume an integrity requirement that the probability of exceeding a 0.5-meter alert limit must be lower than 10⁻⁷. The 0.5-meter alert limit therefore corresponds to approximately five times the position standard deviation, so the maximum allowable position error standard deviation is then approximately 0.1 meters. Accuracy at this level clearly requires differential GNSS carrier-phase measurements. We assume a nominal GNSS double difference (DD) carrier ranging error standard deviation of approximately 0.02 meters, and that carrier cycle ambiguities can be readily resolved in an open-sky environment prior to initiation of vehicle motion.

Given the assumptions made of the maximum allowable position error standard deviation and the GNSS ranging error standard deviation, the maximum allowable horizontal dilution of precision (HDOP) is about 5.

FIGURE 3 shows GPS and GNSS availability — the fraction of time the HDOP requirement is met over 24 hours — along a section of State Street in downtown Chicago. The availability results using GPS only and excluding only blocked LOS signals ranged from 0% to 9% along the block and 9% to 30% at the intersections (see FIGURE 3a). Using four full GNSS constellations (GPS, Galileo, GLONASS and BeiDou), availability ranged from 48% to 82% along the block and 72% to 100% at the intersections (see FIGURE 3b).

FIGURE 3. The percentage of GPS or GNSS availability in 3D-mapped downtown Chicago. We exclude satellites producing blocked LOS signals or both blocked and reflected LOS (NLOS) signals from the measurements. Each column expresses a lane of southbound or northbound travel. The availability is the percentage of total time when HDOP meets the self-driving car integrity requirements in 24 hours. (Image: Authors)

When we also excluded satellites producing reflected LOS signals that reach the vehicle, the availability dropped significantly at every point (see FIGURE 3c). We assert that FIGURE 3c expresses the reality of GNSS availability because building-reflected multipath signals degrade positioning accuracy and would affect integrity negatively. It’s obvious from these results that GNSS alone is insufficient to meet the autonomous driving requirements in an urban environment, and multi-sensor integrated navigation systems are needed to augment poor GNSS signal availability.

MULTI-SENSOR INTEGRATION

We begin by considering tightly coupled INS/GNSS integration using an EKF, and then integrate a realistic sensor suite including WSS and vehicle dynamic constraints that enforce resistance to lateral sliding and vertical movement. If it is known from another source that the vehicle is not moving (for example, it is in the parking gear), a static mode constraint (SMC) can also be applied.

INS/GNSS Integration. Tightly coupled INS/GNSS integration with an EKF uses the INS measurement to predict vehicle motion. The continuous process model uses a state vector having the position in the navigation frame, the velocity, the attitude, bias errors and cycle ambiguities, with the input vector having accelerometer-specific force measurement in the body frame and gyro-rotation-rate measurements. A white-noise vector drives the inertial measurement unit (IMU) states.

The GPS/GNSS measurement model includes the measurement vector having carrier and code phases, and the observation matrix containing LOS vectors and the vector of white receiver thermal noise.

INS/GNSS/WSS/VDC Integration. For the vehicle in motion, we developed a model consisting of a WSS measurement in the along-track direction, a non-holonomic constraint resisting lateral sliding, and a holonomic constraint on vertical movement (see FIGURE 4).

The INS/GNSS/WSS/VDC integration using the EKF consists of the process model and the measurement models.

INS/GNSS/SMC Integration. The static mode constraint provides zero-velocity measurements to the EKF measurement update to mitigate position error propagation. We use SMC only when it is known that the vehicle is not moving; for example, when the vehicle is in the parking gear. 

Error Propagation Analysis. We tested the time from perfect initialization to when position error exceeds 0.1 meters in GNSS-denied environments. FIGURE 5 shows the error growth in the along-track (x), the cross-track (y) and the vertical (z). The error specifications for a STIM300 tactical-grade IMU are used in this analysis. The standard deviation of the WSS measurement noise is assumed to be 0.05 meters per second, and the standard deviation of the movement constraint violations is 0.001 meters per second. The vehicle is moving at 5 meters per second except when we test the SMC.

FIGURE 5. The vehicle position error growth vs. time in the along-track (x), cross-track (y) and vertical (z) directions. Each graph represents the navigation system introduced in the multi-sensor integration section. The vehicle is moving at 5 meters per second (a and b) or 0 meters per second (c). (Image: Authors)

The INS can coast 15.6 seconds before the position error standard deviation exceeds 0.1 meters in both the along-track and the cross-track directions (see FIGURE 5a). The INS/WSS/VDC can coast 16.5 seconds in the along-track direction, and significantly more than 40 seconds (the simulation duration) in the cross-track direction (see FIGURE 5b). In static mode, INS/SMC estimate errors do not grow with time in any direction, as expected (see FIGURE 5c). In GNSS-denied environments, the non-holonomic constraint suppresses the cross-track position error, but the WSS measurement hardly affects the along-track position error. The SMC works perfectly, but the usage is limited to when the vehicle is known to be stationary.

SIMULATION SCENARIO

We imagine a future driverless-car mission scenario in which multi-sensor navigation systems are practicable. To minimize congestion in a city, autonomous vehicles will be held outside the urban core when not in use. In the clear open-sky environment, a vehicle in a parking lot completes GNSS initialization using the INS/GNSS/SMC system. Once requested for action, the vehicle departs for the city from the parking lot, and the motion of the vehicle improves alignment by the INS/GNSS system. Safe navigation can be ensured using the system to provide continuity under overpasses and bridges in the open-sky environment. Upon entering the urban core, navigation becomes more dependent on the INS/WSS/VDC system.

A reasonable numerical target for differential GNSS initialized position error is 0.02 meters, and for the INS alignment yaw angle error 0.1 degrees.

Local GNSS multipath errors from nearby vehicles will vary with the satellite elevation angle. Prior experimental results show that lower elevation-angle satellite signals (below 33 degrees) are much more likely to be impacted by multipath than higher ones (see TABLE 1).

TABLE 1. The nominal GNSS multipath error values in the simulation.

INITIALIZATION AND ALIGNMENT

Initialization takes place in a parking lot with a clear sky view. A vehicle is in the parking gear, enabling SMC to be applied. FIGURE 6a shows a typical example: with INS/GPS/SMC, system initialization takes about 31 minutes, and with INS/GPS, about 36 minutes. Therefore, SMC does speed up GPS initialization, although the improvement is modest.

The yaw angle is not aligned during the initialization, but roll and pitch are immediately aligned (see FIGURE 6b). Earth’s gravity affects roll and pitch angle alignment but not yaw angle.

FIGURE 6. (a) Comparisons of initialization time between INS/GPS and INS/GPS/SMC in an open-sky environment. The INS/GPS/SMC system initializes rapidly. (b) Transitions of roll, pitch, yaw alignment during the initialization. Yaw angle alignment cannot be performed when the vehicle is stationary. (Image: Authors)

Yaw angle alignment cannot be performed when the vehicle is stationary or moving with constant velocity. Accelerated motion, either straight or turning, is required. FIGURE 7 shows the behavior of the yaw angle error standard deviation using the INS/GPS system when centripetal (see FIGURE 7a) or tangential (see FIGURE 7b) acceleration is applied. The yaw angle can be aligned in a couple of seconds for either type of acceleration. To represent typical initial motions of self-driving cars, we model a parking-lot departure via a “Z”-shaped path. In this scenario, the yaw alignment error reaches 0.1 degrees within a couple of seconds (see FIGURE 7c).

FIGURE 7. The behavior of yaw angle error when centripetal (a) or tangential (b) acceleration is applied; (c) shows the behavior while following a z-shaped path. The yaw angle can be aligned in a couple of seconds in each case. (Image: Author)

EVALUATION IN URBAN ENVIRONMENTS

After initialization and alignment in the open-sky environment, we simulated the vehicle traveling into the urban core. The urban environment in our study is 3D-mapped State Street in Chicago, which runs north-south and transits from low-rise neighborhoods to central downtown. We selected one congested section surrounded by tall buildings and computed the position error standard deviation along the path. The evaluation points are at 10-meter intervals over a total distance of 170 meters. The yellow lines in FIGURE 8 denote the visible satellites, identified by their pseudorandom noise (PRN) code numbers, at each point. We assume for convenience that the INS/GPS system is initialized and aligned at the first evaluation point. In reality, we would expect a degraded initial condition because we are starting the simulation in an urban canyon.

FIGURE 8. Evaluation points and PRN numbers of visible satellites at each point. (Image: Author)

In the first simulation, the car equipped with the INS/GPS system moved either 1 or 5 meters per second. The y-axis in FIGURE 9 represents the position error standard deviation, and the x-axis represents the distance in meters. The dotted line expresses the number of visible satellites. The error when the vehicle velocity is 1 meter per second exceeded the maximum allowable position error standard deviation of 0.1 meter, at the distance of 60 meters. However, when the velocity was 5 meters per second, the maximum allowable position error standard deviation was never reached. It is also clear from the figures that error propagation is significantly affected by the number of visible satellites.

FIGURE 9. A comparison of position error growth between velocities of 1 meter per second and 5 meters per second. (Image: Author)

In the second simulation, we compared two different navigation systems, INS/GPS and INS/GPS/WSS/VDC. The vehicle moved at 1 meter per second in the same urban environment. The INS/GPS/WSS/VDC system does provide relief, but the error propagation is still clearly affected by the number of visible satellites (see FIGURE 10).

FIGURE 10. A comparison of position error growth between the INS/GPS and INS/GPS/WSS/VDC systems for a velocity of 1 meter per second. (Image: Authors)

In GNSS-challenged environments, INS error propagation is a function of time. When a vehicle moves faster, it clears the blockage area more quickly, reducing the impact of INS drift — a function of time, not distance. In contrast, GNSS error is completely determined by location. Because INS error propagation depends on how long the vehicle stays in an area of GNSS outage, protection levels for trips through the same area will be different if the vehicle is smoothly cruising or gets stuck in a traffic jam.

CONCLUSION

To gain a better understanding of how long and under what local conditions multi-sensor integrated navigation systems can maintain fault-free integrity, we evaluated navigation positioning errors in 3D-mapped downtown Chicago. The system we developed consists of sensors with which self-driving cars would reasonably be equipped: GNSS, INS, WSS and dynamic constraints. We showed that INS/GPS position errors along the path depend very strongly on the vehicle’s speed. When the system is augmented with WSS/VDC, position errors are suppressed, but the error propagation is still strongly influenced by the number of visible satellites.

ACKNOWLEDGMENTS

The research described in this article is supported by the National Science Foundation. Figure 1 was created by Alexis Arias of the Landscape Architecture + Urbanism Program at the Illinois Institute of Technology (IIT). The authors greatly appreciate the advice and help of Nilay Mistry from that program. 

This article is based on the paper “Evaluating INS/GNSS Availability for Self-Driving Cars in Urban Environments” presented at ION ITM 2021, the virtual 2021 International Technical Meeting of The Institute of Navigation, Jan. 25–28, 2021. 

KANA NAGAI is a Ph.D. candidate and research assistant in mechanical and aerospace engineering at IIT.

MATTHEW SPENKO is a professor of mechanical and aerospace engineering at IIT. He earned his M.S. and Ph.D. degrees in mechanical engineering from the Massachusetts Institute of Technology.

RON HENDERSON is a professor and director of the Landscape Architecture + Urbanism Program at IIT. He earned his Master of Landscape Architecture and Master of Architecture from the University of Pennsylvania.

BORIS PERVAN is a professor of mechanical and aerospace engineering at IIT. He earned his M.S. from the California Institute of Technology and Ph.D. from Stanford University.