Precise Localization of Mobile Robots via Odometry and Wireless Sensor Network

Abstract

Precise localization of mobile robots in uncertain environments is a fundamental and crucial issue in robotics. In this paper, to deal with the unbounded accumulated errors of dead reckoning (DR)-based localization, wireless sensor network (WSN)-based localization is applied to calibrate the uncertainty of odometry using a Kalman filter (KF). In addition, to further aid in obtaining precise positions and reduce uncertainty, a novel backward dead reckoning (BDR) localization approach is proposed. The experimental results demonstrate the success and reliability of the proposed method.

1. Introduction

A fundamental problem for an autonomous mobile robot is knowing its current position and orientation by sensorial observation and previous accurate localization and it is a popular research topic in the mobile robot community [1]. Although global positioning system (GPS) is suitable for mobile robot localization in outdoor environments, it is difficult to use in an indoor environment. Furthermore, because a large proportion of the robots are designed for indoor use, this represents a severe limitation on the application of mobile robots [2].

A common and basic localization method called dead reckoning (DR) is used to estimate the position by counting wheel rotations with the help of encoders. An encoder is a kind of simple and important sensor and is mounted on most mobile robots with wheels. However, there are unavoidable accumulated errors for DR-based localization over long distances, in that it needs to utilize the previous position to estimate the next relative one and during which, the drift, the wheel slippage, the uneven floor and the uncertainty about the structure of the robot will together cause errors [3]. Since the uncertainty of dead reckoning must be compensated for by precise localization, combining this technique with external sensors and odometry has become a new trend [4].

Landmarks are now commonly used to assist the dead reckoning method in precise localization. The positions of landmarks are already known and they can be used for mobile robots to clear the accumulated errors of odometry. One kind of these landmarks is natural signals [5–7]. Researchers have implemented various electronic devices to capture the characteristics of natural signals. Although these methods are capable of reducing the uncertainties of position estimation, the landmarks generally require a regular shape or other regular characteristics, which is difficult in practical applications. In addition, expensive sensors are also necessary for the feature extraction of the environments. The other kind of landmark is man-rated devices [2, 8, 9–11]. Obviously, it is simpler for sensors to capture the characteristics of man-rated landmarks than using natural signals, but it is rather difficult to transplant these landmarks to an unknown environment.

In recent years, the use of wireless sensor network (WSN) has been increasing in importance in smart buildings, industrial fields and other areas of application [12, 13]. WSN is a crucial element of distributed control systems and is used for the measurement and monitoring of temperature, humidity, light and other environmental parameters. In this paper, WSN is utilized as an assistant for dead reckoning in localization systems, which can be easily implemented by adding a localization function to the WSN that is already installed in many buildings.

WSN-based localization has been studied widely in wireless communication in the past decades. There are generally three kinds of distance measurement methods: received signal strength indication (RSSI), time of arrival (TOA) and time difference of arrival (TDOA) [14–16]. Both TOA and TDOA depend highly on precise time measurements of radio signals and precise time synchronization of nodes. So we choose the RSSI solution to estimate the distance between the reference nodes and the mobile robot (which is also called the blind node here). Based on the distance obtained by WSN, we can obtain the position of the mobile robot with a RSSI-based localization algorithm. For the hardware of WSN studied in this paper, we utilized Zigbee CC2431/2430 modules produced by Texas Instruments. Zigbee is a wireless network communication standard based on the IEEE 802.15.4 and is low-cost, low power consumption, low data rate, has a strong networking ability and other advantages. Therefore, Zigbee is suitable for most applications and large amounts of Zigbee nodes can be used in practice. So it is highly feasible to extend the overlapping area of WSN by utilizing Zigbee, which could better assist the DR method in localizing mobile robots with a higher precision over long distances. Dead reckoning is a kind of relative localization method that has an unbounded accumulated error, while the localization via WSN is a kind of absolute localization method whose error is limited to a certain range. The complementary characteristics of these two approaches make their fusion theoretically feasible and practical.

The rest of this paper is organized as follows. The next section discusses the issues of DR-based localization and the analysis of the accumulated localization errors. Section 3 describes how to calibrate the errors of dead reckoning using Zigbee-based localization and a backward dead reckoning (BDR) method is proposed to further reduce the localization uncertainties. In Section 4, several groups of simulated experiments and real experiments are presented which test the proposed localization methods in detail. Conclusions are given and future works suggested in Section 5.

2. Problem Formulation

In this section, the statement of the problem and the DR-based localization is introduced and discussed. Then the motivation of applying WSN to reduce the odometry errors for more precise localization is discussed.

2.1. Statement of the Problem

