Next Article in Journal
Analysis of a DC-DC Flyback Converter Variant for Thermoelectric Generators with Partial Energy Processing
Next Article in Special Issue
Using Bluetooth Low Energy Technology to Perform ToF-Based Positioning
Previous Article in Journal
Unbalanced Two-Way Filtering Power Splitter for Wireless Communication Systems
Previous Article in Special Issue
Many Ways Lead to the Goal—Possibilities of Autonomous and Infrastructure-Based Indoor Positioning
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Evolutionary Optimization Strategy for Indoor Position Estimation Using Smartphones

Geodetic Institute and Chair for Computing in Civil Engineering & Geo Information Systems, RWTH Aachen University, 52074 Aachen, Germany
*
Authors to whom correspondence should be addressed.
Submission received: 31 January 2021 / Revised: 24 February 2021 / Accepted: 1 March 2021 / Published: 6 March 2021
(This article belongs to the Special Issue Indoor Positioning Techniques)

Abstract

:
Due to their distinctive presence in everyday life and the variety of available built-in sensors, smartphones have become the focus of recent indoor localization research. Hence, this paper describes a novel smartphone-based sensor fusion algorithm. It combines the relative inertial measurement unit (IMU) based movements of the pedestrian dead reckoning with the absolute fingerprinting-based position estimations of Wireless Local Area Network (WLAN), Bluetooth (Bluetooth Low Energy—BLE), and magnetic field anomalies as well as a building model in real time. Thus, a step-based position estimation without knowledge of any start position was achieved. For this, a grid-based particle filter and a Bayesian filter approach were combined. Furthermore, various optimization methods were compared to weigh the different information sources within the sensor fusion algorithm, thus achieving high position accuracy. Although a particle filter was used, no particles move due to a novel grid-based particle interpretation. Here, the particles’ probability values change with every new information source and every stepwise iteration via a probability-map-based approach. By adjusting the weights of the individual measurement methods compared to a knowledge-based reference, the mean and the maximum position error were reduced by 31%, the RMSE by 34%, and the 95-percentile positioning errors by 52%.

1. Introduction

The automatic determination of a location in an earth-related reference system is essential in many areas of life and economy. This is the reason why global navigation satellite systems (GNSS), such as GPS, GLONASS, or Galileo, have become of high economic importance. The range of applications for automatic position determination extends from ascertaining the location of a person in the leisure sector (e.g., for hiking or sailing) up to locating people (e.g., for rescue and emergency forces) and tracking objects (e.g., goods and merchandise) to determine the position and orientation of air, water, and land vehicles for navigation and autonomous navigation purposes.
Whereas GNSS is typically used outdoors, its application is usually limited due to shading or attenuation as well as other propagation effects (fading, multipath) of the electromagnetic signals within buildings, underground, or in built-up areas (“indoor”). However, most of the aforementioned applications would also benefit from automatic indoor positioning [1,2]. As a result, numerous local positioning systems have been developed in the past to enable the automatic localization of people or objects in “GNSS-free” space [3,4]. In contrast to outdoor areas, however, there is no positioning technology analogous to GNSS. Instead, different technologies are used depending on the specific application.
For pedestrian indoor localization, smartphones have increasingly gained attention due to their distinctive presence in everyday life and the variety of available built-in sensors and communication technologies.
Therefore, this work is based on the fusion of smartphone sensor data like accelerometer, gyroscope, Wireless Local Area Network (WLAN) and Bluetooth (Bluetooth Low Energy—BLE) signals, and magnetic field anomalies with the non-sensory digital model of the building. Thus, no complex nor expansive infrastructure is needed.
To fuse the information sources, a Bayesian filter approach is used (Section 3). With this filter, the probability distributions of various location estimations are superimposed to get the current position and to consider the respective sensor inaccuracies.
This work’s novelty is the combined use of a grid-based representation of the particle filter (PF) and the optimization scheme Genetic Algorithm (GA) for weighing multiple information sources. Furthermore, the grid-based PF is realized on a multiple hypothesis testing approach. In this work, the particles of the PF are not moving freely in contrast to a classic PF [5]. Instead, they are represented by localized grid cells of the building model and only the values they associated with can change (Section 4).
Thus, this grid represents a position matrix that changes its values regarding to the relative information of the pedestrian dead reckoning (PDR), the absolute information of WLAN and BLE fingerprinting, and the magnetic field anomaly map. For this, the walls’ structure and the fingerprinting maps are discretized to a grid. Also, the step sizes are cropped to fit into this grid. Due to reasoning using the building model, particle movements through walls or false positions inside walls are attenuated. Consequently, some building positions are more likely to represent the actual location than others for every recognized step. As a result, this sequence of probable and unlikely positions will increase some grid cells’ value. Finally, the high gird cell values will converge, and the cell with the highest value represents the current position.
The convergence speed and the overall accuracy of the estimated position to represent the real position can be influenced by weighting the probability distributions. Instead of a knowledge-based approach, this work investigates the GA and compares it with other optimization strategies (Section 5) to achieve optimal weights and, thereby, a higher position accuracy.
The experimental method and data collection are discussed in Section 6, whereas in Section 7, the optimization results for the grid-based PF are shown. In summary (Section 8), by adjusting the different uncertainty sensor profiles, the accuracy was improved by about 34% compared to the equally weighted sensor probability distributions.

2. State of the Art and Related Work

Generally, local positioning systems for automatic indoor position determination of people can be implemented based on various technologies. These are often divided into infrastructure-based, infrastructure-less (inertial measurement units—IMU; camera-based [6] or passive magnetic fields [7]), and hybrid systems, which fuses multi-source information [8,9]. Especially for pedestrian localization, smart devices such as smartphones are predominantly used because of their mass-market availability and sensor-richness.
Infrastructure-based positioning systems (e.g., radio systems such as WLAN [10,11,12,13], radio-frequency identification—RFID [14,15,16], or Bluetooth [17,18]) needs additional hardware that has to be set up, calibrated, and maintained. Therefore, various techniques are applied, which can estimate the distance between transmitter and receiver via the signal propagation characteristics. Thus, if enough transmitters are available, the actual position can be estimated via lateration. Otherwise, the position can also be determined via fingerprinting. Therefore, in the offline phase, the received signal strength at various building positions has to be measured. Thereafter, the position in the online phase can be estimated based on the received signal strength in comparison to the offline fingerprinting database. Numerous works on BLE and WLAN-based fingerprinting are presented in the extensive meta-reviews of [19,20].
The infrastructure-less localization systems are often based on a dead reckoning approach via IMU, which are now already integrated into many devices. The IMU can provide heading and speed information via self-contained sensors like accelerometers, gyroscopes, and magnetometers for relative continuous localization [21,22]. Since IMU are embedded as Micro-Electro-Mechanical Systems (MEMS) in smartphones, they can be directly used for pedestrian dead reckoning. However, the sole use of MEMS-IMU for pose estimation is only feasible for a short period of time due to its drift behavior [23,24]. Alternatively, high-performance IMU sensors with high weight and power consumption could achieve high-quality measurements, but these are unsuitable for pedestrian localization.
Besides infrastructure-based and infrastructure-less systems, hybrid systems are becoming a standard for pedestrian localization with smartphones. In these systems, multi-source information like IMU data and additional infrastructure-based systems (e.g., WLAN fingerprinting, BLE beacons, building model) are fused [25].
In [26], the hybrid multi-source information fusion of a small low-cost inertial navigation system (INS) with GPS, barometer, and a camera is described. In [27,28,29], the data of low-cost smartphone sensors (IMU, magnetometer, barometer) and approximate estimation methods (fingerprinting) based on communication technologies (WLAN, BLE) are combined with digital building models for pedestrian localization. In [30], fuzzy logic was used with an abstracted building model with 90 degree turns and BLE signals as landmarks. Furthermore, in ref. [31] the authors used fuzzy logic to consider the noisy and uncertain WLAN or BLE data. Moreover, robust multi-source information fusion positioning technology is shown in [32,33], while [34] identifies hybrid systems as most suited to mass-market applications and [35,36] explicitly focuses on IPS solutions applicable to smartphones. In the most recent work of [37], a survey of the different positioning techniques for collaborative localization is given.
While the localization in the outdoor areas is solved, there are numerous problems to solve in indoor areas. Therefore, to categorize the performance and compare different localization algorithms, the authors of [38] identified six key challenges of positioning. These challenges are accurate and continuous localization, scaling to multi-story buildings, signal bias adaptation at scale, upscaling to large numbers of measurements, identifying varying walking profiles, and observing signal delays. They also evaluated their localization algorithm based on these challenges for a shopping mall, including three multi-story buildings and a large open underground passageway.
To solve the problem of accurate and continuous localization, multi-source information fusion positioning from different sensors often uses Recursive Bayesian Estimation methods. Their basic idea is to estimate the current state of the system, taking into account all previous state measurements up to this point in time and represent the state estimation by a probability density function (PDF) [39,40]. Well-known forms of Recursive Bayesian Estimation algorithms are the Kalman filter (KF) [41] with its variants (Iterative Kalman Filter (IKF), Adaptive Kalman Filter (AKF)) and extensions (e.g., Extended Kalman Filter (EKF), Unscented Kalman Filter (UKF)) [42,43,44,45,46], or Sequential Monte-Carlo (SMC) methods [47].
The KF predicts the actual state based on the previous system state and linear functions, but the state transitions are often nonlinear. Therefore, the state transitions are approximated in the EKF with the tangent of a nonlinear function and Gaussian noise [39]. In contrast, the UKF uses a weighted, statistical, linear regression process for linearization. Thus, instead of the tangent, so-called sigma points are extracted from the input distribution and transformed using a nonlinear function.
The sigma points are based on the mean value and are symmetrically oriented using the covariance [46]. However, the KF and its variants are based on a Gaussian probability distribution. Alternatively, SMC filters, also known as PF [48], can be applied for state estimation since they can approximate any (non-Gaussian) distribution as well as linear and non-linear system models. The PF also often uses Gaussian functions to reflect the sensor uncertainties [49,50]. In particular, PF, in the context of (robot) localization also referred to as Monte Carlo Localization (MCL), has proven as a suitable method for multi-source information fusion for pedestrian localization, e.g., [8,12]. In [51,52,53,54], the digital building model was integrated into a PF to evaluate the particles against the building structure, while [55,56,57] used an abstracted discretized grid-based building representation.
Because of the digital building model’s nonlinearities in combination with nonlinear pedestrian moving patterns and stochastically intricate representations of the measurement signals of the hybrid positioning systems, this work weights its information sources explicitly to improve the localization accuracy. Therefore, it aims to reproduce a system’s PDF by weighted particles and reflect the sensor uncertainties with Gaussian functions, while a detailed grid-based building representation and a novel particle interpretation as localized grid cells are investigated. Thereby, the number of particles was drastically increased and the performance was enhanced via fast and efficient 2D matrix multiplications.
The input information sources (position data, sensor observations, building models) are weighted using optimization methods to determine the actual position with high accuracy. Therefore, classical optimization methods (e.g., hill climbing or gradient descend algorithms like the Nelder–Mead method) require good initial guesses for the global extreme estimation [58]. Otherwise, a convergence against local extrema may occur and the algorithm fails to estimate the global optimum. Classical optimization schemes like Gauss–Newton [59] or Levenberg–Marquart [60] show the problem that they need continuously differentiable functions for optimization, which are not available due to the complexity of the environment described in this work.
Thus, to avoid local minima in the search process, global optimization strategies can be used. One common strategy known for its robustness end flexibility is the GA [61,62,63,64,65]. GA can be assigned to heuristic optimization methods. These algorithms are used specifically if the functions that have to be optimized are nonlinear or the calculations are computationally intensive. This could be the case if the amount of data is either complex or extensive. Moreover, there are no restrictive requirements for the target function, which does not need to be differentiable or continuous. Furthermore, the GA’s basic functionality is easy to understand, the algorithm can be applied even with little knowledge of the problem structure, and functions with numerous dependent and independent parameters can be optimized [66].

