detected and counted, and these are then used as the inter‐fingerprint distance measurements. Feeding the inter‐fingerprint distances to a multidimensional scaling (MDS) algorithm results in a high‐dimension space called the fingerprint space, where the mutual distances between points (fingerprints) are preserved. The fingerprint space is then mapped to the physical floor plan to associate fingerprints with their corresponding physical locations in the indoor environment. The mapping is achieved by exploring the spatial similarity between the fingerprint space and a transformed floor plan, called the stress‐free floor plan. The stress‐free floor plan is a space that transforms a normal floor plan into a high‐dimension space using MDS, in such a way that the geometrical distances between the points in the new space reflect walking distances instead of straight distances. The rationale behind such transformation is that, due to the presence of obstacles (e.g. walls), the walking distance between two locations is not necessarily equal to the geographical distance between them. LiFS was shown to achieve good performance, with the 95th percentile mapping error being lower than 4 m and an average error of 1.33 m. The radio map generated using LiFS can be used as a starting point for various fingerprint‐based localization techniques.
Several other efforts have addressed map matching. In [136], a framework was proposed to combine a backtracking particle filter (BPF) with different levels of building plan detail to improve the indoor localization performance via dead reckoning. Particle filters are able to take into account building plan information during indoor localization with a technique called map filtering [137]. With map filtering, new particles are not allowed to occupy impossible positions given the map constraints. For example, particles are not allowed to cross directly through walls. Particles that transition through such obstacles are deleted from the set of particles or downweighted, as shown in Figure 37.7. BPF further exploits particle trajectory histories to improve upon simple particle filters, by recalculating previous state estimates after invalid particles are detected. In order to enable backtracking, each particle has to remember its state history or trajectory. Mean location estimation errors when using dead reckoning, dead reckoning with particle filters, and dead reckoning with BPF were shown to be 7.7, 3.1, and 2.6 m, respectively [136].
Figure 37.7 Particle transition near obstacles: if a particle tries to move to an impossible location, for example, across walls defined in the map, it will be killed off [136].
Source: Reproduced with permission of IEEE.
Predicting the trajectory of a mobile subject can also help reduce ambiguity when using fingerprinting for localization [138]. As an example, displacement and direction information obtained with dead reckoning impose relative geometrical constraints between consecutive location queries along a trajectory. These constraints transform the fingerprint matching from essentially being a point matching process to one that now involves line fitting by embedding the entire trajectory into the radio map. ACMI [139] employs FM broadcast signal fingerprinting for localization, and uses trajectory predictions for localization accuracy improvement. Experimental results have demonstrated that localization errors decreased from 10–18 m to 6 m, along with an increase in the room identification accuracy from 59% to 89%, when trajectory matching was used.
Certain indoor landmarks and contexts also possess distinctive sensor signatures. For example, accelerometer readings on an elevator exhibit a sharp surge and drop at the start and the stop of the elevator. An investigation of such unique acceleration patterns of stairs, elevators, escalators, and so on, was performed in [111], and it was concluded that if the locations of these structures were known previously, they could serve as landmarks to improve indoor localization accuracy (e.g. to overcome dead reckoning drifts).
The techniques discussed so far address 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
