Position, Navigation, and Timing Technologies in the 21st Century. Группа авторов

the problem of positioning a mobile subject in an indoor environment with a known map or landmarks. A more difficult problem that has been studied by the robotics community involves SLAM for robots to navigate in a priori unknown environments [81]. In SLAM, a moving robot explores its environment and uses its sensor information and odometry control inputs to build a “map” of landmarks or features, while also estimating its position in reference to the map [140]. Odometry refers to the control signals given to the driving wheels of the robot. Simple integration of these odometry signals can be considered to be a form of dead reckoning. EKF‐SLAM [81] employs an EKF to represent the large joint state space of robot pose (position and orientation) and all landmarks identified so far. The approach known as FastSLAM uses a Rao‐Blackwellized particle filter (RBPF) [141] where each particle effectively represents a pose and set of independent compact EKFs for each landmark. The conditioning on a pose allows the landmarks to be estimated independently, leading to lower complexity. SLAM implementations for robot positioning always build on sensors and robot odometry that are readily available on robot platforms. The sensors can consist of laser rangers or a single or multiple cameras mounted on the robot platform, and the features are extracted from the raw sensor data. SLAM is considered to be a “hard” problem, in contrast to the two easier special cases: positioning in an environment with known landmarks or building a map of features given the true pose of the robot. In [140], a SLAM approach was proposed for learning building paths/maps automatically by observing data from a mobile subject, which can either be used to localize the subject or provide maps for others. The approach made use of inertial sensors together with principles derived from the FastSLAM framework [141] and dynamic Bayesian networks.

      37.5.6 Hybrid Techniques

      Each of the five classes of techniques discussed in this section so far has drawbacks when used in isolation. Therefore, a recent trend has been to combine various techniques together, to successfully bridge the differences among different types of techniques and overcome the limitations of a single type of localization strategy to improve accuracy. Some of these hybrid techniques can also be used in both indoor and outdoor environments.

      37.5.6.1 GPS‐Based Techniques

      The wireless‐assisted GPS (A‐GPS) was pioneered by SnapTrack (now part of Qualcomm) and can be used for indoor locales. The approach leverages the cellular network together with GPS signals. Many cellular network towers have GPS receivers (or a base station nearby), and those receivers often constantly collect satellite information to detect the same satellites as cellular phones. This data is sent to the cellular phone (when requested), speeding up the time to first fix (TTFF; to acquire the orbit and clock data of relevant GPS satellites), which on a mobile device without assistance can take a long time (minutes) in some cases. Not only does the TTFF get reduced, but the approach can enable localization in indoor environments, where the GPS signals detected by the cellular phone are often very weak, with accuracies ranging from 5–50 m.

      37.5.6.2 Techniques Fusing RF Signals with Dead Reckoning

Several techniques have been proposed that combine inertial sensor readings with data from RF signals for indoor localization. For example, in [142], an indoor localization framework is proposed that combines Wi‐Fi RSSI fingerprint‐based positioning and dead reckoning data, with the help of a Hidden Markov Model (HMM). The dead reckoning consists of an accelerometer‐driven step length estimation and a magnetic‐field‐based heading calculation. While dead reckoning achieves high precision over short time periods, it suffers from error accumulation over longer durations. In contrast, the positioning error with Wi‐Fi fingerprints does not increase with time, but has less accuracy over the short term. Thus, the sensor data fusion of dead reckoning and Wi‐Fi positioning yields a synergistic effect, resulting in higher robustness and precision. The proposed HMM is based on the discrete positions of the Wi‐Fi fingerprints as the hidden states and the RSSI Wi‐Fi measurements as the observable states (a Markov model is called hidden if it contains an underlying stochastic process that is not directly observable, but can be observed through another stochastic process [143]). State transitions depend on movement inputs from dead reckoning. The use of the HMM makes it possible to deal with ambiguities resulting from Wi‐Fi fingerprinting. The HMM approach is also computationally less expensive than the filtering schemes used in other efforts. For instance, particle filters are used in [144, 145] for the integration of Wi‐Fi positioning and dead reckoning, but the particle filters have high computational costs, depending on the number of particles computed. Kalman filters and EKFs are also not well suited for such sensor data fusion, as the assumption of Gaussian distributions is in conflict with the ambiguous outputs of Wi‐Fi fingerprinting algorithms. In [146], another HMM‐based indoor localization approach was proposed that fused Wi‐Fi fingerprints and dead reckoning. In the work, the HMM is augmented to take into account vector (instead of scalar) observations, and prior knowledge about user mobility drawn from personal electronic calendars (e.g. a calendar entry of “meeting in conference room C103A at 1 p.m.” can be useful to estimate the probability associated with positioning of the subject in room C103A). An extension of the Baum–Welch algorithm [147] is used to learn the parameters of the augmented HMM.

The LearnLoc framework [148] fuses Wi‐Fi fingerprinting with dead reckoning to create a low‐cost, infrastructure‐less indoor navigation solution. The framework adapted and enhanced three machine learning techniques that took inputs from inertial sensors and Wi‐Fi fingerprinting to make predictions about indoor location on a map in the presence of noise (e.g. due to incorrect sensor readings). The three supervised learning algorithms used to assist with indoor localization were based on KNN, linear regression (LR), and nonlinear regression with neural networks (NL‐NN). Regression‐based variants of these algorithms were used instead of the more traditional classification‐based variants. This is because a classification technique requires dividing the entire indoor map area into a fine‐grained grid for classification toward accurate localization, which creates a prohibitively large input space that is impractical to process on resource‐constrained mobile devices. For instance, their efforts to implement SurroundSense [149] that proposes an SVM‐based classification technique for indoor localization for real‐time localization on a smartphone were not successful because of the large memory footprint and slow performance (taking close to a minute for each prediction) with the approach. In contrast, regression can allow fast predictions with much lower resource demands, which is what is needed for real‐time indoor localization with mobile devices. Figure 37.8(a) shows a detailed look at the predicted paths by the KNN‐based LearnLoc variant for different Wi‐Fi scan intervals. Not surprisingly, the lowest Wi‐Fi scan interval (1 s) results in the highest accuracy, but also incurs a very high energy consumption overhead because scanning is performed very frequently (as can be seen by the high density of green dots that represent Wi‐Fi scan instances in Figure 37.8(a) for the 1 s interval case). As the Wi‐Fi scan interval increases, the paths traced start deviating notably from the actual path, and the estimation errors increase. A scan interval of 4 s was chosen for all three LearnLoc variants to balance energy consumption on a smartphone with localization accuracy. Figure 37.8(b) summarizes the paths traced by the three LearnLoc variants and the Footpath [150] inertial navigation (Inertial_Nav) technique. It can be observed that the path traced by the Inertial_Nav technique greatly deviates from the actual path due to error accumulation over time. The sequence alignment algorithm in the Inertial_Nav technique aims to overcome this error with periodic recalibration, but is not always successful in doing so. For the LearnLoc variants, the green points in the figure indicate instances where a Wi‐Fi scan was performed. The KNN variant performs best, with an average error of 2.23 m. The accuracy can be improved much further if scan intervals smaller than 4 s are chosen. LearnLoc is one of the very few techniques to explore trade‐offs between energy consumption and accuracy during indoor localization, and also consider realistic resource constraints when devising algorithms meant for execution on resource‐constrained mobile devices. A more recent work, CNNLoc [151], improves upon LearnLoc by using a more sophisticated