3. Basic Localization Strategy

As described in Section 2, PF are often applied for pedestrian navigation in buildings. In a PF implementation, the system states are discretized by numerous independent weighted particles that approximate the PDF at each point in time. In the case of position estimation, the particles represent possible concrete positions in space.
Applying the particle filtering process requires the following four consecutive steps [39,40,67]:
(1)
Initialization;
(2)
Prediction Sampling;
(3)
Importance Sampling/Correction;
(4)
Normalization and Resampling.
After the initialization, the recursive update steps (2) to (4) are performed continuously for each filter epoch. As soon as the particles cluster around one point (convergence), they indicate the current position.
The present work has been built on the approach presented in [68,69], whose PF-based algorithm is briefly described in the following. In the initialization, numerous (500–2000) independent particles are randomly distributed in the walkable areas of a building and outside the walls. This step is followed by prediction sampling, which predicts the actual location based on PDR. Therefore, the observations of the built-in accelerometer, gyroscope, and magnetometer smartphone sensors are used. After that, the importance sampling weights each particle concerning the difference between the predicted and observed position in step three.
Finally, the weights are normalized in the resampling step and particles with low weights are replaced with new and randomly distributed ones. Thus, the PDF p ( x k | Z k ) is estimated with the observations from step 0 to k , the current posteriori probability x k i , the individual weights w k i , and the Dirac delta function δ :
p ( x k | Z k ) i = 1 N w k i · δ ( x k x k i ) .
Here, the weighting is defined as a two-dimensional standard normal distribution with ( x s i , y s i ) as the predicted and ( x k , y k ) as the observed position as follows:
w k i = 1 2 π σ 2 exp ( ( x s i x k ) 2 + ( y s i y k ) 2   2 σ 2 ) .
If a particle moves inside a wall—according to the building structure taken from a digital building model—it is deleted, or its weight is decreased drastically.
In addition, further existing infrastructure-based positioning systems such as WLAN fingerprinting, proximity estimates based on BLE beacons, and magnetic field anomaly maps can be integrated. For this purpose, probability density distributions (e.g., normal or uniform distribution) are assumed for each positioning information and fused with the PF estimate via a Mixture model [70]. Through this approach, the probability distribution of the sensor measurements of the PDR, BLE proximity and WLAN fingerprinting, and the magnetic field anomalies can be approximated and fused via the Bayesian Filter approach (described by Equation (3)) [39,71,72]. The likelihood p ( z k | x k )   of the measurement model represents the system state x k and its correlation to the current observation z k at timestamp k . The a-priori probability p ( x k | Z k 1 ) represents the information of the model and p ( z k | Z k 1 ) is used for normalization. This filter fuses the respective position estimations of the involved localization techniques using multiplication and normalization to obtain a single position output:
p ( x k | Z k ) = p ( z k | x k ) · p ( x k | Z k 1 ) p ( z k | Z k 1 ) .
Subsequently, this recursive plausibility test removes some particles and the majority of the particles will group around the actual position. If the particles group in several clusters, strategies like the kernel density estimation with mixture models can help choose one group representing the actual position [73].

4. Extended Localization Strategy

