fde module

Fault Detection and Exclusion (FDE) methods for GNSS applications.

fde._edm(points)

Creates a Euclidean distance matrix (EDM) from point locations.

See [3] for more explanation.

Parameters:

points (np.array) – Locations of points/nodes in the graph. Numpy array of shape state space dimensions x number of points in graph.

Returns:

edm – Euclidean distance matrix as a numpy array of shape (n x n) where n is the number of points in the graph. creates edm from points

Return type:

np.array

References

[3]

I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli. “Euclidean Distance Matrices: Essential Theory, Algorithms, and Applications.” 2015. arxiv.org/abs/1502.07541.

fde._edm_detection_statistic(edm)

Calculate the EDM FDE detection statistic [5].

Parameters:

edm (np.ndarray) – Euclidean distance matrix from GNSS measurements

Returns:

• detection_statistic (list) – EDM FDE detection statistics

• svd_u (np.ndarray) – The U matrix from SVD

• svd_s (np.nddary) – The Sigma matrix from SVD

• svd_v (np.ndarray) – The V matrix from SVD

References

[5]

D. Knowles and G. Gao. “Detection and Exclusion of Multiple Faults using Euclidean Distance Matrices.” ION GNSS+ 2023.

fde._edm_from_satellites_ranges(sv_pos, ranges)

Creates a Euclidean distance matrix (EDM) from points and ranges.

Creates an EDM from a combination of known satellite positions as well as ranges from between the receiver and satellites.

Technique introduced in detail in [4].

Parameters:

• sv_pos (np.array) – known locations of satellites packed as a numpy array in the shape state space dimensions x number of satellites.

• ranges (np.array) – ranges between the receiver and satellites packed as a numpy array in the shape 1 x number of satellites

Returns:

edm – Euclidean distance matrix in the shape (1 + s) x (1 + s) where s is the number of satellites

Return type:

np.array

References

[4]

Knowles, Derek, and Grace Gao. “Euclidean distance matrix-based rapid fault detection and exclusion.” NAVIGATION: Journal of the Institute of Navigation 70.1 (2023).

fde._residual_chi_square(navdata, receiver_state)

Chi square test for residuals.

Implemented from Blanch et al [6].

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m and residuals residuals_m.

• receiver_state (gnss_lib_py.navdata.navdata.NavData) – Reciever state that must include the receiver’s state of: x_rx_wls_m, y_rx_wls_m, and z_rx_wls_m.

Returns:

chi_square – Chi square test statistic.

Return type:

float

References

[6]

Blanch, Juan, Todd Walter, and Per Enge. “Fast multiple fault exclusion with a large number of measurements.” Proceedings of the 2015 International Technical Meeting of the Institute of Navigation. 2015.

fde._residual_exclude(navdata, receiver_state)

Detection statistic for Residual-based fault detection.

Implemented from Blanch et al [7].

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m and residuals residuals_m.

• receiver_state (gnss_lib_py.navdata.navdata.NavData) – Reciever state that must include the receiver’s state of: x_rx_wls_m, y_rx_wls_m, and z_rx_wls_m.

Returns:

normalized_residual – Array of the normalized residual for each satellite.

Return type:

np.ndarray

References

[7]

Blanch, Juan, Todd Walter, and Per Enge. “Fast multiple fault exclusion with a large number of measurements.” Proceedings of the 2015 International Technical Meeting of the Institute of Navigation. 2015.

fde.evaluate_fde(navdata, method, fault_truth_row='fault_gt', time_fde=False, verbose=False, **kwargs)

Evaluate FDE methods and compute accuracy scores

The row designated in the fault_truth_row variable must indicate ground truth faults according to the following convention. A value of 1 indicates a fault and 0 indicates no fault. 2 indicates an unknown fault status usually due to lack of necessary columns or information.

Measurements that are returned as “unknown” (fault=2) by the fault detection method are excluded from all accuracy scores.

Accuracy metrics are defined accordingly:

True Positive (TP) : estimated = 1, truth = 1 True Negative (TN) : estimated = 0, truth = 0 Missed Detection (MD), False Negative : estimated = 0, truth = 1 False Alarm (FA), False Positive : estimated = 1, truth = 0

True Positive Rate (TPR) : TP / (TP + MD) True Negative Rate (TNR) : TN / (TN + FA) Missed Detection Rate (MDR) : MD / (MD + TP) False Alarm Rate (FAR) : FA / (FA + TN)

