Abstract
This paper investigates how global navigation satellite systems (GNSSs) and inertial navigation systems (INSs), when appropriately augmented by ranging from local landmarks, can safely navigate vehicles through a real-world urban environment. We begin by considering safety requirements for driverless vehicles under fault-free assumptions and developing measurement models for multi-sensor integrated navigation systems using an extended Kalman filter. The critical elements of urban navigation are then discussed, including individual INS noise parameter specifications, vehicle speed, and the effect of velocity updates. Covariance analyses performed along a 9-km-long urban transect in downtown Chicago show that velocity updates measured by wheel speed sensors, vehicle kinematic constraints, and zero-velocity updates can extend navigation continuity by bridging intermittent GNSS signal availability. However, position reference updates at intervals between 15 and 35 m, based on light detection and ranging data from local landmarks in our case, are needed to achieve full navigation availability through the transect.
1 INTRODUCTION
Integrity has been the driving principle behind safety requirements for aviation navigation for decades (Davis & Kelly, 1993; Grimes, 2007; SC-159, 2004). More recently, integrity has been adopted for automated ground vehicle applications as well (Cosmen-Schortmann et al., 2008; Zhu et al., 2018). Integrity risk quantifies the reliability of the information provided by a navigation system; if the risk is too high, the vehicle carrying the system may be in danger. Fault-free integrity risk measures the probability that the navigation system output error exceeds allowable containment bounds when no sensor faults exist. Evaluating the fault-free integrity risk is the first critical step in determining whether a navigation system can meet the demands of an intended operation. If a system cannot meet such demands, there would obviously be no point in taking the next step of evaluating the presence of sensor faults.
Driverless vehicles will need to operate with integrity levels on local and residential streets subject to corresponding positioning accuracy at the centimeter level (Reid et al., 2019). This requirement can be achieved with global navigation satellite system (GNSS) real-time kinematic (RTK) positioning in open-sky environments (Feng & Wang, 2008), but buildings surrounding urban streets limit satellite visibility (Chapman et al., 2002) and can cause significant multipath effects (Khanafseh et al., 2018).
The exclusion of reflected GNSS signals is essential to ensure positioning integrity for driverless vehicles on urban roads (Cosmen-Schortmann et al., 2008). To exclude these signals, three-dimensional (3D) environment maps are needed to provide the means to trace GNSS signals. The concept of “shadow matching” identifies signal blockages in urban canyons (Groves, 2011), which can be accomplished by overlaying sky plots of satellite locations on a hemispherical sky view of the shadows to distinguish between line of sight (LOS) and blocked signals (Chapman et al., 2002; Johnson & Watson, 1984). Reflection points can be predicted via Householder transformations to identify satellite signals affected by multipath reflections (Householder, 1958; Jakobsen et al., 2015), so that the associated measurements from these satellites can be excluded to avoid loss of integrity in the position estimation process (Obst et al., 2012). However, an excessive number of such exclusions comes at the cost of RTK positioning accuracy and losses of carrier phase cycle ambiguities (Ong et al., 2009).
Integration with an inertial navigation system (INS) can help provide continuous navigation through GNSS signal outages. An extended Kalman filter (EKF) enables tight coupling of the INS and GNSS to achieve better position estimation performance in urban environments than GNSS alone (Falco et al., 2017; Groves, 2013). In principle, the complementary interaction between the sensors—the INS bridging GNSS signal outages and the GNSS calibrating the drifting INS error—would help ensure that centimeter-level accuracy is maintained. However, because INS errors drift over time, the integrated system cannot maintain high accuracy without frequent error corrections from the GNSS. The use of high-quality navigation-grade inertial sensors could slow down the error propagation, but their cost is incompatible with driverless vehicle applications (Brown & Hwang, 2012). An inertial measurement unit based on a micro-electromechanical system (MEMS) makes INS affordable for the application at hand. Further, as we will show later in this paper, the slower drifts in navigation-grade inertial instruments (relative to MEMS) are helpful only over time intervals much longer than those needed to meet the requirements of driverless vehicle navigation.
Other information sources that are freely available (more or less) on automobiles include wheel speed sensors (WSSs), vehicle kinematic constraints, and zero velocity updates (ZUPT). WSSs connected to the vehicle’s rear wheels measure the angular rates and help estimate the velocity in the heading direction (Gao et al., 2006; Hazlett et al., 2011). Vehicle kinematic constraints make use of the assumption that an automobile does not slip laterally and maintains contact with the ground (Godha & Cannon, 2007). When a vehicle is known to be stationary, for example, at stop signs and traffic signals, ZUPT inputs can be used to temporarily halt INS drift and correct velocity errors (Grejner-Brzezinska et al., 2001). Velocity information helps to control position error growth during GNSS signal outages.
Besides GNSS, feature-matching is another approach for positioning in urban environments. For example, light detection and ranging (lidar) can measure distances and angles with respect to environmental features (i.e., local landmarks), which can then be associated with known feature locations stored in an onboard database (Groves, 2013). By integrating lidar into a combined GNSS/INS/lidar localization system, it should be possible to maintain centimeter-level accuracy in urban streets (Wan et al., 2018). However, the reliability of lidar localization can be an issue when features are extracted incorrectly during harsh weather (Levinson et al., 2007), on congested streets (Joerger et al., 2017), or during roadside construction. Because of our emphasis on fault-free integrity, we do not address this important concern in this paper. Nevertheless, even with the assumption of fault-free feature extraction, the density of mapped landmarks required to positively contribute to urban navigation performance is an open question.
This paper investigates how GNSS and INS, when appropriately augmented by lidar ranging from local landmarks, can ensure safe navigation through a real-world urban environment under fault-free assumptions. Additionally, we determine which system elements and parameters are the most critical to urban navigation performance, including individual INS noise parameter specifications, average vehicle speed, kinematic constraints, landmark density, integrity requirements, and the effects of velocity updates.
This paper is organized as follows. Section 2 describes navigation performance requirements for driverless vehicles and simulates GNSS availability along a 9-km-long urban transect in downtown Chicago. In Section 3, we develop sensor measurement models and introduce a tightly coupled INS/multi-sensor integration scheme using an EKF. Section 4 determines which elements of the navigation system are the most essential to enable urban navigation. In Section 5, we provide the results of covariance analyses predicting how multi-sensor navigation systems may be able to meet fault-free integrity requirements in an urban environment. Section 6 presents our conclusions.
2 NAVIGATION PERFORMANCE REQUIREMENTS
2.1 Fault-Free Integrity Requirements
To ensure integrity, a vehicle computes a protection level that upper bounds its horizontal positioning error with respect to a specified probability of exceedance. Fault-free integrity can be evaluated based on whether the protection level exceeds a required alert limit, which defines a position domain containment volume (SC-159, 2004). However, official quantitative requirements for self-driving vehicles have not yet been established.
In this work, we are primarily interested in developing a methodology for evaluating fault-free integrity performance; thus, having a precise knowledge of the requirements is not strictly necessary. However, given our additional goal of providing potentially useful quantitative results, we consider example requirements, namely, maximum allowable position error standard deviations of 0.05 and 0.1 m, which bracket the range for safety-critical automated driving defined by the European Union Agency for the Space Programme (EUSPA, 2021). Although these may appear to be simply accuracy requirements, they can also serve as fault-free integrity requirements if we assert that they represent standard deviations of Gaussian overbounds of the error distributions and that all satellite measurements predicted to be corrupted by reflections from buildings are actively rejected.
At the upper end (0.1 m), if we assume roughly that the probability of exceeding a 0.5-m alert limit in both lateral and longitudinal directions should be lower than 10−7/moment, the 0.5-m alert limit corresponds to approximately a 5σ protection level under fault-free conditions (Table 1); thus, the maximum allowable position error standard deviation is approximately 0.1 m. At the lower end (0.05 m), we take into account results from the comprehensive analysis reported by Reid et al. (2019), where, in their strictest scenario, they derive requirements consistent with a position error standard deviation of approximately 0.05 m. Table 1 summarizes the parameters associated with the integrity requirements.
Summary of Parameters Associated with Integrity Requirements
In their end state, as acknowledged by Reid et al. (2019), integrity requirements should define a probability to be evaluated over a specific period (e.g., “per hour”) or distance (e.g., “per km”). Moreover, attitude integrity requirements that determine the allowable vehicle pose are specified. However, from a performance evaluation perspective, these factors would complicate performance evaluations considerably. Hence, in this first analysis, we treat the example position-domain standard deviation requirements as applying punctually at each instant in time, with the intent to address the more difficult problem in future research.
2.2 Continuity and Availability
Continuity represents the ability of a navigation system to ensure integrity throughout an entire trip. A loss-of-continuity event occurs at a moment between departure and arrival when the vehicle exceeds the allowable position error standard deviation. The concept of a continuity requirement is described as follows:
1
With the aid of 3D maps and satellite almanacs, the continuity can be predicted before a trip is initiated. The navigation function is deemed available for a specified trip if there is no predicted loss of continuity during the trip.
Continuity is influenced by the local environment and the time of day because of the impact of GNSS satellite motion. We assess availability by changing vehicle departure times during the day and verifying whether continuity is maintained for the entire trip. If continuity is maintained for all departure time trials over 24 h, we determine the availability to be 100%:
2
According to EUSPA (2021), the availability requirement of safety automated driving is more than 99.9%. Ideally, we desire 100% availability because driverless vehicles will be expected to be capable of operating at any time of day, just as human-driven vehicles are today. This goal can be achieved by using GNSS RTK in open-sky environments with base stations installed on building rooftops or in other open-sky areas within approximately 10 km, even for position-domain standard deviations of 0.05 m. However, such considitons are unlikely to occur in urban environments without aid from other sensors.
Our availability evaluation scenario assumes that the driverless vehicle enters an urban core from an open-sky starting point at which it has already completed GNSS RTK cycle ambiguity initialization and INS alignment, with an initial horizontal position error standard deviation of < 0.02 m and yaw attitude error standard deviation of < 0.1 deg (Nagai et al., 2021a). We evaluate the navigation performance after initialization and alignment for vehicles leaving the starting point every 15 min over 24 h.
2.3 GNSS Availability in a City
We begin our analysis by simulating availability using GNSS RTK with four constellations—the Global Positioning System (GPS), Galileo, Russia’s global navigation satellite system (GLONASS), and BeiDou—for a driverless vehicle traveling 9 km on State Street in Chicago. The route along the street passes through various environments, from low-rise near-open-sky neighborhoods to dense urban canyons with skyscrapers taller than 100 m. We use high-definition 3D maps containing all streets and buildings to exclude blocked and reflected signals (Figure 1(a)).
(a) High-definition 3D maps showing our simulation transect, State Street in Chicago; (b, c) LOS, blocked, and reflected signal identification
The 3D map allows us to project the field of view at 10-m intervals along the road, with a distance of 6 m from the sidewalk, onto a hemisphere representing the building occupancy in the sky. When the projection is overlapped with a sky plot of satellites, we can predict the signals from the satellites blocked by the buildings (Figure 1(b)). These satellites are obviously not used for positioning.
Signals reaching a vehicle’s receiver via specular reflection must be excluded as well. Because State Street consists of parallel lanes running from south to north, the building planes facing east and west are considered the primary reflection sources. We use the building occupancy sky plots and Householder transformations to determine whether a hypothesized reflection ray vector strikes the physical wall. If the simulated ray strikes the wall, the antenna receives the reflected signal from a phantom satellite direction (Figure 1(c)) (Nagai et al., 2020). The west/east-facing reflections have the same elevation as the original signals because the satellites are distant from the reflected sites. To protect fault-free integrity, range measurements associated with reflected signals are not included in subsequent positioning calculations. In the actual State Street environment, all surfaces have the potential to cause reflections, including north- and south-facing planes at times (at intersections, for example). However, our analysis will show that even if we ignore these additional potential reflections (i.e., do not exclude the affected satellites), there are still not enough visible satellites for safe vehicle navigation.
First, we consider GNSS satellite visibility along the street using the horizontal position dilution of precision (HDOP) (Nagai et al., 2020). For a 0.1-m maximum allowable position error standard deviation and 0.02-m GNSS RTK ranging error standard deviation, the maximum allowable HDOP is approximately 5. Figure 2, which depicts GNSS-satellite-visible regions in which the HDOP is less than 5, shows how GNSS satellite visibility gradually deteriorates as building height increases. We divide the environments in the figure into three qualitative categories: open-sky, intermittent GNSS-visible, and a succession of GNSS-denied areas. Figure 3 shows that the navigation availability never actually reaches 100% after 2000 m with GNSS RTK (Nagai et al., 2021b) because all estimated integer ambiguities are reset once the vehicle passes under an overpass. GNSS RTK re-initialization is never completed to provide satisfactory accuracy, even if there is sufficient GNSS satellite visibility. The results clearly show that INS augmentation is required to recover integer ambiguities between GNSS signal outages and to extend navigation continuity into the urban canyon.
GNSS satellite visibility simulation along State Street in Chicago for HDOP < 5 HDOP = 5 corresponds to a 0.1-m 1σ position error assuming a 0.02-m 1σ RTK ranging error.
GNSS RTK availability simulation in a fault-free integrity requirement for a driverless vehicle traveling from south (left) to north (right) on State Street
The maximum allowable error position standard deviation is assumed to be 0.1 m in both the lateral and longitudinal directions.
3 MULTI-SENSOR INTEGRATED NAVIGATION SYSTEMS
To improve availability, we now investigate integrating GNSS RTK with INS, ZUPT inputs, WSSs, and non-holonomic (NHL) and holonomic (HL) kinematic constraints. These are what we term “conventional” augmentations by simulation. We will later consider lidar as an optional additional sensor. Figure 4 shows the multi-sensor integration architecture, and the computation efficiency determines the sensor integration order. The tightly coupled EKF integration utilizes the INS measurement for prediction and the other sensor measurements for observation. The observations (z) from each sensor are incorporated through the measurement updates , and the INS measurements and the process model then generate the time updates
. Integrity evaluation requires an error change across the environments with the multiple sensors. Therefore, the error state vector of the Kalman filter is utilized rather than the state itself. The derivations of the following equations are provided in the references cited below. Detailed explanations of the elements of the plant matrix F, coefficient matrix Γ, observation matrices G and H, and noise vectors w and v are given in Appendix A.
Multi-sensor integration architecture
The INS linearized discrete dynamic model (Tanil, 2016) is described as follows:
3
where x is the state error vector consisting of the position error in the navigation frame δrN, velocity error δvN, attitude error δEN, and INS bias errors for the accelerometers ba and gyroscopes bg. Φ is the state transition matrix, and Γu is the input coefficient matrix. and
are the input error vectors expressed in the body frame for the accelerometer specific force measurements and gyroscope rotation rates, respectively. Γw is the noise coefficient matrix,
is the white noise vector of the process model, and W is the covariance matrix of w.
The ZUPT in the EKF minimizes the propagation of position errors when the system knows that the vehicle is not in motion. This determination can be made by monitoring the velocity measured by the WSSs. The ZUPT measurement model (Nagai et al., 2021a) is as follows:
4
where δvB is the velocity error in the body frame (set to zero), H1 is the observation matrix, and is the vector of the velocity violation noise, modeled as white noise over the duration of the stop.
The lidar measurement model (Nagai et al., 2021b) is as follows:
5
where di is the range measurement to the i-th landmark (i.e., i = 1, 2, …, n), θi is the angle measurement, and the superscript * refers to reference values derived using the surveyed positions of the landmarks. The scalars and
are survey bias errors in the x and y directions, and
is the white noise vector on the lidar measurements.
The range and angle white noise statistics in Table 2 are manufacturer-specified parameters (i.e., Ouster OS1-64), but they do not fully account for the measurement error in lidar positioning. Survey error also contributes to this error. This error exists if landmark-reflected contour points are converted to a landmark center position that is different from the corresponding mapped location listed in the database. These landmark database errors are sometimes included by increasing the standard deviation of the lidar white noise. Instead, we correctly treat these errors as a bias vector δp incorporated into the EKF states, in our case, with an assumed zero-mean 0.02-m 1σ initial error. The error budget of lidar models has not yet been specified, and it cannot be simply described by manufacturer specifications and survey uncertainty. Therefore, this lidar model requires additional validation.
Multi-Sensor Noise Parameters
The EKF GNSS double-difference measurement model (Tanil, 2016) is as follows:
6
where λ is the carrier wavelength, ϕ is the carrier phase measurement, ρ is the code phase measurement, G is the observation matrix containing LOS vectors excluding the pseudorange measurements associated with the blocked and reflected signals, m is the multipath error, N is the integer ambiguity, Γ3 is the noise coefficient matrix, and is the white noise vector of the GNSS measurements.
WSSs are standard equipment for all vehicles, and vehicle kinematic constraints are applicable without equipment. We developed the model described in Equation (7), which consists of WSS measurements in the along-track direction, an NHL constraint resisting lateral sliding, and an HL constraint on vertical movement (Nagai et al., 2021a):
7
where δRR and δRL are the radius errors of the wheels, LB is the skew-symmetric matrix form of distance between the center of mass and the wheel axis, is gyroscope rotation rate measurement error, Γ4 is the noise coefficient matrix, and
is the white noise vector of the WSS measurements. Both Equations (4) and (7) refer to the velocity of the WSS, but Equation (4) is used only when the vehicle is stationary.
We use the state estimate error covariance for the integrity analysis. The EKF error covariance matrix propagation is described as follows:
8
9
where is the updated estimate covariance, K is the Kalman gain,
is the predicted estimate covariance, Φ is the state transition matrix, and Q is the covariance associated with w in the discrete-time domain.
contains each state’s error variance along the diagonal:
10
The states can change with the combinations of sensors, and Equation (10) is an example of the INS-only case assumption. The position error standard deviation (Σr) contains the error standard deviation of the along-track (σx) and that of the cross-track (σy). We compare σx and σy to the maximum allowable position error standard deviations. is used for integrity evaluation rather than
because
will be available to the vehicle at the INS output rate, which will be much higher than the GNSS output rate. Table 2 shows the sensor noise parameters used in our simulations.
4 CRITICAL ELEMENTS OF URBAN NAVIGATION
4.1 Analytic INS Position Error Models
Integration with INS should extend the continuity in an urban environment, with the duration of extension varying, in principle, with the INS quality or “grade.” Unfortunately, a general grade categorization is not particularly useful as a quality guideline for the current application because of the complex contributions of individual INS error characteristics. The outputs from accelerometers and gyroscopes in an INS (specific forces and angular rates, respectively) are each subject to Gaussian white noise and slowly varying biases. Manufacturers specify these error sources in terms of random walk, bias stability, bias time constant, and bias repeatability noise parameters (Woodman, 2007). A random walk is additive Gaussian white noise on the accelerometer and gyroscope measurements, and bias stability and bias time constants of the accelerometers and gyroscopes are typically used to model the biases themselves as first-order Gauss–Markov processes. The initial knowledge of the bias state is referred to as bias repeatability. Table 2 describes the INS noise parameters of a STIM300 (tactical grade) and an Ellipse2 (industrial grade).
The EKF automatically produces the best estimation by accounting for these INS noise parameters, but it renders the impact of the individual error source invisible. However, we can determine the contribution of each INS error source to the total position error by deriving analytic INS position error models to evaluate how fast these errors propagate during GNSS signal outages. The analysis results will provide immediately useful information to aid INS selection for driverless vehicle applications.
We derive two analytic INS position error models, considering the bias as a first-order Gauss–Markov process or as Gaussian white noise (dubbed precise and approximate, respectively). The derivations of the equations have been given by Nagai et al. (2022). Assuming perfect initialization and alignment, the precise INS position error model is described as follows:
11
12
13
where t is time, Qva is the power spectral density (PSD) of the accelerometer random walk, Qηa is the PSD of the accelerometer bias stability, Qvg is the PSD of the gyroscope random walk, and Qηg is the PSD of the gyroscope bias stability. g is the gravitational acceleration, a is the accelerometer bias time constant, and b is the gyroscope bias time constant. The approximate INS position error model is described as follows:
14
Figure 5 presents the STIM300 INS position error drift versus time based on the two analytic INS position error models, Equations (11) and (14), and the actual EKF results. The jitters exhibited in the magnified inset plot of Equation (11) are caused by round-off errors resulting from the numerous additions and subtractions in the contributing Equations (12) and (13). The approximate INS position error model given by Equation (14) produces the same results as the EKF within a few minutes and only begins to diverge from the EKF results after approximately 30 min. We will use Equation (14) for the analysis in the remainder of this section because the INS position drift error reaches the 0.1-m maximum allowable position error standard deviation in less than 20 s.
STIM300 INS drifting position error versus time based on two analytic models and EKF results
Figure 6 shows the contribution of each STIM300 (Figure 6(a)) and Ellipse2 (Figure 6(b)) INS error source to the total position error and how fast each propagates under a GNSS signal outage. The accelerometer and gyroscope random walks contribute the majority of the total position error at the beginning, but the gyroscope bias stability surpasses all other sources after 1 h. Although the bias stability of the Ellipse2 is 14 times larger than that of the STIM300, the error source has far less of an impact over short intervals (~20 s) than the gyroscope and accelerometer random walks, which are revealed here to be critical INS specifications for driverless vehicle applications. This result is significant because INS cost is most strongly influenced by bias stability performance.
Error propagation due to (a) each STIM300 INS error source and (b) each Ellipse2 INS error source
RW: random walk
Figure 7 compares the position error drifts for three different INS grades, including all error sources after perfect initialization and alignment. The Ellipse2 performs essentially the same as the STIM300: both exceed a 0.1-m position error standard deviation at approximately 16 s. This type of direct position drift evaluation enables INS selection by performance rather than grade, which can minimize costs. Of course, stricter requirements on specific INS noise parameters can help with endurance but will undoubtedly incur higher costs. Nevertheless, such requirements will be far from sufficient to control drift in dense urban environments. For example, the navigation-grade INS (HG9900) can withstand approximately 70 s of GNSS signal outage in Figure 7, equivalent to 700-m endurance for a vehicle traveling at 10 m/s (36 km/h). Even neglecting the excessive cost of this sensor for the driverless vehicle application (likely higher than the cost of the vehicle itself), a succession of GNSS-denied areas spanning several kilometers, as shown in Figure 2, far exceeds 700 m. Therefore, the navigation-grade INS by itself would still be insufficient to bridge the GNSS signal outages.
Performance boundary examination among three grades of INS
4.2 Vehicle Speed
A vehicle’s speed is a significant factor in urban navigation performance because the car minimizes the INS position error drift by increasing speed to pass through a congested sky environment more quickly. To observe this trend, we select one congested section surrounded by tall buildings and compute the position error standard deviation along the path. The evaluation points are at 10-m intervals over a total distance of 170 m. The yellow lines in Figure 8 denote the visible satellites, identified by GPS pseudorandom noise (PRN) numbers, at each point. The strip below the yellow lines shows the locally visible sky at each evaluation point. We assume that the navigation system has already been initialized and aligned at the first point.
Evaluation points and GPS PRN numbers of visible satellites at each point
In the simulation, the car equipped with INS/GPS moves at one of two different speeds: 1 or 5 m/s. Figure 9 shows the position error standard deviation versus the distance traveled. The dotted line shows the number of visible satellites. When the vehicle is held at a constant speed of 1 m/s, the error standard deviation exceeds 0.1 m at a travel distance of 60 m (Figure 9(a)). However, when the vehicle has a constant speed of 5 m/s, the error standard deviation never reaches 0.1 m (Figure 9(b)). A vehicle clears the blockage area more quickly when it moves faster, reducing the impact of INS drift, which is a function of time, not distance. Protection levels for trips through the same area will be different if the vehicle is smoothly cruising or gets stuck in a traffic jam. Vehicle motion in an urban environment is not entirely predictable, and even if it were, safety concerns would still limit the maximum allowable speeds. However, for GNSS-obstructed locations in which it is known that the vehicle must stop (e.g., certain intersections, bus stops for buses), INS error drift can be, albeit temporarily, predictably paused with a ZUPT input.
Comparison of position error growth between velocities of 1 and 5 m/s (a) Position error growth at velocity of 1 m/s INS/GPS (b) Position error growth at velocity of 5 m/s INS/GPS
4.3 Velocity Update
Dead-reckoning sensors other than an INS are also available for vehicles navigating urban environments. WSSs can provide continuous velocity updates, and ZUPT inputs are applicable when the system can identify stationary situations. We next investigate how velocity updates can slow down INS position error drift during GNSS signal outages and reveal both the benefits and limitations of these additional sources of dead reckoning.
During a GNSS outage, the EKF uses additional velocity information to improve position accuracy by exploiting the correlation between the position and velocity states. The position error after a velocity update σr+ is related to the position error before the update σr−, the correlation between position and velocity before the update σrv−, and the velocity error before the update σv− as follows:
15
Prior to the velocity update, σr−, σrv−, and σv− grow with the coasting time, and σr− = σr follows the error profile in Equation (14). After the velocity update, the INS position error profile is given as follows:
16
where the time t is referenced to the onset time of the GNSS outage and other notations are the same as in in Equation (14). The derivations of Equations (15) and (16) have been provided by Nagai et al. (2022). In Table 3, Equations (14) and (16) are compared to show the fractional position error improvements associated with each INS noise parameter following a velocity update. The relative contributions to position error reduction from a velocity update differ for the individual INS noise parameters. For example, the position error generated by gyroscope bias stability is reduced by a factor of 1/6 after the velocity update, while that generated by the accelerometer random walk is 1/2. Figure 10 shows the ZUPT position error corrections realized by using the EKF and Equation (16). The position correction for the Ellipse2 is greater than that for the STIM300 because of the higher gyroscope bias instability. Despite the improvements afforded by velocity updates, Equation (16) clearly shows that position errors will still accumulate over time during GNSS outages unless alternative external position reference updates are available.
Fractional Position Error Improvement After Velocity Update Associated with Each INS Noise
Parameter
RW: random walk
Position error corrections with ZUPT based on the EKF and Equation (16)
4.4 Position Reference Density
To regain control over navigation performance in urban environments, we consider augmentation by lidar ranging from local landmarks. A lidar sensor detects objects in the surrounding space and measures the ranges and angles of those within its field of view. Although all objects in urban environments can serve as external ranging sources for lidar, our focus is on extracting pole-like landmarks (e.g., street lamps). We assume that the pole cross-section center is computed from the reflected laser contour points with negligible feature extraction error and that the navigation system utilizes the range and angle to this computed center for the measurement. The centers are associated with predefined landmarks that correspond to known locations on a map. The vehicle estimates its position using the mapped landmark locations and lidar measurements. Assuming that landmarks can be added to existing environments, we can predict the necessary position reference density for future urban environments in which navigation availability for driverless vehicles is essentially 100%.
We integrate lidar ranging with the multi-sensor navigation system (INS, ZUPT, lidar, GNSS, WSS, NHL, and HL) for two different landmark density assumptions: (1) traffic light poles already existing at intersections (approximately every 200 m) based on actual mapped locations and (2) streetlight poles purposefully arranged at 15-m to 35-m intervals in the longitudinal direction. In either case, the landmarks are lined up 6 m away from the vehicle in the lateral direction. As the vehicle drives in the along-track direction, the external position references for the lidar are taken from the closest landmark within a 6.5-m distance (Figure 11). The simulation results in the following section show that the position reference density is a major factor in ensuring fault-free integrity.
Configuration of the vehicle and a position reference landmark measured by lidar
5 COVARIANCE ANALYSIS
We simulate a driverless city bus traveling 9 km along State Street in Chicago, from 35th Street in the south to North Avenue in the north. The bus route along the street passes through a variety of environments, ranging from low-rise, near-open-sky neighborhoods to dense urban canyons with skyscrapers taller than 100 m. High-definition 3D maps used in the simulation include all of the streets and buildings (Figure 1(a)). The range of bus speeds is determined via GPS traces collected from Chicago Transit Authority buses in 2018; the speeds vary with location along the route and the time of day. We select a 5:00 pm commute time, which has the slowest average speed, and assume that the bus halts at all bus stops along the street for 20 s with a deceleration or acceleration of 1 m/s2 (Figure 12). The results of seven simulation scenarios (Table 4) are shown in Figures 13–20 to demonstrate how the integration of different sensors affects navigation availability.
Bus speed: nonstop (left) and stop (right) scenarios
Simulation Scenarios and Corresponding Figures Showing the Navigation Performance Results
Navigation performance: stop / INS, GNSS / STIM300
Navigation performance: nonstop / INS, GNSS / STIM300
Navigation performance: stop / INS, ZUPT, GNSS / STIM300
Navigation performance: stop / INS, ZUPT, GNSS, WSS, NHL, HL / STIM300
Navigation performance: stop / INS, ZUPT, GNSS, WSS, NHL, HL / Ellipse2
Navigation performance: stop / INS, ZUPT, lidar, GNSS, WSS, NHL, HL / STIM300 / traffic light poles
Navigation performance: stop / INS, ZUPT, lidar, GNSS, WSS, NHL, HL / STIM300 / every 35 m
Navigation performance: stop / INS, ZUPT, lidar, GNSS, WSS, NHL, HL / STIM300 / every 15 m
Each plot in Figures 13–20 shows the standard deviation of position error versus distance traveled and includes results for the along-track (left side, blue) and cross-track (right side, red) directions. The starting point is in the open sky, and the environment gradually changes to deep urban canyons as the distance increases. The simulation is repeated every 15 min for 24 h, corresponding to a total of 96 trials, and each thin gray line shows the position error standard deviation at that time. The upper bound of the set determines the availability; the navigation system provides 100% availability when the upper bound is less than either 0.1 or 0.05 m. The black lines indicate the 0.1-m or 0.05-m threshold associated with the integrity requirements, and the thicker lines indicate that the error exceeds the threshold.
A comparison of Figures 13 and 14 shows that a vehicle’s speed strongly influences the position error; the navigation performance in the nonstop scenario is much better than that for the stop case (without ZUPT) between 3500 and 4500 m. The INS position error drift exceeds the 0.1-m standard deviation when the vehicle slows down or stops in GNSS signal outage areas. However, the vehicle speed is not always controllable in urban environments (e.g., because of traffic lights, congestion, etc.); thus, we next look at the effectiveness of ZUPT inputs applied in stationary vehicle situations to reduce the effects of INS drift.
Figures 13, 14, and 15 show that when the vehicle starts and stops repeatedly in GNSS-compromised environments, ZUPT inputs improve performance to nearly the same level as the nonstop case. The INS position error drifts when the vehicle stops coincide with a GNSS signal outage, but the ZUPT input calibrates the INS position error. Incorporating ZUPT with deliberate vehicle stopping improves navigation availability when the vehicle is unable to travel at high speeds to a GNSS-available area. However, the need to decelerate and accelerate near stopping points lengthens the overall duration of the trip, which increases the effects of inertial drift and tends to counteract the gains achieved by the ZUPT. The results show that ZUPT-aided operations are not always superior to nonstop operations, as Figures 14 and 15 exhibit nearly the same results.
A comparison of Figures 15 and 16 illustrates the effect of adding WSS measurements and vehicle kinematic constraints. The velocity updates from WSSs reduce the along-track position errors between 3500 and 4500 m, as shown in the left plot of Figure 16. For an along-track 0.1-m maximum allowable position error standard deviation, the performance improvement is sufficient to extend navigation availability further into the city. Relative to the along-track results, the superior performance in the cross-track direction shown in the right plot of Figure 16 demonstrates the powerful effect of the NHL constraints.
Figures 16 and 17 show results for the two grades of INS investigated earlier: the tactical-grade STIM300 and industrial-grade Ellipse2. Based on the analysis in Section 4, it is not surprising that the performance results are essentially the same for the two INS grades.
Collectively, Figures 13–17 show that a navigation system comprised only of “conventional” elements (i.e., INS, ZUPT, GNSS, WSSs, and NHL and HL kinematic constraints) does not provide navigation availability through the city beyond 4500 m. The conventional sensors can extend availability to regions in which intermittent GNSS signals exist between 3500 and 4500 m but not beyond 4500 m because of the concentrated succession of GNSS-denied situations (see Figure 2). External position reference updates are needed to complete the transect passage.
Figure 18 shows the impact of augmenting the navigation system (i.e., INS, ZUPT, lidar, GNSS, WSSs, and NHL and HL kinematic constraints) with lidar ranging from traffic light poles already existing at intersections. The availability is improved but clearly not sufficient. Figures 19 and 20 show that the position reference density required to ensure end-to-end availability is approximately one landmark every 35 m for a 0.1-m maximum allowable position error standard deviation and every 15 m to achieve a 0.05-m maximum standard deviation.
An overview of the navigation system performance results is shown in Table 5. Here, the “travel distance” denotes the distance for which each system keeps the position error standard deviation at less than 0.1 or 0.05 m successively from the starting point. The “availability fraction” is defined as the sum of the distances for which the position errors do not exceed 0.1 or 0.05 m over the total transect distance of 8970 m.
Overview of Navigation System Performance
Each integrated sensor increases the traveled distance and availability coverage, indicating that conventional sensors that improve the position accuracy contribute to navigation performance. However, conventional navigation systems do not provide satisfactory integrity and availability for driverless vehicles throughout the city because of the GNSS satellite visibility dependency. The length of GNSS outages determines the necessary navigation sensors required for urban navigation. When GNSS position reference updates are not acquired before the position error exceeds the maximum allowable position error standard deviation, the system must be augmented by an alternative sensor that provides a position reference— in our case, lidar using local landmarks—allowing driverless vehicles to navigate safely in the absence of faults through urban areas.
6 CONCLUSION
We explored future navigation systems with the goal of achieving 100% availability for urban driverless vehicles. We began by considering candidate fault-free integrity requirements corresponding to Gaussian overbounding distributions with standard deviations between 0.05 and 0.1 m. We evaluated the performance along a 9-km-long urban transect in downtown Chicago, where availability using GNSS alone, as evaluated by compliance with the integrity requirement, falls far short of 100%. We then considered multi-sensor integrated navigation architectures consisting of an INS, ZUPT, GNSS, lidar, WSSs, and NHL and HL kinematic constraints to improve navigation availability. We note that the lidar model requires additional validation because the feature extraction error of pole-like landmarks was assumed to be negligible. Our investigation of individual INS noise source contributions revealed that the accelerometer and gyroscope random walks contribute to the total position error considerably more than the accelerometer and gyroscope bias stability for the driverless vehicle application. A vehicle with low speed is more likely to exceed the allowable error because of INS time-dependent error drift. Intentional vehicle stops with ZUPT inputs mitigate the error propagation, but the associated decelerations and accelerations lengthen the total drive time such that the resulting availability is essentially the same as in the nonstop scenario. Velocity updates from WSSs can partially calibrate along-track position errors but do not completely reset the INS drifting position errors. Position reference updates are required to handle the concentrated succession of GNSS-denied conditions in the Chicago transect. To achieve 100% availability of fault-free integrity, with requirements corresponding to maximum standard deviations between 0.05 and 0.1 m in both lateral and longitudinal directions, position reference spacing is required—in our case, lidar ranging from local landmarks—between 15 and 35 m, respectively.
HOW TO CITE THIS ARTICLE
Nagai, K., Spenko, M., Henderson, R., & Pervan, B. (2024). Fault-free integrity of urban driverless vehicle navigation with multi-sensor integration: A case study in downtown Chicago. NAVIGATION, 71(1). https://doi.org/10.33012/navi.631
APPENDIX A: MULTI-SENSOR MEASUREMENT MODELS
The details of the multi-sensor EKF models in Section 3 are provided here. The INS continuous linearized dynamic model is as follows:
A1
where δrN is the position error vector in the navigation frame including the along-track (δx), cross-track (δy), and vertical (δz) directions. δvN is the velocity error vector, and δEN is the attitude error vector including the roll (δϕ), pitch (δθ), and yaw (δψ) directions. ba,g are the INS bias error vectors for the accelerometer and gyroscope, respectively. NRB is the rotation matrix from the navigation to the body frame, and Qbe is the matrix that transforms Euler angle rates to body rotation rates. is the accelerometer specific force input error in the body frame, and
is the gyroscope rotation rate input error. νa,g are the white noise vectors on the accelerometer and gyroscope measurements arising from the random walk, and ηa,g are the bias white noise vectors on the accelerometer and gyroscope measurements arising from bias stability. The * superscripts refer to constant matrices evaluated at nominal values. The plant matrix F is as follows:
where is the Earth’s rotation rate expressed in the navigation frame, τa,g are the bias time constants for the accelerometer and gyroscope, and
is the vehicle rotation rate expressed in the body frame.
The EKF ZUPT measurement model is as follows:
A2
where δvB is the velocity error vector in the body frame and ν1k is the vector of the velocity violation noise modeled as white Gaussian noise.
The EKF lidar measurement model is as follows:
A3
where d is the ranging measurement vector containing the i-th landmarks (i = 1,2,…, n), θ is the angle measurement vector containing the i-th landmarks, and δp is the survey error vector containing px and py of the i-th landmark locations. is the vehicle reference position in the along-track direction, and
is the vehicle reference position in the cross-track direction. νd is the vector of ranging measurement white noise, and vθ is the vector of angle measurement white noise.
The EKF GNSS measurement model is as follows:
A4
where λ is the carrier wavelength, ϕ is the carrier phase measurement vector, ρ is the code phase measurement vector, and G is the observation matrix containing LOS vectors (e) excluding the measurements associated with blocked and reflected signals. m is the multipath error, and N is the integer ambiguity. νϕ and νp are the vectors of receiver thermal white noise on the carrier and code, respectively.
The EKF WSS, NHL constraint, and HL constraint measurement is given as follows:
A5
where LB is the skew-symmetric matrix form of the distance between the center of mass and the wheel axis and ωR,L are wheel rotation rates in the along-track direction. δRR,L are the radius error of the wheels, and is the gyroscope rotation rate measurement. νg is the vector of the gyroscope measurement white noise, vω is the speed sensor measurement white noise, ζ is the NHL constraint cross-track movement violation white noise, and h is the HL constraint vertical movement violation white noise.
Equation (A5) includes the gyroscope input error , which is also used by the EKF process model. Therefore, the measurement noise (νg) and process noise are correlated, and we cannot integrate these models directly into the EKF. To resolve this issue, the process model and the noise are modified according to the method described in Chapter 8 of Bar-Shalom et al. (2004).
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.