Innovation: Improved navigation through GNSS outages

Innovation Insights with Richard Langley

Fusing Automotive Radar and OBD-II Speed Measurements with Fuzzy Logic

SYN·ER·GY /ˈsinərjē/ noun: the interaction or cooperation of two or more organizations, substances, or other agents to produce a combined effect greater than the sum of their separate effects; from the Greek, “working together.” That is how the Oxford Dictionary defines this useful property that we often apply to business activities and other human interactions. But it can just as well describe the basis of an apparatus such as a navigation system that consists of several devices working together to produce a safer and more accurate result.

We all know that GPS or any GNSS for that matter doesn’t work everywhere all the time. For example, in built-up areas, signals can be blocked and reflected by buildings leading to positioning errors or complete outages. That is why it is quite common nowadays to combine a GNSS receiver together with an inertial measurement unit or IMU (often in the same package) to produce a more reliable solution for continuous navigation. But IMUs drift and so during an extended GNSS outage, the fidelity of the position reported by the GNSS plus IMU system will degrade with time. And so additional sensors must be added to the mix to improve the reliability of the navigation system. LiDAR, cameras, altimeters and so on have all been used severally or individually to augment the basic GNSS plus IMU combination. Self-driving cars, for example, use multiple sensors to provide safe navigation under specific conditions. Such specialized systems are quite expensive and so we might ask: Can the basic combination of GNSS and an IMU (or some of its components) be augmented by measurements already available in most vehicles or provided easily and inexpensively by equipment add-ons?

Yes. One measurement that helps is the forward speed of the vehicle. This is available from the vehicle’s on-board diagnostics computer system that tracks and regulates a car’s performance. Car manufacturers have adopted a standard for reporting data, the latest version of which is OBD-II. It is easy to interface to the OBD-II connector in a vehicle and extract the speed measurements – the same measurements displayed by the vehicle’s speedometer. Another potential source of speed measurements is the radar in most modern vehicles used for adaptive cruise control. That measurement is hard to acquire and has other limitations. But the idea to use radar as an input to a navigation system is a good one and easily obtained and installed radar units can be used instead.

But how do you optimally combine all of these sensor readings to produce reliable navigation? In the Innovation article this month, we take a look at how fuzzy logic can be used to get a reliable speed estimate, how that can be combined with accelerometer and gyroscope measurements to get position, velocity and attitude of a vehicle and, lastly, how that can be combined with GPS-derived position and velocity in an extended Kalman filter to produce an integrated navigation solution. Now that’s synergy.

Abosekeen

Standard land vehicles and self-driving cars have acquired precise navigation solutions to improve safety and assist drivers. GNSS is used as the primary source of the navigation solution for such applications. However, when driving in environments such as urban canyons, tunnels, or under bridges, GNSS signal reception deteriorates. Worse, it may suffer from a full outage. Because of this, we need a supplemental or backup system, such as an inertial navigation system (INS). The INS provides a complete navigation solution, and it is not affected by signal deterioration or jamming. GNSS/INS integration can achieve better accuracy than GNSS alone. However, such efficiency cannot be maintained during extended GNSS outages, especially with low-cost and commercial-grade inertial sensors for the INS. This drawback principally occurs because the INS solution suffers from accumulated error growth over time. This error causes path or trajectory drift, which becomes significant in the long term.

The fusion between an INS and a GNSS-based system provides a more robust solution than each system alone. In particular, INS/GNSS integration requires both systems to provide the vehicle with an accurate solution. However, when the vehicle is in challenging environments, the GNSS receiver cannot successfully update the integration filter, leaving the INS as the only source for the solution. When a GNSS outage is prolonged in some extreme situations, the solution quality deteriorates rapidly from INS drift. In particular, when using a micro-electromechanical system (MEMS) based inertial measurement unit (IMU), the drift rate significantly increases.

Several approaches have been introduced to overcome such drawbacks. Our reduced inertial sensor system (RISS) concept can be a replacement for the INS in land vehicle and ground robot applications. RISS can provide a complete navigation solution with fewer sensors than a standard INS. It is easily implemented for common land or self-driving vehicle navigation because it uses the vehicle’s on-board diagnostics standard II (OBD-II) device to determine the vehicle’s forward speed. INS requires two integration steps for positioning, but using the OBD-II speed measurements in the RISS mechanization requires only one.  This reduction reduces the drift rate because it limits error accumulation from the integration process.

