Img Source - Ray Dak Lam
Introduction to Particle Filter
Indoor navigation allows us to provide navigation solutions and organize navigation inside the building. To implement the navigation, it’s necessary to create the correct positioning model. The algorithm estimates the position of the object and builds a statistical distribution of potential positions of the object. One of the approaches used to create a probabilistic positioning model is a particle filter. This will be the subject of today’s article.
Problem statement
Let’s suppose that we have a certain location, where we need to provide precise real-time indoor positioning of a person. Location plan with the “white area” — part of the space where it’s possible to go as well as barriers and other obstacles, including walls, facilities and non-walking parts of the building is provided. The user is located in a place where it is impossible to use traditional positioning methods such as GPS / GLONASS signals or these technologies cannot give a precise outcome. In this case, we need to implement another navigational approach that can solve the described problem with sufficient accuracy.
Figure 1 - Plan of the location with barriers
Available Technologies
Indoor navigation can be provided using smartphones. Regular smartphones operate with multiple data acquisition technologies for communication, internet access, and other purposes. WiFi and Bluetooth® are popular protocols that are used for data exchange. Also, there are inertial sensors, such as accelerometers, magnetometers, and gyroscopes. They are used to locate the phone in space and provide measurements of the screen position, rotation, and other useful information.
The Navigine blog has articles covering information about Bluetooth® Low Energy protocol and navigation using WiFi. Another important approach in telecommunication is RSSI. RSSI stands for received signal strength indication. It allows one to calculate the distance between the emitter of radio signals and the receiver depending on the strength of the received signal. The propagation model of Bluetooth® signals assumes that the signal power between the smartphone and the source of the signal decreases with the distance between them. The advantage of RSSI positioning is that it does not require large energy consumption. The disadvantage of RSSI is that the energy of electromagnetic waves cannot be measured through metal constructions. Other obstacles also affect the signal propagation so the accuracy of navigation drops down.
That is why it is necessary to use other sources of information that can provide additional data such as user speed and motion direction. During the movement, the position of the user can be adjusted according to the measurements from numerous sensors. These sensors include an inertial navigation system, consisting of an accelerometer, gyroscope, magnetometer, and external signals, most commonly from Bluetooth® and WiFi protocols.
Indoor Navigation
Indoor navigation is different from usual GPS positioning. Since sometimes it’s impossible to use GPS inside the building, various approaches are used to provide indoor navigation, including installations of iBeacon, WiFi access points, and sensors. You can read in detail about indoor positioning.
Navigine uses compound solutions as a combination of radio signals and sensor data. Positions of WiFi access points and Bluetooth® transmitters are known in advance. It allows real-time measuring of the power of signals between transmitters and the smartphone, which can be used to calculate the distance between them and use this information during navigation.
Demo of the particle filter algorithm on the Railway Terminal
Since the measurements can not give an accurate position due to perturbations, noise, and inconsistency, it is necessary to find the optimal point among different variants. The task of a particle filter is to determine the possible position of the user based on measurements and provide the most probable location on the map as a result.
Navigine SDK
Learn more about the professional Real-Time Indoor Navigation solutions for mobile apps
DISCOVER INDOOR NAVIGATIONParticle Filter: Definitions and Overview
The particle filter generates so-called particles. Each particle represents a certain state of the system - position and orientation. First, at the very beginning of navigation, particles are generated with normal distribution, because there is no information about the positioning of the device. The coordinates and orientations of a device are distributed according to the geometry of a location. This procedure is called sampling.
Each particle has its parameter - weight. This number represents the probability of the system being in a certain state. The bigger the weight, the larger the probability to find a user in a particular place. Then during navigation, the measurements from sensors give more precise information about the position of a smartphone. The weight of a particle is calculated according to the measurements. For different types of data distribution protocols, Navigine applies different likelihood models with specific distributions of the weights. Particles that correspond to positions that were not observed during the data acquisition step, “die”.
The resampling procedure creates more particles around points that are closer to a solution, so the number of particles is compensated by new ones. For other particles, weights are adjusted and the overall position of a user on the map is corrected. The particle filter is called the Monte Carlo localization method. It is also referred to as a Bayesian filtering problem. Let’s dive into the algorithm.
How Particle Filter Works
Initialization
Figure 2 - Initialization of the particles
The initial generation of the particles is held in the area where the device can be possibly found. Since the map consists of various barriers, such as walls and other obstacles, the user can not be placed anywhere. Also, the important point is that navigation is possible only to those places on the map that are close to the transmitters to provide stable signal coverage. That is why the initialization of the particles takes place only after the first package of accumulated signals. On figure 2 one can see the initialization of the particles. Particles with red color are supposed to have higher weights and particles with blue color have low weight correspondingly.
Prediction
Figure 3 - Measurements acquisition and trajectory
The position of each particle can be predicted using trajectory information from a sensor fusion module that combines the measurements from different sources. Position adjustment provides the length of the step and motion direction. Position and angle increment depend on an additional value that is randomly generated based on the possible step length and direction. This uncertainty is needed because it is necessary to take into account all the possible changes in the trajectory. Particles with positions that do not fit in the location predicated by the geometry are considered to be dead (have zero weight). Sometimes the accuracy of measurements can not provide a sufficient number of particles with valid positions. In this case, the weights are to be initialized again. As one can see in figure 3, highlighted green circles represent transmitters in the measurement acquisition area. Measurements from other transmitters are not taken into consideration. The trajectory of a user is mapped by a dashed line.
Correction and resampling
Figure 4 - Localization of the particles Particle filter localization
The correction procedure is applied whenever the smartphone receives a package of accumulated signals. This process is divided into four parts.
1. Mutation
To reduce the number of calculations and improve the accuracy of prediction, mutation can be applied. There is a set of generated particles that are supposed to be a subject of mutation procedure. The number of particles to be mutated is determined by algorithm settings. Mutation resamples coordinates and directions of the particles in a set according to the map and received measurements. In this case, sampling is followed by Gibbs distribution.
2. Additional sampling
As one can see in figure 3, only the nearest transmitters are taken into account. The signal propagation distance of a transmitter is relatively small, therefore it is convenient to sample particles around the closest transmitter. The distance between a transmitter and a device can be calculated according to the signal power. The number of particles to be sampled is determined by initial settings.
3. Weights calculation
Figure 5 - RSSI
We suppose that accumulated signals are independent variables. The probability of a particle getting a signal with a certain power from the transmitter is calculated using the normal distribution. The power of the signal between transmitters and a device is calculated according to a logarithmic model of signal distribution based on distances between transmitters and a device. It uses the concept of a received signal strength indicator (RSSI). This model is described in an article about the distance path-loss model. After that, the weights of particles are normalized to compose a 1 in the sum.
4. Resampling
Figure 6 - Resampling of the particles
After multiple steps of the correction procedure weights of some particles that represent the wrong position become extremely low, close to zero. These particles do not have a significant result in the distribution of the total weight. However, computational resources are still used because these particles are also taken into consideration. Resampling solves this problem by erasing particles with the lowest weights and duplicating particles with the highest weights. This procedure is called multinomial resampling.
Estimation
Eventually, when all the particles are assigned a weight, it is possible to calculate the final coordinate and motion direction. It is determined as a weighted average of the particles’ states.
Particle Filter and Other Methods
The particle filter has some advantages over other methods of Bayesian filtering. It allows the initial state distribution to be non-gaussian, which is extremely useful in our case. For example, the Kalman filter requires the incoming distribution to be normal. Also, as was mentioned before, sampling of the particles is useful for generating particles from different distributions. It does not require assumptions about state distribution. However, the particle filter has side effects when it comes to high-dimensional systems.
Conclusion
The particle filter is a well-compound approach to provide a system with weight coefficients and determine the coordinate and motion direction of a user according to the weight distribution. The particle filter algorithm has significant advantages over other methods that allow Navigine to use it in our solutions. Check out Navigine applications for IOS and Android that use Particle Filter for indoor positioning.
Here are some links that can be helpful to learn more in detail about particle filtering:
If you want to know more about Particle Filter, please watch our lecture on YouTube.
Are you interested in particle filters for indoor positioning systems? Discuss more in a private free consultation:
