Using Sensor Fusion and ML to Navigate Underground When GPS Fails

Speaker 1 [00:42]

all right welcome everyone thank you very much for attending this session and we hope you've been having a good time at the conference so far our speaker this afternoon is etn chambly and he's going to introduce himself in a bit but just a few housekeeping details please put your phones on silent if you need to ask any questions use the talks tool and would read them out at the end of the session so thank you and i hope you enjoy this session please give our speaker a really warm You're welcome.

Speaker 2 [01:15]

Thanks for the introduction. So, I'm Etienne. I work as a data scientist at Transit, and today I'll explain how a smartphone can estimate its location underground when the GPS stops working. So, first of all, what is Transit? It's an app for getting real-time information about public transit systems. For example, you can get real-time schedules, you can get service disruptions, and you can plan a trip. Out of curiosity, raise your hand if you've used Transit before. A few people. We're pretty new in Germany, but we're bigger in other places. We've been developing Transit since 2012. We have now over 100 employees. We have 8 million monthly users, and we're live in 1,000 cities, 29 countries, and 15 cities in Germany, including Darmstadt. that, so I encourage you to try it out. The art of transit is the Go mode. Go is a step-by-step guide through your trip, and it's relying on the user location to give you the most relevant information at any given time. So when you're walking to your stop, you want to know which street to turn. That's the info that's shown. When you get to your stop, you You want to know how long you have to wait, so it will give you the schedule for the next buses or trains. And then once you're on board your vehicle, you want to know when to get out, so it will tell you how many stations or stops are remaining until you need to get out, and it will give you a push notification in case you fell asleep. Now this used to all fall apart when you were in a subway, because it relies so much on user location. if you don't see the skies, you can see the satellites, and GPS doesn't work in subways. But now it does. How is it possible? That's the subject of today's talk. So to get an intuition on how it might work, let's do a thought experiment. Let's say you're kidnapped. You're in a subway, you're blindfolded, so you can't see the signs and you can't hear the announcements. But luckily, you're a subway nerd. You know the stations by heart. You know where you got on, and you know which direction the train is headed. So the question is, would you be able to tell where you are? And I think so. You could probably feel when the train starts to move, and then when it stops. And at that point, you know you've traveled one station, and you just repeat that process, and you count the number of stations, and you could always figure out at which station you are or between which two stations you are. This is the intuition that gave us hope that a problem like this could be solved. And in fact, it's pretty close to the way that we actually solved the problem. So which clues do we have in order to infer the location? The first one is locations from the device. So, the smartphone's OS gives app locations that are generally based on GPS, but when that's not available, it falls back to other strategies like Wi-Fi scanning, Bluetooth scanning, or based on network infrastructure. And that relies on mapping cell tower addresses to locations, but this mapping changes over time, and the accuracy is never really good. oftentimes we'll have an accuracy radius of over a kilometer which is not really usable for what we want to do here you can see visually what it looks like it's a trip in Paris where the train starts above ground and we get dense and frequent GPS locations but eventually it goes underground and then the locations get super sparse far away the updates are less frequent so usable but not enough on its own. The second clue is the train schedule. Because we're a public transit app, we're already used to ingesting these and they are saved on device in case the network goes down. And those can't really be relied on in absolute terms, but the time delta between the stations is respected. So if it's supposed to take three minutes between stations, that's usually reliable. and the last clue is motion sensors so you might know that almost all smartphones now have at least an accelerometer and a gyrometer for angular acceleration those are used among other things to infer if the phone is in a landscape or portrait orientation but there is much more than that that we can do with the accelerometer data just looking at it like that it doesn't look like much but feed it through an ML network and you can get useful labels out of it. So like any machine learning project we need a lot of data and this data set doesn't exist so we had to collect it. The three inputs that I talked about need to be logged as well as some ground truth about where the user actually is. So in order to do this we developed a special screen on the development version of the app where you can enter as you do your trip, whether you're walking, standing still, on a moving train, on an idle train, an escalator, everything gets logged. And we want the data set to be diverse because we want the feature to work everywhere. So we made sure that the data collection was done by different people different cities with different types of devices and an important thing to note about this data is that annotation is impossible after the fact so a human labeler couldn't look at the sensor data and say oh this is an elevator which is in contrast with a lot of typical machine learning tasks and it makes a lot of the typical data cleaning techniques not apply in this case so the The data quality is even more important because we can't correct the labels. And if you ever find yourself in a situation like this, we have a few takeaways that I hope you can be inspired from. First of all, we relied exclusively on trained employees to collect the data. We invested a lot of effort in the protocol because some situations can be a bit ambiguous and we want to make sure that different labelers give the same label for the same situation then even though we can't fully check the labels we can add some automated coherence checks for example it's impossible for someone to go straight from an elevator to a moving train they probably need to walk a little bit in between maybe stand still while they wait so with automated checks like that we catch at least some labeling errors and finally when in doubt we discard the data sometimes the labeler will tell us i fell asleep at this point i wasn't paying attention and i was late on the label and in that case we prefer to get rid of the trip than to have bad data in the data set which we couldn't fix later with these methods we managed to collect 300 trips which is respectable but really not enough to train a deep learning network so the other thing we did is leverage our millions of go users and those don't put any labels on their trip so we needed to rely on some heuristics to kind of have a approximate ground truth the way that we did that is mostly based on gps speed so this is a an oversimplification but But basically, if the speed is really low, we assume that they're stationary, they're waiting for their vehicle. If they're walking within a certain range of speeds, well, they're probably walking, and if they're going faster than a certain threshold, they're probably automotive. And so we have these three classes that are not actually what we want to predict, but And it's a pretext task to get the model to learn useful representations of the sensor data. To get an idea of what the data looked like, we passed it through a fast Fourier transform, and you can see it on the frequency domain. Here at the beginning and the end of the trip, there's a clear peak at about two hertz, and you can probably guess what that is. It's somebody walking, making about two steps per second. In the end, using a fast Fourier transform as part of the pre-processing is something we tried but didn't yield good results. But at least for a human, visually it kind of helps to see if somebody might be walking. Now as in any machine learning task, one of the most important decisions we needed to take is how do we transform our problem into some kind of classification or regression and the way that we ended up doing it is by saying we have a target variable where a value of one represents a moving train and a value of zero can be anything else can be walking standing still an escalator and if we can get a model to predict that then all that's left to do is count those kinds of square waves and we know how many stations have been traveled and we can infer the user location and at the bottom you have an actual prediction from a train model and the the waves are very visible and you can note that at the end there is a smaller wave that's actually an escalator and it turns out the vibrations from escalators are somewhat similar to moving trains but we're able to tell them apart and not count them as a station So, the training happens in two stages because, as I explained, we have two datasets. The first big dataset from user is used to train CNN, convolutional neural network, which is typical for image classification, but it turns out it also works very well for our sensor data. This allows us to train a pretty deep network because we have millions of trips and we predict the mode as I explained which is not exactly the label that we want but it allows us to train this big network that can then be used in transfer learning where we freeze the weights and we keep training a smaller model that's based on intermediate activations from some layer in the middle of the pre-trained model the the cut point is important and we treat it as a hyper parameter so we try different values see what works best and this has two advantages first of all it gives us these two outputs from a model that's not much bigger than the base model which is good because as I'll explain later we eventually put this on device so we want the model to be small and the other advantage is we get way better performance than if we tried to get the moving metro prediction from the employee data alone which is a very small data set so this gives us a binary prediction moving metro or not but what we actually want is a predicted location so how do we go from one to the other the answer is a module we call the mixer and it brings together the motion type moving train or not the recent device locations as well as the train schedule and generally it just counts the square waves as i explained but there's also some fancy logic that can happen for example in new york city sometimes the train frequency is so high that a train will leave a station while there's still another train waiting at the next platform so they can't go all the way they stop in between platforms and that's a tough edge case for us to solve because when it stops between platforms it looks like it stopped at a station and so in order to figure out what happened we look at the train schedule if we expect the train to move for five minutes between stations and it moved for one minute we're sometimes able to recover from these situations we can also recover from mistakes when the we get a recent device location that has high accuracy and it's different from our previous prediction sometimes we're able to correct and one thing that's cool to notice is that those three inputs all work offline the device locations like we can still get them from wi-fi scanning or bluetooth beacons the subway schedule is already stored for offline use and the motion detection relies on the model which is only two megabytes so we were able to package it. It's relatively small compared to the rest of the app and all that allows us to keep running the model even when the network fails which happens pretty often in subways depending on the city. Does it work? The answer is it generally works but not always as any project like that there's a certain error rate. It works about 90% of the time where the prediction is less than one station away from the true location and you can see it on this graph so the x-axis is the true station index and the y-axis is the predictions so in a perfect case we would follow the black diagonal line whenever the like each line here the colored lines are are separate trips so when they're below the diagonal it means the prediction was late and when they're above it means it was early so you can see just from this that we are late more than we are early and also some sometimes the the prediction can recover when it comes back to the diagonal so it makes mistakes and it doesn't stop us from deploying this for millions of people to use the important thing is to somehow surface the uncertainty we don't want people to get off the the subway when we tell them to at the wrong moment so what the user experience looks like before you would have a location that jumps around infrequently maybe you'd get an update every few minutes it's immediately obvious that the location was unreliable now the location moves in real time which can make it look more reliable than it really is so it's important for us to send a message that it's an approximation so we have this big yellow banner at the top which I personally don't like but it's important to say don't necessarily get off when we tell you to we also change the notification text it used to say get off in two stations or get off now now it just says to pay attention to your surrounding. Your stop is coming up. What's next? We want to have the confidence interval be displayed to the user in a way that's less aggressive than a warning banner. We already have an estimate of it. It's an asymmetric confidence interval in the sense that we generally think that we maybe late more than early and we want to show it in a way that's intuitive so we're thinking about this kind of visualization where you you have a range displayed on the map and you know exactly between which stations you may you may be the other thing we want to add is broadcasting vehicle locations which is something we already do for buses and it's one of the most loved features of transit where if you're on board a vehicle that doesn't have a GPS transponder it's not shown on the map for other users but if you activate go and you ride that bus you'll be broadcasting your location and then other users can see it on the map and they can literally thank you in the app it's something that would be especially valuable for subways because in a lot of of cities, there is just no real-time locations in subways. It would be something new, and it's difficult because we know that we have a system that's not as reliable as GPS, so one approach would be to look at when different users' predictions agree and somehow merge those and surface them for other users. We are also thinking about adding other features as input to the moving metro model like the OS because we know that different phones will record sensor data in slightly different ways, or the city because the rolling stock has a big impact on the vibration patterns that we're trying to detect. In terms of infrastructure, we've been using a GCP product called Vertex AI. system would work but the important thing is that you have some kind of dependency graph encoded to tell you what tasks depend on which tasks output and the reason it's important is some of these tasks take really long to run several days several weeks and when you rerun them you might not want to run the whole pipeline you only run you only want to run the one that changed but then all the downstream tasks also need to be updated so vertex ai or airflow or even just a make file if it's a smaller project would work and it allows us to iterate much more quickly and not have to remember okay i updated task x which ones need to be rerun also it caches the step outputs so they can be reused if the task doesn't need to rerun and it allows us to run different pipelines in parallel which is super useful to test out ideas we can just run them both see how the performance compares at the end and the cost of a full run is below 50 euros which is kind of refreshing compared to bigger model training pipelines Thanks a lot. I hope you try Transit and when you see the vehicle location moves, you'll know a bit what's under the hood.