RISS depends mainly on OBD-II speed measurements to provide the land vehicle forward velocity. Unfortunately, these speed measurements are vehicle-specification dependent. Furthermore, these speed measurements are vulnerable to several types of error sources that can be categorized as deterministic (systematic) and non-deterministic (non-systematic). Deterministic errors come from wheel-diameter changes due to variations in temperature, pressure, tread wear, speed, unequal wheel diameters between the different wheels, inefficient wheelbase (track width), limited resolution and sample rate of the wheel encoders. Non-deterministic error sources include wheel slips, uneven road surfaces and skidding. Both groups of error sources negatively affect the velocity, traveled distance and heading estimations using the speed measurements from the OBD-II device.

Accordingly, we have made several RISS modifications to enhance performance, such as integration with a GPS receiver by enhancing the system design matrix for the integration filter. Moreover, an azimuth measurement update from magnetometers was added to the RISS/GPS integrated navigation system to provide azimuth updates during GPS outage periods, so the system can ensure more reliable positioning accuracy in challenging GNSS environments. Furthermore, we introduced a radar-based RISS to overcome OBD-II speed measurement errors. With this system, we demonstrated the superiority of using a frequency modulated continuous wave (FMCW) radar as a speed source instead of the one based on the OBD-II device. Automotive adaptive cruise control (ACC) mainly uses the Doppler measuring technique to measure the target’s (the vehicle ahead’s) relative distance and velocity. The primary radar unit’s radiation pattern is supposed to be a narrow beam to avoid other moving objects. Unfortunately, clutter affects forward-looking radar-collected data. Besides, extracting the onboard vehicle’s speed is difficult primarily because of the radar installation position.

We improved the use of ACC by modeling the linear and non-linear error components with Fast Orthogonal Search as a non-linear system identifier. This provided a more precise solution during outages extending from 60 seconds to 10 minutes. Furthermore, vehicle positioning using ACC was enhanced by extracting the primary and target vehicles’ relative distances under specific rules in urban canyons. These results encouraged us to introduce a fusion between the RISS and ACC, developing a more robust navigation system that relies on more than one sensor type.

In this article, we propose a smart fusion technique to produce more accurate velocity information from both the Doppler radar and the OBD-II speed measurements. Our new RISS mechanization for land vehicle navigation uses the fused speed from the radar and the OBD-II device with a vertical gyroscope and two transversal accelerometers.

3D-RISS MECHANIZATION

Our approach relies on a RISS incorporating a single-axis gyroscope, accelerometers, and speed measurements. Two accelerometers are used to estimate the pitch and roll angles instead of using two additional gyroscopes. Speed from the OBD-II device and heading information from the gyroscope aligned with the vehicle’s vertical axis enables the calculation of velocity, as shown in FIGURE 1. Calculating pitch and roll from accelerometers rather than gyroscopes retains RISS’s low cost while avoiding the gyroscope’s underpinning integration of velocity and position errors. When pitch and roll are calculated from accelerometers, the first integration of the gyroscope to obtain pitch and roll is eliminated, and thus the error in pitch and roll is not proportional to time integration.

FIGURE 1. Block diagram of speed measurements from the OBD-II device and RISS mechanization. (Image: Authors)

ACC-RADAR-BASED RISS

The radar-based RISS mechanization can provide a complete navigation solution (including 3D position, velocity and attitude) using a reduced number of sensors compared to the classic INS. It consists of longitudinal and transversal accelerometers, one vertical gyroscope and one radar unit (see FIGURE 2). In this mechanization, the OBD-II-device-related measurements are replaced by those extracted from the FMCW radar.

FIGURE 2. Radar-based RISS/GPS integrated navigation system block diagram. (Image: Authors)

MULTI-SENSOR DATA FUSION

Data fusion is the process of combining data from multiple sensors and related information to achieve more specific inferences than can be achieved by using a single, independent sensor. Fusion processes are often categorized into three modes — low, intermediate and high-level fusion:

