How a small R&D team achieved great results in the Kaggle competition without using ML algorithms

A few months ago, Navigine R&D team started participating in the Indoor Location & Navigation competition from XYZ10 and Microsoft Research.

The purpose of the competition was as follows: organizers provided the participants with logs from hundreds of shopping centers, where visitors walked along specific routes. It was necessary to predict the floor and the x, y coordinate of the visitor on that floor based on radio signals and inertial sensors. In addition to the logs, the participants had metadata in the form of a map, which shows the location of cafes, shops, and other points of interest (POI).

What steps were taken by our team? Let’s take a closer look at this from their view.

1. The first step was converting the data to our format. This step was necessary because the format provided by Kaggle did not quite fit us, and this applied to both logs and floor plans.

2. Next, we found out that our submissions were tested by organizers only on a small subset of malls, so we were able to discard about ~70% of the data and only looked at those few for the rest of the competition.

3. Following, we looked at the floor plans and the trajectories that people walked. Logs were collected through crowdsourcing, where people walked with their smartphones from one key point on the map to another. Thus, we could linearly interpolate between and get a good enough estimate for intermediate timesteps for most of the points. However, sometimes it was clear that those interpolated trajectories passed through the shop, so we had to shift them back to the corridor to make them more plausible.

4. The log data consisted of two main components. Accelerometer, gyroscope, and magnetometer measurements as internal measurements. Wi-Fi, and less often beacons signals as external radio signals. Knowing the time of radio measurements, we combined them with known trajectories to estimate sources’ location.

5. After restoring the position of the beacons by the least-squares method, we launched our navigation algorithms. First, we used the original floor plans, yet there were some unfixable problems with them. We began to expand the zones next to the route lines by roughly 1.5 meters and use this area as a possible navigation path to solve it.

6. As our main solver, we used a particle filter. We tried two approaches: a regular one and a graph particle filter. Here is the key difference between these filters: in an ordinary particle filter, particles can be randomly located in the specified area, and in a graph filter, all particles are located on the branches of the graph. It is also worth mentioning that a graph particle filter did not use any information from inertial sensors. In theory, it should lead to a worse solution. However, using post-processing, they score almost equally in the 5.1–5.4 meter range.

7. The last stage was postprocessing, which consists of two actions: error minimization by pedestrian dead reckoning (PDR) and snapping to grid. The first operation combined global and local solutions and was very beneficial for a graph particle filter. The second operation allowed us to utilize some ground knowledge about data collection. We knew almost all the points that people had to visit, thus snapping to those points improved our metrics.

8. It is worth noting that for a while, we had significant problems with Kaggle’s data. For example, data lines could be concatenated, so we had to run a special program to correct them. Another issue was related to Wi-Fi points. Once the phone connects with one of them, it continues to write this particular data signal to the log until a specific time limit has passed. As a result, radio points could be marked visible in the record long after they should be, which greatly affected our algorithms. To work around this problem, we used the arrival time of the signal. This time allowed us to remove duplicates — if we saw a Wi-Fi point with the same time mark, we discarded it from the logs.

9. The organizers of the competition made several leaks that partially helped us. The general idea of all those leaks was about obtaining and utilizing the actual timestamps of test logs. With those timestamps, we were able to find interconnections between test and train data and consequently get starting and ending points for some of the paths.

Overall, more than a thousand teams participated in the competition. There were specialists in many areas, machine learning and Kalman filters among them. However, the leaders are mainly those who use machine learning. In the end, we managed to get in the top 100 with approximately 5-meter accuracy!