Speaker 1 [20:58]

Thank you very much. I, for one, really enjoyed this session. I think I can say that many of us here also enjoyed this session. We've got a couple of questions here. The first one says, would it be possible to incorporate audio data such as station announcements?

Speaker 2 [21:14]

It's a great question. It's something we've thought about. It would be so easy to just turn on the microphone, listen to the announcement, and yeah. But the reason we don't do it is it takes permissions which we don't currently ask for. For a public transit app to ask microphone permission can seem weird. But yeah, it's definitely something we've thought about, and I think it would work great.

Speaker 1 [21:42]

Thank you, and next one says, have you considered supplying the motion data to the rail companies to give them hints for their maintenance?

Speaker 2 [21:51]

Interesting. We haven't considered it. It's a good question. Maybe it would help preventive maintenance. What might make this difficult is we've realized that the sensor data depends a lot on how the people hold their phones. If they're sitting down with it on their lap or if it's in a bag or in their backpack, makes a big difference to the vibration patterns. it be used to tell if if some part is vibrating more I'm really not sure but it's a good question

Speaker 1 [22:27]

Are you combining the data from different users riding in the same train in order to increase readability?

Speaker 2 [22:35]

Good question. We currently don't. We've done it from manually collected data. So one subtlety when collecting the data is that the annotation itself is done in real time and that has an impact on the sensor data. because if you're entering annotations, you have your phone out, it can't be in your pocket, and also you might behave a bit differently. So what we did is have two people ride the subway together, one of which is annotating and the other one is just minding their own business, and we applied the annotations to both of them. So that's a bit the same idea, but it's done by employees and not anonymous users.