• Data level combines several sources of the same type of raw preprocessed data to produce a new data set expected to be more informative and useful than the inputs.
• Feature level combines features such as edges, lines, corners, textures or positions into a feature map used for the segmentation of images, detection of objects, and so on.
• Decision level combines decisions from several expert modes. Methods of decision fusion are voting, fuzzy logic and statistical methods.

Various approaches for multi-sensor data fusion including weighted average, Bayesian estimators, adaptive observers, algebraic functions, fuzzy logic, neural network, soft computing, non-linear system fusion, and Kalman. Drawbacks of these methods include:

• the necessity of adding new sensors to the system.
• use of linear estimation models that need previous knowledge of signal statistics.
• the presence of more than one faulty signal — an essential limitation of the performance. 
• the need to understand the behavior of the system to generate governing rules.

We used a data-clustering approach, which divides the data from a particular set into subsets (clusters) based on similarity. It could be defined as a reorganizing process for the dataset.

Fuzzy C-means (FCM) Algorithm. The FCM clustering algorithm represents the “fuzzify” step in the fuzzy system and is based on the minimization of an objective function called the C-means functional. The FCM algorithm (FIGURE 3) computes the standard Euclidean distance norm, which induces hyperspherical clusters. Hence it can only detect clusters with the same shape and orientation because the common choice of the norm-inducing matrix is the identity matrix. Three parameters in this algorithm have to be determined at the beginning: the number of clusters, the weighting parameter representing the system’s fuzziness, and the ending threshold, respectively.

FIGURE 3. FCM flowchart. (Image: Authors)

Cluster Number Selection. The FCM algorithm required predefining the number of clusters (Figure 3). This number can be entered randomly, taking iterations and time to converge to the best number, or be calculated. Many methods could be used, such as the validation parameters but only in an offline mode, or by using the data distribution itself and calculating the probability density function (PDF) by first calculating the data’s kernel and then calculating the PDF. This process can be done using the smooth kernel density estimator (SKDE), which is a powerful real-time approach. The main idea is that the measurements values drift in two directions around the acceptable region of measurements (see FIGURE 4). The number of clusters has to be determined in every instance of measurement. From the same figure, the partitions may be three if the drift was in two directions from the accepted region or may be two partitions if the drift at any instance were to the left or to the right direction (one direction drift).

FIGURE 4. Measured data partioning. (Image: Authors)

Subsequently, the number of clusters is determined according to the following two rules, based on the kernel estimator’s maximum peak location: If the maximum peak of the SKDE is left- or right-skewed, then the number of partitions is two; if the maximum peak of the SKDE is centered, then there are three.

METHODOLOGY

The methodology of the implementation of our approach is divided into two parts. The first part utilizes the FCM explained in the previous sections to produce a fused vehicle forward speed from the radar and the OBD-II device. The second part uses the fused speed in the INS mechanization instead of using one sensor only. Further, the mechanization output is integrated with the GPS receiver to establish a more accurate navigation system.

Sensor Fusion using Fuzzy Clustering. The data-fusion technique using the fuzzy clustering algorithm (FIGURE 5) consists of five main parts:

• collecting data from the environment by using multiple sensors.
• grouping the collected data by using the FCM algorithm in cluster form (“fuzzification”).
• applying the fuzzy clipping rule using a cutting tool (fuzzy process).
• making use of the clipping-rule properties to perform the fusion mechanism (additional process).
• using the mean of the minimum to estimate the fusion output (“de-fuzzification”).

FIGURE 5. Sensor data fusion mechanization. (Image: Authors)

The first part is concerned with setting the sensors for measuring a particular phenomenon from the environment. The second part is to “fuzzify” these measured data, using the FCM to separate the sensors’ data to a certain number of clusters with membership matrix and cluster centers. The fuzzy process deals with the output clusters and membership functions through a fuzzy process called the fuzzy clipping rule. This rule divides the membership function into two regions: the upper region of the cutting threshold, which is clipped and is useless in the fuzzy environment, and the lower region from the cutting threshold, which is the useful region in the fuzzy environment.

