Particle swarm optimization–based minimum residual algorithm for mobile robot localization in indoor environment

Abstract

For indoor mobile robots, many localization systems based on wireless sensor network have been reported. Received signal strength indicator is often used for distance measurement. However, the value of received signal strength indicator always has large fluctuation because radio signal is easily influenced by environmental factors. This will bring adverse effect on the distance measurement and deteriorate the performance of robot localization. In this article, the measured data are dealt with weighted recursive filter, which can depress the measurement noise effectively. In the linearization procedure, the least square method often causes additional error because it seriously relies on anchor nodes. Therefore, a minimum residual localization algorithm based on particle swarm optimization is proposed for a mobile robot running in indoor environment. With continuous optimization and update of particle swarm, the position that gets the best solution of objective function can be adopted as the final estimated position. Experiment results show that the proposed algorithm, compared with traditional algorithms, can attain better localization accuracy and is closer to Cramer–Rao lower bound.

Introduction

With wireless sensor networks (WSNs), the localization for indoor mobile robot has become one of the most important research issue. Different devices and methods, such as Ultra-WideBand (UWB), ¹ Bluetooth, ² and camera, ³ have been extensively studied and tested in this field, many of them acquired great progress. However, most of them must rely on special hardware and will cause high expense. Comparatively, the localization methods based on received signal strength indicator (RSSI), which is widely used in WSN system, do not rely on extra hardware device. Therefore, RSSI-based methods have become a popular topic in these years. ⁴ Unfortunately, their accuracy is prone to be influenced by environment noise. As a result, the performance of localization algorithm needs to be improved imminently to obtain satisfactory precision.

Since the fluctuation of wireless signal is caused by environmental interferences during propagation, researchers proposed that measurement compensation should be adopted to reduce errors. Using similarity criteria, Chaurasiya et al. ⁵ proposed a localization scheme based on multidimensional scaling algorithm. Amount of measured distance is converted into position coordinates to improve the localization accuracy in three-dimensional sparse deployment of large-scale environment, but its performance is sensitive to parameter settings and lacks robustness. By introducing the maximum likelihood estimation based on the location probability grid, Kong et al. ⁶ proposed a maximum minimization algorithm that shows favorable performance in non-line-of-sight (NLOS) environment. Tian et al. ⁷ proposed an adaptive localization strategy which is robust to the variation of environmental parameters. In spite of the improvement of the localization accuracy, the algorithm needs more traffic information and energy consumption. For related studies, it is generally assumed that the mean and the variance of measurement noises are accordant to the Gauss distribution in line-of-sight (LOS) environment, while that of NLOS error follows Gauss or uniform distribution. For instance, Wang et al. ⁸ proposed an improved maximum likelihood estimation, called “two-step least square,” to reduce NLOS error and improve the performance effectively. His assumption is that the covariance matrix of measurement noise is known beforehand. Actually, the measurement noise is vulnerable to the surrounding parameters. Li et al. ⁹ proposed that the gradient of the source field can be used, so that a theoretical upper bound on the tracking error can be acquired.

Residual error analysis of position measurement can promote the precision of data processing and target localization. For instance, Chen ¹⁰ puts forward the idea of residual weighted which improves the localization accuracy by using residual error to deal with complex environment condition. Yu et al. ¹¹ proposed a voting matrix–based residual weighted (VM-RWgh) algorithm to mitigate NLOS errors in indoor localization system. The VM-RWgh algorithm can effectively overcome the effects of NLOS errors, even when more than half of the measurements contain NLOS errors. The above methods need abundant prior information and historical data. Based on the relative RSSI and the split-step particle swarm optimization algorithm, Xiufang and Shufang ¹² proposed a WSN localization algorithm, called improved particle swarm optimization–improved received signal strength indicator (IPSO-IRSSI). Combined with the idea of survival of the fittest selection and adaptive weight approach of the optimal objective function, the IPSO-IRSSI algorithm promotes a mechanism of filtration of anchor nodes (ANs) and a particle swarm optimization (PSO) step algorithm. Chan et al. ¹³ proposed a residual test (RT) that can simultaneously determine the number of LOS ANs and identify them. Then, localization can proceed with only those LOS ANs. The RT method works on the principle that when all measurements are LOS, the normalized residuals have a central χ ² distribution versus a noncentral distribution when there is NLOS.

