Computer Laboratory

Ramsey Faragher

Simultaneous Localisation and Mapping on a Smartphone - Part II

Following the previous development work on a particle-filter based Smartphone SLAM scheme for indoor positioning, I turned my attention to reducing the computational load. My main aim was to develop a navigation framework that selected a tracking filter from a set of options to satisfy the current key demand, be it highest accuracy, battery life, integrity, etc. For example if battery life is key, then sensible choices can be made based on the time since last GNSS fix. If a user moves into a building for a few moments, perhaps to collect mail, buy a sandwich, etc, then a tracking estimate based on dead reckoning alone would easily suffice to track this short GNSS-denied journey. It would certainly be a waste of computational cycles, and so battery charge, to immediately initiate a particle filter tracking hundreds of hypotheses. What is actually required therefore is a scheme to monitor aspects such as the current level of confidence of various system parameters during both GNSS availability and GNSS denial. While key parameter such as step length are well modelled, and the current position uncertainty is low, then a dead reckoning scheme is expected to provide low drift performance. The current position estimate uncertainty can be monitored and system can move to a more complicated tracking scheme such as a SLAM scheme once it is clear that the user is undergoing extended operations under GNSS denial. The historical tracks for each hypothesis back to the moment of GNSS denial can be generated when the more computationally-hungry filter is initialised. Given very extended operations in this environment, and so multiple SLAM loops closures, the framework could then move to a scheme fusing dead reckoning with the fingerprint map built up during the earlier SLAM stages. In effect therefore an expected battery draw profile for extended operations in a new building would be low at first (dead reckoning shortly after GNSS loss), then high (SLAM), than back to low again (dead reckoning fused with the fingerprint maps generated by SLAM)

This concept was discussed and demonstrated in "SmartSLAM - an Efficient Smartphone Indoor Positioning System Exploiting Machine Learning and Opportunistic Sensing", which was awarded a best presentation accolade at ION GNSS+ 2013.

The paper describes two new filtering schemes. The first is a new way of fusing PDR and fingerprint data using a Kalman Filter framework. Raw fingerprint data are sparse and discrete, yet the Kalman Filter requires a differentiable, continuous mathematical model of the measurements being made. To account for this Gaussian Processes Regression was used to generate continuous signal strength maps for each signal source, with the fingerprint data used for training. These continuous maps can then be used to provide the measurement prediction step in the Kalman Filter, and the maps can be differentiated numerically in the spatial dimensions to provide "Jacobian maps" to populate the Jacobian matrix as needed. This new scheme is called the Fingerprint Extended Kalman Filter, or FEKF. A movie comparing the PDR, FEKF and particle filtering schemes is given below. In this movie a set of prior signal fingerprint maps are available to the FEKF and particle filter schemes to provide position constraints, but the computation load of the FEKF scheme is much lower than the particle filter since FEKF is elegantly tracking and updating one hypothesis rather than hundreds.

The second new filtering scheme is an extension of this FEKF concept to permit SLAM-like auto corrections. However in order to provide low computational load, a SLAM approximation is developed, rather than a full SLAM scheme. Full details are available in the paper. A movie comparing the PDR, FEKF smoother (SLAM approximation) and DPSLAM schemes is given below.

Contact Information

Ramsey Faragher
Senior Research Associate
University of Cambridge
Computer Laboratory
15 JJ Thomson Avenue
Cambridge CB3 0FD
United Kingdom

Phone: +44 1223 763767
Email: rmf25 [at]