Accurate Navigation Without GPS | Hacker News Reader

Accurate Navigation Without GPS

spectrum.ieee.org

125 pointsmhb61 comments

What's novel here is that it is a compact, pretty accurate solid-state inertial navigation unit.

https://en.wikipedia.org/wiki/Inertial_navigation_system

[edit] Here's a paper from 2017 to give some context to the problem of inertial navigation using the solid-state gyros and accelerometers you find in smartphones:

https://arxiv.org/pdf/1703.00154.pdf

> Abstract— Building a complete inertial navigation system using the limited quality data provided by current smartphones has been regarded challenging, if not impossible. We present a probabilistic approach for orientation and use-case free inertial odometry, which is based on double-integrating rotated accelerations. Our approach uses a probabilistic approach in fusing the noisy sensor data and learning the model parameters online. It is able to track the phone position, velocity, and pose in real-time and in a computationally lightweight fashion. The information fusion is completed with altitude correction from barometric pressure readings (if available), zero-velocity updates (if the phone remains stationary), and pseudo-updates limiting the momentary speed. We demonstrate our approach using a standard iPad and iPhone in several indoor deadreckoning applications and in a measurement tool setup.

Also: Apple is reportedly working on a full inertial navigation solution, probably for indoor use.

What is novel about that? Phones have had them for years

The ones in phones generally use GPS corrections when tracking movement.

Yes, but this paper is all about incorporating prior knowledge of human locomotion in a corrective step. There is no innovation in the field of pure inertial navigation; this would not help e.g. a quadrotor.

No, it’s that a cheap compact unit can be used accurately by using an understanding of the foot-planting gait of a human to remove low frequency drift in that cheap unit.

The whole concept is that, using a foot, which is only moving quickly or still, you can filter out the the low frequency component of all of the signals. These sensors are relatively accurate under movement and large signals, just not so much when stil, since their signal strengths become relatively low to the offsets and noise in the system.

So it measures the difference from zero in the accelerometer signals when the foot is planted and then accounts for that when the foot is moving?

