@article {Bhamidipatinavi.547, author = {Sriramya Bhamidipati and Shreyas Kousik, and Grace Gao}, title = {Set-Valued Shadow Matching Using Zonotopes for 3D-Map-Aided GNSS Localization}, volume = {69}, number = {4}, elocation-id = {navi.547}, year = {2022}, doi = {10.33012/navi.547}, publisher = {Institute of Navigation}, abstract = {Unlike many urban localization methods that return point-valued estimates, a set-valued representation enables robustness by ensuring that a continuum of possible positions obeys safety constraints. One strategy with the potential for set-valued estimation is GNSS-based shadow matching (SM) in which one uses a three-dimensional (3D) 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 3D-map-aided GNSS localization. ZSM represents buildings and GNSS shadows using constrained zonotopes, a convex polytope representation that enables propagating 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. We demonstrate our algorithm{\textquoteright}s performance using simulated experiments on a simple 3D example map and on a dense 3D map of San Francisco.}, issn = {0028-1522}, URL = {https://navi.ion.org/content/69/4/navi.547}, eprint = {https://navi.ion.org/content/69/4/navi.547.full.pdf}, journal = {NAVIGATION: Journal of the Institute of Navigation} }