When the MacBook got the acceleration sensor, I hacked up a little program to estimate velocity, and a button to reset at stoplights. Some friends drove me around, it worked poorly. it did pretty ok on the highway, but awful in the city.

I think if I kept messing with it, it'd get a lot better, but I sorta lost interest. This was more of a fun weekend toy.

I think all phones have them, and they might be reachable through chrome/safari. And it is kinda fun to play with, but you'll probably hit sampling rate errors pretty quick. you gotta guess the shape of the curve between datapoints.

I said it downthread, but GPS is even more absurd. And we take it for granted.

But it's based on the same idea, only getting position as a derivative of velocity. (And some borderline-magic statistics applied.)

And that's before taking into account the absurdity of how low power the broadcast signal is.

GPS doesn't work that way. It uses instantaneous time-of-flight computation.

How do you think the 'instantaneous time-of-flight' computation is done?

There's a lot of math that phrase is hiding. It's not a magic black box. It just often seems that way.

At no point is velocity differentiated when computing a GPS fix. (Or integrated, which may be what you meant.)

Your point stands, though... the way it does work is pretty much indistinguishable from magic, from a 1970s perspective. Those guys were wizards.

If you want to understand GPS more, https://ciechanow.ski/gps/ is always an amazing read, witchcraft confirmed.

Isn't it about finding the time difference between pseudorandom coded signals. Granted the satellite positions and paths need to be known, which is another part of the puzzle. That involves some calculus, I'm sure.

Yes but measuring diffs in either the pseudocode itself or the underlying carrier wave is basically measuring relative velocities wrt each sat and the observer.

It's all summing dx/dt + dy/dt + dz/dt, for i paths between satellites and ground stations (or more receivers for differential or rtk or vrs style). [2]

Which reduces most of the time to summing DELTA-Xi + DELTA-Yi + DELTA-Zi + delta-t(timeerrors). For i paths between each sat and ground receiver.

Which you should recognize the transformation if you've ever taken calculus. Even if you don't integrate every time you get a fix.

Part of what I describe as math 'magic' is that you can cancel out most of the unknowns and most of the unsolved calculus if you add a second fixed receiver.

Google and Apple location services 'cheat' and do this via subbing a nearby wifi MAC with known coordinates, which for them is good-enough. But augmented gps from FAA or DOT or coastguard etc work the same way, but with real gps receivers on the ground in realtime. Obviously without having to substitute anything.

Either way- the extra known variable greatly simplifies the math via canceling-out terms.

Plus there are both closed and open form solutions developed since initial GPS deployment that allow solving without direct integration.

Chapter 12 of [0] Surveying gets into the math, including transformations, if you want to see the math details.

Or [1] GPS by van Sickle for a good overview of the various methods/ technologies. (Also survey-centric).

[0]https://books.google.com/books/about/Surveying_theory_and_pr...

[1]https://books.google.com/books?id=J0fLBQAAQBAJ&pg=PA63&sourc...

[2] despite wgs84 and lat/lon being associated as default 'GPS coordinates', the 'raw' gps system data is xyz Cartesian in feet, then transformed to lat lon or whatever else.

My assumption was that GPS doesn't use dead reckoning to get a fix (other than the satellite paths). Do receivers use the Doppler effect to directly measure velocity?

Edit: this article seems to support my view that they don't start with velocities: https://insidegnss.com/wp-content/uploads/2018/01/marapr15-S... "How does a GNSS receiver estimate velocity?"

Dead reckoning isn't really the right term- there are broadcast and published ephemera (ephemeris-es) for the satellites of various qualities. (Both predicted and observed and then even levels of correction days or weeks later, for high precision/accuracy or strictly static obvs. stuff.)

The doppler mostly comes into play with the small delta-t errors, but again, more math magic cancels most of it out in most cases, or what remains is negligible.

It's more of a signals/sync thing that gets into antenna design and (to simplify) getting all signal cycles from the various satellites working within a single aligned synced cycle, if that makes sense.

One reason the old gps units needed a long time to get an initial fix was waiting to download the broadcast, in ~bits/sec. This can now be downloaded much quicker via internet or other methods.

And there are dozens of other similar shortcuts possible depending on receiver capabilities/ connectivity/ observervation methods.

Which is to say that there's no one 'right' way to get a fix- and the 'most' correct original design was the ~hour long broadcast download. And no one does that anymore.