As mentioned above, it is difficult for mobile robots to localize themselves in an unknown indoor environment. To simplify the indoor localization problem, the environments are classified into two typical kinds. One is a single room environment as shown in Figure 1, where the structure is simple and there are few barriers. As shown in Figure 2, the other kind of environment is relatively more complicated and a mobile robot will have to move across several rooms, which requires a higher accuracy of localization over long distances. The problems studied in this paper focus on how a mobile robot can obtain its current location and its previous trajectory precisely, in both of these two typical kinds of indoor environments with a known starting point.

Figure 1.

Single room environment

Figure 2.

Complicated environment with several rooms

2.2. DR-based Localization

As shown in Figure 3, a differential-drive mobile robot is used in our research. It has two encoders mounted on both wheels, respectively. When a wheel rotates 360°, 20 pulses will be detected, so the resolution of the encoder is 10.0mm with a wheel-diameter of 64mm.

Figure 3.

The differential-drive mobile robot

As shown in Figure 4, we define coordinate $xoy$ as the world coordinate system of the external environment. The position of the robot at the ${\mathrm{k}}^{th}$ sampling step is denoted as vector ${\mathrm{P}}_{\mathrm{k}}=[{\mathrm{x}}_{\mathrm{k}},{\mathrm{y}}_{\mathrm{k}},{\theta }_{\mathrm{k}}]$ , where ${\mathrm{x}}_{\mathrm{k}}$ , ${\mathrm{y}}_{\mathrm{k}}$ are the two-dimensional coordinates and ${\theta }_{\mathrm{k}}$ is the orientation of the robot with regards to the coordinate $xoy$ .

Figure 4.

Demonstration of DR scheme (a) The schematic structure of the mobile robot (b) World coordinate system and robot-centred coordinates (c) Model of DR-based localization

Meanwhile, we define $\mathrm{x}\prime \mathrm{o}\prime \mathrm{y}\prime$ to describe the robot-centred system, and ${\mathrm{P}}_{\mathrm{k}}\prime =[{\mathrm{x}}_{\mathrm{k}}\prime ,{\mathrm{y}}_{\mathrm{k}}\prime ,{\theta }_{\mathrm{k}}\prime ]$ stands for the displacement and orientation of the robot in relation to the coordinates $\mathrm{x}\prime \mathrm{o}\prime \mathrm{y}\prime$ . In the world coordinate system, the relative displacement $\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}}$ and orientation $\mathrm{\Delta }{\theta }_{\mathrm{k}}$ of the robot between two sampling steps can be described as follows [1]:

$\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}}\text{=}\frac{\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k},\mathrm{r}}^{\prime }+\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k},\mathrm{l}}^{\prime }}{2}$ (1) $\mathrm{\Delta }{\theta }_{\mathrm{k}}\text{=}\frac{\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k},\mathrm{r}}^{\prime }+\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k},\mathrm{l}}^{\prime }}{\mathrm{L}}$ (2)

where $\mathrm{\Delta }\mathrm{d}{\prime }_{\mathrm{k},\mathrm{r}}$ , $\mathrm{\Delta }\mathrm{d}{\prime }_{\mathrm{k},\mathrm{l}}$ stands for the relative displacement of the right wheel and the left wheel of the mobile robot respectively, which are measured by encoders installed on each wheel of the robot. L is the distance between the centres of the two wheels. Hence, for the sampling step k, $\mathrm{k}\text{=1,2,3,}\dots \text{,n}$ , we can obtain the following equations to describe the position of the robot:

${\mathrm{x}}_{\mathrm{k}+1}\text{=}{\mathrm{x}}_{\mathrm{k}}+\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}}\cos ({\theta }_{\mathrm{k}}+\frac{\mathrm{\Delta }{\theta }_{\mathrm{k}}}{2}\text{)}$ (3) ${\mathrm{y}}_{\mathrm{k}+1}{\text{=y}}_{\mathrm{k}}+\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}}\sin ({\theta }_{\mathrm{k}}+\frac{\mathrm{\Delta }{\theta }_{\mathrm{k}}}{2}\text{)}$ (4) ${\theta }_{\mathrm{k}+1}={\theta }_{\mathrm{k}}+\mathrm{\Delta }{\theta }_{\mathrm{k}}$ (5)

Therefore, given the previous position, the next position can be worked out according to equations (1)~(5)). However, we also discover that if there is a small error in any step of the DR localization, the calculation of the next position is inevitably influenced and finally leads to a fairly large deviation between the actual position and the result. Figure 5 shows the expected trajectory of the robot and the estimated trajectory with the DR-based measurement errors.

Figure 5.

DR-based localization with and without errors

Research has shown that there are systematic errors and non-systematic errors in the DR-based localization [3]. The systematic errors are caused by (a) unequal wheel diameters, (b) uncertainty about the effective wheelbase, (c) the limited encoder resolution and the limited sampling rate. The non-systematic errors contain (a) different toughness of the floor, (b) wheel-slippage due to slippery floors, over-acceleration or fast turning. Since the non-systematic errors are unexpected, there can still be no perfect solution to totally eliminate the errors of odometry.

