Session B2a: Advancements in Navigation Algorithms

Set-Based Position Ambiguity Reduction Method for Zonotope Shadow Matching in Urban Areas Using Estimated Multipath Errors
Sanghyun Kim, Jiwon Seo, Yonsei University
Location: Beacon B

The Global Navigation Satellite System (GNSS) is widely utilized across various applications such as autonomous driving and intelligent transportation systems to provide positioning, navigation, and timing (PNT) information. However, the performance of GNSS in urban areas is often unreliable compared to open sky environments. This is because GNSS signals are blocked, reflected, and diffracted by tall buildings, leading to measurement errors. As a result, GNSS positioning errors exceeding 100 meters can occur in urban areas. Various methods such as measurement weighting and consistency checking have been proposed to address this problem. Among them, 3D mapping-aided (3DMA) GNSS has gained attention recently, especially with the increased availability of high-precision 3D city models.
One of the prominent methods within 3DMA GNSS is shadow matching. Shadow matching starts by placing a grid onto the specified area, with each grid point representing a potential receiver location. Then, the visibility of satellites is calculated for each grid point, comparing it with measurements such as carrier-to-noise-density ratio (C/N0) to derive a score. Subsequently, the grid point with the highest score is determined as the receiver's location. While shadow matching has demonstrated its ability to effectively enhance urban GNSS positioning performance, the discretized manner of the technique has presented limitations. Since positioning accuracy is influenced by the resolution of the grid, increasing the grid resolution can potentially improve accuracy but also leads to a trade-off with increased computational load. To address the trade-off issue stemming from the discretized manner of shadow matching, a novel set-based shadow matching, known as zonotope shadow matching (ZSM), has recently been proposed.
ZSM utilizes zonotopes to represent shadow matching as set-based objects. Zonotopes are convex and symmetrical polytopes commonly used in various control algorithms for set representation, offering the advantage of enabling rapid vector concatenation operations. Furthermore, zonotopes can be extended to constrained zonotopes without requiring symmetry. ZSM represents buildings in the 3D city model using constrained zonotopes and calculates GNSS shadows, which are areas where line-of-sight (LOS) signals are blocked by buildings. Afterward, the ZSM algorithm initiates with a coarse set-valued receiver position, progressively refining it through set operations utilizing GNSS shadows, which are represented as constrained zonotopes. Finally, ZSM estimates a set-valued receiver position without the discretization approach of conventional shadow matching.
However, ZSM still faces several challenges. One of these is the presence of multi-modal position ambiguity, which occurs not only in ZSM but also in conventional shadow matching. It represents a phenomenon where multiple receiver positions are estimated, leading to ambiguity in determining the correct receiver position. For instance, the set-valued receiver position estimated using ZSM arises as multiple disjoint sets, each referred to as a mode, rather than a single connected set. Selecting the correct mode is crucial for ensuring receiver position accuracy. To reduce multi-modal position ambiguity in ZSM, a filtering architecture utilizing GNSS pseudorange measurements, known as the satellite-pseudorange consistency (SPC) filter, has been proposed. This method involves constructing an SPC plane for each satellite to map the mode distribution in the 2D position domain to the range offset domain. As the output of the SPC filter, the probability of each mode being the correct one is obtained, and the mode with the highest probability is selected.
According to a previous study, a mode selection accuracy of 78% was achieved when using the SPC filter with signals received in a single epoch. In the literature, iterative filtering was applied to improve the performance of the SPC filter by using multiple pseudorange measurements collected at a single location over an extended period. Additionally, a trained LOS classifier was developed to down-weight NLOS satellites, increasing the mode selection accuracy to 100%. However, in practice, obtaining multiple pseudorange measurements at a single point in dynamic environments is challenging, and the performance of the LOS classifier can vary significantly depending on the surrounding environments. Therefore, algorithms are needed to accurately select modes, even when only pseudorange measurements from a single epoch are available and no LOS classifier is present.
In this study, we propose a set-based position ambiguity reduction method for zonotope shadow matching in urban areas using estimated multipath errors. Unlike the existing method that creates SPC planes using pseudorange measurements contaminated by multipath errors, we aim to estimate and correct these errors in pseudorange measurements from NLOS satellites to generate more accurate SPC planes. By leveraging the distribution of modes obtained from ZSM, we can predict the approximate propagation paths of satellite signals, allowing us to estimate the multipath errors. Since the receiver's location is represented by multiple set-based modes rather than a single coordinate, we assume the receiver is located at the centroid of each mode and predict the propagation path accordingly.
As a result, while the previous study creates a single SPC filter, we generate multiple SPC filters (one for each mode) using pseudorange measurements that compensate for multipath errors. To determine the most reliable filter result among several, we check the consistency between the mode selected by each SPC filter and the mode used as its basis. Specifically, if the SPC filter created using the multipath error estimated from the m-th mode selects the m-th mode, the result is considered trustworthy. If two or more such occurrences are observed, the mode with the highest probability is chosen as the final mode.
We validated the performance of the proposed method using GNSS signals collected in urban areas surrounded by tall buildings. The results showed that, while the existing method demonstrated a mode selection accuracy of 86%, our method achieved 91% accuracy, confirming its improved performance. Furthermore, we analyzed the positioning accuracy of the ZSM algorithm based on the mode selection results. Ideally, when the mode containing the true receiver position is selected for all epochs, an RMS error of 14.02 m could be obtained. However, with the existing method, the RMS error increases to 17.70 m due to occasionally selecting a mode that does not include the true receiver position. In contrast, with the improved mode selection accuracy of our method, the RMS error decreases to 16.56 m, reflecting a 6.4% improvement in positioning performance.