After obtaining the corresponding measurement data or filtering, the position of the target node (TN) can be estimated. For target localization and tracking based on WSN, the algorithms can be divided into two categories, iterative localization algorithm and non-iterative localization algorithm, according to whether the historical information and the Markov transfer model are involved or not. Non-iterative localization algorithms use only current observation data of target position for location estimation, without prior knowledge of environment noise and measurement noise. Typical non-iterative methods include the least square (LS) algorithm, ¹⁴ residual weighted (RWgh) localization algorithm, ¹⁵ and so on. LS does not require the environmental noise parameters to be known in advance. However, for nonlinear localization system, it will generate additional errors and is seriously dependent on the measurement accuracy of ANs. Iterative localization algorithms, such as Kalman filter ¹⁶ and Particle filter, ¹⁷ not only use current observational data but also involve historical observation information for localization estimation. It is necessary to determine the environmental noise and the measurement noise in advance. By simulating appropriate environmental noise parameters, the iterative algorithm can obtain better positioning accuracy. However, it is difficult to obtain the noise parameters in practical application. Furthermore, the noise parameters will change with the time and the environment. Therefore, there are still many limitations in practical application of the iterative localization algorithm.

In recent years, new algorithms, such as deep learning and recurrent neural network, were introduced into the field of WSN localization and obtained excellent performance. For instance, a recurrent neural network is proposed by Li and Qin ¹⁸ to tackle the formulated nonlinear inequality problem defined on a graph in real time, and then the model is applied to range-free localization of WSNs. And, the architecture of the circuit implementation of the neural network for WSN localization is given. Since the feasible solution set to this problem is often infinity and Laplacian Eigenmap is often used as heuristic information to gain better performance, Li et al. ¹⁹ adopted a continuous-time projected neural network and the corresponding discrete-time projected neural network to tackle this problem iteratively. To deal with the variant and unpredictable wireless signals, Zhang et al. ²⁰ proposed a wireless positioning method based on deep learning. The positioning is casted in a four-layer deep neural network structure pretrained by stacked denoising autoencoder that is capable of learning reliable features from a large set of noisy samples and avoids hand engineering.

According to the characteristics of WSNs, we present a novel method for target localization. Since there exists large fluctuation in RSSI measurements, we adopt the weighted recursive filter method to depress the measurement error. Considering the shortcomings of LS algorithm, we propose a minimum residual (minRE) algorithm based on PSO to improve the localization accuracy effectively. Experiment results show that the precision of our algorithm is closer to the lower bound of Cramer–Rao than existing algorithms.

Iterative recursive weighted average filter

In order to reduce the deviation between the measurements and the theoretical data, common method is to use a proper filter. When the target moves, it will create a continuous trajectory. Although the sampling points are discretely distributed, there is certain relationship between the data from adjacent sampling. Therefore, we can effectively use historical information to filter the measurement data.

Signal propagation model

For RSSI, the signal strength will decrease when it travels in the air. At present, the lognormal shadowing model is most widely used for RSSI estimation

$P(d)[dBm]=P(d_0)[dBm]-10n\text{log}\left(\frac{d}{d_0}\right)$

1

where P(d)[dBm] represents the signal strength received by node receivers. P(d ₀)[dBm] is the path loss at reference distance of d ₀. n means the path loss exponent, which is vulnerable to the environment variation. In addition, d represents the distance between two sensor nodes. Generally, d ₀ is assumed to be 1 m. Moreover, the wireless signal propagation model is

$P(d)=P_0-10n\text{log}(d)$

2

Here, P ₀ and n own close relation with environment factors and the hardware configuration of sensor nodes.

Iterative recursive weighted filter

RSSI measurements always fluctuate obviously because it is sensitive to the environment variation and the nodes’ situation. In order to reduce the fluctuation, the iterative recursive weighted filtering (IRWF) algorithm ²¹ is adopted to filter the RSSI measurements in this article.

In short, IRWF uses previous measurement data to filter current measurement. Let $\tilde{P}(t)$ represents original RSSI measurements and $\widehat{P}(t)$ as the filtered RSSI information. The input of IRWF is $\widehat{P}(t-2),\widehat{P}(t-1),\tilde{P}(t)$ , while the output is $\widehat{P}(t)$ .

$\text{Initialization:}\text{Filter}1(1)=\tilde{P}(1);\text{Filter}2(1)=\tilde{P}(1);\text{Filter}3(1)=\tilde{P}(1)$

If (t = 2)

$\begin{array}{l}\text{Filter}1(t)={\beta }_1\tilde{P}(t-1)+{\beta }_2\tilde{P}(t)\\ \text{Filter}2(t)={\beta }_1\text{Filter}1(t-1)+{\beta }_2\text{Filter}1(t)\\ \text{Filter}3(t)={\beta }_1\text{Filter}2(t-1)+{\beta }_2\text{Filter}2(t)\end{array}$

