Technical Article • September/October 2015
Urban Localization and 3D Mapping Using GNSS ShadowsUrban localization using GNSS is notoriously imprecise due to blockage of satellite signals by tall structures. However, this very phenomenon of blockage can be exploited to derive valuable (but very noisy) location information by “shadow matching” against 3D maps of the environment. This article describes a realtime, lowcost, cloudbased Bayesian localization and tracking solution that combines shadow information and raw GNSS position estimates with probabilistic motion models to substantially improve urban localization. The Bayesian framework also extends to enable synthesis of 3D maps from crowdsourced GNSS data.
Share via: Slashdot Technorati Twitter Facebook It is by now well known that GNSSbased localization in builtup urban environments can be extremely inaccurate. This is a fundamental problem that hardware enhancements cannot solve. A GNSS receiver estimates 3D location and timing from pseudoranges from four or more satellites, assuming that these pseudoranges correspond to direct lineofsight (LOS) paths from each satellite. In urban canyons, however, the signal from a satellite to the receiver suffers from multipath propagation and shadowing. Even if the LOS path is available, the pseudorange estimate may be corrupted due to the presence of alternative paths. Furthermore, the LOS is frequently blocked except for satellites at the highest elevations; so, the satellite is either unavailable, or the strongest path seen by the receiver is a reflection off a building, leading to a pseudorange often significantly larger than that for the LOS path. These errors in pseudoranges lead to large errors in localization (e.g., up to 50 meters in highrise environments such as New York City). Attempts to enhance GNSS localization using signals from other sources, such as cellular and WiFi, have had limited success: it is difficult to use geometric techniques to infer location in a complex propagation environment, and received signal strength measurements are subject to significant fluctuations due to multipath fading and shadowing.
Shadow Matching If we interpret these SNR measurements with the aid of a 3D map of the environment, then we can significantly reduce localization uncertainty by performing shadow matching, as shown in Figure 1 (see inset photo, above right, for all figures). In its simplest form, the concept of shadow matching is summarized as follows:
Shadow Matching with 3D Maps Any GNSScapable Android smartphone or tablet can provide, via the location application programming interface (API), its estimated position with uncertainty, as well as the satellite coordinates and SNRs. Thus, shadow matching can be performed entirely in software without requiring any changes in GNSS receiver hardware or firmware. The article by Wang et alia listed in the Additional Resources section near the end of this article provides an introduction to the basic idea of shadow matching. Wang and his coauthors reported promising results in mitigating GNSS crossstreet errors using relatively straightforward techniques. While shadow matching clearly provides information that is useful for urban localization, naive application of this idea using deterministic algorithms has significant limitations. First, the concepts of “high SNR when not blocked” and “low SNR when blocked” are inherently probabilistic, because SNRs exhibit large fluctuations due to multipath fading. Second, the range of SNRs seen by a device depends on the hardware implementation and physical realization of the GNSS receiver. Third, the potentially large errors in the raw location estimates output by the GNSS receiver are not captured by the typical computations of uncertainty regions based on dilution of precision (DOP), because these implicitly assume that paths to all satellites are LoS. Hence, it is unclear how large an area to perform shadow matching over and how to fuse shadow matching information with GNSS location estimates. Finally, shadow matching is based on having access to accurate 3D maps, which are not readily available in many settings. In the work described here, we address the preceding challenges through an adaptive Bayesian framework for inference, localization, and tracking with two complementary ingredients:
Increased accuracy in urban localization clearly has many compelling applications, including car services, delivery services, navigation and guidance for vehicles (including for emerging automated and semiautomated operation), tourism, and hyperlocalized advertising. We do not discuss any application in detail but instead focus on core technical aspects of our proposed solution in the remainder of this article. In particular, we describe the key concepts behind these algorithms in more detail, discuss cloudbased implementations with lightweight application layer modifications to mobile devices, and provide experimental results demonstrating the scalability and efficacy of these techniques. Initial results based on these ideas, and the underlying technical details, were described in a series of publications last year. (See the articles by A. T. Irish et alia and J. T. Isaacs et alia in Additional Resources.) The experimental results reported here are based on significant enhancements to those techniques.
RealTime Localization and Tracking We consider a discrete time model, typically with samples spaced by one second. The true 3D location at time t is denoted by x_{t}, and the corresponding GNSS location fix is denoted by y_{t}. The satellite SNR measurements are denoted by z_{t,n}, where z_{t,n} is the SNR to satellite n at time t. Modeling GNSS Location Fixes. The measurement model for the GNSS location fix is, in principle, straightforward: y_{t} = x_{t} + e_{t}, where the covariance of the error e_{t} can be estimated using standard DOPstyle computations. However, these standard computations assume that the paths seen by the GNSS receiver are LOS, whereas many of the dominant paths in urban environments are actually strong reflections, with the LOS path blocked. Thus, in order to obtain satisfactory localization performance, we need to modify the model for {e_{t}}, resulting in a nonGaussian statistical model. Modeling Satellite SNR Measurements. We represent the 3D map m using an occupancy grid: space is divided into binaryvalued “voxels” or “cells,” with m_{i} = 1 if the ith cell is occupied, and m_{i} = 0 if the ith cell is unoccupied. If the ray from a hypothesized location to a satellite crosses only unoccupied cells, it is classified as LOS. If a ray passes through at least one occupied cell), it is classified as NLOS (or shadowed). Figure 2 illustrates this approach. On the left, we illustrate ray tracing: blue/red lines represent LOS/NLOS signal paths to satellites, light/dark grid cells approximate empty/occupied space. On the right, we show typical SNR distributions that have been found to yield good performance: Rician for LOS, and lognormal (with smaller mean and higher spread) for NLOS. Note that we have made a drastic simplification in our model for NLOS rays, in that the distribution does not depend on the number of occupied voxels the ray crosses. Although it might be possible to improve performance using a more detailed model, our simplification leads to a significant reduction in computational complexity, while yielding excellent localization performance. Additional improvements can be obtained by introducing dependence of the LOS/NLOS SNR distributions on satellite elevation. Tracking framework. We use a standard linear state space model for pedestrian motion, with the state consisting of position and velocity. However, because the measurement model is nonlinear and nonGaussian, a standard Kalman filter cannot be used. Simple extensions such as the extended Kalman filter also do not work, as the posterior distribution of the state is often multimodal. We therefore use a particle filter. Roughly speaking, it operates as follows: At each time t, the posterior distribution of the state is approximated by a discrete probability mass function putting weights at a set of hypothesized state values, or particles. These particles are propagated probabilistically to obtain a new set of particles and weights at time t + 1, based on the dynamics of the motion model, and the new set of measurements. The particle filter has by now become a standard tool, but we have needed to make a number of modifications in order to account for modeling uncertainties. Figure 3 shows example pedestrian results for Bush Street in downtown San Francisco. Figure 3(a) shows the mean trails and 68 percent confidence circles for the GPS reported fix (red) and the particlefiltered estimate (blue), with the ground truth path in yellow. Note that GPS makes crossstreet errors which are corrected by our algorithm. Figure 3(b) shows the SNR likelihood surface at the beginning of the trail: GPS starts out with a crossstreet error, which our algorithm is able to correct because the SNR likelihood has a strong peak on the correct side of the street. The large greyishgreen ellipse is the 3σ uncertainty estimated by GPS around its (incorrect) estimate, while the smaller black ellipse is the 3σ uncertainty estimated around the location estimate provided by the particle filter. Finally, Figure 3(c) shows the composite SNR/GPS likelihood surface, which exhibits a peak at the correct location. We also show the satellite rays colored likely LOS (green) to likely NLOS (red) according to our SNR model; from the image, we can see that these do correspond to unblocked and blocked rays, respectively. Vehicular applications require more sophisticated motion models, and knowledge of the road network can also be exploited. However, the essential ingredients, in terms of the measurement model and the particle filter, are the same. Figure 4 shows example vehicular results with the 68 percent probability tunnels for both the GPS reported estimate (red) and our filtered estimate (blue), along with a road centerline clamping of the filtered estimate (green).
SLAM for CrowdSourced 3D Maps Our approach for Bayesian estimation of the map is to use a factor graph representation of the measurements and the quantities to be inferred, which allows us to employ loopy belief propagation to approximately compute the map marginal posteriors. While a detailed exposition of factor graphs is beyond the scope of this article, we provide intuition into their applicability in our context. Figure 5 illustrates the construction of the factor graph based on measurements corresponding to a single GNSS receiver over two consecutive time periods. The variables that we wish to perform inference on, denoted by circles, are the binaryvalued map cell occupancies {m_{i}} (which is our primary interest in shadowbased SLAM) and the true locations {x_{t}} as a function of time t (which are, for the mapping task, nuisance variables to be averaged out). The factors represent the statistical information about the variables provided by the measurements. In Figure 5, the factor g_{t} represents p(y_{t}  x_{t}), the likelihood function corresponding to the GPS fix at time t, and the factor f_{t,n} represents p(z_{t,n}  m,x_{t}), the likelihood function corresponding to the SNR to the nth satellite at time t. Belief propagation can now be implemented by the standard sumproduct algorithm described in the article by F. Kschischang et alia, passing messages back and forth between nodes. A message is simply a function whose domain is the set of values taken by the variable. Thus, for a binaryvalued map cell m_{i}, a message is a binary vector. For a position variable x_{t}, we simply quantize its possible set of values to a discrete set (e.g., with K possible values), and a message is then a Kdimensional vector corresponding to the values of the function evaluated at these K points. A message along an edge from a variable node to a factor node is simply a product of messages coming along all of the other edges. A message from a factor node f to a variable node v is more complicated: it involves products of messages coming into that factor node, but also involves summing over (marginalizing out) all variables other than v. We refer the reader to the article by A. T. Irish et alia (2014a) for details, but it is worth mentioning that our simplified SNR model (in which the NLOS model for SNR is independent of the number of occupied map cells intersected by the ray) is key to tractable computation of messages from SNR factor nodes to position and map variable nodes. The preceding procedure has been successfully used to construct 3D maps of the campus of the University of California, Santa Barbara (UCSB), as well as of downtown Santa Barbara. Here we will present sample results for the latter based on about 25 hours of input data from four Android devices. Figure 6(a) shows an aerial view, with GNSS traces in red and mapped region outlined in yellow. Figure 6(b) shows the cell occupancy estimates for 2D slices at multiple heights. We employed a “warm start” with prior information based on 2D OpenStreetMap data employed to initialize the map for the first couple of slices. Note, however, that, given enough data, 3D maps can be generated without any prior information. (This was the case for the 3D maps generated for UCSB campus; see A. T. Irish et alia (2014a) for details).
Architecture and Implementation The preceding architecture naturally scales to include additional sources of information when available — for example, inertial navigation, WiFi, and cellular. Such information can be sent from mobile device to cloud, and can be incorporated into the Bayesian computations done in the cloud. Such extensions are also under development.
Conclusions Several academic research groups worldwide have demonstrated the promise of shadow matching over the past few years. However, a key innovation in the approach described here is that, in contrast to the ad hoc algorithms used previously, it is based on a Bayesian inference framework that systematically accounts for significant modeling uncertainties and nonlinearities, and seamlessly extends to incorporate additional sources of information as they become available. The approach proposed here has been demonstrated to provide significant improvements in localization over raw GNSS estimates in challenging highrise environments such as downtown San Francisco, with latencies of the order of 100 milliseconds. With current (and ever decreasing) cloud computing costs and the inherent parallelizability of the core computation bottlenecks (such as ray tracing and particle sampling techniques), providing such a service is estimated to cost less than one U.S. penny per hour per device. On the mapping side, shadowbased SLAM provides a method for creating 3D maps from scratch and an effective means of refining them from a warm start. The former is probably most important for military applications. For most urban environments worldwide, 2D maps together with public municipal data on building heights can be used to build a coarse 3D map, which can subsequently be refined by shadowbased SLAM. Even in areas where accurate 3D building models are available, shadowbased SLAM provides the ability to continuously monitor and capture changes in the environment (e.g., new construction, demolition). It also captures features such as trees and lampposts. As vehicles migrate towards automated operation, a finegrained mapping of features in the environment become increasingly important for timely decision making in navigation and path planning. While the cloudcentric architecture described previously in the “Architecture and Implementation” section enables immediate deployment of shadowmatching technology on mobile devices via a lightweight SDK, it is also of great interest to explore means of efficiently migrating some of the algorithmic functionalities to a mobile device. Accomplishing such a migration would reduce reliance on network connectivity by exploiting the computational resources available on today’s smart phones. Selfcontained operation with limited or no network connectivity is also an important feature for incorporating these advances in urban localization into vehicular navigation systems.
Additional Resources Copyright © 2017 Gibbons Media & Research LLC, all rights reserved. 