Additional processes are applied to benefit from the previous stage — the existence of two regions, one useful, and the other not. This process aims to distinguish between the membership’s functions of the clusters. This could be achieved by generating a binary code that represents the membership function of the clusters. This binary code is generated by comparing the membership function with the threshold value. After the clustering process, each cluster membership function is represented as a binary code. The creation of this code depends upon the membership functions for the clusters and a variable threshold level.

The defuzzification part aims to extract the suitable value and in the same units as those of the measurements. This part produces the fusion output. This output comes from the minimum binary code, which denotes the selected suitable cluster membership function. This cluster contains the optimum solution. This solution or the fusion process output is determined by the centroid of the selected membership function.

Fusion-Radar-RISS/GNSS Integrated Navigation System. In this part of our technique, the fusion algorithm’s output is used in producing a full navigation solution as a control input of the RISS mechanization. This solution is subsequently integrated with the GPS receiver in a loosely coupled scheme using an extended Kalman filter (EKF). The overall proposed integrated navigation system is shown in FIGURE 6.

FIGURE 6. Block diagram of fused radar-RISS/GPS integrated navigation system. (Image: Authors)

EXPERIMENTAL WORK

We carried out the experimental work to verify the proposed navigation system’s effectiveness by traveling real road trajectories. The testbed equipment was mounted inside and outside the test van.

The interior testbed coincides with the van axes. It was rigidly and firmly fixed in the rear seat location using a standard seat chassis. For inertial sensors, we used both a low-cost MEMS IMU and a tactical-grade IMU. The specifications of these units are shown in TABLE 1.

TABLE 1. Performance characteristics of IMUs.

We used a dual-frequency GPS receiver with an output rate of 1 Hz. The tactical-grade IMU includes three fiber-optic gyroscopes and three MEMS accelerometers. The tactical-grade IMU and the GPS receiver were integrated using an off-the-shelf assembly developed by the manufacturer to provide a fully integrated, tightly coupled GNSS/IMU system that delivers a highly accurate 3D navigation solution. This tightly coupled integrated system from the manufacturer is used as a reference to compare the performance and the effectiveness of our proposed methods.

The FMCW radar development kit from the manufacturer was mounted on the front bumper. The unit’s working frequency is 24.5 GHz with a maximum frequency span of 1.5 GHz, a maximum update rate of 10 Hz, a maximum detectable speed of 215 kilometers/hour, and a 3 dB-beamwidth angle of 8.5°. The chirp frequency spans were adjusted to be 0.125 GHz. The maximum coverage range was 30 meters, and the minimum was 0.5 meters.

RESULTS AND DISCUSSION

We conducted a road test with the proposed approach in the downtown area of Kingston, Ontario, Canada, in August 2017.

The trajectory followed is shown in FIGURE 7 projected on a Google map with the approximate locations of the outages. The reference is plotted in red, and the black arrows mark the direction of motion.

FIGURE 7. Road test trajectory with ovals indicating the approximate locations of GPS outages. (Image: Author)

Performance Evaluation. The proposed system performance was tested over six simulated outages. The outages have been selected to contain several dynamics such as turns, consecutive turns, stopping, crossing intersections, and straight driving. Furthermore, the outages occurred at different speed levels. The proposed system performance was compared to the traditional RISS/GPS and Radar/RISS/GPS integrated navigation system. The comparison criteria are 2D-position root-mean-square error (RMSE) and the maximum errors.

We compared our results using the radar-only versus OBD-II device test. TABLE 2 shows the RMSE of the 2D-position from the three systems in meters. Notice that the proposed system’s performance is better than the other two systems during four of the six outages. This result was achieved using the smart fusion technique to fuse the FMCW radar and the OBD-II speed measurements. Accordingly, the obtained speed is positively affecting the overall system performance.

TABLE 2. 2D-Position RMS-error for the low-cost INS unit during outages.

The average 2D-position RMSE reached 18.24 meters when using the OBD-II speed measurements only and 9.5 meters when using the radar only. On the other hand, the RMSE reached 9.4 meters when using the fusion between the two systems. The improvement percentage was 48.4% when applying the proposed integrated navigation system and 47.8% when using the radar-based system. The results show that the proposed system outperformed the other systems in outages 2, 3, 5 and 6 but did not do better than the radar-based system in outages 1 and 4. We highlight three outages.