Else

$\begin{array}{l}\text{Filter}1(t)={\beta }_3\widehat{P}(t-2)+{\beta }_4\widehat{P}(t-1)+{\beta }_5\tilde{P}(t)\\ \text{Filter}2(t)={\beta }_3\text{Filter}1(t-2)+{\beta }_4\text{Filter}1(t-1)\\ +{\beta }_5\text{Filter}1(t)\\ \text{Filter}3(t)={\beta }_3\text{Filter}2(t-2)+{\beta }_4\text{Filter}2(t-1)\\ +{\beta }_5\text{Filter}2(t)\end{array}$

End

$\widehat{P}(t)=\text{Filter}3(t)$

Here, [β₁, β₂, β₃,β₄,β₅] are weight parameters that meet β₁ + β₂ = 1 and β₃ + β₄ + β₅ = 1.

minRE localization algorithm

minRE algorithm

Without loss of generality, we assume that there are N ANs and a mobile TN. The distances between TN and ANs are calculated with the RSSI measurements. If these measurements have no deviation, the measured distance can be employed by trilateration method to compute the target position. However, the measured distances usually show large deviation because it is easily influenced by complex factors such as hardware configuration, ranging mode, and environment conditions. When all measured distances are smaller than real distance, there will be no intersection area. If some measured distances are larger and others are smaller than real distance, it is hard to determine whether there exists intersection area or not. The minRE localization is to find a position where the minimum sum of measurements’ squared residual can be obtained. Finally, the coordinates of this point can be used as the estimated location of the target.

Let the position of AN _i be (x_i , y_i )(i∈(1,2,…, N)) and the position of TN be (x, y). The measured distance between AN _i and TN is defined as

$d_i^{\text{mes}}=d_i+{\omega }_i$

3

where d_i represents the real distance and ω_i represents measurement noise that is difficult to obtain due to the influence of complex factors.

According to the principle of minRE localization, the sum of target’s squared residual can be formulated as a fitness function

$f(X)={\displaystyle \sum _i^N{\left\{\left|\right|X-{\text{AN}}_i\left|\right|-d_i^{\text{mes}}\right\}}^2}$

4

where ||X − AN _i || represents the Euclidean distance between X and AN _i .

$\left|\right|X-{\text{AN}}_i\left|\right|=\sqrt{{(x-x_i)}^2+{(y-y_i)}^2}$

5

If there is no measurement error, then

$\underset{w_i\to 0}{\text{lim}}f(X)={\displaystyle \sum _i^N{\left\{\left|\right|X-{\text{AN}}_i\left|\right|-d_i^{\text{mes}}\right\}}^2}={\displaystyle \sum _i^N{\left\{\left|\right|X-{\text{AN}}_i\left|\right|-d_i^{ }\right\}}^2}$

6

When $\underset{w_i\to 0}{\text{lim}}f(X)=0$ , the position X must be the target’s real position if there are enough noncollinear anchors. However, with measurement error, generally there is f(X) > 0. As f(X) comes closer to 0, the position X is closer to real position of the target. Therefore, at a given time step t, the X which achieves minimum f(X) can be regarded as the estimated location of target.

$X=\text{arg}\text{min}f(X)$

7

PSO algorithm

As an efficient stochastic search algorithm, PSO employs multiple particles to simulate the targets’ location. In the search space, every particle adjusts its velocity and position according to the flying experiences of history, so that the whole swarm gradually approaches the best solution. ²²

For the sake of convenience, we define some symbols. Let pbest represents the best fitness of each particle, while gbest represents the global best fitness. The position of ith particle is represented by x_i = (x_{i 1}, x_{i 2},…, x_iD ), while the velocity of ith particle is represented by v_i = (v_{i 1}, v_{i 2},…, v_iD ), 1 ≤ i ≤ m, and 1 ≤ d ≤ D. The historical optimal position of the particle swarm is represented by p_g = (p_{g 1}, p_{g 2},…, p_gD ). Here, we assume that the swarm owns m particles which simulate and search the target position.

The position and velocity of particles are updated as following

$v_{id}^{k+1}=\omega v_{id}^k+c_1\xi (p_{id}^k-x_{id}^k)+c_2\eta (p_{gd}^k-x_{gd}^k)$

8

$x_{id}^{k+1}=x_{id}^{k+1}+v_{id}^{k+1}$

9

where ω is the inertia weight that controls the exploration of local and global search region. The larger ω is, the stronger the local search ability of the particles becomes. The smaller ω is, the stronger the ability of spatial search becomes. c ₁ and c ₂ are acceleration constants between 0 and 2. ξ and η are random numbers between 0 and 1.

