Industry 4.0 is triggering the rapid development of solutions for indoor localization of industrial vehicles in the factories of the future. Either to support indoor navigation or to improve the operations of the factory, the localization of industrial vehicles imposes demanding requirements such as high accuracy, coverage of the entire operating area, low convergence time and high reliability. Industrial vehicles can be located using Wi-Fi fingerprinting, although with large positioning errors. In addition, these vehicles may be tracked with motion sensors, however an initial position is necessary and these sensors often sufer from cumulative errors (e.g. drift in the heading). To overcome these problems, we propose an indoor positioning system (IPS) based on a particle filter that combines Wi-Fi fingerprinting with data from motion sensors (displacement and heading). Wi-Fi position estimates are obtained using a novel approach, which explores signal strength measurements from multiple Wi-Fi interfaces. This IPS is capable of locating a vehicle prototype without prior knowledge of the starting position and heading, without depending on the building's floor plan. An average positioning error of 0.74 m was achieved in performed tests in a factory-like building.
visible Access Points (APs)) are obtained in known positions (reference points) which compose
the building’s radio map. In the online phase, a Wi-Fi fingerprint is obtained, then it is
compared against the radio map using a similarity function (e.g. Euclidean or Manhattan
distance). Finally, a position is obtained using for example the k-Nearest-Neighbor (kNN)
algorithm. Due to the nature of Wi-Fi signals, fingerprinting is characterized by large maximum
errors and achieves mean errors between 2 m and 4 m [
The positioning and tracking of industrial vehicles have demanding requirements, namely, a fast convergence time (the time it takes to find the absolute position of the vehicle with an acceptable positioning error), a low maximum error, and coverage of the entire operating area. In this paper, we address the indoor positioning of industrial vehicles, including autonomous mobile robots, manned or even hybrid vehicles (can be both autonomously and manually operated). To solve this problem, we propose a particle filter (PF) solution for the fusion of motion data with Wi-Fi fingerprinting. It takes advantage of the Wi-Fi technology that provides coverage of the entire operating area, which makes it afordable to deploy in large industrial scenarios. In addition, vehicles are tracked using motion sensors, namely, an inertial measurement unit (IMU) (providing heading) and a rotary encoder (providing displacement) to improve accuracy. In our solution, no assumptions are made regarding the starting position/heading, i.e. there is no initial information regarding the position and heading of the vehicle. The absolute heading provided from the IMU sensor could be used, however it can be afected by magnetic perturbations from large machinery in industrial environments. Since the proposed solution will be deployed in an industrial scenario it should be capable of estimating the position as well as the heading.
The main contributions of this paper are threefold. First, the proposed solution achieves better performance than traditional Wi-Fi fingerprinting for indoor tracking. Second, indoor positioning and tracking of industrial vehicles is achieved without any assumption regarding the starting position/heading. Third, in contrast with most particle filters, which take advantage of the oflor plan to remove particles that have hit walls or obstacles, the proposed solution does not depend on the building’s floor plan.
Diferent technologies may be used for localization and tracking in indoor environments, such
as, Wi-Fi [
The ubiquity of WLAN networks has led many researchers to explore Wi-Fi for indoor positioning and tracking. In [11], several positioning solutions are compared against each other in an of-site competition, in which teams implement their own algorithms using the same training and evaluation data, collected with a smartphone. The solution with the best results uses Wi-Fi fingerprinting based on the kNN algorithm, achieving a mean error of 3 m.
Improved positioning performance is achieved when Wi-Fi is combined with other sensors.
In [
Zou et al. [12], proposed a system based on pedestrian dead reckoning (PDR). Two approaches may be used to provide position estimates: one that uses a PF to fuse Wi-Fi fingerprinting with PDR, and another based on a PF that uses Wi-Fi nfigerprinting with PDR but also adds iBeacon technology to improve position estimates. The proposed solution achieves a mean error of 1.48 m and 0.60 m in performed tests using the former and the latter approaches, respectively.
Liu et al. [13] proposed a network-based indoor tracking system, which uses a PF to combine inertial data with physical layer channel state information (CSI) from Wi-Fi signals. A mobile device (smartphone) broadcasts Wi-Fi packets (with IMU timestamped data) to anchor nodes that are distributed through the indoor environment. Anchor nodes send the packets to a central server that extracts the CSI information from WiFi cards in anchor nodes, and finally track the target with these two pieces of information. A mean error of 1.30 m was achieved in experiments carried out in a building with 16x18 m.
In [14], machine learning is used to merge Wi-Fi fingerprinting with PDR data. Initial position and heading are estimated with the proposed algorithm that takes advantage of PDR data to mitigate the weakness of Wi-Fi-based positioning. Performed experiments in a large building (167x27 m) have revealed a mean error of 2.71 m.
The main drawbacks of the above-mentioned solutions are that some use PDR which is not applicable to vehicles because the movement models of vehicles and pedestrians are diferent, and some solutions require additional infra-structure (iBeacons or anchor nodes) which represent additional deployment and maintenance costs.
Particle filters are a type of Monte Carlo algorithms suitable for solving estimation problems in non-linear non-Gaussian scenarios. In comparison to the Kalman filter, PFs have the advantage of not relying on any local linearization technique or any crude functional approximation. The disadvantage of PFs is that they are computationally expensive. However, with the increasing computational capabilities, it is now possible to have real-time applications for indoor positioning.
A particle filter uses many particles with diferent weights which represent the probability of the particle being in the real position. Initially, particles are dispersed throughout the space and, as the vehicle starts moving, particles also move and start converging to an area where it is more likely to be the vehicle’s true position. Updating particles’ positions and weights as the vehicle moves around allows to remove particles from places where it is unlikely or impossible for the vehicle to be at. The removal of particles is performed in a process called resampling. In this process, particles with lower weights are removed and particles with higher weights are copied to create new particles. The weighted average of the particles’ positions and headings represents the estimated position and heading of the vehicle.
As introduced previously, the particle filter depends on three processes: sampling (when data from sensors is received); updating particles’ weights; and resampling. The flowchart, in Figure 1, depicts the top level algorithm of the proposed PF.
A particle is defined as p = (w, x, y, h, ho), where w denotes the weight of the particle, (x, y) represent the position coordinates of the particle in a Euclidean space (since we are considering one single floor the z coordinate value remains fixed, hence it is not used), h represents the heading of the particle and ho represents the heading ofset of the particle, which is used because the initial heading is unknown.
initialize particles
Alg. 1
start get next sample ODO
no IMU
no WIFI yes yes yes update particles' positions
Eq. 1 update particles' headings
Eq. 2 update particles' weights Eqs. 3, 4 update vehicle position and
heading Eqs. 11, 12 resample Eqs. 6-8
After particles have been initialized (see Section 3.2), the algorithm enters a loop that waits for data coming from sensors. In this loop: • Every time a new odometer sample is received, the positions of the particles are updated; • Particles’ headings are updated when a new IMU sample is obtained; • Particles’ weights are updated when a new Wi-Fi sample is obtained, then they are subject to resampling; • Finally, an estimated position and heading is obtained by combining the particles’ positions and headings. This process is performed after updating the particles’ headings, defining the PF sampling rate which is a reasonable update interval (20 Hz) that does not compromise computing performance.
As an alternative to using the building’s floor plan to remove particles that have hit walls or obstacles, we propose a diferent approach where the reference points used in Wi-Fi fingerprinting are used to define areas where vehicles can navigate, therefore only a limited set of points is necessary to define these areas. If particles move into areas where no reference points exist, they must be removed. Navigable areas are defined by a set of reference points, where each point covers the area of a circle with radius r.
Usually, particles are uniformly distributed throughout the navigable space when they are initialized. This approach leads to large errors in initial iterations, as particles take some time before converging into a small area. We explore a diferent approach, where particles are created near reference points where it is more likely for the vehicle to be near. Algorithm 1 describes how particles are initialized.
Algorithm 1: Initialize particles. 1: procedure Initialize Particles(W iF in, M ) 2: c=centroid of first W iF in Wi-Fi position estimates 3: RP s=list of ref. points within a rini radius of c 4: np = M/#(RP s) 5: for rp in RP s do 6: for i = 1 until np do 7: w = 1/M 8: x = rp.x + rand(0, r) 9: y = rp.y + rand(0, r) 10: h = 0 11: ho = rand(− π, π ) 12: p = (w, x, y, h, ho) 13: P = P ∪ {p} set of all particles
In our experiments, the total number of particles (M ) considered is 3000, a distance of √2 m and 4 m were defined as the r and rini values, respectively. The first value was chosen because the reference points used to create the radio map are distributed in a grid with 1 m between points. The second value (4 m) represents the typical mean error of a Wi-Fi fingerprinting system. The number of Wi-Fi position estimates obtained before the initialization was defined as W iF in=3. Each Wi-Fi position estimate was obtained using kNN with k=5.
Particles need to be moved to a new position with each new odometer sample. The position of each particle is updated using a motion model, where the displacement is obtained from the latest odometer sample, and using its current heading value: x = x− 1 − (l + nl) ∗ sin(h) y = y− 1 + (l + nl) ∗ cos(h) (1) where x− 1 and y− 1 represent the previous position coordinates of the particle, l represents the displacement and nl represents zero-mean Gaussian noise added to the displacement. In conducted tests, nl is defined by N(0, 0 .004 m).
Once a new heading sample is received, particles’ headings are updated. A particle’s heading includes the heading obtained from the IMU sensor, a random value and the random heading ofset (which was generated when the particle was created): h = θ + nθ + ho (2) (3) (4) where θ represents the latest heading sample from the IMU sensor, nθ represents zero-mean Gaussian noise and ho is the heading ofset of the particle. In our experiments, nθ is characterized by N(0, 0.05o).
Particles’ weights are updated based on Wi-Fi position estimates. Whenever a particle is further than r meters of any reference point within the indoor space, its weight is set to zero, because it means that the particle has moved into an area where the vehicle cannot navigate through. The r parameter depends on the distance between adjacent reference points.
The current weight of a particle is updated based on the distance between the particle and the latest Wi-Fi position estimate. The larger the distance between the particle and the latest Wi-Fi position estimate, the lower its weight will be. The final weight of each particle depends on the current weight value and on its previous value:
w = (1 − α ) ∗ w− 1 + α ∗ (1 − dn) where w− 1 represents the previous particle weight, dn is the normalized distance between the particle and the latest Wi-Fi position estimate, and α is a value between 0 and 1 which represents how much the current weight contributes to the particle weight, conversely, (1 − α ) represents how much the previous weight contributes to the particle’s weight. The normalized distance, dn, is given by: dn =
d − min(D) max(D) − min(D) where d represents the distance between the particle and the latest Wi-Fi position estimate, and D represents the set of distances between all particles and the latest Wi-Fi position estimate. Warm-up Once particles are initialized, the PF starts estimating the vehicle’s position. During the first iterations, the confidence on the vehicle’s estimated position is low because the initial heading is unknown and because the particles take some time to converge into a concentrated cluster. Therefore, during the first iterations, the importance of Wi-Fi position estimates should be higher when updating the particles’ weights. After this period, Wi-Fi position estimates can be given a lower importance in updating the particles’ weights. This can be done by adjusting the value of alpha in equation 3 over time, starting with alpha equal to one and reducing its value during the warm-up period up to a minimum value (α min), as follows: α (t) = ︃{ (1 − α min) ∗ (e− t/35) + α min , t < twarm− up α min , t ≥ twarm− up where t denotes the time since particles were created, α min denotes the value of α after warmingup, and twarm− up defines the warm-up time. We have set α min = 0.05 and twarm− up = 180 s.
Resampling particles has the purpose of removing particles with lower weights and replace them with new ones in order to allow a faster convergence and to maintain the particle diversity. Two parameters are used to define how particles are removed, the resample percentage and the weight threshold. The first ( resample%) defines a percentage of particles with lower weights that are removed. The second (wth) denfies a threshold where particles with weights lower than it are removed.
In the resampling process, two distinct cases (depicted in Figure 2) may occur depending on the resample%, the wth and the particles’ weights. Figure 2 (a) shows the case in which percentage of samples removed from the wth criteria is lower than resample%, while Figure 2 (b) illustrates the opposite case.
1 1 1 1 2 2 2 2 3 3 3 3 (5) (6) (ordered by decreasing weight) (ordered by decreasing weight) ...
...
PPaarrttiicclleess (a) ((aa)) ...
...
PPaarrttiicclleess ((bb)) (b) (ordered by decreasing weight) (ordered by decreasing weight) rreessaammppllee%%
wwtthh wwtthh rreessaammppllee%%
MM--22
MM--11
M
M MM--22
MM--11
M M
In both scenarios, the particles removed due to the resample% (represented in green in following a similar process as the one described in Section 3.2. The weight of new particles near the Wi-Fi position estimate is defined by: w = ︃{ wmin
, dvw > dmax f (dvw) , dvw ≤ dmax where dvw represents the distance between the vehicle’s latest position estimate (ρ vehicle) and the Wi-Fi position estimate (ρ wifi), dmax defines the maximum allowed distance between ρ vehicle and ρ wifi, and, f (dvw) = dmax − dvw dmax
× (wmax − wmin) + wmin where the distance dvw is converted into a weight value between wmin and wmax, the lower the distance the higher the weight value. This gives more emphasis to ρ wifi estimates when they are closer to ρ vehicle and have a lower impact when ρ wifi is further away from ρ vehicle, which occurs when ρ wifi is an outlier.
IMU sensors are susceptible to magnetic perturbations which afect magnetometer readings, consequently afecting the estimated heading, which usually leads to drift in the heading. Drift can be minimized by assigning diferent heading ofsets to resampled particles because there are particles that follow the real trajectory whilst others will move away from the trajectory or move into non-navigable areas. Particles that follow the real trajectory are the ones that hold the most likely heading ofset, therefore they will end-up having higher weights. To minimize drift in the heading and improve heading estimation, resampled particles created around ρ wifi have a new heading ofset, defined as:
A combined sample can be obtained by computing the average of the RSSI values from each interface: where where ho′ is the heading ofset of a randomly selected particle (from the subset of particles with weight higher than wth) and nho represents a zero-mean Gaussian distributed random angle. In our experiments, nho is defined by N(0, 8 ◦ ).
When the resample% of particles is lower than the number of removed particles due to the wth (Figure 2 (b)), it is necessary to create new particles (represented in purple in Figure 2 (b)) to maintain the total number of particles constant. These new particles are created from the sub-set of particles that have weights higher than wth, which are randomly selected and copied.
We have set the following parameters in the resampling process: dmax = 4 m, wmin = 0.05, wmax = 0.5 and resample% = 0.1.
We have devised a new technique for improving positioning performance with Wi-Fi
fingerprinting. In this technique, described in [
Let us assume that N interfaces are used and that all of them collect a sample at the same time instant.
We define a Wi-Fi sample
sit as the list of RSSI (Received Signal Strength Indicator) values measured by interface i, from each of the R access points, in time instant t: ho = ho′ + nho sit = (︁ RSSI1i , ..., RSSIRi)︁ st = ︂( RˆS︂SI1, ..., RˆS︂SIR
︂) ︂( RSSIj1 + ... + RSSIjN )︂ (8) (9) (10) where RSSIi refers to the signal strength of AP i from the radio map sample (rm) and the online test sample (t).
The most similar radio map Wi-Fi samples are the ones used to find a Wi-Fi position estimate. We use the kNN algorithm to find the position estimate based on the k most similar radio map Wi-Fi samples: ∑︁k ρ wifi(x, y) = i=1 ski(x, y) (13) where ρ wifi(x, y) represents the Wi-Fi position estimate and s represents each of the k most similar Wi-Fi radio map samples. In our experiments we set k = 5.
The weighted average of particles’ positions represents the vehicle’s estimated position, defined as:
The calibration phase comprises the collection of several combined Wi-Fi samples at known reference points spread through the navigable space. In the real-time phase, the similarity of a Wi-Fi sample is computed for all samples of the radio map. Manhattan similarity was chosen as the similarity function, defined as: (12) (14) (15) ρ vehicle(x, y) = ∑︁M i=1 pi(x, y) × pi.w ∑︁M
i=1 pi.w hvehicle = tan− 1 ︄( ∑︁M
i=1 sin(pi.h) × pi.w )︄ ∑︁M
i=1 cos(pi.h) × pi.w where ρ vehicle(x, y) represents the vehicle’s position, pi(x, y) and pi.w refer to the position and weight of the ith particle.
Similarly, we obtain the estimated heading of the vehicle: where hvehicle represents vehicle’s heading, pi.h and pi.w refer to the heading and weight of the ith particle.
We conducted experiments using a prototype of a vehicle that we refer to as mobile unit. Before starting any experiments it was necessary to map and afix tags to the floor in the testing scenario so that we could create the radio map and obtain ground truth information when running experiments.
The PIEP building, shown in Figure 3, is located at the University of Minho and measures 50 by 20 m and is more than 8 m high. In many aspects, it is similar to a factory plant with large machinery, plenty of metal structures and tools, and some large open spaces, therefore it is an ideal scenario to conduct experiments.
Eleven Wi-Fi APs operating in the 2.4 GHz frequency band, represented by the blue circles in Figure 4, are present in the building. The set of reference points considered in the Wi-Fi radio map are represented by the grey squares in Figure 4. The distance between adjacent reference points is one meter, in most of the cases.
20 15 10 5 0 path 1 path 2 path 3 path 4 AP ref. point -30 -20 -10 0 10 20
Before performing tests, it was necessary to create a radio map by collecting 20 samples at each reference point (around 4000 total samples). Each one of the samples includes merged RSS values from five fingerprints, each one of them collected through a diferent Wi-Fi interface.
We collected test data in four distinct trajectories, depicted in Figure 4. The duration of each trajectory was 10, 6, 6 and 4 minutes respectively, and the travelled distance over all trajectories sums up to almost 300 m. Data was collected by moving the mobile unit over the trajectories at normal pedestrian speed (around 1 m/s). Ground truth data was manually collected, with the help of a video camera pointed towards the floor where it recorded the reference tags as the mobile unit moves over them.
We have equipped a trolley with several sensors. It can be easily pushed to emulate the movement of a vehicle in indoor environments. As shown in Figure 5, the mobile unit is equipped with a Raspberry Pi Model 3B with integrated Wi-Fi interface as well as the following sensors: four external Wi-Fi interfaces (Edimax EW-7811un) connected through a USB HUB; an IMU (Xsens MTi-300 AHRS) to measure the heading; and an absolute encoder (US Digital A2) to measure the displacement.
The euclidean distance between the position estimate and the ground truth was used as the positioning error metric. The PF solution was executed with data from each testing trajectory ifve times and obtained similar results.
Table 1 shows the PF positioning results of each trajectory which include position estimates of all runs. The last two columns of the table (“All” and “After warm-up”) consider all position estimates of all runs. For comparison, Table 2 shows Wi-Fi fingerprinting results, obtained with k = 5.
The proposed PF is capable of minimizing the main problems of Wi-Fi fingerprinting, reducing overall the maximum error (from 18.12 m to 9.48 m) and achieving a great improvement in the mean error (from 3.68 m to 1.47 m). The maximum error with the PF is still considerable due to the warm-up period, in which particles are still converging.
Regarding the results achieved with the PF, a significant improvement is observed (Table 1) in the overall mean error after the warm-up time. The mean error is reduced from 1.47 m to 0.74 m because larger positioning errors, mostly observed during the warm-up period, are not considered. This can be observed in Figure 6, that depicts the error variation over time in each trajectory (includes all five runs). As expected, larger positioning errors are observed during the initial phase when the PF is still converging. Once the PF converges, the positioning error remains low, suggesting that better overall results would be achieved in longer experiments. Industrial vehicles are expected to be in operation during long periods, therefore this last metric (after warm-up) is the one that better represents the expected accuracy of our solution in a real environment.
0 100 300 400 0 100 200 300
The PF estimated positions of trajectory 1 are depicted in Figure 7. As can be seen, initially there is a higher error during the warm-up period, then the PF converges and the estimated path follows the real trajectory closely. 10 9 8 7 ) 6 m r( 5 ro4 r E3 2 1 0 8 7 6 )5 m (4 r o rr3 E2 1 0 20 15 10 5 0 -30 -20 -10 0 10 20
Figure 8, shows the CDF of the positioning error. The overall CDF curve of the PF has a much higher maximum error (over 9 m) when comparing to the PF CDF after warm-up where the maximum error is approximately 2 m.
In the performed tests, we have considered that the initial heading is unknown, because magnetic perturbations, if present, might afect the absolute heading estimated by the IMU sensor. However, in scenarios where magnetic perturbations are not a concern, there are applications where the initial heading is provided and reliable, for instance, electric industrial vehicles usually charge in a docking station where they maintain their heading, hence knowing the initial heading can speed-up the convergence time of the PF. In this context, we decided to run the previous experiments with a known initial heading and achieved an overall mean error of 0.85 m and 0.80 m (after warm-up). The main diference in these results is that the larger errors are minimized, reducing the mean and maximum errors. When the initial heading is known, the maximum error of trajectories 1, 2 3, and 4 is 1.58 m, 4.39 m, 1.42 m, and 1.87 m, respectively.
Table 3 shows the proposed solution compared with similar indoor positioning systems. The
best performance is achieved with the proposed PF (after warm-up). The solutions in [
We have presented a solution for the indoor positioning and tracking of industrial vehicles, consisting of a particle filter that performs the sensory fusion of Wi-Fi and motion sensors’ data without depending on the floor plan of the building. In addition, the proposed solution is capable of estimating the position and heading without knowledge of the initial position and heading. Wi-Fi fingerprinting takes advantage of existing WLAN infra-structure and allows to obtain an absolute position which is used to provide an initial position and to update particles’ weights whenever a new Wi-Fi sample is obtained. Motion sensors (IMU and encoder) allow an accurate tracking of the vehicle during the navigation through the industrial space. We conducted experiments in a factory-like environment where we collected test data with a vehicle-like prototype. An overall mean error of 0.74 m and maximum error of 2 m are achieved when considering that the particle filter has already converged. The performance achieved by our solution makes it suitable for the localization and tracking of vehicles in industrial environments, allowing to improve day-to-day tasks performed by these vehicles. It is also appropriate for supporting indoor navigation, however it does not have suficient accuracy for tasks such as docking, which require higher accuracy. In the future, we intend to develop a solution to improve the particle filter convergence time and to conduct further experiments to validate this solution using real industrial vehicles.
This work has been supported by FCT – Fundac˜a¸o para a Ciˆencia e Tecnologia within the R&D Units Project Scope: UIDB/00319/2020, the PhD fellowship PD/BD/137401/2018 and the Technological Development in the scope of the projects in co-promotion no 002814/2015 (iFACTORY 2015-2018). [10] E. Ivanjko, I. Petrovci,´ Extended Kalman filter based mobile robot pose tracking using occupancy grid maps, Proc. Mediterr. Electrotech. Conf. - MELECON 1 (2004) 311–314. doi:10.1109/melcon.2004.1346851. [11] J. Torres-Sospedra, A. Jimen´ez, A. Moreira, T. Lungenstrass, W.-C. Lu, S. Knauth, G. Mendoza-Silva, F. Seco, A. Per´ez-Navarro, M. Nicolau, A. Costa, F. Meneses, J. Farina, J. Morales, W.-C. Lu, H.-T. Cheng, S.-S. Yang, S.-H. Fang, Y.-R. Chien, Y. Tsao, OfLine Evaluation of Mobile-Centric Indoor Positioning Systems: The Experiences from the 2017 IPIN Competition, Sensors 18 (2018) 487. URL: http://www.mdpi.com/1424-8220/ 18/2/487. doi:10.3390/s18020487. [12] H. Zou, Z. Chen, H. Jiang, L. Xie, C. Spanos, Accurate indoor localization and tracking using mobile phone inertial sensors, WiFi and iBeacon, 4th IEEE Int. Symp. Inert. Sensors Syst. Inert. 2017 - Proc. (2017) 1–4. doi:10.1109/ISISS.2017.7935650. [13] Z. Li, D. B. Acuna, Z. Zhao, J. L. Carrera, T. Braun, Fine-grained indoor tracking by fusing inertial sensor and physical layer information in WLANs, 2016 IEEE Int. Conf.
Commun. ICC 2016 (2016). doi:10.1109/ICC.2016.7511162. [14] L. H. Chen, E. H. K. Wu, M. H. Jin, G. H. Chen, Intelligent fusion of wi-fi and inertial sensor-based positioning systems for indoor pedestrian navigation, IEEE Sens. J. 14 (2014) 4034–4042. doi:10.1109/JSEN.2014.2330573.