Yes, but that technique isn't new either. Here's a 2014 paper that cites a 2009 paper about it (I didn't follow the trail):

https://www.omicsonline.org/open-access/understanding-the-pe...

But there is still going to be cumulative error and drift, right? Has this system reduced the cumulative error so that in some pedestrian use cases it is accurate enough?

Both. Long term drift will be extra challenging to correct as the cumulative error is staircase. (Beta distribution)

What this is is actually a step counter, combined with step length and heading estimate from an accelerometer w/ gyroscope plus compass. When the counter makes a mistake, the effects will be catastrophic.

> What's novel here is that it is a compact, pretty accurate solid-state inertial navigation unit.

Per the article, there is nothing special about the IMU they're using. What's novel here is the use of a foot-mounted pressure sensor and inverse kinematics to correct for accelerometer noise.

Agreed, but to clarify my comment, an IMU is not an inertial navigation system. I'm saying they constructed a pretty accurate inertial navigation system.

The paper I cited helps to point out the difference between taking inertial measurements and putting together a reasonable navigation system.

Strange that they don't use the age-old term for this sort of position-tracking: dead reckoning.

https://en.wikipedia.org/wiki/Dead_reckoning

That's because it isn't simple dead reckoning. Dead reckoning is just a part of inertial navigation.

It's the other way around: Inertial navigation is just a very accurate implementation of dead reckoning.

True but drift is inherent in dead reckoning due to cumulative errors and evidently the trick this guy used eliminates the drifting or limits it (the prototype was accurate to 5 meters).

Well, Wikipedia defines dead reckoning as:

> the process of calculating one's current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time and course.

It still seems applicable, even if the hardware has advanced sufficiently that errors are minimized.

Dead reckoning is exactly as described in that pull quote, but the problem is that when you integrate, e.g., accelerometer readings to get velocity, you also integrate its bias, which varies over time, and in the case of MEMS sensors will cause very significant errors.

The solution described in this article significantly improves on that by using the pressure data on foot strike as an observation to estimate the IMU's biases and correct the IMU-only position and attitude.

EDITED TO ADD: In many inertial navigation systems - presumably including this one - dead reckoning will still be used as a fallback in the case where corrections fail (i.e., no GPS or insufficient pressure data)

I think the position error will still be unbounded over time with this approach. What it does give you is sharply bounded velocity error, which in turn makes position error grow much more slowly.

It’s basically dead reckoning as you’d see in a car (where you always know your speed pretty accurately) versus in a plane (where speed is an output of the dead reckoning process as well as an input).

The cumulative errors that this device reduces are inherent to the measurement, drift in dead reckoning is just the sum of the errors in measurement and the assumptions thereof. This device simply provides a more accurate dead reckoning with cheap IMU sensors.

Dead reckoning is like pure IMU integration. In this work they detect the instant of zero velocity and do something like a Kalman update with a velocity measurement

No. Dead reckoning is using relative measurements. Your algorithm is irrelevant.

Yes, but those "relative measurements" are IMU measurements, which are accelerations and angular rates. The only way to get position and attitude from that is to integrate. All that is to say, the parent comment was dead (sorry) on.

You’re being needlessly narrow minded. Any improvement on that integration that doesn’t use an absolute source of position is still dead reckoning. Do you think ancient sailors used IMUs?

He's not totally wrong here. The "IMU" you're using consists of a fix, clock, compass, and airspeed indicator (in my case). You're doing the same basic stuff that inertial guidance would do but slower and with less accuracy.

And going back to the great-great-great grandparent comment, I've heard from instructors and other pilots that the 'dead' bit of the word came originally from a shortening of 'deduced'. Something like 'deduced' -> 'ded' -> 'dead' or so. I'm not totally sure of the accuracy of that etymology but it sounds plausible to me.

Wikipedia disagrees:

The term "dead reckoning" was not originally used to abbreviate "deduced reckoning," nor is it a misspelling of the term "ded reckoning."

https://en.wikipedia.org/wiki/Dead_reckoning

I agree that without absolute measurement, it’s still just dead reckoning. However, the article is dedicated to describing a novel source of absolute measurement.

Do you... know what these words mean? Absolute positioning has to be calculated from an absolute frame, like GPS. This is relative positioning, corrected by detecting periods when there should be no motion.

Am I an old man now? Where is my cane? Get off my lawn!

Maybe, but I (selfishly) believe old dogs can learn new tricks. Leaving off the first sentence of your comment would convey the same meaning while keeping any well-earned crotchetiness hidden from view.

Actually the term is apparently Zero Velocity Update (ZUPT somehow).

https://www.omicsonline.org/open-access/understanding-the-pe...

They use dead reckoning.

Dead reckoning requires speed information. They have invented an application specific way to reduce cumulative errors in speed from IMU unit.

Accelerometers and gyroscopes can't differentiate between constant linear speed and staying still (both have zero acceleration) and errors in speed accumulate constantly. Airplances and ships have ways to measure speed without GPS, even if currents or wind prevent accurate ground speed measurements. Small inexpensive devices like this don't have that.

This application uses foot movement to calibrate speed in every step. The same can be done with laser, ultrasound etc. but doing it with IMU sensors only is a neat trick.

The GP was saying that they don't use the term itself, though.

In general, inertial navigation has one significant difference over traditional dead reckoning: it is unaffected by currents. This is effectively irrelevant when traveling on land, of course, but then again, I don't recall seeing 'dead reckoning' being used to describe navigation on land.

And then there was this solution before GPS...

https://www.fastcompany.com/3047828/who-needs-gps-the-forgot...

Funny that all it took was to re-compensate for the noise of the accelerometer on every step. Sometimes, simplest is best.

One would think that this could be used with GPS to protect against GPS jammers trying to fool the device's view of where it is -- useful for avionics!

Not so easy to periodically touch your foot to the ground in that situation.

You misunderstood. The idea is to use an IMU to sanity check GPS. If you see too much drift or large jumps in GPS position/speed, or fail to get GPS readings for a long time, then you alert that GPS may be jammed and being to navigate using only the IMU and last known good GPS position.

IMU's are already used to increase the local accuracy of GPS. The problem is that due to double integration (acceleration -> velocity -> position) the errors accumulated badly.

It would only work for walking planes. :)