Speaker 1 [23:21]

Great. Do you have any idea why the model is late more often than early and can you try to correct for that?

Speaker 2 [23:28]

Yes. The reason it's late is usually because it fails to detect departure from a station or arrival at a station. And then once we make a mistake, the mistake can carry over for a while until we get a device location to fix it. For it to be early, the most typical reason is because we detected a station when there wasn't one, and it's more rare. But the good thing to note is that this bias is actually on purpose we prefer to be late than early um but that's done with the the cost function we make a late prediction cheaper than an early one

Speaker 1 [24:12]

and how do you deal with a person jumping on the underground in the wrong direction when they have to change?

Speaker 2 [24:18]

yeah that's that's unhandled it's a we make a lot of assumptions and one of them is the user will do the trip that they said they would do if they go in the wrong direction we're unable to detect it if we eventually get a location we will update the prediction but that's a hard problem we can't differentiate different directions yet

Speaker 1 [24:45]

And what do you do with the stops between the stations?

Speaker 2 [24:49]

Stops between stations, I explained it a bit, but it really relies on the schedule to try and figure out if it might be a stop between stations. So if we stopped much faster than we were supposed to, according to the schedule, we detect it as a stop between stations. and well the the location just displays it as such the vehicle location will stop moving between station and then resume once the train starts moving again

