Abstract

In this study, we proposed a new way to localize mobile robots in a very noisy environment. The mobile robot is equipped with an active RFID reader and some tags are placed in the room to provide RF Beacons in order that the robot can localize itself with the known tag geographical locations. The RFID equipments are working in 916 MHz band and the tags are battery enabled so the range of the experiment can effectively increase to 50 m. First there is a model estimated for the noise in the environment, which can be expressed as a Gaussians distribution then the RFID propagation model is obtained from a series of experimental tests. There are two different methods for noisy data filtering, Kalman Filtering as the best ever used method and a new method of particle filters with expectation maximization core. The diversity and multi-path effects in this experiment were considered as unwanted signal effects. The results show a good convergence in the EM method after very low iterations. The advantage of the EM method to Kalman filtering is not relying on the initial values. The precision of this new method in a normal environemt is between 4-7 cm in >10 iterations.

---

INTRODUCTION

There are different methods to localize a mobile robot. The most famous method is GPS, which is limited to outdoor environment as the property of satellites line of site.

There are some other ways using wheel encoders, Gyros and accelerometers, which can measure and calculate Robot movements or rotations and as the results its relational location. But most of these methods are valid just for short ranges and there is no judgment of the accuracy of the location estimation after some moves. For example, tropological landmark system (Leonard and Whyte, 1991) can sense some marks on the ground with special camera, laser or sound waves, but this requires a high precision of installing marks over the ground and with any reason the sensation can be blocked so the Robot may loose the marks and restoring the right path may be a hard work.

The most localization problems have used bayes algorithms (Fox et al., 2003) for filtering the data, which these algorithms are suitable for application with ideal sensors without any internal errors. The best accuracy values for localizations in all experiments does not <5 cm (Deans and Herbert, 2008).

In this study, we propose a new method to localize the mobile robot by means of estimating the distance between the robot and Radio Tags put in the environment with known fixed or random geometry (future work). The distance to each radio Tag is estimated by its received signal strength in the robot. The advantage of radio localization is not relying on the line of sight between the robot and the tags so the method may be applied in the environments even with lots of blockings. As the proposed way uses RFID active tags with memory inside, the problem of relativity is already solved, which means that the estimated distance of each tag is exactly related to a specific tag and may not be misrelated to others.

In this study, there are two series of data; one is the real location and of the mobile robot which is obtained by a grid environment with 10 cm square houses. The second data is obtained by the measurements of RFID sensors and related algorithms.

In the 1st step, there is a precise analysis of the Noise model in the environment and with assumption of such a noise model and a known propagation model the localization algorithm is applied to the data.

Kalman filtering has shown suitable and acceptable results in the past experiments especially in a noisy environment (Kantor and Singh, 2002), so this algorithm can be the reference of the test results.

The Kalman filter algorithm is very sensitive to sensor internal noises and the initial parameters have a vital affect on the results (Kurth et al., 2003).

Noise modeling and measurement validity limits: Before the main experiment, we have to obtain a true model of the Noise in the environment and to define where are the boundaries of the validity of each tag read RSSI (Received Signal Strength Indicator).

So, the mobile robot which is equipped with a RFID reader is located to different known distances to a typical Tag and with much iteration the RSSI is recorded per each distance and the error of each read value is obtained. Some typical record errors are shown in the Fig. 1.

As shown in Fig. 1 for example in 12.8 m distance there are 300 read values, which the number of read records is shown in horizontal axis and the distance measurement error is shown in the vertical axis. These figures will propose that the error figure is very similar to a Gaussian distribution curve. So, we will suppose the noise model a Gaussian noise model.

With this assumption, we can assume the error with a variance and mean value for a Gaussian distribution. All experiments will be recorded as the mean value and the covariance will show the uncertainty of each read record series. Figure 2 and 3 show the mean and variance of each measurement. In the Fig. 2, it shows that in the distances <3 m and >21 m the variance are high so the measurements have lost their validity in these limits.

But note that these measurements are done for a typical environment and this offline test must be done per each experimental environment.

RFID propagation model analysis: As the RFID tags and reader used in this experiment are working in 916 MHz frequency channel, a propagation model in the similar project (Seidel and Rappaport, 1992) with the similar frequency band in indoor environment is used for this aim.

According to this model, each read RSSI value has the following relation with distance between the tag and the reader: RSSI α PT.dⁿ While, the PT is the received voltage of the sent signal, d is the distance between the transmitter (reader) and the receiver (TAG) and nε (-2, -0.1).

This is an ideal model for propagation, while many parameters such as multi-path, electromagnetic noise and device internal noise are affecting this model. The Eq. 1 can be expressed more precise with Eq. 2.

 

Fig. 1:	Some histograms of errors in read RSSI

 

 

Fig. 2:	Means of measurements and real distance

 

 

Fig. 3:	Variance of the measurements

 

(1)

While,

 

RSSI I->j	=	The RSSI read in node j when the signal transmitted from i
PTi	=	The voltage of the signal when sent from i
dij	=	The distance between i and j as we are looking for dij, the equation can be expressed like as:

 

(2)

The a_i can be supposed equal to 1 for more simplicity. The errors are identified as the following terms:

(3)

In a real indoor experiment with 14 tags and a reader the read RSSI in different distances are shown in Fig. 4.

As shown in Fig. 4, finding a linear relation between RSSI and distance is impossible. It is remarkable that the best values for parameter n according

 

Fig. 4:	The relation of RSSI and distance

 

 

Fig. 5:	The estimated distance validity with real distance in the experiment

 

to Nguyen and Rattentbury (2008) is not valid for this test as the best values is between -0.5 to 0.2 here. So, the propagation model in Eq. 4 must be change back to Eq. 5:

(4)

With assumption of this equation as our propagation model, the following values are obtained:

Although, these values show that the model in Eq. 5 fits more our experiment but still does not explain why the estimated distances are not identical to the RSSI. The reason of such error can be explained according to Fig. 5.

The Fig. 5 shows that the error follows a rule in all readings: the lower distances are over estimated and the higher distances are under estimated.

The Fig. 5 explicitly shows that the experiment done on 16 tags, which are located in 4x4 rows obeys a pattern for error in distance estimation.

 

Fig. 6:	The standard deviation of iterations and the means

 

 

Fig. 7:	The calculated relation between RSSI and distance (green)

 

In this Fig. 5, the read data are categorized in clusters in horizontal direction. A mean value for each cluster is shown as a black horizontal line in each cluster. The slope line in black shows the best line fitting of all means. All of overestimations are illustrated in Fig. 5.

To obtain an arithmetic model from the experiments, we consider the following downward exponential Eq. 5:

(5)

This is a general equation, which its parameters a and b must be estimated with a weighted non linear regression. The formula for non linear regression is:

(6)

In this experiment, the weights are the inverse of standard deviation of the experiments:

(7)

In the Fig. 6, this standard deviation obtained from the real experiment is shown.

With the above assumptions and the regression formula there will be a valid model for the relation between RSSI and distance:

x = 1/b log. (u-y/a)

In the Fig. 7 this relation is shown.

 

Fig. 8:	Robot location and tags installed in the environment

 

MATERIALS AND METHODS

The required data for this test is obtained from a mobile robot moving on a grid surface with 10x10 cm houses. There is a RFID reader installed on this robot with its antenna which communicates with tags located around the surface. The data is read with a laptop connected to the reader via a serial cable. When a tag answers to the call of the reader, its RSSI from that specific TAG is transmitted to the host computer (laptop). While, according to the theory introduced in the previous study, there is a expectation that the read RSSI of each tag has a nonlinear relation with the correspondence distance, the RSSI is converted to its relevant distant in meter according to Eq. 8.

The tags are installed in the height 45.7 cm from the ground, which is the height of the antenna of the robot. The environment of the experiment is a 4x5 m room. The tags are located around the room with 1 m distance of each other as shown in Fig. 8. The robot is programmed to move in a pre assigned path.

RESULTS AND DISCUSSION

Trilateration for geometric localization: Now with the method RFID propagation model analysis, we can estimate robot distance from each Tag with a Guasian error model assumption.

The distance of the robot from a single tag can not lead us to the geometry of the robot. But distances to each three Tags can help us to calculate the location of the robot with Trilateration method (Awad et al., 2007). The Fig. 9 illustrates the method. Here, the robot location is B, which is unknown and to be calculated. There are three tags located in P₁-P₃. Distances r₁-r₃ are known. So B (x, y, z) can be calculated by:

 

Fig. 9:	Trilateration method to calculate geometry

 

 

 

With the x-z calculated from each three tag from 14 total tags there are 364 probabilities of robot location:

These 364 values can supposed as a probability cloud, which is showed in Fig. 10.

Expectation maximization method for robot location identification: As the noise model in the environment is supposed as a Gussian noise according noise modeling and measurement validity limits, The probability cloud of the robot location can be supposed as a Gussian probability function too.

To estimate the location of the robot in this probability cloud, first the density of the cloud must be approximated. The density function of this cloud Matrix in one coordination is Zhang et al. (2008):

 

Fig. 10:	Probability cloud of the robot location

 

 

Fig. 11:	The robot location with Kalman Filter Mean and with EM Method

 

 

 

So, the aim of EM method is maximizing the above equation per all values for x:

We suppose a z value as:

The above function is a Normal distribution function with a known mean and covariance:

The proposed algorithm to maximize the above function is:

•	Let θ(0) be an initial solution

•	Repeat the following two steps for t = 0, 1, 2,…

•

E-step:

•	Calculate the expectation value of log-likelihood of complete data conditioned by observed sample and the current solution θ(t)

(8)

where the summation is taken over all samples

•

M-step:

•	Let θ(t+1) be such θ that maximizes Q (θ|θ(t))

With the proposed formula and the method in all three coordinations, the density of the probibilty function will be calculated. The calculated value for the experiment can be shown in the Fig. 11.

As shown in Fig. 11, the obtained value with EM method is very close to the value calculated with mean value of the probibilty matrix. This neighborhood shows the validity of the method results in an ideal environemnt.

But as this method follows the Guassian probibility characteristics all probable noise effects, which are Guassian are considered while the simple mean method does not defeat such effects.

CONCLUSION

The noise modeling of an indoor environment and validation of read data shows that the noise model obeys a rule with a Guasian characteristic. The propagation model of the signals with 916 MHz frequency in the environment is obtained exactly with a weighted least square regression and validates the ranges of the read model with a guasian model. At last, the density of the probailbity cloud from tralateration iterations of each three tag can be found with EM method. This method is exactly applicable to a model to find the mean value when the model is obeying Gusian characteristics.

The experimental resuls shows a neighborhood with Kalman filter method result value and showed very close values to the real measured robot location on the grid surface.

The precision of this method with normal environemt is between 4-7 cm in >10 experiments.

How to cite this article:

Akbar Ghahri and Mohammad Ali Nekoui. Localization of Mobile Robots with RFID Technology and Expectation Maximization Algorithm.
DOI: https://doi.org/10.36478/ijssceapp.2009.8.14
URL: https://www.makhillpublications.co/view-article/1997-5422/ijssceapp.2009.8.14