feature article
Subscribe Now

Navigating Indoors

Not As Easy As You Think

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:

Imec/BlinkSight announcement

Leti/BeSpoon announcement


Sensor Platforms

Trusted Positioning

2 thoughts on “Navigating Indoors”

  1. 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.

Leave a Reply

featured blogs
May 25, 2023
Register only once to get access to all Cadence on-demand webinars. Unstructured meshing can be automated for much of the mesh generation process, saving significant engineering time and cost. However, controlling numerical errors resulting from the discrete mesh requires ada...
May 24, 2023
Accelerate vision transformer models and convolutional neural networks for AI vision systems with the ARC NPX6 NPU IP, the best processor for edge AI devices. The post Designing Smarter Edge AI Devices with the Award-Winning Synopsys ARC NPX6 NPU IP appeared first on New Hor...
May 8, 2023
If you are planning on traveling to Turkey in the not-so-distant future, then I have a favor to ask....

featured video

Automate PCB P&R Tasks for Designs in Minutes

Sponsored by Cadence Design Systems

Discover how to get a dramatic reduction in design turnaround time by automating your placement, power plane generation, and critical net routing with Cadence® Allegro® X AI technology. Built on and accessed through the Allegro X Design Platform, Allegro X AI reduces P&R tasks from days to minutes with equivalent or higher quality compared with manually designed boards.

Click here for more information

featured contest

Join the AI Generated Open-Source Silicon Design Challenge

Sponsored by Efabless

Get your AI-generated design manufactured ($9,750 value)! Enter the E-fabless open-source silicon design challenge. Use generative AI to create Verilog from natural language prompts, then implement your design using the Efabless chipIgnite platform - including an SoC template (Caravel) providing rapid chip-level integration, and an open-source RTL-to-GDS digital design flow (OpenLane). The winner gets their design manufactured by eFabless. Hurry, though - deadline is June 2!

Click here to enter!

featured chalk talk

How IO-Link® is Enabling Smart Factory Digitization -- Analog Devices and Mouser Electronics
Safety, flexibility and sustainability are cornerstone to today’s smart factories. In this episode of Chalk Talk, Amelia Dalton and Shasta Thomas from Analog Devices discuss how Analog Device’s IO-Link is helping usher in a new era of smart factory automation. They take a closer look at the benefits that IO-Link can bring to an industrial factory environment, the biggest issues facing IO-Link sensor and master designs and how Analog Devices ??can help you with your next industrial design.
Feb 2, 2023