minRE localization algorithm based on PSO

From “minRE localization algorithm based on particle swarm optimization” section, we can know that the minRE localization algorithm is a function for solving unconstrained optimization problem

$X=\text{arg}\text{min}f(X)=\text{arg}\text{min}{\displaystyle \sum _i^N{\left\{\sqrt{{(x-x_i)}^2+{(y-y_i)}^2}-d_i^{\text{mes}}\right\}}^2}$

10

Here, (x_i , y_i ) represents the position of AN, AN _i, while (x, y) represents the position of TN X.

Assuming that the number of particles is M and the maximum iterations is W, the solution of PSO-minRE localization algorithm can be described as following:

Step 1: Initialization

We use parameter w to denote the index of the particle updating iteration. Therefore, there is w = 1 in the initialization step. And, parameter m is used to denote the index of particle.

The particles and their initial velocity are generated randomly within the target environment

$X_m^1=[x_m^1,y_m^1,z_m^1]$

11

$V_m^1=[v{x}_m^1,v{y}_m^1,v{z}_m^1]$

12

The mth particle’s fitness $f(X_m^1(t))$ is calculated and regarded as the initial individual best value it has achieved so far

$B_m^1=X_m^1$

13

Meanwhile, the initial global best fitness of particle swarm is the particle which achieves minimum f(X). It can be descripted as

$B_g^1=\underset{m=1:M}{\text{arg}\text{min}}f(X_m^1)$

14

• Step 2: Update particles at wth iteration (2 ≤ w ≤ W)

According to the individual best and the global best, the particles’ velocity and position can be updated as

$V_m^w=\omega V_m^{w-1}+c_1\xi (B_m^{w-1}-X_m^{w-1})+c_2\eta (B_g^{w-1}-X_m^{w-1})$

15

$X_m^w=X_m^{w-1}+V_m^{w-1}$

16

Here, ω, c₁, c₂, ξ, and η own same meaning as equations (8) and (9) in “PSO algorithm” section.

Step 3: Update the optimal particle and optimal swarm