But just about every method (I'm aware of) is derived one way or another from the general eqns I gave above.

(But my exposure is almost entirely geodesy, engineering, and surveying, and my military (encrypted) knowledge comes from my PLS instructor being ex army intelligence, not hands on. But which is also why I am at least aware of so much of the missile tie-in issues.)

And there are signals processing and CS tricks also, which I only barely grasp.

But if something says it starts with baseline (propagating signal path) lengths to get position, it's skipping the step of how it measures/ estimates those initial baseline lengths.

It is how Apollo navigated, although both the ground (via ground tracking) as well as the crew (via locating stars through a extant, and the Apollo computer having a database of the position of several dozen bright stars) could update their current position throughout the flight.

Apollo used star sightings to check the accuracy of the gyros that measured which way the spacecraft was pointed. The stars could not be used to determine position like a ship at sea could do.

Besides inertial navigation, they had a transponder that would echo back a continuous pseudorandom bit stream, and the delay gave a precise measurement of distance.

Thank you for the correction, but are you sure that is accurate? I was definitely under the impression that although their position was normally updated by the ground (to the AGC, via their uplink capability), and the sextant was normally used to determine their orientation, the astronauts could use their optical equipment and calculations to determine their position as well as their orientation, albeit it with less precision. This NASA website (https://www.nasa.gov/history/afj/compessay.html#:~:text=Opti...) seems to say as much:

"Optical navigation subsystem sightings of celestial bodies and landmarks on the Moon and Earth are used by the computer subsystem to determine the spacecraft's position and velocity and to establish proper alignment of the stable platform."

And Wikipedia (https://en.m.wikipedia.org/wiki/Apollo_PGNCS):

"The CM optical unit had a precision sextant (SXT) fixed to the IMU frame that could measure angles between stars and Earth or Moon landmarks or the horizon. It had two lines of sight, 28× magnification and a 1.8° field of view. The optical unit also included a low-magnification wide field of view (60°) scanning telescope (SCT) for star sightings. The optical unit could be used to determine CM position and orientation in space."

The errors would be less of a problem than Apollo's, when your longest possible flight is only 45 minutes or so. And I'm not sure, but I guess the ballistic portion of the flight is uncontrolled (since the steering is from the rocket motors), so perhaps only the first few minutes are all it needs to maintain accuracy for?

At least modern ICBMs do a star sight to calibrate at the top of their trajectory but, yes, that’s what inertial guidance is. Draper Labs basically pioneered.

It's far from the top of their trajectory (by then the warheads are long separated), and only submarine-launched missiles need it.

Ah. I'm only somewhat familiar with Trident.

Ground-based launch sites can supply both position and orientation very accurately (few seconds of angle), more accurately than stellar correction can, and their gyro platform can keep it within a few seconds of angle as well.

Submarines can determine their position accurately enough, but their orientation data can be improved upon using stars.

The MIRV bus takes in the angular fix just before it starts giving the warheads their individual nudges.

You obviously know more than I do. I just have some second-hand non-classified info related to submarine-launched.

I also could not believe inertial navigation systems worked as well as they do when I first learned about them. At some point in time the most sophisticated IMUs were actually export-controlled!

Maybe this has changed or is ineffective now that smartphone/quadcopter IMUs have caught up.

Advanced IMUs are still export controlled and the state-of-the-art is classified. The US military considers this a cornerstone technology and has invested heavily in R&D over the years. The IMUs that are widely available commercially have improved significantly over the years but so have the military versions.

> Maybe this has changed or is ineffective now that smartphone/quadcopter IMUs have caught up.

They did not caught up. There are two kind of IMUs: one where you have to account for the rotation of the Earth during signal processing and one where there is no point because it will be lost in the noise anyway. The smartphone/quadcoptee IMUs are the second kind. The first kind is still export controlled.

consumer-grade IMUs are still well below the performance of even much older military-grade IMUs (which tend to be impressive feats of precision engineering with pricetags to match, but also physically much larger). You'll still find anything that's useful for working out position over any time period is export-controlled (dual-use or stricter).

That's super interesting to learn, thanks for letting me know! I'm a software guy but I love learning about sensors, it's always amazing.

I mean it's a nuclear missile, millimeter accuracy isn't really necessary. Somewhere in the general vicinity is good enough for it's purpose of going boom.

Well, accuracy makes a big difference if you're trying to hit a hardened target like a missile silo. Missile guidance has been a constant effort to squeeze out more and more accuracy. Minuteman I started with an accuracy of 2 km, but now Minuteman III is said to have an accuracy of 120 meters. The Peacekeeper (MX) missile, no longer in service, is said to have an accuracy of 40 meters. You can use a much, much smaller warhead if you're 40 meters away compared to 2 kilometers.

One thing I never understood is why they phased out the peacemaker and not the much older minuteman.

The START II treaty limited Russia and the US's ICBMs to a single warhead each, and the Peacekeepers were optimised as a platform to host multiple independently targetable re-entry vehicles (MIRVs) and when the US agreed to revert to a single warhead per missile the Minuteman III was much cheaper to maintain than the Peacekeeper.

So even though Russia withdrew from START II almost immediately, the US continued to unilaterally remove the MIRV capability from its ICBM fleet and stick to single warhead Minuteman IIIs.

The following was an interesting read on the super-fuze.

https://thebulletin.org/2017/03/how-us-nuclear-force-moderni...

shooting something 12000 miles away, 0.1% off is 12 miles. That's missing the target and will not destroy whatever you were trying to destroy

In the early days, that’s why nukes went into the megaton range. Because then 12 miles will still destroy your target.

Then they got a lot more accurate than .1%

In general, the USSR had bigger bombs because they weren't as accurate as US bombs. So yes.

> surely all the little errors compound?

Random errors (i.e. noise) cancel out in the long run thanks to integration. You're then only left with systematic offset errors which can presumably be calibrated out to a large extent.

Really depends on what you mean by random. If it is truly random then you will end up with a random walk.

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

We can assume the error will have a random (whether it's actually truly random or merely pseudo-random doesn't matter here, just assume it's indistinguishable from truly random for this discussion) and a non-random component.

The random component I assume to be gaussian (thermal noise, for example) and therefore symmetrical around the real value. It's obvious we can remove this type of noise through averaging (of which the core operation is integration).

The non-random component I assume to be a skew that can be calibrated out.

With these two assumptions in mind you can see that yes, it's indeed a random walk, but a very well behaved one.

No, you can't remove the random walk error by integrating. The point is that after integrating, what you're left with the random walk error. To make this concrete, if you buy a commercial-grade gyroscope for $10, it will have a random walk error of several º/√h. So after summing the errors for an hour, you're left with several degrees of random error, which is bad. If you spend $100,000 on a navigation-grade gyroscope, you'll get a random walk error < 0.002º/√h, which is much better.

As far as calibrating out the skew, of course you can do that to some extent, but it's not a magic bullet. The Minuteman periodically measures skew and even applies equations for the change in skew with acceleration. The problem is that skew is not constant; it changes with time, changes with temperature, changes with position, and changes randomly, so you can't just calibrate it out. That's one reason why missiles use strategic-grade IMUs for a million dollars rather than a commercial-grade gyro for $10: you're getting drift of .0001º/hour instead of .1º/second.

You are correct, I forgot to separate between long-term and short-term random effects.

Short-term random effects (as in, the part of the gyro's random walk error significantly higher in frequency than the inverse of the integration period) will get cancelled out by integration, assuming they're Gaussian.

Long-term random effects (mainly from time and temperature like you mentioned) will instead tend accumulate with integration aka worsening with time.

P.S. great fan of your many ventures into retro tech, keep them coming!

that was not what you forgot and your summary is still wrong. kens is correct. i suggest programming some simple simulations using a random number generator to get a better feel for the space

Would you like to expand on what I missed and how my summary is still wrong? Genuinely asking.

try it: take gaussian white noise with zero mean and integrate it twice. You'll see the signal does not stay close to zero, in fact it will drift arbitrarily far away from it over time (it's only necessary to integrate once for this to be true, but doing it twice as an IMU needs to will make it more obvious).

You are correct, I initially did not explicitly separate the noise according to its frequency (my mistake). Integration only helps with high frequency error and can actually worsen low frequency error, more details in my second reply to kens.

One can't cancel out random errors by integrating. You should take kragen's suggestion and write a quick simulation. To make this concrete, flip a coin 10 times. Take a step to the left for heads and a step to the right for tails. Most of the time you won't end up where you started, i.e. you have residual error.

> One can't cancel out random errors by integrating.

An ideal integrator has a response of 1/s. That's just a 1st order low-pass filter with the pole at 0. Therefore, it will filter out high frequency noise.

> Take a step to the left for heads and a step to the right for tails. Most of the time you won't end up where you started, i.e. you have residual error.

I wrote a quick simulation based on your suggestion [1]. Started by generating 1e6 random points and then applied a high-pass filter. Calculated the cumulative sum on both the original and the filtered version. TL;DR: filtered version has small and very fast variations but doesn't feature the much larger amplitude swings seen in the original.

Integration indeed does not help for those large slow swings (I'd call it drift in case of a gyroscope), but that's what I was trying to get at when I started to distinguish between short and long term random effects. What I was trying to get across originally is that "all the little errors" (which I read to mean tiny fast variations, forgetting that drift is a much bigger issue in gyroscopes) which OP mentioned get filtered/canceled out. I totally missed to explain that this will vary with frequency, which was my bad.

[1] https://github.com/afonsotrepa/noise-sim/tree/master

yes! but also keep in mind that 1/s is never 0 for any finite s, so even at high frequencies the error resulting from random noise is never zero, it's just strongly attenuated

That's right but "the Bode plot of an integrator is a line with a -20 dB/decade slope" doesn't really roll off the tongue ;)

it's implicit in this comment by kens though:

> if you buy a commercial-grade gyroscope for [us]$10, it will have a random walk error of several º/√h. So after summing the errors for an hour, you're left with several degrees of random error, which is bad. If you spend [us]$100,000 on a navigation-grade gyroscope, you'll get a random walk error < 0.002º/√h, which is much better.

if the slope was anything else, the unit of °/√h wouldn't make sense; it would have to be °/h or °/∛h or something. similarly for noise figures given in nanovolts/√Hz

That is how all self-guided weapons systems worked before GPS was viable. Many still retain that capability as a fallback. Notably, the Tomahawks fired during Desert Storm had to transit over Iranian airspace because they needed the mountainous terrain to correct for their inertial drift before turning toward their targets over the flat Iraqi plains.

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

Almost all. Walleye television-guided glide bombs used edge detection on a television signal to aim themselves in. A human would designate a target at the start but then the bomb would autonomously track the target. An optical fire-and-forget system developed in the 1960s.

Sidewinders are another example. Both developed at China Lake.

> before GPS was viable

GPS can be jammed (see Russia-UKraine war), so inertial systems are still very important for rockets, for example some HIMARS rockets start with GPS and then rely only on inertial while getting close to target.

Himars relies on inertial navigation the entire flight and uses GPS updates to course correct. If the GPS is blocked for a sufficient amount of flightime, even with the intertial navigation, the accuracy can become unusably low.

This is how the Russians have been throwing double digit percentages of launches off course.

Terminal guidance since ~1995 on higher-end weapons has switched to hybrid inertial + scene matching (various sensor types).

F.ex. the 90s Tomahawk used terrain contour matching to orient itself

For more details see https://apps.dtic.mil/sti/tr/pdf/ADA315439.pdf (US translation of a mid-90s Chinese survey of the guidance space, but it covers the material and is publicly available)

Afaik, most modern systems use infrared target matching for final course correction. (Initially developed to allow anti-shipping missiles to autonomously prioritize targets, but now advanced enough to use in land scenarios as well)

I don't think ATACMS or GMLRS missiles have any terminal guidance apart from their aim point. The GMLRS missiles that carry german SMART munitions do, technically, since the SMART munition has it's own targeting system.

It wouldn't make much sense to me, as most ATACMS warheads are area based, not point target based, so they wouldn't expect to aim at a single target. Also these systems are relatively cheap compared to things that DO have such guidance

They don't and are definitely at the dumb/cheap end of the scale. (or in ATACMS' case, dumb/big)

I think anything developed before ~2005 that wasn't explicitly anti-ship doesn't have terminal guidance. Cruise missiles maybe/not.

Things after (e.g. SBD2 / StormBreaker) started to, because components were finally cheap and mature enough during the development cycle.

Only cruise missile have tercom. Himars and Excalibur do not have any camera or terrain matching system

The little errors do compound, but the errors have been made progressively littler; a modern ring-laser gyro INS has a drift of one millidegree per hour or less.

Or you can add an external correcting factor, such the Trident's astronav system that takes star-shots to recalibrate the INS.

When Nintendo Wii motes first appeared, they were some of the few devices at the time with cheap MESM accelerometers and gyroscopes that were programmer-friendly.

I remember taping two together back to back and integrating acceleration across them. That's when I learned Kalman filters. It was accurate enough so I could throw it across my desk and measure the desk length :)

Kalman filters were also used in the AGC - useful for landing on the moon. I suspect they were not used by the Minuteman - does anyone know?

https://en.wikipedia.org/wiki/Kalman_filter#History

https://github.com/chrislgarry/Apollo-11/blob/master/Luminar...

See https://news.ycombinator.com/item?id=40692333

Operation Black Buck [1] used inertial navigation.

[1] https://en.wikipedia.org/wiki/Operation_Black_Buck