Accurate Indoor Tracking

This week Ramsey Faragher joined us from the Digital Technology Group at Cambridge University. He's trying to make it possible to locate where people are in a room or building, with high precision.

Chris - So, how do we locate people in buildings at the moment or how are we trying to do that?

Ramsey - So, there's a couple of standard schemes. One of them would be to deploy fixed infrastructure specifically in the environment which would cost a lot of money; putting beacons in the environment and giving people special receivers that they can go around with and be positioned by. A much cheaper scheme is to use things that are already pervasive in the environment and that's what I'm looking at. So, for example, as I move through a given building, I can tell the difference between different rooms because I can see the colours of the wallpaper and pictures, and the size and shape of the rooms. A smartphone can do a very similar thing in radio eyes and magnetic eyes, and a smartphone can learn what different rooms look like by the different signal strengths in the radio and different magnetic patterns. What I work on is a way of making a device learn about the building and learn about what all the rooms look like, so that when you come back, you can very accurately locate where you've been in that building.

Chris - So, you as the holder of the smartphone would be able to localise where you are and where you have been. What about turning it around and the building knowing where you are? I could see that would be useful in situations like for instance fires or even patient care in a hospital.

Ramsey - Yeah and that's certainly very possible too. So, a way of doing that is that you choose to transmit the data that you're working out to someone so they can know where you are. But certainly, there are things that you can do to allow an infrastructure in an environment to work out where people are. So, a typical example is you put receivers through the environment and when someone is texting or on the internet, on their phone or they're making a phone call, the receivers through the environment can pick up these signals and work out the time difference of arrival of all the different signals so they can effectively work out who you're closest to as you move through the environment. And very similar to the techniques we've just been discussing about GPS, given some receivers spread through the environment, you can work out where the transmitter is, the person who's texting or calling as they move through the environment. You can work out their position as they move through the environment by receiving the data from them.

Chris - It sounds actually quite a simple problem to surmount, but the fact that we're not doing this means there must be some wrinkles. So, what are the wrinkles?

Ramsey - So, it's certainly a very simple problem when the world is a nice perfect sphere and you're in a vaccum and all that kind of stuff. The problem is in an indoor environment, it's extremely complicated. The metal in environments, the effect of signals going through walls, all these kind of stuff, and the technique that I'm working on where the system learns what the environment looks like as it moves around actually flips the whole problem on its head. The more complicated the signal environment, the nastier it is, the more unpredictable the nature of the signals, the better the positioning and instead of trying to model and predict, and work out what the signal should look like in a given place, you just record what it looked like when you were there, record all of these patterns, all of these signals, and you piece together what that environment must look like and what this really complicated pattern of radio and magnetic fingerprints looks like.

Chris - That though requires the device to slowly build up a picture of its world it's living in. what about the first time you go into a novel environment? It's not going to know anything then, is it? So, how will it acquire that information or give meaningful information to start with?

Ramsey - This is the kind of key of the whole system. You have some way of estimating your motion around the environment. So, the typical one we use is a modern smartphone is full of sensors - accelerometers, gyroscopes, a magnetic compass, a barometer, they're designed for gaming and making your screen rotate when you turn the phone round and in actual fact, you can do a really good job of tracking a user through an environment as they move. So, I walk along with my phone held out in front of me and the shaking that goes on in the phone, my software can recognise that and infer that I'm walking. It can use the gyro-smoothed compass to infer a heading that I'm walking along. Using that technique, you can get a good estimate as a person as they move around the building.

The problem is, the errors accumulate with that system. So, if I walk 100 metres, I might have a 2-metre error. If I walk a kilometre, I might have a 25-metre error. The more I move around in my building, the worse it gets, but it's good enough to start piecing all these fingerprints together. What the system basically does is, it recognises when it's come back to a place it's been before. It sees a sequence of fingerprints that match the past and it can observe a correction that it needs to drive through the system and it corrects its current position estimates, and the journey as to how you got there. It effectively keeps tidying itself up and the longer you operate in a building or if multiple people move through a building and they can all share data, then you can very quickly build-up these maps. The clever bit then comes when you've got a good enough map to turn off all of these sensors and just use the radio and the magnetic fingerprints which is a much cheaper battery life-wise way of navigating around an environment.

Chris - So, that tells me where I am in a building. How could we actually use knowledge of that data?

Ramsey - Indoor location based services currently estimated to be worth billions of dollars, just from the consumer point of view of things like pushing location specific adverts to people. There's an interest in the ability to do things like target a text message or a push notification to somebody who's in a rival store to your store. They might be looking at classic CDs in some shop and you can push them. It's tagged to that little advert that says, "I see you're currently looking at the classics section in that store. If you come to my store, here's a 5-pound gift voucher. It's valid for an hour and here is the route from where you're stood right now to where my shop is" and that's worth a lot of money.

Beyond adverts and the consumer stuff, the emergency services would love this kind of capability so that when I make an emergency call, they know exactly where I am inside a building to the floor and the room, never mind, just the building I'm in. But also tracking the emergency services themselves - the safety and security of firemen moving through a building, knowing that outside in the fire truck someone is watching them move through that environment and knows to the room where they are. It's a huge safety line and of course, from the military sector too, looking after soldiers moving environments as well.

Chris - It sounds pretty intrusive though, but I can see why this will be valuable from, if we were sort of designing an office or designing a public place and we wanted to see how the average person moved through it. You could achieve much better formatting in order to safeguard people's route through it. If it's a minefield, taking your military analogy of if it's just an office, finding your way from the kitchen to the photocopier to cut down wasted time or maximise contact with people so you're more likely to have interactions that are meaningful in the workplace, that kind of thing.

Ramsey - Yeah. I mean, it's certainly only intrusive of course if you've not chosen to take part in this, but the whole point is, I'm taking GPS that we love and depend upon this life-saving technology and moving it into the indoor environment so we can still benefit from all of those capabilities. I'm sure you've been in a supermarket at some point, trudging up and down the aisles, wondering where the hell the beans are or whatever. The capability to fire up your phone and do satnav at the shelving level in a big supermarket is something that everyone would opt into.

Chris - Undoubtedly, where can I buy shares? I mean, is this actually good to go?  Have you got this system written or are you at the stage where you've got the bare bones of this and you're beginning to see it implemented or do trials?  Where's it at?

Ramsey - This runs live right now on my phone. I'm working on smartphone applications to do this kind of stuff. One of the fantastic things about smartphones is the sheer pace at which they're improving and the kind of approaches I use and the kind of levels of software machine learning that goes on. Ten years ago, you would've needed a desktop computer that was quite an expensive one. Nowadays, you can deploy it all on a smartphone and do it all live on a smartphone. It's only improving - the number of calls on the phones, number of sensors in the phones. So, it's a great time to work on this kind of stuff and it's real time and ready to go right now.