Speaker 1 [25:21]

Have you noticed differences in the motion data after tracks were replaced?

Speaker 2 [25:26]

After checks were replaced, tracks were replaced. Good question. No, I haven't. But there's definitely a lot of difference between systems. And we're biased by the cities that we live in because it's cheaper for us to collect data there. So in Montreal, it's rubber tires. So it works well in other systems that have rubber tires. but yeah the biggest difference really comes from the rolling stock rather than the the rails from my experience

Speaker 1 [26:00]

Okay, and coming from a control theory background, this seems like a good use case for Kalman filters. Did you evaluate them? And if yes, what is your experience?

Speaker 2 [26:11]

Yes. So I'm not super familiar with Kalman filters, but I think one approach that we tried at the beginning that was similar is to try to basically take the acceleration and integrate it twice to get the distance covered. And the issue with that is that we're unable to tell the orientation of the user inside the train. So to us, a turn, like the acceleration from a turn looks the same as the acceleration from braking or accelerating. And we weren't able to get reliable results from that, even though it looks like a simple and intuitive solution.

Speaker 1 [26:57]

Okay, this one says, I suggest the integral area under the curve over the acceleration graph could be a more precise measure of the distance traveled compared to just taking the time length between of the square.

Speaker 2 [27:11]

Yes, so I think that that's the the same suggestion and I do think it sounds very intuitive maybe there's a way to make it work but from what we tried it had a lot of issues and also like a bad property of this is that the error is squared and integrated over time so it can really diverge if there's any miscalibration of the accelerometer.

Speaker 1 [27:36]

Okay, and which library are you using to run the model inference and device?

Speaker 2 [27:41]

On device, so we have, it's separate for iOS and Android. We compile the model differently for both so that they can use the device hardware. On iOS, it's Core ML. On Android, it's something else. I don't remember the name. But we start from a TensorFlow Lite model that we then specialize for each platform.

Speaker 1 [28:06]

Great. I have a final question that says, how do you deal with people walking on the train?

Speaker 2 [28:10]

on the train yeah that's a tough one but surprisingly enough we're able to differentiate from someone walking in the train from someone walking on a on a stable ground and the reason it works is because we have a lot of that in the training data we have a lot of people walking on moving trains but it's labeled as a moving train and the model is able to predict moving train even when somebody is walking. We haven't many people that are dancing, though. That might not work.

Speaker 1 [28:42]

Great. Thank you so much for this really insightful session. Could we give him a big round of applause, everyone? Thank you. Thank you very much. And enjoy the rest of the conference.