It’s simply getting from here to there. How hard can that be?
In fact, if it’s indoors, then things aren’t that far away, so that should be even easier, right?
Wrong. Indoor navigation is a bugaboo that’s got all kinds of folks scrambling to figure out how to get you to where you need to be.
As we’ve seen before, navigation outside uses a mix of technologies, but satellite systems figure prominently in the solution. Other technologies simply fill the gaps when the satellite signal is weak or blanks out for short periods of time. During such blackouts, IMUs and map-matching can do a reasonable job of keeping you going, and when the signal comes back again, we can zero out any accumulated errors and we’re back on track.
Not so inside a building, where GPS realistically gets taken out of the toolbox. And we saw how, at CES, Movea and others were showing their efforts at getting around using only IMUs and sensor fusion and the occasional check-in point. Here the check-in serves as the error reset, allowing the IMUs to “restart.”
A conversation with Sensor Platforms’ Kevin Shaw provided some insight on some of the issues and approaches from a motion-sensing standpoint. We can start with just the accelerometer to keep things simple for the moment.
Our problem is to figure out where we are in relation to where we want to be. In other words, position. You get to a position by traveling some speed from one point to another. And you get to a speed by accelerating from another speed. And the accelerometer measures those accelerations.
But accelerometers are noisy. Yes, they’re getting better, but if you monitor the output over time, even on a stationary sensor, you’ll see the acceleration measurements average the correct value (zero if stationary) with a more or less constant noise band around it. And if you want an acceleration value and the noise is tolerable, you might be okay with this.
To get speed, you need to integrate the acceleration over time. So the impact of that noise accumulates. The average is still correct, but the error increases linearly with time.
To get position, you need to integrate the speed over time. And the linearly-increasing noise accumulates again. So your position measurement will look right on average, but the error will increase as the square of time.
This means that dead reckoning has a sell-by date: your errors can accumulate in minutes, even seconds. Which is why it’s fine for outside gaps in GPS. But it’s a problem if it’s all you’ve got for navigation. You need some way to reset every once in a while (and we’re not talking enough time to get you across the building) to zero out the error and start over.
All of the above error discussion assumes you know your orientation exactly. That way you can figure out where gravity is and subtract that out. But once you start changing orientation, you need a gyroscope to tell you your new orientation so that you can figure out where gravity is to avoid it leaking into the measurements. So now you have gyroscope errors and drift to compound the issue.
One of the things that can possibly be relied on to help with indoor navigation is the fact that the travelers are probably on foot. So now we’re dealing with a subset of the problem, referred to unmysteriously as Pedestrian Dead Reckoning. (Not to be confused with Dead Pedestrian Reckoning, which is what’s in store if you don’t honor crosswalks while driving.)
And this starts out sounding like, “Problem solved!” – and then it gets complicated too. Here’s the deal: when you walk, you take a stationary foot, lift it up, move it forward, and place it down again. You repeat that with the other foot, but – and this is the key – while the other foot is moving, that first foot is stationary again.
This means that you get a known velocity with every step: that zero-speed point. So the accelerometer has to be accurate only for the length of one stride – and then it can reset to zero, clear the errors, and start over. Simple, right?
Well, yes, if your accelerometers are in your shoes. But if you are using your smartphone to get around, putting it in your shoe probably isn’t an option. (If nothing else, the sweat will make the little red moisture sensor turn red and you’ll go out of warranty. Oh wait, pretty much anything turns that red – it’s the get-out-of-warranty-free feature… so… never mind.)
So now you’ve got an accelerometer in your pocket or your hand or somewhere not on your feet. So you no longer have that guaranteed-stationary reset point. The acceleration of your body will likely have a cadence to it that relates to your footfalls – sort of like a low-frequency drone under all the other signals if the pace is consistent. But now you have to start making judgments about how to manipulate that acceleration signal to figure out what the feet are probably doing in order to figure out where you are. And orientation, as you blithely flip your phone around, compounds the problem.
Folks are working hard on this problem, but no one is saying that we’ll be able to navigate accurately indoors based on our smartphones alone. Especially since “navigation-grade” sensors are not what go into your phone. So again, we bring a number of different solutions to bear.
One company, Trusted Positioning, actually claims that they can provide navigation-grade performance from a smartphone. But they’re not relying solely on the cellphone. Their T-PN algorithm takes a number of inputs – including GPS and WiFi – and they make decisions on how best to navigate depending on what they think is happening and what signals are available. They might decide you’re driving or walking; they have “misalignment” algorithms to figure out how your phone is oriented compared to how you are oriented.
Each “update” – that is, some input that gives them information about where you are or what’s going on – gets pulled into the algorithm as a constraint. In fact, they loosely speak of each of the many “clues” that are out there as being constraints. The trick is in figuring out what’s happening when and how to apply those constraints to their general model. There may even be times when it doesn’t have a mode to latch onto, in which case you’re “flying blind,” based only on the phone sensors.
The key here is on narrowing the error band. They have a model that relies on 5-10 minutes of accurate GPS position, velocity, and timing data, from which they determine an optimal error model that incorporates calibration of the sensor (which might change each time the phone is turned on) and the stochastic behavior (which can vary by sensor and by phone and over time). So during those few minutes of calibration time, it churns out a more accurate model for a single “mission” that should allow longer unassisted navigation runs. Next time you do this, it might come up with a different model.
The Trusted Positioning solution can use WiFi to triangulate, but WiFi wasn’t really designed to be good at that. And we all know that WiFi is affected by walls and shelves and probably even large crowds of people that are constantly shifting and moving about.
So yet another idea that has recently been touted by two European research institutes, imec and Leti, uses so-called impulse radio ultra-wideband (IR-UWB). This leverages technology being standardized under the personal area network (PAN) and body area network (BAN) efforts of IEEE 802.15.4 and 802.15.6.
The idea is that pulses of energy transmitted over a broad band are used over time to code information. They can therefore share or overlap the bands currently used by narrowband carrier-based standards because, at any specific frequency, the energy effectively fades to the background. These signals can be used as beacons that can go through walls and provide more accuracy over longer distances than WiFi.
Both groups made announcements within a short time of each other. (Coincidence?) Imec discussed their work with BlinkSight to create a system that could track movements accurate to 10 cm. Leti, meanwhile, announced work with BeSpoon culminating in a world-record line-of-sight distance measurement of 3641.60 meters across Lac du Bourget in the French Alps. Both of these announcements featured single-chip implementations of the IR-UWB standard.
So IR-UWB might be yet another of the many clues that can be used for navigation. Of course, it then becomes yet another wireless technology buried inside a phone (there’s always room for one more, right?).
My sense is that we’ll be hearing a lot more about indoor navigation solutions largely as a result of increasingly sophisticated fusion models that can provide more intelligent guesses as to what’s going on. (Hopefully they can avoid hitting the Annoying Valley along the way…) There are probably lots of positional clues that haven’t been tapped yet. Imagine the camera recognizing landmarks, for instance, and estimating how far away from them you are and in what direction. Assuming it’s not just looking at the inside of your pocket or your feet…
We’ll keep an eye out for new developments. After all, how hard can it be?
More info:
We look at various approaches to indoor navigation above. What other ideas do you see being brought into this battle?
Please take a look at DecaWave http://www.decawave.com which have just gone into mass production with the World’s first IEEE802.15.4a chip, an IR UWB chip giving 7cm precision raging at 3 sigma reliability, with unprecedented LOS (line of sight) and NLOS (non line of sight, i;e., through obstructions). Such performance at world’s best price and power points.