As an essential extension of the previously described basic approach, the particle representation was modified in this work from free-moving particles to a grid-based interpretation with fixed possible particle locations. For this, the building model given in vector format was transferred from its global Universal Transverse Mercator (UTM) coordinates to a local coordinate system and discretized to a raster grid. Thus, each particle is interpreted by a grid cell, which represents a quadratic element (or pixel) of a 2D matrix. This representation of the building model is shown in Figure 1a. Figure 1b illustrates a section of this model in case of an unknown starting position. Since the actual starting position is unknown, the presented PF does not initialize the possible position via random particles. Instead, each pixel of the initial matrix in Figure 1a (yellow cells) represents a start hypothesis of the current position ( I 0 ), and only these pixel values can change. With this changed particle interpretation, the number of usable particles was drastically increased while keeping the computational load low via fast and efficient 2D matrix multiplications on the Graphical Processing Unit (GPU).
To reflect the building topology’s valid positions, wall-free areas, e.g., rooms, floors, door areas, and stairs, are characterized as possible starting positions (yellow cells). In contrast, wall or outdoor areas are invalid starting positions (blue cells). In this exemplary cell array of 556 × 335 pixels with an edge length of 0.15 m, there exist 76.614 valid out of 186.260 possible initial positions. Only grid cells that are likely to be entered get a value of one. In contrast, inaccessible areas get zeros pixel values and waist-high obstacles like fixed desks or benches get a value in between to reflect the unlikelihood of passing through such objects.
The process of our position estimation algorithm is shown in Figure 2. In Figure 3, the grid-based building model and the related walkway structure (Figure 3a), as well as example maps of a BLE (Figure 3b) and a WLAN fingerprinting-based radio map (Figure 3c), and the magnetic field anomaly map (Figure 3d) are shown. All information, therefore, was converted into a grid cell representation of the corresponding PDF.
The walkway structure (Figure 3a) is an assumption of the paths in a building based on the skeletonization of the walkable indoor area. This map’s highest values (yellow cells) represent areas with a high distance to the walls nearby inside the building.
The BLE (Figure 3b) and the WLAN (Figure 3c) fingerprinting radio map illustrate a position estimation based on a weighted k-nearest-neighbors (WKNN) fingerprinting (k = 5) [74]. If a position can be estimated via BLE or WLAN-based fingerprinting, each of these positions was convoluted with a symmetric 2D Gaussian function to reflect the position uncertainties based on previous measurements.
The magnetic field anomaly map (Figure 3d) was estimated using the magnetic anomalies caused by ferromagnetic objects, in the present case, especially fire-protection doors. These anomalies influence the magnetometer if the smartphone is near these doors. Therefore, the areas of the fire-protection doors are convoluted with a symmetric 2D Gaussian function with a standard deviation (σ) of 1.0 m. The used values of σ were postulated in [5].
For the estimation of the positions, the measurement uncertainties of the PDR have to be considered. Therefore, the empirically determined probability distributions of the step size estimation (Figure 4a, σ = 0.15 m) and the heading estimation (Figure 4b, σ = 40°) are fused to a resulting step probability distribution (Figure 4c). The current position distribution matrix is then superimposed with the resulting probability distribution of step estimation at each position after a determined movement. This process corresponds to the discrete 2D convolution formulated in Equation (4) and predicts the actual movement. I is the image and I* represents the result after a discrete convolution with the convolution kernel k   ϵ   R n × n . The coordinates of a pixel are x and y, n is the kernel’s size in the first dimension, while a is the center of the convolution kernel’s size:
I * ( x , y ) = i = 1 n j = 1 n I ( x i + a y j + a ) k ( i , j ) .
Due to the sensors’ measurement uncertainties, the current position at building junctions could be determined wrong, and therefore, a false path would be taken. This process usually leads to a state where the determined position gets stuck in a wall. This scenario, known as the Kidnapped Robot Problem [39], is solved automatically by the algorithm without detecting a faulty state because the particles are not erased, and the grid cell values are not set to zero in a large environment around the current position. This is achieved by shifting the wall areas (blue areas in Figure 1a) for each step with the respective step length in pixel according to the movement’s heading using Bresenham’s line algorithm [75]. Using this algorithm, all position updates (step length and heading) are translated to pixel-wise shifts to reflect the raster-discretized translation.
All grid cell values, which were implausible to represent the current step’s start, are attenuated by 90%. Therefore, the correct position can be estimated again if it was lost after only a few steps. This procedure reduces the values of wall areas and the areas which cannot be reached with the current step probability distribution. This weakening process is shown in Figure 5a after five steps.
The procedure of superimposing the probability distribution map ( I Z 1 ) with the current step distribution ( k C S D   ϵ   R n × n ) represents the prediction step. In contrast, the Hadamard products (element-wise multiplications ) of this result with the maps of walkway structure ( I W S ), BLE ( I B T ), WLAN ( I W L A N ), and of the magnetic field anomalies ( I M F A ), as well as of the weakening of implausible areas ( I w e a k ) corresponds to the importance sampling or update step in the classical PF approach.
These calculations and the normalization are repeated recursively for each step. Therefore, the current position is determined from each previous position estimate and the current sensor data. This process and the respective probability distributions are shown in Figure 5b–d after 2, 5, and 20 steps. Furthermore, the video “S1 Extended Localization” of the Supplementary Materials illustrates the step-by-step positioning determination.
A maximum of three decimal places was allowed for each parameter to limit the parameter combinations’ depth. For instance, the combination [0.153; 0.982; 0.349; 0.787; 0.622] is one of the possible individual parameter vectors.
In Equation (5), a pixel’s coordinates are x and y, while a is the center of the convolution kernel’s size ( k C S D ).
To avoid zero-pixel values and ensure the further usability of cells, the distributions of the walkway structure, BLE, WLAN, and magnetic field anomalies are multiplied by a weighting factor w i (interval from 0 to 1) and an offset of +1 is added:
I = ( i = 1 n j = 1 m I Z 1 ( x i + a y j + a ) k C S D Z ( i , j ) ) ( I w s Z · w 1 + 1 ) ( I B T Z · w 2 + 1 ) ( I W L A N Z · w 3 + 1 ) ( I M F A Z · w 4 + 1 ) I w e a k Z I Z = I max   ( I )
To reflect the discrepancy between the possible body height, leg length, personal walking speed, and walking style between the examined pedestrian of [76] and the one in this work, an adjustment can be made. Therefore, the step length could be changed within the parameter optimization by multiplying a weighting factor 2 · w 5 (interval from 0 to 1) to the estimated step length before the steps are discretized. Nevertheless, the minimal step length is equal to one cell’s size and the maximal is equal to the doubled estimated step length. During the first steps or at building junctions, I Z will have multiple peaks, but only the highest cell value indicates the current position. The knowledge-based parameter combination is [1; 1; 1; 1; 0.5], which represents the equal trust in the fused position information of the walkway structure, BLE fingerprinting, WLAN fingerprinting, magnetic field anomalies, and the step length estimation.

5. Optimization Strategies

For determining the weights w 1 to w 5 , used in the prediction step for fusion the position information of the different sources (Equation (5)), in general, optimization methods can be applied. For the implementation the procedure was to carry out test runs in buildings with ground truth points (GTPs) and then to estimate the weights with a root-mean-square error (RMSE)-based fitness metric shown in Equation (6). To obtain small values for the distances between the GTPs and the corresponding estimated positions, the product of the RMSE values’ reciprocals for each involved test run is used. Furthermore, for better numerical handling, a scaling factor of 10 was chosen:
F i t n e s s = t e s t   r u n = 1 N 10 R M S E t e s t   r u n .
Due to the high ambiguity and the unknown (mixed) stochastical distributions of the input variables, the optimization quickly converges to a local minimum when using classical search methods (e.g., gradient-based methods). Therefore, global optimization procedures are recommended to maximize the quality metric and avoid local extrema.
However, because of the building model’s nonlinearities, the used 2D maps, and the cropped steps, jumps and plateaus of the metric values exist. This also makes the stochastic description of the weights difficult and no gradients can be easily derived analytically. Thus, gradient-based optimization methods are not applicable and only function evaluations appear expedient.
Hence, in this work a GA is investigated to avoid the convergence against local extrema and to find optimal weights despite the complex optimization problem. For evaluation and benchmarking, the GA is compared with four other local and global optimization strategies (Hill Climbing, Nelder–Mead method, Simulated Annealing, Particle Swarm) to illustrate the necessity for more complex and robust search techniques.

5.1. Genetic Algorithm

Since especially the GA is investigated in this work, it will be introduced first in this section.
The GA is a flexible and robust optimization strategy whose general structure is shown in Figure 6. The GA is based on the observation of nature in which biological evolution (following Darwin’s thesis) has led to complex life forms optimally adapted to their environment. Therefore, it can be assumed that not only the results of biological evolution are optimal, but also its mechanisms [77]. Accordingly, a potential solution in the parameter space is abstracted as an individual in an artificial environment [78] and successful patterns are combined to achieve better results. Here, a specific weighting constellation is called an individual.
In the context of this work, the (μ, λ)-strategy (μ—parents and λ—children) is pursued [79], and as in biological evolution, a limited lifespan of individuals [78] is used. The maximum age of an individual is 5 % of the number of generations and the population size is kept constant in every generation.
However, it is crucial that the optimum search is global and does not just converge to a local optimum. Therefore, inferior individuals also have a small probability of getting selected [80].
The genetic operator’s selection, recombination, and mutation create the next generation from the random starting parameter space (the starting population). This process is repeated until most parameter combinations converge or a maximum number of generations has been reached. To achieve progress in the optimization, selecting the best individuals of a generation is required in each optimization step based on a quality metric [81].
Because the computation time for sorting is negligible in this work, and to prevent a convergence occurring directly at the beginning, a ranking selection is used in contrast to the frequently used recombination schemes of roulette wheel or competition selection. This selection applies the sorted rank instead of the absolute fitness values and determines whether an individual will be selected for recombination. A dominance of single individuals and convergence to a local extremum is thus prevented.
In this approach, individuals with r a n k   1 represent those with the lowest fitness value, whereas rank n describes the best [64]. To determine the probability of selection, [82] suggests the following procedure: the expected value E m a x is assigned ( 1 E m a x 2 ) to the highest-ranked individual. The value E m i n for the worst individual is estimated from E m i n = 2 E m a x and the probability of an arbitrary individual E ( i ) to be chosen is calculated using r a n k ( i ) . Thus E ( i ) is the linear index of the i -th element in the sorted array of length n :
E ( i ) = E m i n + ( E m a x E m i n )   ·   ( r a n k ( i ) 1 ) n 1 .
A real-valued genetic representation of each individual with five property vectors between 0 and 1 is used in this work. To take advantage of different recombination techniques, 80% of the next generation is created by intermediate and 20% by combining recombination. On the one hand, intermediate recombination is used in which each parameter of a new individual is represented as the average of the respective parent’s parameters [79]. On the other hand, the combining recombination recomposes the details of different individuals and thus, the advantageous components of the parent individuals can be combined in the optimal case [83]. Here, individuals can also be combined with themselves. To avoid the resulting more homogeneous population and convergence without reaching the optimum, the individuals’ parameters are mutated to prevent diversity loss. Thus, a local optimum can be left again and the search space is explored extensively.
Each child individual is created by recombination of two parents and subsequent mutation. This process concentrates the search space around promising areas of the model space. A mutation in the GA describes the arbitrary modification of the genetic material of an individual. For achieving this, the Gauss-mutation was used, which adds a Gaussian distributed random value u · m u t a t i o n _ r a t e   ( u   ~   N ( 0 , σ ) ) to each component of the recombined child generation. Random changes with low probability secure the diversity within the population [84]. Due to this probability distribution, many mutations will only make small changes, but larger jumps are also possible [83]. Table 1 shows an overview of the features used for the GA in this work.
All of the described procedures can replace the entire parent population with the new individuals, but this may result in the best individual’s loss. The results of [85,86] had shown that elitism could significantly speed up the GA’s performance, which can also help prevent the loss of good solutions once they are found. To achieve this and reach a better convergence, the worst offspring (20% of the population size) is replaced by the best parent individuals [64]. Furthermore, 20% of the parent individuals are chosen to be elite individuals [86] without any lifespan.

5.2. Hill Climbing