$B_m^w=\{\begin{array}{l}{B}_m^{w-1}\begin{array}{cc},& f(X_m^w)>f(B_m^{w-1})\end{array}\\ X_m^w\begin{array}{cc},& f(X_m^w)\le f(B_m^{w-1})\end{array}\end{array}$

17

$B_g^w=\{\begin{array}{cc}{B}_g^{w-1},& \underset{m=1:M}{\text{min}}f(X_m^w)>f(B_g^{w-1})\\ \underset{m=1:M}{\text{arg}\text{min}}f(X_m^w),& \underset{m=1:M}{\text{min}}f(X_m^w)\le f(B_g^{w-1})\end{array}$

18

• Step 4: Check for stopping criterion

If the iteration index w < W, set w = w + 1 and go to Step 2. Otherwise, the desired target position can be estimated

$\tilde{X}(t)=B_g^W$

19

Experiment results and analysis

Experimental environment is set as 10 × 6 m² in our laboratory. There are total 27 seats arranged in four rows. Two rows are along the wall and the other two rows are in the center of the room. Five ANs are located at AN1(8, 1), AN2(1, 1), AN3(1, 5), AN4(8, 5), and AN5(4.5, 3). The target trajectory consists of three line segments and two sharp turns. Its length is 16 m. Sampling frequency is set as f = 2 s⁻¹. The layout of environmental space is shown in Figure 1. To avoid the noise and disturbance near the ground, these five ANs are mounted on the tripods 1.6 m high. All these ANs are ZigBee nodes with 8-bit microcontroller and 2 dB antenna. One ZigBee node is carried by iRobot and acts as the mobile target. Its speed is M_v = 1 m s⁻¹. Experiment suite is shown in Figure 2.

Figure 1.

Environment deployment.

Figure 2.

Experiment suite. (a) ANs and (b) TN. AN: anchor node; TN: target node.

Distance measurement analysis

In the experiment, we firstly get the RSSI data among the nodes. Taking the AN, AN1 and AN2, as an example, the initial measurement data are shown in Figure 3. As we can see, there is large fluctuation.

Figure 3.

RSSI measurement after IRWF. (a) AN1 and (b) AN2. RSSI: received signal strength indicator; IRWF: iterative recursive weighted filtering; AN: anchor node; TN: target node.

Compared with the environment layout in Figure 1, we can find that the signal strength becomes weak when the target moves away from the AN. When the target moves toward the AN, the signal strength becomes strong. In other words, RSSI decreases when the distance increases. On the whole, the measured value follows the real trend but the fluctuations can be seen obviously. If these fluctuations are not handled properly, there will be large error when RSSI model is used to calculate the distance.

In this article, the IRWF algorithm is used to filter the initial RSSI value. Since the weights in IRWF have significant influence on the filtering result, it is necessary to make analysis with different parameters. The evaluation index is that the mean error between the filtered RSSI and the measured RSSI is close to 0, while the filtered curve owns small fluctuations. We did experiment for 100 times to determine the weights value. Then, we get β₁ = 0.1, β₂ = 0.2, and β₃ = 0.7. As the result shown in Figure 3, the fluctuations of the measured value are effectively weakened by the IRWF algorithm. Stable filtering result can be acquired while the changing trend of the curve is kept well.

For AN1 and AN2, the distance estimation based on the RSSI model is shown in Figure 4. Compared with the method to use originally measured RSSI value, the result with IRWF filter is obviously more accurate. Figure 5 gives a comparison of the estimation error between unfiltered method and iterative filtering method. As shown in Figure 5, 80% distance error fall into the range of [−2, 2]. The filtered mean error and the mean square error are 1.3 and 1.5 m, respectively. However, corresponding value of the unfiltered situation is 2.1 and 2.4 m, respectively. Therefore, through the IRWF algorithm, we can improve the accuracy of the distance estimation and make a solid foundation for better target localization.

Figure 4.

Distance estimation based on RSSI measurements. (a) AN1 and (b) AN2. RSSI: received signal strength indicator; AN: anchor node; TN: target node.

Figure 5.

Error analysis of the measured distance. (a) Localization error and (b) CDF: Cumulative distribution function.

Localization estimation based on proposed algorithm

When the distance between AN and TN is calculated, we can get the node position. In this article, comparative experiment is implemented among the LS algorithm, residual weighted (RWgh) algorithm, and the proposed PSO-minRE algorithm. Furthermore, the localization result is compared with the Cramer–Rao lower bound (CRLB), ²³ which is a metric of unbiased estimation that usually used as the performance reference for localization algorithms. The experiment was repeated for 10 times to get average value for evaluation. To make a vivid scenario of indoor service, the mobile robot (TN) moved along the trajectory as shown in Figure 1. We set 33 sampling points on the trajectory for RSSI measurement. At every sampling point, the RSSI value was measured for 12 times and then was recorded with sequential number. Therefore, we collected 120 data at each sampling point. Then, the data are processed on PC to get the localization result. Since the proposed algorithm is not an iterative one, this equals to do the experiment for 120 times.

To depict the localization scenario, we take 1 of the 10 experiments as an example. As shown in Figure 6, the localization results of LS and RWgh have large deviation, while the proposed algorithm is closer to real position.

Figure 6.

Comparison of localization results. (a) LS algorithm, (b) PSO-minRE algorithm, and (c) residual weighted algorithm. LS: least square; PSO: particle swarm optimization; minRE: minimum residual.

Corresponding to Figure 6, the localization error is shown in Figure 7. We can see that the localization error of the proposed algorithm is closer to CRLB than LS and RWgh algorithm. The statistical results of all the 10 experiments are given in Table 1. Compared with LS and RWgh, the localization accuracy of the proposed algorithm is improved significantly. According to Figure 7 and Table 1, the proposed PSO-minRE algorithm owns more stable performance in indoor environment. Since the trajectory consist of straight line and sharp turn, we can draw the conclusion that the proposed algorithm’s performance can meet real requirement well because the robot always moves on continuous path.

Figure 7.

Localization error of various algorithms. (a) Localization error and (b) cumulative error distribution.

Table 1.

Localization error statistics.

Algorithm	Mean error (m)	Max error (m)	Mean square (m)
LS	1.10	3.1	0.51
Residual weighted	1.05	2.8	0.85
PSO-minRE	0.70	1.8	0.14

LS: least square; PSO: particle swarm optimization; minRE: minimum residual.

Conclusion

The research and application of target localization based on RSSI have been widely studied in WSN. Since RSSI is sensitive to environmental factors, we firstly filtered the measurement to effectively reduce the measurement error. Then, the localization algorithm based on PSO-minRE is proposed to overcome the dependence of LS algorithm upon the distance measurement and transform the localization procedure into an optimization problem. Experiment was implemented to verify and analyze the performance of the proposed algorithm. In addition, although the proposed has high precision, it will cause computational complexity. Therefore, it is necessary to improve the computational efficiency when applied on large-scale sensor networks.