The first outage had two left turns after a stop sign over a slippery road. This outage lasted for only 50 seconds, but the system’s behavior was due to wrong measurements combined with a complicated driving scenario when using the traditional RISS/GPS. On the other hand, the radar-based RISS/GPS produces a better solution because of having better velocity measurements in the mechanization, which provides the navigation filter with a better navigation solution. The proposed system limits the drift to around 16.7 meters, while the traditional system had a 68.7-meter drift in its solution.

The proposed system based on the fusion between both speed sensors — OBD-II and radar — could not compete with the radar because of the enormous gap between the two sensors and the lack of extra sensors. Despite that, the system produced a solution with 2D-RMSE of 22 meters, which is also better than the traditional RISS based on the OBD-II device and close to the results from fusing the radar. This problem can be solved by using an extra radar unit, typically installed with an ACC system. The system usually uses six radar units, two in the front and four at the vehicle’s corners.

The second outage duration was 80 seconds and contained two consecutive turns, right then left. The radar-based system reduced the solution drift from 28.13 to 23.58 meters. In contrast to the previous outage, the proposed system reduced the 2D-position maximum error to 14.2 meters. The proposed system’s result is superior to the radar-based system, which performed better in the previous outage because the OBD-II and radar measurements gap is not as large as the previous outage. The dynamics, the average speed and the road surface differ from the first outage.

The third outage was chosen to be a slight turn and mostly straight driving with an average speed of 60 kilometers/hour. This outage lasted for 110 seconds, and the proposed system holds the solution error growth down to 8.9 meters. The traditional system had a higher error growth rate and held it to 20.6 meters, and the radar-based system error reached 14.92 meters. This outage contained fewer dynamics when compared to other outages. Moreover, the slippage and false counting by the OBD-II device was not as considerable as in the first outage.

CONCLUSIONS AND FUTURE WORK

The performance of using a multi-sensor data-fusion technique based on fuzzy clustering successfully fuses the data measured by both the radar and the OBD-II device to produce a more robust forward speed of a moving land vehicle. The proposed system performance tested during six simulated GPS outages containing various dynamics significantly improved the overall navigation system, especially when the GPS signals were blocked. Finally, the fusion between multiple sensors leads to better performance if there are enough sensors or a fault-detection system to prevent the faulty sensor from biasing the fusion results. Moreover, the results demonstrate the superiority of the proposed fused radar RISS/GPS over each system alone.

As an extension to work reported here, we plan to apply our approach with an extra number of sensors to avoid the kind of drift that happened in outage number one. In addition, we suggest that a sensor fault-detection smart algorithm be added to the system to detect and control faulty sensors.

ACKNOWLEDGMENT

This article is based on the paper “Enhanced Land Vehicle Navigation by Fusing Automotive Radar and Speedometer Data” presented at ION GNSS+ 2020 Virtual, the 33rd International Technical Meeting of the Satellite Division of The Institute of Navigation, Sept. 21–25, 2020.

MANUFACTURERS

Our testbed used a Crossbow (now Moog Crossbow, www.moog.com) MEMS-grade XBOW IMU300CC IMU and a NovAtel/Hexagon (www.novatel.com) IMU-CPT tactical-grade IMU. We also used a SPAN-OEM4 or SPAN-SE NovAtel/Hexagon dual-frequency GNSS receiver. The radar development kit used is a Sivers IMA (now Sivers Semiconductors, sivers-semiconductors.com) RK1001K/00.

ASHRAF ABOSEKEEN is a lecturer in the Department of Avionics Engineering, Military Technical College, Cairo, Egypt. He received a B.Sc. and M.Sc. in electrical engineering from the Military Technical College in 2004 and 2012, respectively. He received his Ph.D. from the Department of Electrical and Computer Engineering, Queen’s University, Kingston, Ontario, Canada, in 2018.

UMAR IQBAL is an assistant clinical professor in the Department of Electrical and Computer Engineering, Mississippi State University. He completed his Ph.D. in electrical and computer engineering at Queen’s University in 2012.

ABOELMAGB NORELDIN is a professor in the Department of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, Ontario with a cross-appointment at both the School of Computing and the Department of Electrical and Computer Engineering, Queen’s University.