The Hill Climbing algorithm searches for the next maximum starting from the initial position (knowledge-based parameter combination) with decreasing step size (0.05; 0.02; 0.01; 0.005; 0.002; 0.001). The steps taken are identical to the Gauss–Newton algorithm (in contrast to the Levenberg–Marquardt algorithm, which uses a dynamic step size estimation) because minimizing the sum of least squares (therefore the RMSE) and maximizing the reciprocal generate the same step selection.
Therefore, the step widths are always reduced if no neighboring position has a higher metric value than the current one. All neighbors with the respective step size are examined (initial values + [−step; 0; step]) for all five weighting parameters. Thus, there are 243 parameter combinations to be examined per step ( 3 5 possible permutations). However, the parameter values cannot exceed or fall below the limit values of 0 and 1. All combinations are stored in a matrix after calculation, which serves as a continuous comparison database to prevent the recalculation of already known parameter combinations.

5.3. Nelder–Mead Method

This algorithm (also known as the downhill simplex method) aims to minimize the metric value via function evaluations in the form of a simplex. Therefore, N + 1 function evaluations are calculated for the N parameters to be optimized. In each step, the point with the worst metric value is replaced by a new one [87,88,89]. The dynamic step size determination allows bypassing local minima at the beginning of the algorithm process before the algorithm’s convergence occurs. Thus, local minima can be circumvented in some cases. To use this algorithm, the metric value is multiplied by “−1”.

5.4. Simulated Annealing

The basic idea is to reproduce a cooling process such as that found in metallurgy. Here, the slow cooling ensures that stable crystals can form since the atoms have sufficient time to arrange themselves. Thus, a lower energy state is achieved, which corresponds to a local optimum. In the context of optimization methods, the temperature corresponds to the probability that an intermediate solution may deteriorate during the iterations. Thus, this optimization procedure can leave local optima and better values can be found [90,91].

5.5. Particle Swarm

This optimization procedure is similar to the GA but was derived from observing flocks of birds [92]. Individuals move in steps through the search space defined by the target function. Depending on the other individuals’ metric values, the orientation of the particle movement, and thus, the values of the parameter values of the next individuals are determined. The particles will gather around the local maxima in the search area with the expectation to hit the global maximum. Problems arise when no particle is near the global maximum. Then the algorithm converges to the local maxima [93].

6. Experimental Evaluation and Data Collection

The experimental evaluation of the optimization strategy and the data collection were performed in a university building. The used smartphones were a Samsung Galaxy S7 (S7 SM-G930F, hereinafter referenced as S7) with an Exynos 8890 (eight cores) and an LG V30 (LG-H930, hereinafter referenced as LG) with a Snapdragon 835 (eight cores), both with Android Oreo (8.0.0.). Three BLE (Bluetooth Version 4.3, Estimote location beacon based on nRF52 SoC and 64MHz ARM Cortex-M4F CPU) beacons were used, placed near the stairways, and there were 109 different WLAN-IDs (IEEE 802.11ac 2.4 or 5 GHz) available. The floor plan of the used building model and the sequence of the measurement runs are shown in Figure 7. All measurement runs are performed on the same floor with 107 GTPs, visualized with red dots, while the start is shown in black and the end of the track in blue. Eight test runs were performed with the S7 and five with the LG. In the case of the S7, five test runs were used to estimate the weights and the remaining three for evaluation, while in the case of the LG, the ratio was three to two runs. Each run consists of approximately 583 steps with an average walking speed of around 1.6 m/s. Because the first steps are needed to achieve a convergence of the particle values, the first 30 steps are excluded from the optimization process. Otherwise, the fastest possible convergence will dominate the overall RMSE estimation.
The smartphones were held in hand in front of the body while walking through the measurement runs recording accelerometer, gyroscope, magnetometer, WLAN, and BLE using a data recording app. Every signal was logged with its timestamp, which was determined by the operation system. The app offers the opportunity to log the reference point when passing by as checkpoints via the current timestamp. The reference points sequence was the same during the measurement runs and each passing was logged with its timestamp. A run consists on average of 583 steps and a measurement duration of approximately 367 s. Each measurement run includes the passing of 157 checkpoints (some GTPs were used twice). The measurement runs were cut to size, so the first and last checkpoints’ timestamps represent the start and end of all recorded signals of a specific run. Measurement data outside of this period was disregarded for further analysis.
It has to be noticed that the deviation analysis was estimated from the data of the runs and during movements. That is why [5] estimated up to 0.3 m deviations between an accurate centered foot on the GTP and the recorded steps.
For better use of the individual signals, accelerometer, gyroscope, and magnetometer sensor data were converted with a spline interpolation to equidistant data points using a frequency of 100 Hz. Then the step detection was implemented according to [94]. For this, the magnitudes of the acceleration signals are determined. A step is only recognized if the acceleration values’ variance in a sliding window with a width of 0.8 s exceeds a value of 0.8.
Since the smartphones were held in hand, a higher value for s i g _ t h r e s h of 0.8 was empirically determined here compared to the original value of 0.6. Subsequently, the acceleration magnitude is smoothed by a moving-average filter with a width of 0.31 s and windowed peak detection with a width of 0.59 s is performed. The sequence of local maximum and minimum accelerations thus determined marks the steps. The step length is then determined using the mean absolute acceleration magnitude of a step, according to [76] (see Equation (8)).
K was determined to be 0.3179 based on an empirical investigation of one part of the data set of Wang [95]:
S t e p   L e n g t h = K · i = 1 N | a i | N 3
The orientation was estimated using the magnetometer to determine the absolute magnetic north direction, while the accelerometer indicates the direction of the gravity vector to determine the down direction. The relative orientation changes were tracked via the gyroscope [96]. This work uses the step size ( σ = 0.15   m ) and heading ( σ = 40 ° ) uncertainties postulated in [5].
During the test runs, it was checked whether beacon signals were recognized for a step. If this is the case, the difference in signal strength between the measured beacon signal and all reference points which have received the recorded Beacon ID in the offline phase will be compared. The inverse squared signal strength differences between the recorded and the reference signals are used to estimate the weights for the position determination. If no match was found, the corresponding reference points for the current position determination are ignored. The position is then determined as the weighted average of all remaining reference positions. Here, in case of signal strength differences of 0, these values are changed to 0.1 to avoid impermissible weights. The median of the position deviations during the runs to the determined positions for registered BLE signals is 6.89 m for the S7 and 4.32 m for the LG.
The same procedure was used for positioning using WLAN fingerprinting. The WLAN fingerprinting provided a higher signal diversity with 109 different WLAN signal sources, whereas BLE uses three. That is why a reference point is only included in the positioning process if it has at least three signal overlaps with the currently registered WLAN signal. Finally, the position is determined from the current step’s permissible reference points as a WKNN ( k = 5 ). The median of the position deviations from the actual position to the determined positions for registered WLAN signals is 4.43 m for the S7 and 7.04 m for the LG.
A simple outlier determination was carried out to determine if magnetic field anomalies are present, which indicate characteristic building parts (especially fire doors). For this, a magnetic field anomaly was detected if the magnetic field magnitude has a greater or lower value than three median absolute deviations from the moving median. For this purpose, a window width of 4 s was used. Furthermore, a magnetic field disturbance is present if the magnetic field magnitude has a value that is more than twice the standard deviation from the mean value of the current run.

7. Parameter Optimization and Performance Analysis

After data collection, the weights for an optimized hybrid localization strategy based on the grid-based approach (Equation (5)) were estimated by means of the GA using the position estimates of the PF and the known position in each GTP as input data.
The results of the GA and for comparison of the different optimization strategies are shown in Table 2. The weights listed one after the other represent the walkway structure, BLE fingerprinting, WLAN fingerprinting, magnetic field anomalies, and the step length estimation. Although the particle swarm algorithm performs best on the LG data, it fails at the more complex data of the S7 and does not reach a good metric value.
The Hill Climbing algorithm reaches the next local optimum but fails to find the global optimum in both datasets. The Nelder–Mead algorithm achieves slightly better results than the pure Hill Climbing but does also not find the possible global optimum. Simulated Annealing achieves good metric values, but overall, the GA outperforms the other algorithms. Although it needs the most computing time, the pure performance of estimating the best metric value is the optimization goal. This process of determining the optimal parameters must only be calculated once at the end of the offline phase.
In contrast to the offline phase, the estimated weights for position estimation are used in the online phase. Thus, a fast computation in the online phase is possible since only one convolution, the element-wise multiplications of the predefined sensor maps and the normalization must be calculated for each step. In Figure 8, the optimization process of the GA is shown. A substantial increase in fitness values can be seen at the beginning of the search during the first 20 generations.
After the cutoff of the first 30 Steps, there are 147 checkpoints left. The evaluation runs’ error distances are shown in Figure 9 for the S7 and Figure 10 for the LG. The specific benchmarks are shown in Table 3 and Table 4, respectively.
Considering all evaluation runs, the mean deviation values were reduced by about 35% for the S7 and 25% for the LG. Furthermore, the RMSE were reduced by about 39% and 26%. The RMSE is approximately 1.97 m for the S7 and 2.93 m for the LG on average. As shown in Figure 11, indicated with dashed lines, the third quartile positioning error was reduced by about 54% (3.57 m to 2.32 m) and 50% (5.35 m to 3.57 m). Moreover, the 95-percentile positioning error was reduced by 67% (6.68 m to 4.00 m) and 38% (7.87 m to 5.71 m) presented with dotted lines. Additionally, the maximum position error was reduced by 39% and 20%.
Based on the determined optimal parameter values from the test runs, the RMSE values were calculated for all evaluation runs and these are shown in Figure 12. It illustrates the decrease of the deviations to the GTPs if the weighting parameters are optimized with the GA.