See below.

It is pity that Loran-C is being shutdown. It could have made use of all those old Long Wave broadcast transmitters.

https://en.wikipedia.org/wiki/Loran-C

But all systems using radio frequencies would be susceptible to jamming. There are alternative GPS systems from Russia, China, and the EU now, no? I suppose the more such systems, the harder for an adversary to jam them all. Of course, some of those are run by potential adversaries, so there's that.

You really need inertial guidance and/or terrain recognition (as the Tomahawks used to do back in 1990) as a fallback.

Not all RF based systems are equal.

GPS received signal strength at the Earths surface is around -130 dBm, barely above the thermal noise floor even in a good receiver.

Around 1000km (most populated areas) from a Loran-C transmitter putting out 1000kW the signal strength is around -50 dBm. That is 9 orders of magnitude harder to jam. All bets are off if your opponent can wheel out 1000kW jammers.

Last I knew, the US military was working hard on this problem. Against 'near-peer' adversaries (e.g., China as opposed to ISIL), they need to function when communication networks are shut down.

I wonder how long before this shows up in foot pods for runners. I would expect companies like Stryd and Garmin to be all over this.

That was my first thought as well. Accurate navigation from footpod data that could eliminate or at least drastically reduce gps usage would be a gamechanger for watch battery life.

The sampling rate you need from the inertial sensors is such that I'm not sure it's likely to use much less power than the GPS for similar accuracy.

Interestingly, both my Stryd foot pod and Garmin 935 watch (with GPS active) last about 24 hours. The Stryd generally provides more accurate distance/pace measurements. At least in one person's testing, the Stryd is the most accurate device currently available for distance/pace:

http://fellrnr.com/wiki/GPS_Accuracy

Distance travelled is quite a bit easier than actual position.

Granted, I haven't touched the tech in almost a decade :-P

http://ieeexplore.ieee.org/document/6851424/?reload=true

This is not the paper corresponding to the research described in the article.

A paper that describes a similar system by the same researchers from 2015 is here: http://ieeexplore.ieee.org/document/7181113/

Its not clear if the system presented at ISSCC differs at all.

I have a small Android app that uses steps sensor to track location:

https://github.com/tananaev/steps-navigation

It's not very accurate and there are some improvements that can be done, but it was an interesting experiment.

Pretty neat, but you would still need to give it a starting location since this only tells relative position.

The example they gave about inside building navigation does kinda make sense. Imagine firefighters with this device in their boots. They all get to the fire and press a snyc button (or click their heels three times) and their device gets the current position from the GPS in their fire truck.

Now they can be accurately (well sort of) tracked inside the building without requiring sky access for GPS.

They don't necessarily need GPS at all if they just want to be able to get back to a starting point.

There will need to be an adjustment made to account for running vs walking, since the foot does not necessarily rest for the same 100ms period while running. Granted, if the sensors are simply measuring the "stillness" of the foot planting, then calculation adjustments should only be limited by the reset period/accuracy of the sensors.

The time period of stillness isn't important for this technique.

It is, for a few reasons. For one, you need to be able to detect the period of stillness, and so how certainly you can detect that time window is a function of how long it is.

Second, you need to be able to make a number of measurements from your IMU during the downtime. If you have an IMU that works at 20Hz and your period if stillness is 100ms, then you know you can get a measurement in. If your period of stillness is 10ms, then you can't.

You could probably determine that with some walking. In a building, there may only be a few places where a right turn makes sense 3m after a left, 2m after a right, etc. Or a Bluetooth beacon.

I wonder if this could be useful on a phone, if a user held the phone steady and the accelerometers picked up the candence of their walk.

And here I clicked expecting Bowditch's.

https://en.m.wikipedia.org/wiki/Bowditch%27s_American_Practi...

Looks a lot like something I worked on at Michigan, years back - https://lojeda.engin.umich.edu/pps/

Cool stuff!

Reply on news.ycombinator.com