To simplify the real trajectories of mobile robots, two kinds of behaviours of mobile robots are modelled in this paper: moving forward and rotation. In the following experiments, the errors resulting from the resolution of the encoders are neglected.

For the behaviour of moving forward, the robot's working space is defined in the $xoy$ world coordinate with the positions $(\mathrm{x},\mathrm{y})$ . As Figure 6 shows, when the robot moves in a real trajectory $OA$ , the DR localization method gives an estimated trajectory $OB$ . For different lengths of $OA$ , the deviation between point B and point A in x and y coordinates are different, the model of which follows the normal distribution $\mathrm{\Delta }~\mathrm{N}(\mu ,{\sigma }^2)$ . As shown in Table 1, the average deviation μ increases as the length of $OA$ increases. The increasing variance ${\sigma }^2$ indicates that the uncertainty of the DR localization method also increases.

Figure 6.

Trajectory of the moving forward behaviour

Table 1.

Normal distributions for different lengths of moving forward

Length of OA	μ x	σ 2 x	μ y	σ 2 y
1m	−0.02	0.0002	−0.068	0.0001
2m	−0.15	0.0004	−0.074	0.0002
3m	−0.33	0.0032	−0.095	0.0004
4m	−0.55	0.0022	−0.135	0.0010
5m	−0.91	0.0041	−0.136	0.0044

For the behaviour of rotation, the robot goes straight toward the turning point T first (as Figure 7 shows), and then makes a turn of 30°, 60°, 90°, 120°, 150° and 180°. In Figure 7, the real turning angle θ is different from the estimated turning angle $\theta \prime$ given by the DR-based localization method. As for the stochastic errors, the difference between these two angles also follows the normal distribution, $\mathrm{\Delta }\theta ~\mathrm{N}({\mu }_{\theta },{\sigma }_{\theta }^2)$ . Table 2 gives their specific values according to real experiments.

Figure 7.

Demonstration of rotation errors

Table 2.

Normal distributions for different rotation angles

Turning Angles	μΔθ	σΔθ2
30°	0.35	2.11
60°	−2.45	2.14
90°	−7.8	2.62
120°	−17.8	3.13
150°	−18.94	3.62
180°	−20.54	2.54

Both the errors of moving forward and rotation are modelled independently. In the simulated experiments, they are dealt with separately to obtain the distinct error model before being combined together. In addition, for long distances, the accumulated error is calculated by linear interpolation based on the experimental measurement data and then this error will be carried forward to the next segment.

Generally DR-based localization is not suitable for the localization of mobile robots when the room is large enough or the robot moves across many separate rooms. Thus, the key to obtaining precise locations is to reduce the accumulated errors by using other sensors. The existing WSN in most smart buildings, factories and many other fields is capable of providing different localization information to help calibrate the DR localization. Therefore, the next section will present an effective approach to combining the WSN and DR-based localization for mobile robots.

3. Calibration of DR Errors via Zigbee-based Localization

In this section, the overall system which combines DR and WSN-based localization is proposed. Then the WSN-based localization is discussed in detail. Finally, the data fusion using a Kalman filter is presented and, for higher accuracy, a novel backward dead reckoning localization algorithm is proposed.

3.1. Overall Localization System

To eliminate the accumulated errors of DR, a WSN-based localization method is utilized in the localization system. In Figure 8, the size of the circles stands for the range of errors. The errors of WSN-based localization are relatively static, while that of DR-based localization become larger and larger along the robot's trajectory. In order to merge these two kinds of localization information from DR and WSN, a Kalman filter is adopted for sensor fusion and is used to reduce the uncertainty of localization. Then the fused position is used to update the previous estimation of the positions. The proposed algorithm called the backward dead reckoning-based localization method is demonstrated in Figure 9.

Figure 8.

Sketch of the proposed localization approach

Figure 9.

The overall localization system with the proposed back dead reckoning algorithm

In Figure 9, part (a) stands for the real trajectory of the mobile robot from step 1 to step k. In part (b), the DR and WSN-based localization will respectively give their estimation for the real trajectory (a). Then the trajectory obtained by data fusion, also a more accurate estimated one, is presented in part (c). Having obtained a more precise position of step k, a n-step backward dead reckoning method is used to give a new independent information to the previous localization of n steps. The issue of how to choose the number of backward updating steps n will be discussed in Section 4.

3.2. Zigbee-based Global Positioning System

A WSN is composed of several sensor nodes that are interconnected over wireless links and it basically consists of the reference nodes with known static locations, the blind node with an unknown location and the Loc Dongle node which connects the WSN system to a computer. Zigbee is a kind of wireless communication protocol based on the IEEE802.15.4 standard. In our localization system, the Zigbee-based WSN is built by CC2431/2430, produced by Texas Instruments. As long as the distances between the blind node and the reference nodes can be measured, a two dimensional localization can be easily calculated. A simplified system for localization using WSN is shown in Figure 10.