8. Conclusions

In this work, an algorithm for smartphone-based pedestrian localization was shown, which combines the classical PDR with fingerprinting and a novel multiple hypothesis grid-based interpretation of the particles of the PF. The grid-based representations of the fingerprinting maps and the estimated step length are weighted with the optimization scheme of the GA to achieve higher position accuracy.
The presented algorithm can deal with natural motion behavior, including dynamic changes of standing and moving with varying step length. This algorithm also does not require the artificial cut of curves to have 90-degree changes. It was also accelerated via GPU-based matrix multiplications to improve the vectorized particle computations.
With the presented probability-map-based approach, the sensor fusion algorithm can combine relative sensor-based movements, absolute fingerprinting-based position estimations, and digital building models in real-time to a step-based position estimation without knowledge of any start position. Moreover, it can deal with uncertain information, sensor noise, and building ambiguities. Other information sources such as brightness measurements, barometer signals, magnetic field inclination and declination anomaly maps, ultrasound, and GNSS can easily be included in the calculations as additional layers in a modular way. Thus, absolute position information is used via additional maps, and referential information is included with convolutions.
It is important to emphasize that in this novel particle interpretation the particles are not moving. In contrast, the particles are represented by fixed grid cells whose probabilities change with every new information source and stepwise iteration. Thus, smooth progress in the change of the position probability distribution indicates the current position, and several position theses can alternate without conflicting with each other.
During the reasoning stage, no particles are removed by walls, but the pixel-wise shifting of the wall maps in the respective direction of steps weakens the values of unlikely positions. The offline optimization of the weights with the GA has to be determined only once for a given environment. In contrast to classical, processing-intensive PF utilizing a large number (e.g., 5000) of freely moving particles, the grid-based implementation allows for seamless application on smartphones to enable real-time position estimation. Another advantage of the presented algorithm is the optionality of a starting position.
A limitation of the current implementation is the fingerprinting specific need of data premeasurement for BLE and WLAN signal maps. Hence, the weights have to be re-optimized when the environment changes (e.g., updated WLAN fingerprinting map, additional BLE beacons, etc.). However, this could be automated by triggering the optimization process after each change of the environment or the databases. Additionally, a denser fingerprinting grid and more BLE beacons would improve the results.
In future work, we will investigate the problems regarding the determination of translation for rotations without clearly recognizable steps or while walking backwards. Furthermore, the algorithm shows promising results and will thus be tested with other datasets, environments, different smartphones, and more subjects. It is therefore intended to use the datasets of the EvAAL Competitions of the last IPINs [97].
In summary, the implemented GA is beneficial for the position accuracy and the localization errors were reduced. In fact, the GA improves the overall mean position accuracy by 31%, as well as the maximum position error compared to the knowledge-based parameter combination using the same sensor data, digital building model, and particle representation.
The overall RMSE was reduced by 34%, whereas the third quartile positioning errors by 54% and 50%. Also, the 95-percentile positioning errors were reduced by 67% and 38%. This improvement was achieved by adjusting the weights of the individual measurement methods to an optimal constellation.

Supplementary Materials

The following are available online at https://0-www-mdpi-com.brum.beds.ac.uk/2079-9292/10/5/618/s1, Video S1 Extended Localization.

Author Contributions

J.G. performed the experiments, recorded and analyzed the data, conceived and designed the algorithms, prepared the original draft, and visualized the results; J.B. supervised this work, gave many ideas and valuable comments, and reviewed and edited the draft. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the Federal Ministry of Education and Research of Germany, framework: SmartNav2POI, grant number: 16SV7914.

Data Availability Statement

All data included in this study are available upon request by contacting with the corresponding author.

Acknowledgments

