Set-Valued Shadow Matching using Zonotopes

Sriramya Bhamidipati, Shreyas Kousik and Grace Gao

Abstract: Urban GNSS-based localization is challenging due to non-line-of-sight effects. Robustness to degraded accuracy is crucial for safety-critical applications. A set-valued representation enables robustness by ensuring that a continuum of possible positions obeys safety constraints; such sets can also be used as inputs for robust estimators. Unfortunately, most urban localization methods return point-valued estimates which do not accurately model the position distribution. One strategy with the potential for set-valued estimation is Shadow Matching (SM), where one uses a 3-D map to compute GNSS shadows (where line-of-sight is blocked). However, SM requires a point-valued grid for computational tractability, with accuracy limited by grid resolution. We propose Zonotope Shadow Matching (ZSM) for set-valued 3-D map-aided GNSS localization. ZSM represents buildings and GNSS shadows using constrained zonotopes, a type of convex polytope that can propagate set-valued estimates using fast vector concatenation operations. Starting from a coarse set-valued position, ZSM refines the estimate depending on the receiver being inside or outside each shadow as judged by received carrier-to-noise density. The final output from ZSM is a set of potentially multi-modal receiver positions (represented using one or more disjoint set components). We demonstrated our algorithm’s performance using simulated experiments on a simple 3-D building map and a dense 3-D map of San Francisco. While achieving a comparable point-valued estimation accuracy as that of the conventional SM, we validated that the proposed ZSM computes a set-valued state estimate that is independent of the point-valued discretization.
Published in: Proceedings of the 34th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2021)
September 20 - 24, 2021
Union Station Hotel
St. Louis, Missouri
Pages: 2373 - 2390
Cite this article: Bhamidipati, Sriramya, Kousik, Shreyas, Gao, Grace, "Set-Valued Shadow Matching using Zonotopes," Proceedings of the 34th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2021), St. Louis, Missouri, September 2021, pp. 2373-2390.
https://doi.org/10.33012/2021.17933
Full Paper: ION Members/Non-Members: 1 Download Credit
Sign In