Position, Navigation, and Timing Technologies in the 21st Century

Today’s smartphones include IMUs, and the fact that they are carried by people almost everywhere makes INS‐based indoor localization particularly attractive. However, one important challenge is to account for the manner in which the smartphone is carried: in front pockets, back pockets, side pockets, shirt pockets, backpacks, handbags, on belt clips, or in the hand. A few efforts on activity recognition have explored estimating phone placements [125], which may help improve the performance of dead‐reckoning‐based localization systems. However, studies have shown that even if a smartphone is located in a single location (e.g. trouser pocket), notable errors are accrued (about 14.4% [131]) when estimating distance traveled, compared to foot‐mounted ground truth sensors.

Accurate trajectory estimation is a major goal of most indoor localization and navigation systems. A pedestrian trajectory consists of a sequence of step vectors. Techniques that utilize an electronic map to determine the position of a mobile person or object along a trajectory in the context of locations provided on the map are referred to as map matching techniques. The idea of applying electronic maps to adjust a mobile subject’s positions has been used in outdoor localization schemes [132]. Similarly, integrating the geometric constraints of floor plans in indoor environments can help improve indoor localization accuracy (e.g. when used in tandem with dead reckoning or Wi‐Fi fingerprinting). In general, the overall geometric shape of a mobile subject’s trajectory should be similar to that of the floor plan, and any deviations can point toward an error in a localization scheme. Various geometric abstraction models have been proposed for map matching, for example, link‐node models [133] and stress‐free floor plans [108]. Particle filtering techniques can additionally be used to exclude unlikely positions for mobile subjects, such as obstacles and walls [134, 135].

LiFS [110] is an example of a framework for matching sensor/signal readings to a physical floor plan. First, continuous measurement of acceleration readings and RSS readings is performed with the aid of smartphone users during their routine work and occupancy of buildings. Footsteps are then 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.