Particle Filtering

#Partilce Filtering. Suppose we have the following scenario

• There is something that we want to measure (say x).
• We can measure something that is related to what we want to measure (x).
• We are aware of the relationship between the measurements and something we want to measure (x).

In such scenarios, particle filtering can be the ideal to be used for knowing what we want to know by using the measurements that we have. While there are other filters such as Kalman Filters, and Extended Kalman Filters that can be used in outdoor environment (outdoor environments can be formalized as Linear and gaussian systems), particle filtering is used predominantly in indoor environments since they are non-linear and non-Gaussian. Particle filtering is widely used in robot localization. The position of a robot or any other entity can be estimated with higher accuracy using particle filtering. It relies on predicting the possible position of the user at any time t=i, based on its past position i.e. the information the algorithm has up to t=i-1. Once the measurements are obtained for t=i from different reference points, then the predicted position is updated based on the new set of measurements. This is a recursive process that continues as long as the algorithm is running. While Partile Filtering wikipedia page provides the basic information about particle filtering, the papers referenced at the end can provide a thorough description of particle filtering and the equations that are used to estimate the position of the object. The video Partile Filter Explained without Equations can serve as a very basic guide of particle filtering.

How the algorithm works

Different reference points that can be used for measurements are placed in the indoor environment. These devices can be BLE beacons, Wi-FI Acces Points (APs), zigbee modules or any transmitter that can help us estimate the distance between the entity and transmitter. The position of the devices is fixed. The robot or any thing whose position is to be estimated starts with estimating the most likely place where it can be in the room based on the measurements. The algorithm helps the robot estimate its position using probability theory. There are certain coordinates in the locality where the robot can be with higher probability (this probability relies highly on the transmitter signal strength). The most likely position spots are represented by particles or dots of bigger size and weight (showing the probability density functions and associated weights). Then as the robot moves, it predicts what its current position can be using particle filtering while simultaneously receiving the measurements from the fixed reference point to update its prediction (and reduce the error in the prediction). This process continues until the algorithm is run. All the particles that are mostly likely the position of the robot have higher weights and usually converge in an area to show the most likely of the possible positions of the robot.

Useful References

1. P. M. Djuric, J. H. Kotecha, J. Zhang, Y. Huang, T. Ghirmai, M. F. Bugallo, and J. Miguez, “Particle filtering,” Signal Processing Magazine, IEEE, vol. 20, no. 5, pp. 19–38, 2003.

2. V. Savic, A. Athalye, M. Bolic, and P. M. Djuric, “Particle filtering for indoor rfid tag tracking,” in Statistical Signal Processing Workshop (SSP), 2011 IEEE, pp. 193–196, IEEE, 2011.

3. K.-C. Lee, A. Oka, E. Pollakis, and L. Lampe, “A comparison between unscented kalman filtering and particle filtering for rssi-based tracking,” in Positioning Navigation and Communication (WPNC), 2010 7th Workshop on, pp. 157–163, IEEE, 2010.