Accuracy : (TP + TN) / (TP + TN + MD + FA) Balanced Accuracy (BA) : (TPR + TNR) / 2 Precision : TP / (TP + FA) Recall : TPR

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m, b_sv_m as well as the time row gps_millis and the corrected pseudorange corr_pr_m. Additionally, the ground truth fault row must exist as indicated by the fault the fault_truth_row variable.

• method (string) – Method for fault detection and exclusion either “residual” for residual-based or “edm” for Euclidean Distance Matrix-based.

• fault_truth_row (string) – Row that indicates the ground truth for the fault status. This row is used to provide results on how well each method performs at fault detection and exclusion.

• time_fde (bool) – Additional debugging info added like timing.

• verbose (bool) – Prints extra debugging print statements if true.

Returns:

• metrics (dict) – Combined metrics that were computed.

• navdata (gnss_lib_py.navdata.navdata.NavData) – Resulting NavData from solve_fde().

fde.fde_edm(navdata, max_faults=None, threshold=1.0, time_fde=False, verbose=False)

Euclidean distance matrix-based fault detection and exclusion.

See [1] for more detailed explanation of algorithm.

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m, b_sv_m as well as the time row gps_millis and the corrected pseudorange corr_pr_m.

• max_faults (int) – Maximum number of faults to detect and/or exclude.

• threshold (float) – Detection threshold.

• time_fde (bool) – If true, will time the fault detection and exclusion steps and return that info.

• verbose (bool) – Prints extra debugging print statements if true.

Returns:

• navdata (gnss_lib_py.navdata.navdata.NavData) – Result includes a new row of fault_edm where a value of 1 indicates a detected fault and 0 indicates that no fault was detected, and 2 indicates an unknown fault status usually due to lack of necessary columns or information.

• timing_info (dict) – If time_fde is true, also returns a dictionary of the compute times in seconds for each iteration.

References

[1]

D. Knowles and G. Gao. “Detection and Exclusion of Multiple Faults using Euclidean Distance Matrices.” ION GNSS+ 2023.

fde.fde_greedy_residual(navdata, max_faults, threshold, time_fde=False, verbose=False)

Residual-based fault detection and exclusion.

Implemented based on paper from Blanch et al [2].

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m, b_sv_m as well as the time row gps_millis and the corrected pseudorange corr_pr_m.

• max_faults (int) – Maximum number of faults to detect and/or exclude.

• threshold (float) – Detection threshold.

• time_fde (bool) – If true, will time the fault detection and exclusion steps and return that info.

• verbose (bool) – Prints extra debugging print statements if true.

Returns:

• navdata (gnss_lib_py.navdata.navdata.NavData) – Result includes a new row of fault_residual where a value of 1 indicates a detected fault and 0 indicates that no fault was detected, and 2 indicates an unknown fault status usually due to lack of necessary columns or information.

• timing_info (dict) – If time_fde is true, also returns a dictionary of the compute times in seconds for each iteration.

References

[2]

Blanch, Juan, Todd Walter, and Per Enge. “Fast multiple fault exclusion with a large number of measurements.” Proceedings of the 2015 International Technical Meeting of the Institute of Navigation. 2015.

fde.solve_fde(navdata, method='residual', remove_outliers=False, max_faults=None, threshold=None, verbose=False, **kwargs)

Detects and optionally removes GNSS measurement faults.

Individual fault detection and exclusion (fde) methods are documented in their individual functions.

Parameters:

• navdata (gnss_lib_py.navdata.navdata.NavData) – NavData of GNSS measurements which must include the satellite positions: x_sv_m, y_sv_m, z_sv_m, b_sv_m as well as the time row gps_millis and the corrected pseudorange corr_pr_m.

• method (string) – Method for fault detection and exclusion either “residual” for residual-based or “edm” for Euclidean Distance Matrix-based.

• remove_outliers (bool) – If True, removes measurements with detected faults (fault status 1) and measurements with unknown fault status (fault status 2) from the returned NavData instance. If false, will detect but not exclude faults or unknowns.

• max_faults (int) – Maximum number of faults to detect and/or exclude.

• threshold (float) – Detection threshold.

• verbose (bool) – If true, prints extra debugging statements.

Returns:

navdata – Result includes a new row of fault_<method> where a value of 1 indicates a detected fault, 0 indicates that no fault was detected, and 2 indicates an unknown fault status which is usually due to lack of necessary columns or information.

Return type:

gnss_lib_py.navdata.navdata.NavData