The authors would like to thank Catia Real Ehrlich for helpful comments, suggestions, and for sharing her data and algorithms at the start of this work.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Schwieger, V. High-Sensitivity GPS—An availability, reliability and accuracy test. In Proceedings of the the FIG Working Week, Stockholm, Sweden, 19 June 2008. [Google Scholar]
  2. Zhang, J.; Li, B.; Dempster, A.G.; Rizos, C. Evaluation of high sensitivity GPS receivers. In Proceedings of the the International Symposium on GPS/GNSS, Taipei, Taiwan, 26–28 October 2010. [Google Scholar]
  3. Willert, V.E.; Willert, V.V.; Gering, S.; Raß, S.; Etzel, J. Automated extraction of image coordinates for Optical Indoor Positioning. In Proceedings of the the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Guimarães, Portugal, 21–23 September 2011. [Google Scholar]
  4. Blankenbach, J. Indoor-Positionierung & lokale Positionierungssysteme. In Leitfaden-Mobile GIS, Von der GNSS-Basierten Datenerfassung bis zu Mobile Mapping; Runder Tisch GIS e.V.: Munich, Germany, 2017; Volume 6, pp. 63–76. [Google Scholar]
  5. Real Ehrlich, C.; Blankenbach, J. Pedestrian Localisation inside buildings based on multi-sensor smartphones. In Proceedings of the the 2018 International Conference on Ubiquitous Positioning Indoor-Navigation and Location Based Service (UPINLBS), Wuhan, China, 22–23 March 2018; pp. 1–10. [Google Scholar] [CrossRef]
  6. Morar, A.; Moldoveanu, A.; Mocanu, I.; Moldoveanu, F.; Radoi, I.E.; Asavei, V.; Gradinaru, A.; Butean, A. A comprehensive survey of indoor localization methods based on computer vision. Sensors 2020, 20, 2641. [Google Scholar] [CrossRef]
  7. Xie, H.; Gu, T.; Tao, X.; Ye, H.; Lv, J. MaLoc: A practical magnetic fingerprinting approach to indoor localization using smartphones. In Proceedings of the the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp ‘14), ACM, New York, NY, USA, 13–17 September 2014; pp. 243–253. [Google Scholar] [CrossRef]
  8. Sakpere, W.; Oshin, M.A.; Mlitwa, N.B. A state-of-the-art survey of indoor positioning and navigation systems and technologies. South Afr. Comput. J. 2017, 29, 145–197. [Google Scholar] [CrossRef] [Green Version]
  9. Brena, R.F.; García-Vázquez, J.P.; Galván-Tejada, C.E.; Muñoz-Rodriguez, D.; Vargas-Rosales, C.; Fangmeyer, J. Evolution of indoor positioning technologies: A survey. Sensors 2017, 2017, 1–21. [Google Scholar] [CrossRef]
  10. Khalil, L.; Jung, P. Spherical simplex unscented Kalman filter for RSSI-based WLAN IEEE 802.11n positioning and tracking. In Proceedings of the the 2015 IEEE 26th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Hong Kong, China, 30 August–2 September 2015; pp. 2094–2098. [Google Scholar] [CrossRef]
  11. Mondal, R.U.; Ristaniemi, T.; Turkka, J. Cluster-based RF fingerprint positioning using LTE and WLAN outdoor signals. In Proceedings of the the 2015 10th International Conference on Information, Communications and Signal Processing (ICICS), Singapore, 2–4 December 2015; pp. 1–5. [Google Scholar] [CrossRef] [Green Version]
  12. Luo, J.; Fu, L. A smartphone indoor localization algorithm based on WLAN location fingerprinting with feature extraction and clustering. Sensors 2017, 17, 1339. [Google Scholar] [CrossRef] [Green Version]
  13. Lohan, E.S.; Torres-Sospedra, J.; Leppäkoski, H.; Richter, P.; Peng, Z.; Huerta, J. Wi-Fi Crowdsourced Fingerprinting Dataset for Indoor Positioning. Data 2017, 2, 32. [Google Scholar] [CrossRef] [Green Version]
  14. Bekkali, A.; Sanson, H.; Matsumoto, M. RFID indoor positioning based on probabilistic RFID map and Kalman filtering. In Proceedings of the the 3rd IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2007), White Plains, NY, USA, 8–10 October 2007; p. 21. [Google Scholar] [CrossRef]
  15. Errington, A.F.C.; Daku, B.L.F.; Prugger, A.F. Initial Position Estimation Using RFID Tags: A Least-Squares Approach. IEEE Trans. Instrum. Meas. 2010, 59, 2863–2869. [Google Scholar] [CrossRef]
  16. Porto, M.C.; Arcidiacono, C.; Cascone, G.; Anguzza, U.; Barbari, M.; Simonini, S. Validation of an active RFID-based system to detect pigs housed in pens. J. Food Agric. Environ. 2012, 10, 468–472. [Google Scholar]
  17. Maratea, A.; Gaglione, S.; Angrisano, A.; Salvi, G.; Nunziata, A. Non parametric and robust statistics for indoor distance estimation through BLE. In Proceedings of the 2018 IEEE International Conference on Environmental Engineering (EE), Milan, Italy, 12–14 March 2018; pp. 1–6. [Google Scholar] [CrossRef]
  18. Nguyen, Q.H.; Johnson, P.; Nguyen, T.T.; Randles, M. Optimized indoor positioning for static mode smart devices using BLE. In Proceedings of the 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Montreal, QC, Canada, 8–13 October 2017; pp. 1–6. [Google Scholar] [CrossRef] [Green Version]
  19. Mendoza-Silva, G.M.; Torres-Sospedra, J.; Huerta, J. A Meta-Review of Indoor Positioning Systems. Sensors 2019, 19, 4507. [Google Scholar] [CrossRef] [Green Version]
  20. Zafari, F.; Gkelias, A.; Leung, K.K. A Survey of Indoor Localization Systems and Technologies. IEEE Commun. Surv. Tutor. 2019, 21, 2568–2599. [Google Scholar] [CrossRef] [Green Version]
  21. Foxlin, E. Pedestrian tracking with shoe-mounted inertial sensors. IEEE Comput. Graph. Appl. 2005, 25, 38–46. [Google Scholar] [CrossRef]
  22. Harle, R. A survey of indoor inertial positioning systems for pedestrians. IEEE Commun. Surv. Tutor. 2013, 15, 1281–1293. [Google Scholar] [CrossRef]
  23. Cramer, M. Genauigkeitsuntersuchungen zur GPS/INS-Integration in der Aerotriangulation. Ph.D. Thesis, University Stuttgart, Stuttgart, Germany, 2001. [Google Scholar]
  24. Becker, D.; Becker, M. A study of non-stochastic IMU errors in strapdown airborne gravimetry. In Proceedings of the 2015 DGON Inertial Sensors and Systems Symposium (ISS 2015), Karlsruhe, Germany, 22–23 September 2015; pp. 1–18. [Google Scholar] [CrossRef]
  25. Ashraf, I.; Hur, S.; Park, Y. Smartphone Sensor Based Indoor Positioning: Current Status, Opportunities, and Future Challenges. Electronics 2020, 9, 891. [Google Scholar] [CrossRef]
  26. Sternberg, H.; Fessele, M.; Hönniger, C. Indoor navigation without infrastructure-based local positioning system. In Proceedings of the 6th International Symposium on Mobile Mapping Technology MMT’09, Presidente Prudente, Brazil, 21–24 July 2009. [Google Scholar]
  27. Willemsen, T.; Keller, F.; Sternberg, H. A topological approach with MEMS in smartphones-based on routing-graph. In Proceedings of the 2015 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Banff, AB, Canada, 13–16 October 2015; pp. 1–6. [Google Scholar] [CrossRef]
  28. Real Ehrlich, C.; Blankenbach, J.; Sieprath, A. Towards a robust smartphone-based 2,5D pedestrian localization. In Proceedings of the 2016 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Alcalá de Henares, Spain, 4–7 October 2016; pp. 1–8. [Google Scholar] [CrossRef]
  29. Masiero, A.; Guarnieri, A.; Pirotti, F.; Vettore, A. A particle filter for smartphone-based indoor pedestrian navigation. Micromachines 2014, 5, 1012–1033. [Google Scholar] [CrossRef] [Green Version]
  30. Pan, M.-S.; Li, K.-Y. ezNavi: An Easy-to-Operate Indoor Navigation System Based on Pedestrian Dead Reckoning and Crowdsourced User Trajectories. IEEE Trans. Mob. Comput. 2021, 20, 488–501. [Google Scholar] [CrossRef]
  31. Kumar, A.; Kumar, D.; Karial, S.K. A hybrid clustering method based on improved artificial bee colony and fuzzy C-Means algorithm. Int. J. Artif. Intell. 2017, 15, 40–60. [Google Scholar]
  32. Cai, S.; Liao, W.; Luo, C.; Li, M.; Huang, X.; Li, P. CRIL: An Efficient Online Adaptive Indoor Localization System. IEEE Trans. Veh. Technol. 2017, 66, 4148–4160. [Google Scholar] [CrossRef]
  33. Tang, H.; Xue, F.; Liu, T.; Zhao, M.; Dong, C. Indoor Positioning Algorithm Fusing Multi-Source Information. Wirel. Pers. Commun. 2019, 109, 2541–2560. [Google Scholar] [CrossRef]
  34. Correa, A.; Barcelo, M.; Morell, A.; Vicario, J.L. A Review of Pedestrian Indoor Positioning Systems for Mass Market Applications. Sensors 2017, 17, 1927. [Google Scholar] [CrossRef] [Green Version]
  35. Maghdid, H.S.; Lami, I.A.; Ghafoor, K.Z.; Lloret, J. Seamless outdoors-indoors localization solutions on smartphones. ACM Comput. Surv. 2016, 48, 1–34. [Google Scholar] [CrossRef]
  36. Davidson, P.; Piché, R. A Survey of Selected Indoor Positioning Methods for Smartphones. IEEE Commun. Surv. Tutor. 2017, 19, 1347–1370. [Google Scholar] [CrossRef]
  37. Pascacio, P.; Casteleyn, S.; Torres-Sospedra, J.; Lohan, E.S.; Nurmi, J. Collaborative Indoor Positioning Systems: A Systematic Review. Sensors 2021, 21, 1002. [Google Scholar] [CrossRef]
  38. Murata, M.; Ahmetovic, D.; Sato, D.; Takagi, H.; Kitani, K.M.; Asakawa, C. Smartphone-based localization for blind navigation in building-scale indoor environments. Pervasive Mob. Comput. 2019, 57, 14–32. [Google Scholar] [CrossRef] [Green Version]
  39. Thrun, S.; Burgard, W.; Fox, D. Probabilistic Robotics; MIT Press: Cambridge, UK, 2005. [Google Scholar]
  40. Klingbeil, L.; Reiner, R.; Romanovas, M.; Traechtler, M.; Manoli, Y. Multi-modal sensor data and information fusion for localization in indoor environments. In Proceedings of the 2010 7th Workshop on Positioning, Navigation and Communication, Dresden, Germany, 11–12 March 2010. [Google Scholar] [CrossRef]
  41. Kalman, R.E. A new approach to linear filtering and prediction problems. J. Basic Eng. 1960, 82, 35–45. [Google Scholar] [CrossRef] [Green Version]
  42. Swerling, P. First-order error propagation in a stagewise smoothing procedure for satellite observations. J. Astronaut. Sci. 1959, 46–52. Available online: https://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM2329.pdf (accessed on 4 March 2021).
  43. Grewal, M.S.; Andrews, A.P. Kalman Filtering: Theory and Practice Using MATLAB, 4th ed.; John Wiley & Sons: New York, NY, USA, 2014. [Google Scholar] [CrossRef]
  44. Julier, S.J.; Uhlmann, J.K. New extension of the Kalman filter to nonlinear systems. In Proceedings of the Signal Processing, Sensor Fusion, and Target Recognition VI (AeroSense ‘97), Orlando, FL, USA, 28 July 1997; Volume 3068. [Google Scholar] [CrossRef]
  45. Welch, G.; Bishop, G. An Introduction to the Kalman Filter; Technical Report; University of North Carolina: Chapel Hill, NC, USA, 1995. [Google Scholar]
  46. Van Der Merwe, R. Sigma-Point Kalman Filters for Probabilistic Inference in Dynamic State-Space Modes. Ph.D. Thesis, Oregon Health & Science University, Portland, OR, USA, April 2004. [Google Scholar]
  47. Doucet, A.; de Freitas, N.; Gordon, N. Sequential Monte Carlo Methods in Practice; Springer: New York, NY, USA, 2001. [Google Scholar] [CrossRef]
  48. Gordon, N.; Salmon, D.; Smith, A. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. Proc. Radar Signal Process. 1993, 140, 107–113. [Google Scholar] [CrossRef] [Green Version]
  49. Einhorn, E.; Schröter, C.; Gross, H.-M. Finding the adequate resolution for grid mapping-cell sizes locally adapting on-the-fly. In Proceedings of the 2011 IEEE International Conference on Robotics and Automation (ICRA), Shanghai, China, 9–13 May 2011; pp. 1843–1848. [Google Scholar] [CrossRef] [Green Version]
  50. Adarve, J.D.; Perrollaz, M.; Makris, A.; Laugier, C. Computing occupancy grids from multiple sensors using linear opinion pools. In Proceedings of the 2012 IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA, 14–18 June 2012; pp. 4074–4079. [Google Scholar] [CrossRef] [Green Version]
  51. Davidson, P.; Collin, J.; Takala, J. Application of Particle Filters for Indoor Positioning Using Floor Plans. In Proceedings of the 2010 Ubiquitous Positioning Indoor Navigation and Location Based Service, Kirkkonummi, Finland, 14–15 October 2010; pp. 1–4. [Google Scholar] [CrossRef]
  52. Nurminen, H.; Ristimäki, A.; Ali-Löytty, S.; Piché, R. Particle filter and smoother for indoor localization. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Montbeliard, France, 28–31 October 2013; pp. 1–10. [Google Scholar] [CrossRef]
  53. Yu, C.; El-Sheimy, N.; Lan, H.; Liu, Z. Map-Based Indoor Pedestrian Navigation Using an Auxiliary Particle Filter. Micromachines 2017, 8, 225. [Google Scholar] [CrossRef] [Green Version]
  54. Pipelidis, G.; Tsiamitros, N.; Gentner, C.; Ahmed, D.B.; Prehofer, C. A Novel Lightweight Particle Filter for Indoor Localization. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Pisa, Italy, 30 September–3 October 2019; pp. 1–8. [Google Scholar] [CrossRef]
  55. Burgard, W.; Fox, D.; Hennig, D.; Schmidt, T. Position tracking with position probability grids. In Proceedings of the the First Euromicro Workshop on Advanced Mobile Robots (EUROBOT ‘96), Kaiserslautern, Germany, 9–10 October 1996; pp. 2–9. [Google Scholar] [CrossRef]
  56. Danescu, R.; Oniga, F.; Nedevschi, S. Modeling and Tracking the Driving Environment with a Particle-Based Occupancy Grid. IEEE Trans. Intell. Transp. Syst. 2011, 12, 1331–1342. [Google Scholar] [CrossRef]
  57. Koroglu, M.T.; Korkmaz, M.; Yilmaz, A.; Durdu, A. Multiple Hypothesis Testing Approach to Pedestrian INS with Map-Matching. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Pisa, Italy, 30 September–3 October 2019; pp. 1–8. [Google Scholar] [CrossRef]
  58. Deuflhard, P. Least squares problems: Gauss-newton methods. In Newton Methods for Nonlinear Problems; Springer: Berlin/Heidelberg, Germany, 2011; pp. 173–231. [Google Scholar] [CrossRef]
  59. Ulbrich, M.; Ulbrich, S. Nichtlineare Optimierung; Springer: Basel, Switzerland, 2012. [Google Scholar] [CrossRef]
  60. Moré, J.J. The Levenberg-Marquardt algorithm: Implementation and theory. In Numerical Analysis; Springer: Berlin/Heidelberg, Germany, 1978; pp. 105–116. [Google Scholar] [CrossRef] [Green Version]
  61. Venter, G. Review of optimization techniques. In Encyclopedia of Aerospace Engineering; Blockley, R., Shyy, W., Eds.; Wiley & Sons: New York, NY, USA, 2010. [Google Scholar] [CrossRef] [Green Version]
  62. Holland, J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence; MIT Press: Cambridge, MA, USA, 1992; ISBN 978-0-262-08213-6. [Google Scholar]
  63. Goldberg, D.E.; Holland, J.H. Genetic algorithms and machine learning. Mach. Learn. 1988, 3, 95–99. [Google Scholar] [CrossRef]
  64. Buttelmann, M.; Lohmann, B. Optimierung mit Genetischen Algorithmen und eine Anwendung zur Modellreduktion. Automatisierungstechnik 2004, 52, 151–163. [Google Scholar] [CrossRef]
  65. Kramer, O. Genetic Algorithm Essentials; Springer: Cham, Switzerland, 2017; Volume 679. [Google Scholar] [CrossRef]
  66. Abdmouleh, Z.; Gastli, A.; Ben-Brahim, L.; Haouari, M.; Al-Emadi, N.A. Review of optimization techniques applied for the integration of distributed generation from renewable energy sources. Renew. Energy 2017, 113, 266–280. [Google Scholar] [CrossRef]
  67. Wang, H.; Lenz, H.; Szabo, A.; Bamberger, J.; Hanebeck, U.D. WLAN-based pedestrian tracking using particle filters and low-cost MEMS sensors. In Proceedings of the 2007 IEEE 4th Workshop on Positioning, Navigation and Communication, Hannover, Germany, 22 March 2007; pp. 1–7. [Google Scholar] [CrossRef] [Green Version]
  68. Real Ehrlich, C.; Blankenbach, J. Indoor localization for pedestrians with real-time capability using multi-sensor smartphones. Geo-Spat. Inf. Sci. 2019, 22, 73–88. [Google Scholar] [CrossRef] [Green Version]
  69. Real Ehrlich, C. Echtzeit-Positionierung für Fußgänger Innerhalb von Gebäuden auf Basis von Smartphone-Sensoren. Ph.D. Thesis, RWTH Aachen University, Aachen, Germany, 2 November 2018. [Google Scholar] [CrossRef]
  70. Härdle, W.K.; Simar, L. Applied Multivariate Statistical Analysis, 5th ed.; Springer: Berlin/Heidelberg, Germany, 2019. [Google Scholar] [CrossRef]
  71. Dellaert, F.; Fox, D.; Burgard, W.; Thrun, S. Monte Carlo localization for mobile robots. In Proceedings of the 1999 International Conference on Robotics and Automation, Detroit, MI, USA, 10–15 May 1999; Volume 2, pp. 1322–1328. [Google Scholar] [CrossRef] [Green Version]
  72. Koch, K.R. Einführung in die Bayes-Statistik; Springer: Berlin/Heidelberg, Germany, 2013. [Google Scholar] [CrossRef]
  73. McLachlan, G.J.; Peel, D. Finite Mixture Models; John Wiley & Sons: New York, NY, USA, 2000; ISBN 9780471654063. [Google Scholar]
  74. Ling, P.; Chen, R.; Liu, J. Using Inquiry-based Bluetooth RSSI probability distributions for indoor positioning. J. Glob. Position. Syst. 2010, 9, 122–130. [Google Scholar] [CrossRef]
  75. Bresenham, J.E. Algorithm for computer control of a digital plotter. IBM Syst. J. 1965, 4, 25–30. [Google Scholar] [CrossRef]
  76. Kim, W.; Jang, H.J.; Hwang, D.-H.; Park, C. A step, stride and heading determination for the pedestrian navigation system. J. Glob. Position. Syst. 2004, 3, 273–279. [Google Scholar] [CrossRef] [Green Version]
  77. Rechenberg, I. Evolutionsstrategie: Optimierung Technischer Systeme Nach Prinzipien der Biologischen Evolution; Frommann-Holzboog: Stuttgart, Germany, 1973. [Google Scholar]
  78. Blume, H.; Franzen, O.; Schmidt, M.; Schröder, H. Anwendung von Evolutionsstrategien zur Optimierung von Algorithmen der Videosignalverarbeitung. VDI-Berichte 1998, 1381, 221–236. [Google Scholar]
  79. Schwefel, H.P.; Bäck, T. Evolution Strategies. Genet. Algorithms Eng. Comput. Sci. 1995, 3, 127–140. [Google Scholar]
  80. Razali, N.M.; Geraghty, J. Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the the World Congress on Engineering, International Association of Engineers, Hong Kong, China, 6–8 July 2011; Volume 2, pp. 1134–1139. [Google Scholar]
  81. Houck, C.R.; Joines, J.A.; Kay, M.G. A Genetic Algorithm for Function Optimization: A Matlab Implementation; Technical Report; North Carolina State University: Raleigh, NC, USA, 1995; Volume 95, pp. 1–10. [Google Scholar]
  82. Baker, J.E. Adaptive selection methods for genetic algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms and Their Applications, Hillsdale, NJ, USA, 1985; Grefenstette, J.J., Ed.; Lawrence Erlbaum Associates: Mahwah, NJ, USA, 1985; pp. 101–111. [Google Scholar]
  83. Weicker, K. Evolutionary Algorithms, 3rd ed.; Springer Science + Business Media: Wiesbaden, Germany, 2015. [Google Scholar] [CrossRef]
  84. Schwarzbach, C.; Boerner, R.U. Genetische Algorithmen und Simulated Annealing: Nichtlineare Optimierung am Beispiel der Widerstandsgeoelektrik. Protok. Über Das Kolloqu. Elektromagnetische Tiefenforschung 2001, 19, 168–173. [Google Scholar]
  85. Rudolph, G. Evolutionary Search under Partially Ordered Fitness Sets. Available online: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.407.1778&rep=rep1&type=pdf (accessed on 4 March 2021).
  86. Zitzler, E. Evolutionary Algorithms for Multi-Objective Optimization: Methods and Applications. Ph.D. Thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, 11 November 1999. [Google Scholar]
  87. Nelder, A.; Mead, R. A Simplex Method for Function Minimization. Comput. J. 1965, 7, 308–313. [Google Scholar] [CrossRef]
  88. Dantzig, G.B. Origins of the simplex method. In A History of Scientific Computing; Association for Computing Machinery: New York, NY, USA, 2010; pp. 141–151. [Google Scholar] [CrossRef]
  89. Lagarias, J.C.; Reeds, J.A.; Wright, M.H.; Wright, P.E. Convergence properties of the Nelder–Mead simplex method in low dimensions. SIAM J. Optim. 1998, 9, 112–147. [Google Scholar] [CrossRef] [Green Version]
  90. Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P. Optimization by simulated annealing. Science 1983, 220, 671–680. [Google Scholar] [CrossRef] [PubMed]
  91. Szu, H.; Hartley, R. Fast simulated annealing. Phys. Lett. A 1987, 122, 157–162. [Google Scholar] [CrossRef]
  92. Kennedy, J. Swarm intelligence. In Handbook of Nature-Inspired and Innovative Computing; Springer: Boston, MA, USA, 2006; pp. 187–219. [Google Scholar] [CrossRef]
  93. Imran, M.; Hashima, R.; Abd Khalidb, N.E. An overview of particle swarm optimization variants. Procedia Eng. 2013, 53, 491–496. [Google Scholar] [CrossRef] [Green Version]
  94. Brajdic, A.; Harle, R. Walk detection and step counting on unconstrained smartphones. In Proceedings of the 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp ‘13), Association for Computing Machinery, Zurich, Switzerland, 8–12 September 2013; pp. 225–234. [Google Scholar] [CrossRef]
  95. Wang, Q.; Ye, L.; Luo, H.; Men, A.; Zhao, F.; Huang, Y. Pedestrian Stride-Length Estimation Based on LSTM and Denoising Autoencoders. Sensors 2019, 19, 840. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  96. Ayub, S.; Bahraminisaab, A.; Honary, B. A Sensor Fusion Method for Smart Phone Orientation Estimation. In Proceedings of the 13th Annual Post Graduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting, Liverpool, UK, 25–26 June 2012; pp. 1–6. [Google Scholar]
  97. International Conference on Indoor Positioning and Indoor Navigation, Resources. Available online: https://ipin-conference.org/resources.html (accessed on 31 January 2021).
