Abstract
Filtering-based indoor positioning using ultra wideband (UWB) requires known velocity to predict prior position in the prediction stage. Velocity can be obtained from an inertial measurement unit (IMU) sensor or the posterior state vector at the previous time stamp. Both methods have limitations when using them in practice. This paper proposes two novel velocity determination approaches, which use measurements to approximate velocity in a self-contained way. They are integrated into particle filtering algorithms for prior position determination. The test result shows that the particle filter with the proposed approaches performs similarly to the Rao-Blackwellized particle filter and slightly better than the particle filter with IMU. Compared with the standard particle filter, the particle filters with our proposed approaches achieve similar positioning accuracies with less computation time. Moreover, it is found that the integration of Angle-of-Arrival measurements in particle-filter-based positioning improves the 3-D positioning accuracy by about 37.3% on average.
1 INTRODUCTION
Indoor positioning plays an increasingly important role in our daily life and industry. Targets to be positioned in indoor environments can be generally classified into two categories. The first category is mobile robots and vehicles that can provide motion information (such as acceleration, velocity, and direction) for accurate positioning. Many indoor positioning methods for these targets have been proposed in the past decade (González, Blanco, Galindo, Ortiz-DeGalisteo, Fernández-Madrigal, et.al., 2009; Yudanto & Petré, 2015; Zhu Yi, Cheng, He, 2020). The second category is pedestrians and objects that are unable to provide the motion information. The accurate positioning of these targets is the focus of this work. The indoor positioning applications of the targets in the second category include pedestrian tracking in shopping malls, goods tracking in logistics, and process monitoring in car-smartmanufacturing factories, etc. These applications generally have strict requirements on positioning performance. Positioning performance metrics usually include accuracy, availability, continuity, and reliability (Lau, Tateshita, Sato, 2015). Accuracy is the most important metric in any indoor positioning system (Liu, Darabi, Banerjee, Liu, 2007; Ranasinghe & Kray, 2018). The achievable accuracy of an indoor positioning system depends on the types of positioning sensors and the algorithm used in position determination.
Considering positioning sensors, an overview of the state-of-the-art indoor positioning sensors/techniques on some key features are presented in Basiri, Lohan, Moore, Winstanley, Peltola, et al. (2017), Lau et al. (2018) and Brena et al. (2017). It shows that ultra wideband (UWB) is more competitive than the other sensors because of the high positioning accuracy (10-15 cm) and the wide coverage (typically 50 m). UWB recently becomes a promising and widely used wireless sensor for indoor positioning (Parikh & Michalson, 2008), and it is used as the positioning sensor in the developed algorithm of this paper. Considering positioning algorithms, the particle filter is a widely used algorithm because it can solve nonlinear and non-Gaussian positioning problems. Particle-filtering algorithm estimates positions through two stages: prediction and update (Chen, 2003). The prior position is estimated through the dynamic model in the prediction stage. However, the velocity of a target to be positioned is usually random and time varying in practice. This causes the difficulty for prior position determination in the particle filter. Some dynamic models use different velocity determination methods to tackle this problem. For example, the velocity in the uniformly accelerated motion model (Gustafsson et al., 2002) is treated as a known value, and it is obtained from a complementary sensor such as an inertial measurement unit (IMU) or an odometer. IMU and odometer sensors can record the information about the target motion and output the parameters required for prior position determination; examples can be found in González et al. (2009), Atia et al. (2011) and Wang & Li (2017). However, using this dynamic model has the limitation that it requires sampling synchronization between two types of sensors. Besides, the relative positions (i.e., lever arm offset/correction) of the two sensors should be measured beforehand. The random-walk model (Pak et al., 2017) is another widely used dynamic model for prior position determination. The velocity components in this dynamic model are treated as the variables in the state vector and estimated through filtering at each time stamp. The random-walk model is generally used in the standard particle filter (Olama et al., 2008) and the Rao-Blackwellized particle filter (Schon et al., 2005). The limitation of the random-walk model is the high computation load because of the increased dimensionality of the state vector. In addition to the above two dynamic models, a constant-velocity model (Pak et al., 2017) is sometimes used for pedestrian positioning. This dynamic model assumes the velocity to be constant. Such assumption is only suitable for the case that the sampling interval of the positioning sensor is very short so that the velocity change of the target between two time stamps is negligible. Besides, Wang et al. (2012) define a specific dynamic model based on the last position estimation and a predefined maximum velocity threshold. However, their method uses the maximum velocity threshold to constrain the distribution of predicted particles and uses the weighted centroid point of the particles as the prior position. The predicted particles are randomly distributed within the square area with the last estimation as the center. This method suffers from some problems; the accuracy of the prior position is highly dependent on the value of the velocity threshold, and the velocity threshold is difficult to determine especially when no complementary sensor can be used in practice. More dynamic models used in particle filtering for different applications can be found in Gustafsson et al. (2002).
The main contribution of this paper is that it proposes two particle-filter based novel velocity determination approaches for prior position prediction. Different to the standard particle filter and the Rao-Blackwellized particle filter which use measurements to determine the velocity, our proposed approaches determine the velocity based on the two consecutive filtered positions or the Chan-Taylor (Chang et al., 2017) estimated positions instead of through filtering itself. Both approaches approximate the velocity in a self-contained way. They provide users with two better options to replace the IMU sensor in particle-filter-based indoor positioning system, which reduces the equipment cost and size. Meanwhile, the limitations of some existing methods are analyzed through positioning performance assessment. Assessments are made by comparing the positioning results of the two proposed approaches with the results obtained by the particle filter with IMU, the standard particle filter, and the Rao-Blackwellized particle filter. As one of the proposed approaches uses the Chan-Taylor algorithm for velocity approximation, the positioning performance of the Chan-Taylor algorithm is also compared with that of the particle-filtering algorithm in this paper. Besides, Lau et al. (2018) indicates that the inclusion of Angle of Arrival (AOA) measurements in a UWB system can improve positioning accuracy. This paper also verifies the impact of AOA measurements in the particle filter on positioning accuracy.
This paper is organized as follows. Section 2 presents the essential background of UWB and the positioning algorithms used in this paper, including the Chan-Taylor algorithm and particle-filtering algorithm. In Section 3, the two proposed approaches for prior position determination are described. The prior position accuracies determined by the proposed approaches as well as the effects of parameters on positioning accuracy are investigated in Section 4. Experimental design, results, and analysis are described in Section 5. Finally, the conclusion and further work are given in Section 6.
2 BACKGROUND
2.1 Indoor positioning with UWB
The definition of UWB from Federal Communications Commission (FCC) can be found in Commission (2002). UWB transmits a radio signal over a wide portion of frequencies based on short pulses (nanosecond level). This property has the advantages for indoor positioning such as high-ranging accuracy (Sahinoglu et al., 2008), very high-penetrating power (Geng et al., 2005), less interference from multipath effect (Sahinoglu et al., 2008), high-speed data transmission (Mitchell & Kohno, 2003), and extremely low power consumption (Gezici & Poor, 2009).
Time difference of arrival (TDOA) is the measurement generally used in UWB-based positioning. The principle of positioning using TDOA can be found in Gezici & Poor (2009). TDOA does not require time synchronization between the transmitter and the receiver. The constant offset can be eliminated by subtraction, but only transmitters must be synchronized. A commercial UWB positioning system developed by the UK Ubisense company can provide both TDOA and AOA measurements. AOA is based on the direction from which the received signal arrives. Multiple antennas in the form of an antenna array are usually employed for AOA estimation (Gezici & Poor, 2009). The principle of AOA estimation via antenna arrays can be found in Gezici (2008). As stated in Section 1, the impact of AOA measurements in the particle filter on positioning accuracy is assessed in this work, therefore, the Ubisense system is used since it can provide both TDOA and AOA measurements. The Ubisense system consists of three parts: a tag for signal transmission, a set of sensors for signal reception, and a workstation PC with a platform named Ubisense Location Engine (LE). Both TDOA and AOA measurements are processed in the LE.
2.2 Chan-Taylor algorithm
The TDOA observation model consists of a list of nonlinear hyperbolic equations. (𝑀 − 1) equations can be set up when 𝑀 sensors are provided. The Chan algorithm (Chan & Ho, 1994) and Taylor algorithm (Foy, 1976) are two advanced solutions for solving these nonlinear equations. Their extensions to 3-D positioning can be found in Zhang et al. (2008) and Liu et al. (2012), respectively.
Both the Chan algorithm and the Taylor algorithm have some limitations when using them alone in practice. The Chan algorithm is based on a practically less likely assumption that the measurement noise must be zero-mean Gaussian distributed. This leads to positioning accuracy reduction in the environments with non-line-of-sight (NLOS) measurements (Li & Luan, 2018). The Taylor algorithm requires an initial position estimate to start the iteration while this initial position is usually unavailable in practice. Chang et al. (2017) proposed a combined Chan-Taylor algorithm which uses the Chan algorithm’s estimate to initialize the Taylor algorithm. This combined algorithm can not only solve the unavailability of the initial position in the Taylor algorithm but also provides the position estimate with better accuracy and robustness than the Chan algorithm (Zhang et al., 2011). The UWB-based indoor 3-D positioning using the Chan-Taylor algorithm can be found in Wang et al. (2020).
2.3 Indoor positioning using particle filter
2.3.1 Dynamic model for particle filter
The detailed concept of the particle filter can be found in Atia et al. (2011) and Risfic et al. (2004). Depending on whether the velocity is known (measurable) or not, two different dynamic models for particle-filter based indoor positioning are briefly described as follows.
Consider that there is an indoor positioning system consisting of a tag and a set of sensors with known coordinates. Denote 𝒙𝑘 = [𝑥𝑘, 𝑦𝑘, 𝑧𝑘]𝑇 and 𝒗𝑘 = [𝑣𝑥, 𝑘, 𝑣𝑦, 𝑘, 𝑣𝑧, 𝑘]𝑇 as the position and velocity of the tag, respectively. The subscript (⋅)𝑘 denotes the time stamp 𝑘. We first consider the dynamic model with unknown velocity. In this situation, the velocity 𝒗𝑘 is usually contained in the state vector as an unknown parameter and estimated along with the position 𝒙𝑘 through the filtering. The dynamic model for this case can be written as (Gustafsson et al., 2002)
1
where 𝒙𝑘 = [𝑥𝑘,𝑦𝑘,𝑧𝑘, 𝑣𝑥,𝑘,𝑣𝑦,𝑘,𝑣𝑧,𝑘]𝑇 is the state vector, and
2
𝑭 is the state transition matrix. 𝑮 is the noise driving matrix. 𝒘𝑘−1 is the motion process noise vector with the known covariance matrix 𝑸 that is needed in the observation model. Δ𝑇 is the sampling interval. Equation (1) is actually the dynamic model for indoor positioning using the standard particle filter. However, containing the velocity into the state vector may cause some problems. The typical problem is that the increased dimensionality of the state vector leads to requiring more particles for filtering, which is known as the problem of “curse of dimensionality” (Gordon et al., 1993; González et al., 2009). The result of this problem is the greatly increased computation load, which is a challenge for real-time applications. A solution to this problem is using the Rao-Blackwellized particle filter. The Rao-Blackwellized particle filter partitions the state vector as 
, where 
is the nonlinear state variable (i.e., position, 
and 
is the state variable with conditionally linear dynamics (i.e., velocity, 
. In this case, the dynamic model in Equation (1) can be divided into two submodels as
3
where
4
For the first submodel in Equation (3), the nonlinear variables are still estimated by the particle filter. For the second submodel in Equation (3), the linear variables are estimated by the Kalman filter. Since the Kalman filter has a much lower computation load than that of the particle filter, the above state vector partition is beneficial for saving computation time. The dynamic models in Equation (1) and Equation (3) are both based on the assumption that the velocity is subject to an unknown acceleration, which is characterized by the motion process noise 𝒘𝑘−1. The detailed processes of using the standard particle filter and the Rao-Blackwellized particle filter for positioning can be found in Olama et al. (2008) and Hendeby et al. (2010), respectively.
Another solution to the problem of “curse of dimensionality” is making the velocity measurable (such as using IMU). In such a case, the number of unknown parameters in the state vector is reduced to three (only three position components), and the dynamic model can be simplified as the uniformly accelerated motion model (Gustafsson et al., 2002), given by
5
where
6
𝑩 is the control input matrix. 𝒖𝑘−1 is the control vector, which characterizes the target’s action within the time interval 𝑘−1 to 𝑘 (i.e., the measurable velocity). The denotations of 𝑭, 𝑮, and 𝒘𝑘−1 are the same to those in Equation (1). Compared with the dynamic model in Equation (1), the dynamic model in Equation (5) has less parameters in the state vector. This parameter reduction results in two advantages. First, the number of particles required for filtering implementation is greatly reduced, and this further reduces the computation load. Second, the reduction of the parameters in the state vector can increase the degree of freedom in the filtering estimation. When less parameters are estimated in the state vector, it means the redundancy is increased since the same number of measurements are used to estimate less unknowns. This increased redundancy/degree of freedom will increase the reliability of filtering estimation (Basiri et al., 2017). Therefore, the dynamic model in Equation (5) is used in our work, and the proposed approaches in this paper are based on this dynamic model.
2.3.2 Observation model for particle filter
Once the predicted particles are obtained in the prediction stage, the observation model is required for particle update. We denote the UWB observations at time stamp 𝑘 as 𝒛𝑘 ∈ ℝ(3𝑀−1)× 1.
7
where 𝑀 is the number of sensors. 𝑑21,𝑘, …,𝑑𝑀1,𝑘, denote the TDOA distances at the tag to Sensors 2 to 𝑀 with respect to the master (reference) Sensor 1. 𝛼1,𝑘,…, 𝛼𝑀,𝑘 and 𝜑1,𝑘,…,𝜑𝑀,𝑘 denote the azimuths and elevations at each sensor to the tag, respectively.
Consider that 𝒙𝑘 is the state vector in Equation (1), Equation (3), or Equation (5). It is assumed that the initial state distribution 𝑝(𝒙0) is known, and it is equal to the posterior density of the initial state, i.e., 𝑝(𝒙0) = 𝑝(𝒙0𝒛0). 𝒙𝑘 is assumed to be updated based on the Markov chain, then 𝑝(𝒙𝑘𝒛1∶𝑘) can be recursively calculated by
8
where 𝑝(𝒙𝑘−1𝒛1∶𝑘−1) is the known posterior state at time stamp 𝑘−1. 𝑝(𝒙𝑘𝒙𝑘−1) is the prediction, which is defined by the dynamic model and the covariance of motion process noise 𝑸𝑘−1, given by
9
where 𝒇(𝒙𝑘−1) is the dynamic model in Equation (1), Equation (3), or Equation (5). 𝑝(𝒛𝑘𝒙𝑘) is the likelihood, which is defined by the observation model and the covariance of measurement noise 𝑹𝑘. Since the TDOA and AOA measurements from each UWB sensor are independent, the likelihood can be factored as
10
where
11
𝑓(⋅), 𝑔(⋅), and ℎ(⋅) are the noise-free observation equations for TDOA distance, azimuth, and elevation, respectively. These equations can be found in Lau et al. (2018). 𝒍𝑖 is the location of the sensor 𝑖. 
, 
, and 
are the variance components in the measurement noise matrix 𝑹𝑘. As a state-of-the-art version of the particle-filtering algorithm, the standard sample-importance-resampling (SIR) uses the prediction 𝑝(𝒙𝑘𝒙𝑘−1) as the importance density and performs resampling at each iteration. SIR has the advantages that the importance weights can be easily evaluated and the importance density can be easily sampled. Therefore, it is used in this work. The details and pseudocode of SIR can be found in Chen (2003). The weighted mean value of particles is used to determine the position at each time stamp.
3 PROPOSED METHODS FOR PRIOR POSITION DETERMINATION
This section describes the proposed methods of prior position determination in particle-filter-based indoor positioning. Equation (5) assumes that the tag’s velocity only changes at each time stamp. During the time interval between two consecutive time stamps, the tag experiences a uniform motion with a constant velocity. This assumption is reasonable since the UWB sampling intervals are usually short (sub-second). Therefore, the second-order term 
in the uniformly accelerated motion model can be neglected, and any residual biases are absorbed in the motion process noise.
The velocity components in the control vector 𝒖 in Equation (5) are usually measured by IMU (Wang & Li, 2017). This requires both sensors to start their data collections at the same time, meanwhile the calculated velocity for position prediction and the UWB observations for update must be strictly matched. Otherwise, unsynchronized samplings may result in the derived prior position being updated by incorrect UWB observations, and this may finally yield an incorrect posterior position. This work proposes two different self-contained velocity approximation approaches to replace the role of IMU for prior position determination. The two proposed approaches are presented as follows.
3.1 Approach 1: Velocity approximation based on consecutive particle filter estimated positions
When the particle filter estimated positions at the consecutive time stamps 𝑘−1 and 𝑘 are known, a velocity can be derived by dividing the distance between them by the sampling interval Δ𝑇. This approach uses this derived velocity to approximate the velocity at the time stamp 𝑘, which can be written as
12
where 
is the approximated velocity using Approach 1 at the time stamp 𝑘. 𝑥𝑃𝐹, 𝑦𝑃𝐹,𝑧𝑃𝐹 denote the coordinates of position estimated by the particle filter. Approach 1 requires an initial velocity estimate for the first time stamp (𝑘 = 0). This initial velocity value can be estimated approximately, and it can be set to zero when considering the target starting at rest. The covariance of motion process noise theoretically should be large enough for the first time stamp (such as twice the covariance of the latter time stamps) since the initial velocity estimate has great uncertainty. This is aimed at making the tag’s true position at the second time stamp locate within the coverage of the predicted particles and enabling the particle filter to converge to the true posterior position. This operation is similar to the roughening operation in Gordon et al. (1993).
3.2 Approach 2: Velocity approximation based on the consecutive Chan-Taylor estimated positions
As described in Section 2, the Chan-Taylor algorithm can estimate a tag’s position without any prior position information but by using TDOA distance measurements alone. Inspired by this feature, this approach first uses the Chan-Taylor algorithm to estimate the tag’s positions at the two consecutive time stamps 𝑘 and 𝑘 + 1. After that, a velocity at the time stamp 𝑘 can be derived by dividing the distance between the two Chan-Taylor estimated positions by the sampling interval Δ𝑇. The equation is
13
where 
is the approximated velocity using Approach 2 at the time stamp 𝑘. 𝑥𝐶ℎ𝑎𝑛,𝑘, 𝑦𝐶ℎ𝑎𝑛,𝑘,𝑧𝐶ℎ𝑎𝑛,𝑘 denote the coordinates of position estimated by the Chan-Taylor algorithm.
Approach 2 can set the motion process noise adaptively since the covariance of this approximated velocity can be determined by the error propagation law. Consider the covariance matrices of 𝒙𝐶ℎ𝑎𝑛,𝑘 and 𝒙𝐶ℎ𝑎𝑛,𝑘+ 1 that are 𝑸𝐶ℎ𝑎𝑛,𝑘 and 𝑸𝐶ℎ𝑎𝑛,𝑘+ 1, respectively, and they are independent. Then the covariance matrix of 𝒗𝑘 is
14
𝑸𝒗,𝑘 does reflect the uncertainty of the approximated velocity, so it can be used to derive the covariance matrix of motion process noise by multiplying it by the square of the sampling interval. In this case, it is unnecessary to set the motion process noise manually through tuning (Laamari et al., 2015) since the algorithm can determine the motion process noise adaptively. The covariance of the positioning estimate obtained by the Chan-Taylor algorithm can be found in Li and Oussalah (2011).
4 INVESTIGATION OF THE EFFECTS OF PRIOR POSITION ACCURACY AND PARAMETERS ON POSITIONING
The velocities derived using the two proposed approaches are both approximated values. The accuracy of the approximated velocity does directly affect the accuracy of the prior position and ultimately affect the positioning accuracy through filtering. In this section, the accuracies of the prior positions determined by the two proposed approaches are investigated analytically first. Then, based on the parameters in the bias vectors, the effects of these parameters on positioning accuracy are investigated through a simulation test.
4.1 Investigation of the accuracy of prior position determined by proposed approaches
4.1.1 Approach 1
To investigate the accuracy of the prior position determined by Approach 1, we consider 𝒙𝑘, 𝒗𝑘, and 𝒂𝑘 are the tag’s true position, velocity, and acceleration at the time stamp 𝑘, respectively. According to the uniformly accelerated motion model, the tag’s true position at the time stamp 𝑘+ 1 can be derived by
15
𝒙𝑃𝐹,𝑘 denotes the particle filter estimated position at the time stamp 𝑘. It can be factored as
16
where 𝒆𝑃𝐹 is the positioning error of the particle filtering algorithm. The tag’s predicted position using Equation (12) at the time stamp 𝑘+2 becomes
17
The bias vector of predicted position at the time stamp 𝑘+ 2 is
18
It shows that the prediction bias has two parts. The first part bias is the second-order term of the uniformly accelerated motion model. The magnitude of this part is dependent on the accelerations as well as the sampling interval. The second part bias consists of the particle filtering estimation errors. These errors are mainly caused by the observation noises and the distribution of sensors, and these errors will propagate over time. Lowering accelerations is theoretically a method for mitigating the first part bias, since when the magnitudes of accelerations are closed to zero, the first part bias is negligible. Therefore, this approach is suitable for the uniform motion with constant velocity. However, this method is unrealistic since the accelerations can be random in practice. To mitigate the overall prediction bias in Equation (18), two methods can be used together. The first method is to decrease the sampling interval Δ𝑇. Since the relation between the first part bias and sampling interval is quadratic, it is significantly sensitive to the magnitude of Δ𝑇. The second method is to set an appropriate covariance of motion process noise to model the uncertainty of the prediction. This covariance can be determined through tuning beforehand (Laamari et al., 2015).
4.1.2 Approach 2
Regarding the Approach 2, we still consider 𝒙𝑘, 𝒗𝑘, and 𝒂𝑘 are the tag’s true position, velocity, and acceleration at the time stamp 𝑘, respectively. 𝒙𝐶ℎ𝑎𝑛,𝑘 and 𝒙𝑃𝐹,𝑘 denote the positions estimated by the Chan-Taylor algorithm and particle filtering algorithm, respectively. They can be factored as
19
where 𝒆𝐶ℎ𝑎𝑛,𝑘 and 𝒆𝑃𝐹,𝑘 are the positioning errors using the Chan-Taylor algorithm and particle filtering algorithm, respectively. At the time stamp 𝑘+ 1, the true position can be written as shown in Equation (15). When Equation (13) is used for state estimation, the tag’s predicted position at the time stamp 𝑘+ 1 becomes
20
The bias vector of the predicted position at the time stamp 𝑘+ 1 is
21
It shows that the prediction bias is only related to the positioning errors using the Chan-Taylor and particle-filtering algorithms at each time stamp. These errors are mainly introduced from the observation noises and the distribution of sensors. Similar to Approach 1, these errors can be mitigated by setting an appropriate covariance of motion process noise.
4.2 Investigation of the effect of parameters on positioning accuracy by simulation test
In order to investigate the effect of motion parameters on positioning accuracy, the two proposed approaches are tested with a trajectory having different accelerations and orientations through a simulation. The simulation assumes that there is an indoor area with the size of 20 m × 100 m, and there are six UWB sensors with known coordinates. Figure 1 illustrates the motion process of the object (such as a person). The object performs four segments of motion. Each motion segment is denoted with different colors for clarity purposes. The process of each motion segment is described as follows.
The plan of the simulation scenario
First segment: the object starts from the known initial point A with a known initial velocity (1𝑚∕𝑠), it performs a uniform motion along the X direction for ten seconds and finally arrives at the point B.
Second segment: when the object arrives at the point B, it performs a sudden 90-degree turn. Then the object moves along the Y direction with the same velocity for ten seconds and arrives at the point C.
Third segment: At the point C, an acceleration of 0.2𝑚∕𝑠2 in the Y direction acts on the object. The object starts to perform a uniformly accelerated motion with this acceleration from the point C. This motion lasts for ten seconds until the object arrives at the point D.
Fourth segment: the acceleration increases to 0.5𝑚∕𝑠2 at the point D, and then the object performs a uniformly accelerated motion with the increased acceleration along the Y direction for ten seconds until it finally arrives at the point E.
Note that the transition between any two motion segments above is continuous and fluent. The whole motion lasts for 40 seconds. The variances of the motion process noise in three directions are assumed to be independent and set to the same value in this simulation. The variance of motion process noise is set to 0.01. This value is from the simulation test in Pak et al. (2017). Since the standard deviation of UWB TDOA range measurement noise is usually in the range of 0.1 m to 0.5 m (Jiménez & Seco, 2017; Wang&Li, 2017), the variance of the measurement noise of UWB TDOA distance is set to 0.01 in this simulation. Figure 2 shows the plan of the trajectories obtained by the particle filtering algorithm with the two proposed approaches. Figure 3 shows the 3-D positioning errors along the trajectory.
The plan of the trajectories obtained by the particle filtering algorithms with the proposed approaches. The scales in X and Y axes are different
The 3-D positioning errors along the trajectory. The scales in X and Y axes are different
It is found that when the object performs a uniform motion (first segment), the positioning accuracies of the two approaches are similar. When the object performs a sudden turn, the positioning error increases obviously in Approach 1 at the consequent first and/or second time stamps (see the time stamp 11 in Figure 3). The same situation happens when an acceleration acts on the object or the acceleration changes (see the time stamps 21 and 32 in Figure 3). Approach 1 uses the filtering positions at the previous two time stamps to approximate the velocity. When the object performs a sudden turn or change of acceleration, the derived velocity is greatly biased. This biased velocity causes a misprediction on the prior position and further leads to a large error on the posterior position. However, the particle-filtering algorithm can find out the predicted particles with high importance weights and discard those with low weights through resampling. Therefore, the large error will not last for a long time (usually one or two sampling intervals), and the positioning accuracies at the latter time stamps will not be significantly affected. Compared with Approach 1, Approach 2 has better robustness. This is because Approach 2 derives the velocity using the two positions estimated by the Chan-Taylor algorithm. The derived velocity and the object location are strictly matched in terms of time. The accuracy of the derived velocity in Approach 2 is not affected by acceleration. It is only affected by the accuracies of the positions estimated by the particle filter and the Chan-Taylor algorithms, see Equation (21). Therefore, the velocity provided by Approach 2 can accurately predict the prior position even if the object performs a sudden turn or change of acceleration. This test shows the characteristics of a particle filter, which can solve nonlinear acceleration and orientation problems.
5 TEST OF THE PROPOSED METHODS
To evaluate the performance of the two proposed velocity approximation approaches, a test is carried out based on an experiment. In the test, the positioning performance (positioning accuracy and computation efficiency) of the particle filtering algorithms using the proposed velocity approximation approaches are compared with the positioning performance of the three state-of-the-art particle-filtering algorithms, i.e., the particle-filtering algorithm using the IMU method, the standard particle filter, and the Rao-Blackwellized particle filter. Meanwhile, the positioning performance of the three particle-filtering algorithms are compared to that of the Chan-Taylor algorithm. The effect of AOA measurements on the positioning accuracy of the particle filter is also evaluated in the test.
5.1 Description of the experimental site and method
The experiment was performed in the atrium of the Sir Peter Mansfield Building at the University of Nottingham Ningbo China (UNNC). There are six UWB sensors installed on the wall of the building with the height of approximately 9 m above the ground. This height can reduce the cost of the need of more sensors to cover the experimental site because of the wide beam angle. Such an environment can be found in airport terminals (for tracking people) and warehouses (for tracking goods/cargos). The UWB hardware used in the test is the Ubisense series 7000. The tag emits a UWB pulse every four Ubisense time slots (each time slot corresponds to 27.029 ms), which is approximately 108.12 ms. The IMU device used in the test is MicroStrain 3DM-GX3-45. Its sampling rate was set to be 100 Hz, which outputs a group of measurements (i.e., acceleration, angular rate, strength of the magnetic field) every 10 ms. The UWB tag and IMU were well stuck on the top of a ranging rod, and the length of the ranging rod can be changed. The ranging rod was tightly fixed on a trolley as shown in Figure 4. To make both the tag and IMU have the same motion in the test, the centers of the two sensors were well stacked and tightly stuck together. It is found that the magnetic effect caused by the current is negligible in the test. Therefore, this stacked installation has no effects on each other’s sensor’s data collection.
The trolley used in the experiment
A stop-and-go method was used in the experiment for the purpose of avoiding any time synchronization problems of the two sensors affecting our accuracy assessments. The stop-and-go method means to start the trolley at rest at a known Point A and move towards and stop at an unknown Point B. During this process, the UWB and IMU data was collected with their own sampling rates. The data of both sensors could be well matched while the trolley stopped at Point B for about ten seconds. Then, the tag’s prior position at Point B can be derived based on the measurements from IMU. The posterior position at Point B can be obtained through the updating step in the particle filter by using the last UWB observation vector in the observation series. Then, this posterior position is regarded as the initial position for the next segment of motion from Point B to Point C. The IMU device used in our experiment is low cost. In order to mitigate the IMU position drifts, the zero-velocity update (ZUPT) technique (Foxlin, 2005) was used. This rigorous stop-and-go test enables both IMU-derived prior position and UWB observation for updating and is strictly position-matched for the evaluation purpose because it is free from the effect of the residual in sampling synchronization, the dynamic of the moving trolley platform, and the accuracy of visiting reference positions at a particular time.
A closed traverse survey was carried out before the test to obtain the coordinates of the UWB sensors in the Universal Transverse Mercator (UTM) reference system. The closed traverse involves four stations, and the total length is 104.697 m. The angular misclosure and linear misclosure of the traverse are 17.5′′ and 4.48 mm, respectively. The fractional linear misclosure is 1 in 23,370. Leveling survey was carried out to determine the heights of the traversing stations. The leveling involves three instrument points. The misclosure of leveling is 1 mm. The coordinates of the two traversing stations in the atrium, i.e., C1 and C2 (see Figure 5), were determined through traverse and leveling. To minimize the errors in traverse and leveling propagating into the coordinates of UWB sensors, the coordinates of the six UWB sensors were determined through the total station survey from C1 and C2. The calculations of the traverse were performed by a MicroSurvey software called Star*Net. The basics of the traverse, leveling, and total station survey can be found in Uren and Price (2010).
Locations of the six UWB sensors and twenty test points in the test (the first three digits for easting “360″ and northing “329″ are omitted, the unit is meter). The terms “easting” and “northing” are the UTM coordinates. Easting refers to the eastward-measured distance from the origin of the coordinates system, while northing refers to the northward-measured distance from the origin
For the purpose of obtaining various geometries for UWB signals, a rectangular track with the size of 9.6 m × 6.4 m was set in the middle of the atrium. Twenty test points with the interval of 1.6 m were distributed on the rectangular track for the stop-and-go test (see Figure 5). The horizontal coordinates of the twenty test points were determined through a total station survey from the two control stations C1 and C2, and their heights were determined through a leveling survey. The coordinates of the twenty test points (determined by the total station survey and leveling survey) are used as the “truth” in the performance assessment. In the test, UWB Sensor 4 acted as the master sensor, and the other five sensors acted as slave sensors. These sensors are connected by shielded CAT6e cables. Before the test, the pitch and yaw values of each UWB sensor were carefully determined by using the dual calibration method in the Ubisense LE. The cabling time offsets were also automatically estimated in the calibration; therefore, the six UWB sensors were tightly synchronized. The trolley started from the test point at the top left corner of the rectangular track in Figure 5. It moved steadily on the track in the clockwise direction and stopped (with the ranging rod pointed at the known test point on the ground) at each test point in turn. Finally, the trolley moved back to the first test point.
Since the height of the target to be positioned can be random in practice, the test was repeated twice with the tag placed at two different heights (Height 1: 1.489 m and Height 2: 2.063 m above the ground). The position estimates at the twenty test points can be obtained at each height. These forty position estimates are then compared with the “truth.” The accuracy assessment metrics are described as follows.
The Distance Root Mean Square Error (DRMSE) evaluates the positioning accuracy in the 2-D horizontal plane:
22
And the Mean Radial Spherical Error (MRSE) evaluates the positioning accuracy in 3-D space:
23
where 𝑛 is the number of samples, 𝑖 is the sample from 1 to 𝑛. 𝑥𝑖, 𝑦𝑖, and 𝑧𝑖 are the estimated easting, northing, and height of sample 𝑖, respectively. 𝑥, 𝑦, and 𝑧 are the “truth” values of coordinates determined by a total station survey.
The computation load of the particle-filtering algorithm with the proposed approaches are evaluated. It is assessed by the average computation time for one group of measurements, and it is determined through the function of “tic” and “toc” in MATLAB (R2016b). The specifications of the computer used in the test are Intel i5-6200U CPU @ 2.30 GHz, 4.00 GB RAM, and the operation system is 64-bit Windows 10 Home Version 1903.
Nine tests with different positioning algorithms and UWB measurements are performed in the evaluation, each test is numbered as shown in Table 1 for clarity. The process and measurement noises in the test are modeled as zero-mean Gaussian variables and mutually independent. The standard deviation of the process noise used in each algorithm is determined by a genetic optimization-based tuning method proposed in Oshman and Shaviv (2000). More examples of tuning methods can be found in Oshman and Shaviv (2000) and Imtiaz et al. (2006). The standard deviations of the measurement noises are determined by a statistical method, which is based on a list of measurements collected using a static tag. For an unbiased assessment in our test, the standard deviations of the process and measurement noises used in the test are shown in Table 2. The standard deviation of TDOA distance 𝜎𝑑 is also used in the Chan-Taylor algorithm. The initial position used for each particle-filter-based algorithm is estimated by the Chan-Taylor algorithm.
Algorithm and observation used for each test (PF: Particle filter)
Standard deviations of the process and measurement noises in each algorithm (PF: Particle filter)
The number of particles 𝑁𝑝 does affect the performance of the particle filter. For an unbiased assessment purpose, 𝑁𝑝 is first set to 5,000 for all the particle-filter-based algorithms. In order to investigate how the number of particles affects the positioning performance in each particle-filter-based algorithm, 𝑁𝑝 is set to nine different numbers ranging from 50 to 20,000. Each test is performed for 150 times (different runs with different seeds), and the mean values are used to represent the positioning results.
5.2 Test results
Table 3 presents the positioning performance of the nine tests. The changes of MRSEs and the average computation time of the five particle-filter-based algorithms (using both TDOA and AOA measurements) with different 𝑁𝑝values are presented in Figure 6 and Table 4, respectively.
Statistical results of the assessment (Np = 5000)
The comparison of MRSE of the five particle-filter-based algorithms with different numbers of particles. The scales in X and Y axes are different. (PF: particle filter)
The average computation time of the five particle-filter-based algorithms with different numbers of particles. (Unit: Ms, PF: Particle filter)
5.3 Discussion and analysis
This subsection discusses and analyzes the positioning performance of the particle filtering algorithms with the proposed approaches. The discussion is based on the performance comparison between the proposed approaches with the state-of-the-art positioning algorithms including the Chan-Taylor algorithm, the particle filter with the IMU method, the standard particle filter, and the Rao-Blackwellized particle filter.
5.3.1 Comparing the particle-filtering algorithm with the Chan-Taylor algorithm (Test-1 vs. Test-9)
The Chan-Taylor algorithm is generally used in static positioning while the particle-filtering algorithm is more often used in dynamic positioning. In this subsection, the positioning performance of the Chan-Taylor algorithm (Test-9) is compared with that of the particle-filtering algorithm (Test-1). This comparison aims to show the superiority of using the particle-filtering algorithm in indoor positioning problems.
Both Test-1 and Test-9 use the same measurements (TDOA) but different positioning algorithms. Positioning results of Test-9 are used as the baseline in this assessment. Regarding the performance in the 2-D horizontal plane as shown in Table 3, DRMSE results of the two tests are similar. DRMSE of Test-9 is only 0.34 cm smaller than that of Test-1. Regarding the performance in 3-D space, the MRSE of Test-1 is 0.29 m smaller than that of Test-9. The 3-D positioning accuracy of Test-1 is higher than that of Test-9 by approximately 25%. This improvement is mainly due to the more accurate height estimation in Test-1. The poor height accuracy in Test-9 may have two reasons. The first reason is the distribution of sensors in the test. In our test site, all the UWB sensors are installed above the ground with similar heights. This leads to the problem that it is impossible to cancel out any range errors in the vertical axis below the horizontal plane. The second reason is that the robustness of the Chan-Taylor algorithm is worse than that of the particle-filtering algorithm. The Chan-Taylor algorithm estimates positions based on the rule of Weighted Least Squares (WLS), and it aims to find out a single optimal solution that can best fit each constraint equation by minimizing the sum of the squares of residuals.
Since the raw TDOA distance measurement may be longer than the true distance due to a distance-dependent systematic bias or sometimes an error from interference, the distance vector will shift in the vertical direction (the horizontal direction has been well constrained by each sensor, which are almost coplanar distributed) to find out the optimal position. This usually causes an obvious shift in height. These error factors cannot be eliminated through differencing, and the error will be propagated through the Chan-Taylor algorithm. As a result, it reduces the accuracy of the derived position and affects the height in particular.
Regarding the computation time, it takes 588.2 ms per measurement on average for Test-1. This is almost 147 times the computation time of the Chan-Taylor algorithm. High computation load is the main limitation for the particle-filter-based algorithms.
5.3.2 Comparing the particle filter using proposed approaches with the particle filter using IMU (Test-3/5 vs. Test-1, Test-4/6 vs. Test-2)
In this subsection, the particle-filtering algorithms with the two proposed prior position determination approaches are compared with the particle filter with IMU. The three algorithms in this comparison are all based on the same dynamic model, in which the velocity is measurable.
Six tests are divided into two groups in this comparison. The first group compares Test-3/5 with Test-1, and the second group compares Test-4/6 with Test-2. This makes each group use the same UWB measurements but different prior position determination methods. The positioning result of Test-1 is used as the baseline in the first group, and the positioning result of Test-2 is used as the baseline in the second group. As shown in Table 3, Approach 1 performs similarly to the IMU-based method in both groups. In Test-3, the application of Approach 1 reduces 2-D accuracy by about 0.2% but improves 3-D accuracy by about 0.4%. In Test-4, the application of Approach 1 improves 2-D accuracy by about 1.6% but reduces 3-D accuracy by about 0.9%. These differences are statistically insignificant. Compared with Approach 1, the application of Approach 2 improves the accuracy slightly especially in the 2-D horizontal plane. In both groups, using Approach 2 can improve 2-D and 3-D accuracies by about 10.3% and 2.3% on average, respectively. Therefore, Approach 2 can provide a more accurate prior position than the IMU-based method or Approach 1. This may have two reasons. First, regarding the IMU-based method, its performance is usually seriously affected by the drifting problem. The accumulation error introduced from drifting is proportional to the third power of time (Wang & Li, 2017). Second, regarding Approach 1, the accuracy of the velocity approximation is related to the acceleration and sampling rate. When the sampling rate decreases, the accuracy of approximation reduces significantly. However, Approach 2 is not affected by these two parameters. The Chan-Taylor algorithm can provide a relatively accurate prior position (with the accuracy of about 20 cm) on the horizontal plane. Although its height estimation is less accurate than the horizontal position estimation, this can be mitigated in the prediction stage by the adaptive variance of motion process noise in the height. In both groups, the computation time of the three particle-filter-based algorithms are similar; the time differences of them are within 30 ms. These differences are negligible in practice.
Compared with the IMU-based method, the two proposed approaches are not affected by the sampling synchronization problem. Moreover, since only UWB is used, it enables the positioning system with the lower cost, smaller in size, and easier equipment installation. However, the IMU method still has its advantage. It can perform seamless positioning in the places where the UWB signals are blocked.
5.3.3 Comparing the particle filter using the proposed approaches with the standard particle filter and Rao-Blackwellized particle filter (Test-4/6 vs. Test-7/8)
In this subsection, the particle-filtering algorithms with the two proposed approaches are compared with the standard particle filter and the Rao-Blackwellized particle filter, respectively. All the three algorithms in this comparison use TDOA and AOA measurements.
Compared with the standard particle filter, the particle-filtering algorithm with Approach 1 improves 2-D accuracy by about 8.6% and 3-D accuracy by about 3.7%. The particle-filtering algorithm with Approach 2 improves 2-D accuracy by about 15.9% and 3-D accuracy by about 5.8%. As described in Section 2.3.1, the standard particle filter suffers from the problem of “curse of dimensionality.” Therefore, it is likely that 5,000 particles used in the test cannot well approximate the distribution of the true density for the standard particle filter, resulting in the larger positioning error. This analysis can be further proven by Figure 6 that except the standard particle filter, the MRSEs of the other four particle-filter-based algorithms tend to become stable when the number of particles is 2,000. After that, the increasing on the number of particles does not have a significant effect on the positioning accuracy improvement because the prior densities have enabled the predicted particles to be distributed closer to the mean of the posterior densities. However, the standard particle requires about 10,000 particles when the MRSE becomes stable. Although these 10,000 particles enable the standard particle filter to achieve similar positioning accuracy with the other four particle-filter-based algorithms, the cost is the greatly increased computation time (1,137.4 ms); see Table 4. This is approximately 4.7 times the computation time required for positioning using 2,000 particles.
Compared with the Rao-Blackwellized particle filter, the particle filter with Approach 2 achieves similar positioning accuracies in both the 2-D plane (with the DRMSE difference of 1.4 mm) and 3-D space (with the MRSE difference of 2.6 mm). Approach 1 performs slightly worse than Approach 2. The DRMSE and MRSE differences between the particle filter with Approach 1 and the Rao-Blackwellized particle filter are 14.6 mm and 9.5 mm, respectively. Although the Rao-Blackwellized particle filter also has six variables in its state vector, it tackles the problem of “curse of dimensionality” by partitioning the linear states. The nonlinear states (position components) are still estimated using the particle-filtering algorithm while the linear states (velocity components) are estimated using the Kalman filter. This implies that the particles occupy a lower dimensional space, which decreases the dimensionality from six to three. Therefore, less particles are required for filtering, and thus the computation time is decreased.
5.3.4 Comparing positioning performance of the inclusion and exclusion of AOA measurements in the particle filter (Test-1 vs. Test-2, Test-3 vs. Test-4, Test-5 vs. Test-6)
This subsection aims to verify the impacts of the inclusion of AOA measurements in particle-filter-based indoor positioning. Test-1/3/5 are compared with Test-2/4/6, respectively. This makes each pair of tests use the same positioning algorithm but different UWB measurements. Table 3 shows that when AOA measurements are included in positioning, the DRMSE and MRSE results of the three particle-filter-based algorithms decrease by about 4.6% and 37.3% on average, respectively. This result agrees with the conclusion in Lau et al. (2018). The accuracy improvements in Test-2/4/6 are mainly due to the more accurate height estimations. In our test site, the UWB sensors with similar heights have well constrained the tag’s horizontal position by TDOA distances. But there are less constraints on the vertical direction due to the lack of UWB sensors below the horizontal plane of the UWB tag. When AOA measurements are used in positioning, the azimuth measurement provides constraint on horizontal position components 𝑥 and 𝑦, and the elevation measurement provides constraint on the vertical position component 𝑧. Moreover, compared with TDOA measurements, AOA measurements have stronger resistance on reflected signals (Quan et al., 2017). Therefore, positioning using both TDOA and AOA can achieve better accuracy than using TDOA alone. Although the UWB sensors with both TDOA and AOA measurements are more expensive than those with TDOA measurement only, the loss in accuracy, robustness, and reliability may have greater concerns than low cost in high-accuracy indoor positioning applications. Regarding the computation time, the integration of AOA measurements increases about 1.6 ms for each particle-filter-based algorithm on average. This time difference is negligible in practice. The integration of AOA measurements will not significantly increase the computation load.
6 CONCLUSION AND FUTURE WORK
Ultra wideband (UWB) is widely used for indoor positioning. Particle-filter-based indoor positioning requires known velocity to predict the prior position in the prediction stage. Velocity can be generally obtained by two methods. One method is using a complementary sensor such as Inertial Measurement Unit (IMU) to provide the parameters required for prior position determination. This method requires the sampling synchronization between two types of sensors and increases the system cost and the equipment size. The other method is using measurements to compute the velocity by treating the velocity as unknown variables and containing it in the state vector. However, this method may suffer from the problem of “curse of dimensionality.”
This paper proposes two novel approaches for prior position determination. Both proposed approaches replace the need of IMU by using two different self-contained velocity approximation algorithms. Approach 1 approximates the velocity based on the two consecutive particle filter estimated positions, while Approach 2 approximates the velocity based on the two consecutive Chan-Taylor estimated positions. The analysis shows that the particle-filtering algorithms with the two proposed prior position determination approaches perform similarly in uniform motion. As for the random motion with the changes of direction and acceleration, Approach 2 has slightly better robustness than Approach 1. The test results show that the particle filter with Approach 2 performs similarly to the Rao-Blackwellized particle filter and slightly better than the particle filter with IMU. The computation time of the two proposed approaches is affordable for most real-time applications. Moreover, it is found that the integration of AOA measurements in the particle filter can improve the 3-D positioning accuracy by about 37% on average.
Future research on using the proposed methods in NLOS indoor environments will be carried out. Some strategies such as the least-median-of-squares (LMedS) method and the residual weighting algorithm (Rwgh) can be integrated into the particle filtering algorithms with the two proposed approaches to mitigate the NLOS effects.
HOW TO CITE THIS ARTICLE
Zhou N, Lau L, Bai R, Moore T. Novel prior position determination approaches in particle filter for ultra wideband (UWB)-based indoor positioning. NAVIGATION. 2021; 68(2):277–292. https://doi.org/10.1002/navi.415
- Received March 22, 2020.
- Revision received February 10, 2021.
- Accepted February 18, 2021.
- © 2021 The Authors. NAVIGATION published by Wiley Periodicals LLC on behalf of Institute of Navigation.
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
Jump to section
Related Articles
Cited By...
- No citing articles found.