Figure 10.

The distribution of nodes in Zigbee-based WSN localization

For the Zigbee-based WSN, the distance is measured using the Received Signal Strength Indicator (RSSI) value which suffers a decrease as the distance increases, as described by the following equation:

$RSSI=-\mathrm{h}\log \mathrm{d}+\mathrm{A}$ (6)

where h stands for the signal propagation constant, d is the distance from the blind node to the reference node and A is the received signal strength at a distance of one metre which is set as 46 based on the recommendation of the data sheet. The blind node collects RSSI values from all the reference nodes respectively, responding to a request, feeds the RSSI values into its own hardware engine to calculate its own position and then sends it back to the computer.

To help a mobile robot localize itself, a blind node is mounted on the robot and the robot moves in an environment in which many reference nodes are set. Three reference nodes in a given localization task are enough to give the position of the blind node. However, in order to reduce the influence of distance errors on localization accuracy, eight reference nodes are used in this work. In addition, in some complicated environments such as offices, buildings and mines, it is economical to apply reasonably large amounts of reference nodes to eliminate the uncertainty of distance measurement, in which regard Zigbee-based WSN is usually low-cost, low-power-consumption and small. Sometimes eight reference nodes are not enough for many practical applications so it will be necessary to extend the area by using more reference nodes. This can easily be achieved by a simple software pre-processor algorithm. Figure 11 shows an example of how the algorithm works. When the mobile robot moves, it receives the eight reference nodes with the highest RSSI values, and all other nodes should be neglected. The algorithm makes this Zigbee-based localization system perform as accurately in larger areas as in a 6m*6m area.

Figure 11.

Extended map with more reference nodes

In the indoor environment with an area of 6m*6m, the deviations in the x and y coordinates are tested. First, because the parameter h depends highly on the environment, several experiments are carried out to help choose an optimal h, which is set as 18 in our study. Then we put the blind node in 81 different positions which are the crossing of the lines every 0.6m of the x-coordinate and y-coordinate, respectively. Both of the deviations conform to the normal distribution and the specific parameters are given in Figure 12, which is a stochastic result from a comprehensive testing on the real Zigbee localization system.

Figure 12.

Normal distributions of deviations in 6m*6m using Zigbee-based localization method

3.3. Data Fusion and BDR Algorithm

3.3.1. Data Fusion using Kalman Filter

DR-based localization suffers from various errors including stochastic errors and non-stochastic errors. The stochastic errors such as the unequal wheel diameter are unavoidable; however, it can be compensated for if the error model can be tested out. In addition, the non-stochastic errors such as the wheel slippage which will result in the measurement errors are modelled as Gaussian White noise [17, 18] which can be reduced using several kinds of signal processing methods such as the Bayesian filter, Kalman filter, DS Evidential Theory, etc. Therefore, it is necessary to first obtain the error models of both the stochastic errors and non-stochastic errors. According to [19, 20], the odometry errors have accumulated unbounded errors as their measured distance increases and there will be a totally wrong estimation of the position when the robot travels as little as 10m [21]. Since the odometry error has already been assumed to be the Gaussian White noise, the mean and variance of the error can be worked out through the experiment. It is easy to further presume that for every localization process i of odometry, the measurement error denoted as ${\mathrm{R}}_{oi}$ , follows a normal distribution ${\mathrm{R}}_{oi}~\mathrm{N}({\mu }_{\mathrm{i}},{\sigma }_{\mathrm{i}}^2)$ , where ${\mu }_{\mathrm{i}}$ is the mean value of the error and ${\sigma }_{\mathrm{i}}$ is the standard deviation.

For Zigbee-based WSN localization, the measurement error can be assumed to be constant due to a certain range of the network layout. For example, if the reference nodes are distributed to form a 6m*6m square in which the robot moves, then a certain ${\mu }_{\mathrm{z}6}$ and ${\sigma }_{\mathrm{z}6}$ can denote the mean and standard deviation of the error of this localization area, thus the measurement error for a $\mathrm{l}\text{\hspace{0.17em}m*}\mathrm{l}\mathrm{m}$ square is ${\mathrm{R}}_{zl}~\mathrm{N}({\mu }_{\mathrm{l}},{\sigma }_{\mathrm{l}}^2)$ . To expand the localization space, only a translation of the 6m*6m square is needed, or more reference nodes can be used to form a larger square where the blind node is localized by the 6m*6m square to which it belongs.

According to the characteristics of the errors of odometry and Zigbee-based WSN, it is naturally true that when the robot moves over a fairly short distance, the localization error of odometry is far less than that of Zigbee-based WSN. However, for a fairly long distance of movement, the odometry error will far outweigh the error of Zigbee-based WSN. So, the BDR has been tasked with working out how to effectively use the two pieces of localization information. The main idea of the BDR is to first use the Kalman filter to fuse the localization data attained by different sensors, to obtain the probabilistic weighted factors to identify the reliability of each sensor and to calculate the optimal estimated position of the mobile robot. After that, the new estimated data will be used to update the previous localization information which seems to not be precise enough. The updating process will refresh every piece of position estimation data and give a more precise position of the robot. In the following section, the data fusion of a multi-sensor system using a Kalman filter and the specific updating method will be discussed in detail.

The basic notion of the Kalman filter is to use recursive calculations to diminish the estimation error to obtain an optimal estimation of a specific state of a system. There are several merits to the Kalman filter which explains its wide application in robot localization [21–23]: (1) past, present or even future states can be estimated; (2) it can still estimate the optimal states of a system even if the precise nature of the modelled system is unknown [24]; (3) it can give the probability that determines the reliability of different sensors and the sensor fusion will reduce the variance estimates [17].

First, we assume that the discrete-time system can be described by the following equations at step k:

${\mathrm{x}}_{\mathrm{k}}=\mathrm{A}{\mathrm{x}}_{\mathrm{k}-1}+\mathrm{B}{\mathrm{U}}_{\mathrm{k}}+{\mathrm{w}}_{\mathrm{k}}$ (7) ${\mathrm{z}}_{\mathrm{k}}=\mathrm{H}{\mathrm{x}}_{\mathrm{k}}+{\mathrm{v}}_{\mathrm{k}}$ (8)

where A is the system matrix, B is the input matrix, H is the observation matrix, ${\mathrm{z}}_{\mathrm{k}}$ is the measurement value, ${\mathrm{w}}_{\mathrm{k}}$ and ${\mathrm{v}}_{\mathrm{k}}$ are the process covariance and measurement covariance respectively which are supposed to be independent of each other and are white Gaussian noises with a normal probability distribution: $\begin{array}{l}{\mathrm{P}}_{\mathrm{w}}~\mathrm{N}({\mu }_{\mathrm{w}},{\sigma }_{\mathrm{w}}^2)\\ {\mathrm{P}}_{\mathrm{v}}~\mathrm{N}({\mu }_{\mathrm{v}},{\sigma }_{\mathrm{v}}^2)\end{array}$

We let ${\sigma }_{\mathrm{w}}^2=\mathrm{Q},{\sigma }_{\mathrm{v}}^2=\mathrm{R}$ , then we can obtain the recursive Kalman filter equations as:

${\mathrm{x}}_{\mathrm{k}|\mathrm{k}-1}=\mathrm{A}{\mathrm{x}}_{\mathrm{k}-1|\mathrm{k}-1}+\mathrm{B}{\mathrm{U}}_{\mathrm{k}}$ (9) ${\mathrm{P}}_{\mathrm{k}|\mathrm{k}-1}=\mathrm{A}{\mathrm{P}}_{\mathrm{k}-1|\mathrm{k}-1}{\mathrm{A}}^{\mathrm{T}}+\mathrm{Q}$ (10) $\mathrm{K}{\mathrm{G}}_{\mathrm{k}}={\mathrm{P}}_{\mathrm{k}|\mathrm{k}-1}{\mathrm{H}}^{\mathrm{T}}/(\mathrm{H}{\mathrm{P}}_{\mathrm{k}|\mathrm{k}-1}{\mathrm{H}}^{\mathrm{T}}+\mathrm{R})$ (11) ${\mathrm{x}}_{\mathrm{k}|\mathrm{k}}={\mathrm{x}}_{\mathrm{k}|\mathrm{k}-1}+\mathrm{K}{\mathrm{G}}_{\mathrm{k}}({\mathrm{z}}_{\mathrm{k}}-\mathrm{H}{\mathrm{x}}_{\mathrm{k}|\mathrm{k}-1})$ (12) ${\mathrm{P}}_{\mathrm{k}|\mathrm{k}}=(\mathrm{I}-\mathrm{K}{\mathrm{G}}_{\mathrm{k}}\mathrm{H}){\mathrm{P}}_{\mathrm{k}|\mathrm{k}-1}$ (13)

where ${\mathrm{x}}_{\mathrm{k}|\mathrm{k}-1}$ represents the prior estimation of system state at step k, and ${\mathrm{x}}_{\mathrm{k}|\mathrm{k}}$ is the posterior estimation of system state at step k, ${\mathrm{p}}_{\mathrm{k}|\mathrm{k}-1}$ is the prior estimate error covariance of ${\mathrm{x}}_{\mathrm{k}|\mathrm{k}-1}$ , ${\mathrm{p}}_{\mathrm{k}|\mathrm{k}}$ is the posterior estimate error covariance of ${\mathrm{x}}_{\mathrm{k}|\mathrm{k}}$ , $\mathrm{K}{\mathrm{G}}_{\mathrm{k}}$ is the Kalman Gain used to minimize the posterior estimate error covariance. Through the five equations above, we can gradually obtain the minimum estimate error covariance described as: ${\mathrm{P}}_{\mathrm{k}|\mathrm{k}}=\mathrm{E}({\mathrm{e}}_{\mathrm{k}|\mathrm{k}}{\mathrm{e}}_{\mathrm{k}|\mathrm{k}}{}^{\mathrm{T}})$ in which ${\mathrm{e}}_{\mathrm{k}|\mathrm{k}}={\mathrm{x}}_{\mathrm{k}}-{\mathrm{x}}_{\mathrm{k}|\mathrm{k}}$ and ${\mathrm{x}}_{\mathrm{k}}$ is the absolute value of the state. Because there are only two sensors for localization, the equations (9)~(13) can be simplified as follows.

We assume that the DR-based localization is the prior estimation of the position and Zigbee-based WSN localization is the measurement information, so at step k of localization we get:

$\mathrm{K}{\mathrm{G}}_{2,\mathrm{k}}=\frac{{\sigma }_{1,\mathrm{k}}^2}{{\sigma }_{1,\mathrm{k}}^2+{\sigma }_{{\mathrm{z}}_2,\mathrm{k}}^2}$ (14) ${\widehat{x}}_{2,\mathrm{k}}={\widehat{x}}_{1,\mathrm{k}}+\mathrm{K}{\mathrm{G}}_2({\mathrm{z}}_{2,}{}_{\mathrm{k}}-{\widehat{x}}_{1,\mathrm{k}})$ (15)

where $\mathrm{K}{\mathrm{G}}_{2,\mathrm{k}}$ is the Kalman Gain of the fusion estimation, ${\widehat{x}}_{1,\mathrm{k}}$ and ${\widehat{x}}_{2,\mathrm{k}}$ represent the prior and posterior estimation of the position respectively, ${\mathrm{z}}_{2,\mathrm{k}}$ is the measurement data from Zigbee-based WSN. Through equations (14)~(15), the optimal localization at each step is achieved by the fusion of the two-sensor localization information. In the following part, this optimal fusion localization information will be used to obtain a more precise position of the robot.

To further aid in obtaining more precise localization by taking the most advantage possible of the position information along the robot's trajectory, a BDR algorithm is proposed based on the Kalman filter-based data fusion method. Equations (1)~(5) are firstly used to calculate the ${\mathrm{k}}^{th}$ step of robot position with the ${(\mathrm{k}-1)}^{th}$ step of the position, since it is represented in the deferential form, it can also be used to calculate the ${(\mathrm{k}-1)}^{th}$ step of the position using the ${\mathrm{k}}^{th}$ step of the position, the equations are as follows:

${\mathrm{x}}_{\mathrm{k}-1}{\hspace{0.17em}}^{\prime }\text{=}{\mathrm{x}}_{\mathrm{k}}\text{-}\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}-1}\cos ({\theta }_{\mathrm{k}-1}+\frac{\mathrm{\Delta }{\theta }_{\mathrm{k}-1}}{2}\text{)}$ (16) ${\mathrm{y}}_{\mathrm{k}-1}\text{=}{\mathrm{y}}_{\mathrm{k}}\text{-}\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}-1}\sin ({\theta }_{\mathrm{k}-1}+\frac{\mathrm{\Delta }{\theta }_{\mathrm{k}-1}}{2}\text{)}$ (17) ${\theta }_{\mathrm{k}-1}={\theta }_{\mathrm{k}}\text{-}\mathrm{\Delta }{\theta }_{\mathrm{k}-1}$ (18)

where ${\mathrm{x}}_{\mathrm{k}-1}$ , ${\mathrm{x}}_{\mathrm{k}}$ , ${\mathrm{y}}_{\mathrm{k}-1}$ , ${\mathrm{y}}_{\mathrm{k}}$ , $\mathrm{\Delta }{\theta }_{\mathrm{k}-1}$ , ${\theta }_{\mathrm{k}}$ and $\mathrm{\Delta }{\mathrm{d}}_{\mathrm{k}-1}$ are defined as the same in equations (1)~(5).

With the backward deduction of DR and the optimal fusion of the two sensors given by the Kalman filter at every localization step, with the rather precise estimation, it is possible to obtain a more precise previous position estimation using the posterior estimation by equations (14)~(18). In this case, the previous estimation deduced by the back recurrence equations with the posterior estimation can be considered as a new measurement by a third sensor, then it can be fused with the optimal estimation given by the Kalman filter using the localization information of the odometry and WSN in this position, as shown in Figure 13., where ${\widehat{x}}_{1,\mathrm{k}-1}\prime$ is calculated by ${\widehat{x}}_{1,\mathrm{k}}$ , ${\sigma }_{1,\mathrm{k}-1}^2\prime$ is the estimation variance of ${\widehat{x}}_{1,\mathrm{k}-1}\prime$ , $\mathrm{K}{\mathrm{G}}_{3,\mathrm{k}-1}$ is the Kalman Gain for estimating ${\widehat{x}}_{3,\mathrm{k}-1}$ using a BDR algorithm and ${\sigma }_{3,\mathrm{k}-1}^2$ is the estimation variance of ${\widehat{x}}_{3,\mathrm{k}-1}$ . Thus, the uncertainty of the previous estimated positions will be reduced by a data fusion of the new information from the posterior estimated positions. No matter how many sensors are used, the Kalman filter can give the optimal fusion estimation; the BDR algorithm can update the localization results to improve the accuracy. This indicates that the BDR algorithm can be applied widely in different localization conditions, where the Zigbee-based WSN can be replaced by other kinds of sensors to help in achieving precise localization.

Figure 13.

The schematic description of the localization process3.3.2 Backward Dead Reckoning (BDR) Method

4. Experimental Results

To test the proposed approach, both of the simulated experiments and real experiments are conducted to demonstrate the performance of these methods.

4.1. Simulated Experiments

In the simulated experiments, the number of backward updating steps, known as n in Section 3, is determined by the numerical experiments for the best performance. Then the performance of the entire localization system is given when the mobile robot moves in the two typical kinds of environments introduced in Section 2.

To evaluate the accuracy of localization, we define the average of the square of deviation $\overline{{(\mathrm{\Delta }\mathrm{P})}^2}$ as the indicator of accuracy, which can be calculated by this equation: $\overline{{(\mathrm{\Delta }\mathrm{P})}^2}=\frac{1}{\mathrm{k}}{\displaystyle {\sum }_{first}^{last}\left|\right|{\mathrm{P}}_{esti}-{\mathrm{P}}_{real}|{|}^2}$ where $Preal$ is the real position of the sampling point of the robot's trajectory, $Pesti$ is the estimated position given by the localization method, k is the number of sampling points. In addition, to evaluate the uncertainty of localization, we also define the average of variances $\overline{{\sigma }^2}$ as the indicator of uncertainty, which can be calculated by this equation: $\overline{{\sigma }^2}=\frac{1}{\mathrm{k}}{\displaystyle {\sum }_{\text{first}}^{\text{last}}{\sigma }_{\mathrm{i}}^2}$ where $\sigma {\mathrm{i}}^2$ stands for the variance of the normal distribution which the estimated position submits to. Obviously, $\overline{{(\mathrm{\Delta }\mathrm{P})}^2}$ becomes smaller when the accuracy of localization is higher, and $\overline{{\sigma }^2}$ also becomes smaller when the uncertainty of localization is less.

For different indoor environments, it is necessary for the BDR algorithm to use the appropriate n. In simulation, the program will run enough times for a specific environment to obtain the optimal parameter n for precise localization under the indication of the smallest $\overline{{(\mathrm{\Delta }\mathrm{P})}^2}$ and $\overline{{\sigma }^2}$ .

Now, first we generate a real trajectory with several line segments and turning angles as the path of the mobile robot. The estimated positions of WSN and DR are given, respectively, using the error models introduced in Sections 2 & 3. Then the localization information is fused via the Kalman filter, which will produce an optimized estimation with much less uncertainty. Finally, the relatively accurate estimation of the position obtained by the Kalman filter is updated using the BDR localization equation (1), (2), (16)~(18), which refreshes the previous path.

For localization in a single room with an area of 50m*25m, we set n as 10 and the performance of the four localization methods (DR, Zigbee, combining DR and Zigbee with KF, BDR) is presented in Figure 14. Obviously, after data fusion by the Kalman filter, the estimated trajectory comes closer to the real trajectory. In addition, by using the proposed BDR algorithm, the accuracy of localization is much higher and meanwhile the uncertainty is much less than with the other three localization methods.

Figure 14.

Comparison between the four localization methods (DR, Zigbee (ZB), Kalman Filter (KF) and BDR) in a 50m*25m map

For localization in a single room with an area of 15m*6m, we set n as 3 and the performance of the four localization methods is presented in Figure 15. Also, by using the proposed algorithm, we can obtain precisely estimated positions. Because there is no extra information from a next point to update the position information of the last point, it will be relatively far away from the real last point, as shown in Figure 15.

Figure 15.

Comparison between the four localization methods with a 15m*6m map

For localization in the complicated environment with several rooms, we set n as 5 and the performance of the four localization methods is shown in Figure 16.

Figure 16.

Comparison between the four localization methods in a complicated environment with five offices

To further verify the effectiveness of the BDR algorithm, we run the simulation program with several maps of different areas. Table 3 gives the numerical indication of the performance of these four localization methods, from which we can see that when the range of the environment is larger than 100m* 100m, DR suffers a huge localization error, which misleads the Zigbee-based localization method badly.

Table 3.

The accuracy and uncertainty of the four methods in different maps

		Average (deviation)2	Average σ2			Average (deviation)2	Average σ2
6m*6m	DR	0.0582	0.3250	18m*18m	DR	0.6424	0.2550
	ZB	1.5352	1.5940		ZB	1.5002	1.5940
	KF	0.0556	0.0299		KF	0.3895	0.1476
	BDR	0.0321	0.0030		BDR	0.2417	0.0216
30m*30m	DR	2.5762	0.6353	42m*42m	DR	4.2524	1.1791
	ZB	1.6495	1.5940		ZB	1.6349	1.5940
	KF	0.9341	0.2208		KF	1.1193	0.2571
	BDR	0.8090	0.0431		BDR	0.8451	0.0519
60m*60m	DR	12.4153	2.3413	80m*80m	DR	28.7095	4.1304
	ZB	1.6327	1.5940		ZB	1.5525	1.5940
	KF	1.6194	0.2733		KF	1.9862	0.2650
	BDR	1.2541	0.0554		BDR	1.4249	0.0543
100m*100m	DR	56.7871	6.3732	120m*120m	DR	102.4103	9.0843
	ZB	1.5799	1.5940		ZB	1.6167	1.5940
	KF	2.2899	0.2474		KF	2.4863	0.2285
	BDR	1.6533	0.0506		BDR	1.7507	0.0469

4.2. Real Experiments

An integral practical experiment is also conducted to show the performance of the overall localization system proposed in this paper. In a plane of 6m*6m in our laboratory, the mobile robot with a blind node on top moves along a pre-established trajectory which is among the eight reference nodes. The experimental environment and the practical trajectory are shown as in Figure 17.

Figure 17.

The environment of the practical experiment

The sampling positions in Figure 17 are listed as (1, 2, …, 9), which are also shown in Table 4. Meanwhile, the estimated positions given by both DR and Zigbee are presented. Then these two kinds of data with uncertainty of their localization are fed into the Kalman filter and the BDR algorithm. Finally, all of the localization results are shown in Table 4, which shows that the localization method of combining DR and WSN, and the BDR method are practical and effective. In addition, these methods will perform better in a larger working space than the existing DR or Zigbee method.

Table 4.

Real positions and estimated positions by the four localization methods

	Real Positions	Estimated Positions byDR	Estimated Positions by Zigbee	Estimated Positions byKF	Estimated Positions by BDR
1	(5.4, 4.8)	(5.40, 4.80)	(5.40, 4.80)	(5.40, 4.80)	(5.40, 4.80)
2	(4.8, 4.2)	(4.79, 4.23)	(4.85, 3.65)	(4.80, 4.23)	(4.80, 4.23)
3	(4.2, 3.6)	(4.25, 3.68)	(4.08, 3.16)	(4.24, 3.68)	(4.24, 3.68)
4	(3.6, 3.0)	(3.61, 3.06)	(4.84, 3.90)	(3.62, 3.07)	(3.57, 3.12)
5	(3.0, 3.0)	(2.92, 3.10)	(4.30, 2.63)	(2.93, 3.10)	(2.96, 3.14)
6	(2.4, 3.0)	(2.25, 3.15)	(1.10, 2.05)	(2.24, 3.13)	(2.38, 3.02)
7	(1.8, 3.0)	(1.70, 3.11)	(2.82, 1.28)	(1.72, 3.06)	(1.91, 2.92)
8	(1.2, 1.8)	(1.07, 1.99)	(2.12, 1.34)	(1.10, 1.97)	(1.18, 1.71)
9	(0.6, 1.2)	(0.73, 1.13)	(−0.06, 1.59)	(0.70, 1.16)	(0.70, 1.16)

5. Conclusion

It is of great importance for a mobile robot to be able to determine its own location. DR-based localization method is prone to unbounded accumulated errors due to various disturbances. However, the errors of Zigbee-based localization are relatively static in both small and large environments, which is a complementary characteristic to DR-based localization errors. The fusion of these two sensors by a Kalman filter can give a fairly precise localization result. The proposed BDR-based localization method can further aid in obtaining a more precise location with much less uncertainty. Several groups of simulated and real experiments are presented which show the success of the proposed methods. The experimental results verify that the Kalman filter method and BDR method are effective and can decrease the localization errors, especially for localization in larger and more complex environments. More real experimental results also show that the proposed methods are effective and feasible for practical applications. In addition, the proposed methods can be easily applied in other circumstances provided that there is alternative sensory information and can be utilized to eliminate the accumulated errors of DR-based localization. Our future work will focus on the further improvement of mobile robot localization and navigation [25, 26] using alternative spatial data, topological information [27] and intelligent control approaches [28].