Figure 1. Building model: (a) structure of the second floor; (b) model section of the grid structure. The walkable indoor areas are represented by yellow pixels, while the areas unlikely to be entered are shown in azure-blue like desks or fixed rows of chairs in the lecture halls. All areas of the building which are not accessible are indicated by blue cells.
Figure 1. Building model: (a) structure of the second floor; (b) model section of the grid structure. The walkable indoor areas are represented by yellow pixels, while the areas unlikely to be entered are shown in azure-blue like desks or fixed rows of chairs in the lecture halls. All areas of the building which are not accessible are indicated by blue cells.
Electronics 10 00618 g001
Figure 2. Workflow diagram for position estimation.
Figure 2. Workflow diagram for position estimation.
Electronics 10 00618 g002
Figure 3. Measurement maps: (a) walkway structure of the indoor area; (b) Bluetooth Low Energy (BLE) fingerprinting based position estimation; (c) map of possible positions based on Wireless Local Area Network (WLAN) fingerprinting; (d) map of magnetic field anomalies.
Figure 3. Measurement maps: (a) walkway structure of the indoor area; (b) Bluetooth Low Energy (BLE) fingerprinting based position estimation; (c) map of possible positions based on Wireless Local Area Network (WLAN) fingerprinting; (d) map of magnetic field anomalies.
Electronics 10 00618 g003
Figure 4. Pedestrian dead reckoning maps: (a) ring of the step size distribution; (b) heading estimation; (c) resulting probability distribution of one step.
Figure 4. Pedestrian dead reckoning maps: (a) ring of the step size distribution; (b) heading estimation; (c) resulting probability distribution of one step.
Electronics 10 00618 g004
Figure 5. Resulting probability distributions: (a) reasoning map after five steps of only wall attenuation; (b) resulting probability distributions after 2, (c) 5, and (d) 20 steps.
Figure 5. Resulting probability distributions: (a) reasoning map after five steps of only wall attenuation; (b) resulting probability distributions after 2, (c) 5, and (d) 20 steps.
Electronics 10 00618 g005
Figure 6. Structure of the Genetic Algorithm: The sequence of selection, recombination, mutation, and substitution is iteratively repeated until a stopping criterion is reached.
Figure 6. Structure of the Genetic Algorithm: The sequence of selection, recombination, mutation, and substitution is iteratively repeated until a stopping criterion is reached.
Electronics 10 00618 g006
Figure 7. Building model with ground truth points (GTP) in red. The test runs started at GTP 1 (black) and ended at GTP 107 (blue). The path taken is approximately 583 steps or respectively 367 s long. The average walking speed was 1.6 m/s.
Figure 7. Building model with ground truth points (GTP) in red. The test runs started at GTP 1 (black) and ended at GTP 107 (blue). The path taken is approximately 583 steps or respectively 367 s long. The average walking speed was 1.6 m/s.
Electronics 10 00618 g007
Figure 8. The optimization process of the normalized fitness values.
Figure 8. The optimization process of the normalized fitness values.
Electronics 10 00618 g008
Figure 9. Position deviation of the evaluation runs for the Samsung Galaxy S7.
Figure 9. Position deviation of the evaluation runs for the Samsung Galaxy S7.
Electronics 10 00618 g009
Figure 10. Position deviation of the evaluation runs for the LG V30.
Figure 10. Position deviation of the evaluation runs for the LG V30.
Electronics 10 00618 g010
Figure 11. Empirical Cumulative Distribution Function of all evaluation runs for the optimized and knowledge-based parameter variants for the corresponding dataset.
Figure 11. Empirical Cumulative Distribution Function of all evaluation runs for the optimized and knowledge-based parameter variants for the corresponding dataset.
Electronics 10 00618 g011
Figure 12. Position deviation of all evaluation runs for the optimized and knowledge-based parameter variants for the corresponding dataset. The red line indicates the median error distances at 1.23 m, 1.73 m, 1.92 m, and 2.50 m. The green line represents the RMSE at 1.98 m, 3.22 m, 2.93 m, and 3.99 m.
Figure 12. Position deviation of all evaluation runs for the optimized and knowledge-based parameter variants for the corresponding dataset. The red line indicates the median error distances at 1.23 m, 1.73 m, 1.92 m, and 2.50 m. The green line represents the RMSE at 1.98 m, 3.22 m, 2.93 m, and 3.99 m.
Electronics 10 00618 g012
Table 1. Features of the GA.
Table 1. Features of the GA.
GA FeatureValue
population size100 random combinations
number of generations100
mutation rate0.05
maximum lifetime5 generations
parent individuals20
elite individuals4
E m a x 1.5
Table 2. Performance analysis. The weights represent the walkway structure, BLE and WLAN fingerprinting, magnetic field anomalies, and step length estimation.
Table 2. Performance analysis. The weights represent the walkway structure, BLE and WLAN fingerprinting, magnetic field anomalies, and step length estimation.
Optimization AlgorithmS7
Metric Value
S7
Time (s)
Determined WeightsLG
Metric Value
LG
Time (s)
Determined Weights
Hill Climbing5490.0910,9250.96;0.64;1;0.36;0.5714.7453790.99;0.99;0.72;0.65;0.57
Nelder-Mead5681.8023731;0.9;1;0.99;0.5715.8414651;1;1;0.86;0.57
Simulated Annealing6704.3711,0440.96;0.77;0.62;0.85;0.5615.8566800.86;0.21;0.50;0.72;0.56
Particle Swarm5280.6672540.62;0.61;0.38;0.73;0.5617.9715,9210.99;0.96;0.32;0.11;0.56
Genetic Algorithm7046.7524,9660.67;0.68;0.83;0.06;0.5617.7816,6010.95;0.73;0.23;0.02;0.56
Table 3. Characteristics of the Samsung Galaxy S7 evaluation runs.
Table 3. Characteristics of the Samsung Galaxy S7 evaluation runs.
Position Deviation (m) (Relative Deviation (%))
Evaluation Run 1Evaluation Run 2Evaluation Run 3
ReferenceOptimizedReferenceOptimizedReferenceOptimized
Max8.514.73 (−44.42%)8.804.47 (−49.20%)8.596.63 (−22.82%)
Mean2.431.57 (−35.39%)2.271.46 (−35.68%)2.671.77 (−33.71%)
Median1.671.21 (−27.54%)1.731.18 (−31.79%)1.781.42 (−20.22%)
RMSE3.171.92 (−39.43%)2.951.76 (−40.34%)3.522.22 (−36.93%)
Table 4. Characteristics of the LG evaluation runs.
Table 4. Characteristics of the LG evaluation runs.
Position Deviation (m) (Relative Deviation (%))
Evaluation Run 1Evaluation Run 2
ReferenceOptimizedReferenceOptimized
Max10.237.40 (−27.66%)8.797.82 (−11.04%)
Mean3.042.36 (−22.37%)3.252.36 (−27.38%)
Median2.301.84 (−20.00%)2.502.08 (−16.80%)
RMSE3.842.93 (−23.70%)4.132.93 (−29.06%)
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Grottke, J.; Blankenbach, J. Evolutionary Optimization Strategy for Indoor Position Estimation Using Smartphones. Electronics 2021, 10, 618. https://0-doi-org.brum.beds.ac.uk/10.3390/electronics10050618

AMA Style

Grottke J, Blankenbach J. Evolutionary Optimization Strategy for Indoor Position Estimation Using Smartphones. Electronics. 2021; 10(5):618. https://0-doi-org.brum.beds.ac.uk/10.3390/electronics10050618

Chicago/Turabian Style

Grottke, Jan, and Jörg Blankenbach. 2021. "Evolutionary Optimization Strategy for Indoor Position Estimation Using Smartphones" Electronics 10, no. 5: 618. https://0-doi-org.brum.beds.ac.uk/10.3390/electronics10050618

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop