Hacker News Reader

Comment by bitwize | Hacker News Reader

Inertial and GPS-based navigation systems have always been complementary components of a complete navigation solution. The problem with inertial navigation is, it because you are reckoning position by taking the second integral of acceleration, error is introduced and what's worse, it accumulates. No matter how accurate the gyros and accelerometers, if you run the system long enough the drift accumulated will have you off from your actual position. So GPS is used to correct the inertial solution with actual position data.

So yeah, it's great that we're getting much better solutions from inertial gear to supplement a faulty or missing GPS solution. But this isn't GPS without satellites.

Now... navigation on or over land by performing SLAM on ground features... that would be interesting.

View on HN

That makes a lot of sense for automatic driving. DARPA's micro-PNT effort, to build a navigation-grade INS into an IC with an angular drift rate of 0.001 deg/hour, would be a huge advance. It's important to reduce dependence on GPS; the system is such an obvious target.

When, a decade ago, we did a DARPA Grand Challenge vehicle, our biggest technical problem was that we had about 3 degrees of heading noise. The AHRS system we were using weighted its magnetometer/compass too heavily and the compass was inside the unit, not on a cable where we could get it further from metal. All the stuff in the vehicle generated enough magnetic fields to mess it up. The heading noise kept the LIDAR scans from lining up properly when the vehicle was moving, and the vehicle had to stop, sweep the LIDAR, and rebuild a picture of its environment too often. Fiber-optic gyros were $20K back then, and back-ordered because of the Iraq war. We needed only about 1 deg/minute max drift.

> Now... navigation on or over land by performing SLAM on ground features... that would be interesting.

I'd more be interested in guidance using x-ray emissions from pulsars and neutron stars. Constant reference points that are almost impossible to jam.

Even better are distant quasi-stellar radio sources (e.g., [0]). The detectable pulsars and neutron stars are close enough (inside our galaxy) that they will not form a fixed reference frame, due to slow motion across the sky. Though, I suppose they're probably good enough over short time intervals, depending on the needed accuracy.

There's also the issue of X-rays not penetrating the Earth's atmosphere. One could try triangulating based on time of arrival for pulsar radio pulses, but that requires a reasonable amount of collecting area with a radio telescope and substantial processing power.

[0] https://en.wikipedia.org/wiki/International_Celestial_Refere...

Edit: slight clarification

Anyone have any idea how much extra "positional" info one could extract out of the position of the sun + an accurate clock?

Granted, I know you couldn't quite get an exact 3d positional reading from just those. But the way I see it, these are complementary systems, and if possible, this extra "data-point" can add accuracy by further narrowing down possible actual locations. Sort of like overlapping 3d volumes (from different systems, with differing levels of accuracy), that allow you to triangulate your position. Each data-source incrementally removing "definitely-wrong" or "very-innacurate" data points from your end calculation.

My M.S. thesis was essentially an attempt to answer this question. The answer, it turns out, is that the readings you get from single bright celestial sources (sun, moon) aren't accurate enough to enable navigation primarily from this data, even assuming perfect timekeeping.

You can use multiple readings of multiple celestial sources (stars) to navigate reliably, but then you've shifted the problem. With a single reference source your main problem is the sensitivity to error (slight angular errors translate to miles). But if you use starlight your primary difficulty is simply measuring the light sources in an affordable way (i.e. short of taking images in real time and doing real time image processing and graph construction on them).

The atmosphere is totally opaque to X-rays[0], so this wouldn't work from the ground.

[0] http://commons.wikimedia.org/wiki/File:Atmospheric_electroma...

True, but you could just use stars. The SR-71's celestial navigation unit could get a fix during the day while it's sitting on the ground: https://books.google.com/books?id=xwPFC3GtcL8C&pg=PA132&lpg=...

The Nortronics NAS-14V2 was designed in the early 60s. I would love to see the insides of one of those things.

One of my bucket list projects is to build a celestial navigation unit using a prosumer-grade CCD and BeagleBoard grade hardware (star maps stored on MicroSD card, computation done onboard providing NEMA output).

The SR-71's celestial nav unit was a work of art. Kudos for the reference.

Clouds, fog and smoke are the obvious issues. Dense tree canopies too.

Sure, those are all obstacles. But the way I see it, they can all complement each other. I.e. One of the posters mentioned drift of accuracy for some alternate positioning methods. You could then periodically, when possible, use this more-accurate but obstacle-susceptible system to "correct" the drift.

Regarding technical viability: what's their luminosity? It's quite hard to compete with solar radiation. x-rays also can't be resolved (there's no small x-ray lens), so I assume you need some kind of shielded detector, which should be vulnerable to all kinds of radiation sources and isotropic -- so a lot of noise and no resolution.

Regarding jamming resistance, if the signal is weak enough considering it's lack of resolve-ability (contrary to advanced GPS antennas which reject ground sources due to multipath and interference), it should be easy to direct an x-ray source at a receiver it and neutralize it.

> Regarding jamming resistance, if the signal is weak enough considering it's lack of resolve-ability (contrary to advanced GPS antennas which reject ground sources due to multipath and interference), it should be easy to direct an x-ray source at a receiver it and neutralize it.

Receivers are entirely passive. You would need to know with certainty location of the receiver to attempt to jam it, unless you're just using an omnidirectional transmitter (hello inverse square law!).

You could aim an x-ray beam at an airplane or car for example. Even with an omnidirectional antenna the signal of distant x-ray sources is so faint you most certainly could overpower it for large distances.

I also didn't realize but in this case unless the x ray sources have very specific, high frequency, detectable temporal radiation patterns you'd rely primarily on their location, and as I've said it's hard to resolve x ray images.

But this isn't GPS without satellites.

Actually, DARPA are looking for exactly GPS-without-sattelites:

Fine-grained PNT is no longer a luxury for the warfighter; it is absolutely essential. That has turned the sophisticated satellite signals on which PNT depends into potential vulnerabilities. To address this concern, DARPA is developing a family of highly precise and accurate navigation and timing technologies that can function in GPS-denied envi- ronments and enable new cooperative and coherent effects from distributed systems.[1]

It's unclear if this is an upcoming DARPA project or one that is ongoing. I find the DARPA website very hard to navigate unless you already know all the program abbreviations. The IARPA website is much better in that regard.

Edit: The program is at [2]. They are looking to combine inertial sensors with "signals of opportunity".

Complementing DARPA’s Micro-PNT program, which is developing chip-scale inertial sensors that are navigation grade or better, PINS is developing an IMU that uses cold atom interferometry for high-precision navigation without dependence on external fixes for long periods of time. Atom interferometry involves measuring the relative acceleration and rotation of a cloud of atoms within a sensor case, with potentially far greater accuracy than today’s state-of-the-art IMUs.

However, because even long-duration IMUs require an eventual position fix, the ASPN effort is developing sensors that use signals of opportunity, which are non-navigation signals from sources like television, radio and cell towers, and satellites, as well as natural phenomena, such as lightning.

[1] From http://go.usa.gov/3rut4 (PDF)

[2] http://www.darpa.mil/Our_Work/STO/Programs/Adaptable_Navigat...

SLAM: http://en.m.wikipedia.org/wiki/Simultaneous_localization_and...

It sounds like they are trying to radically rethink INS though, and if they can dramatically cut drift it would be a huge win. A drift-free INS is the holy grail of location systems (IMO), and we don't necessarily require a 0-drift solution (just extremely low drift).

Though you are right, a system depending on some entirely other phenomenon for location would be even more exciting.

> Now... navigation on or over land by performing SLAM on ground features... that would be interesting.

DARPA does have a plan for All Source Positioning and Navigation using radio-spectrum "signals of opportunity" for position tracking http://www.darpa.mil/Our_Work/STO/Programs/Adaptable_Navigat... .

I wrote an app that does this at a minimum level, for use as a car anti theft device (use an old android phone and a reloadable sim, hide under the car).

How do I show it ti people?

Github? Bitbucket?

"DARPA is investing in radically new technologies... including chip-scale self-calibrating gyroscopes, accelerometers and clocks"

It seems they are trying to eliminate long term bias. More technical description of their approach here: http://scpnt.stanford.edu/pnt/PNT10/presentation_slides/15-P...

> Now... navigation on or over land by performing SLAM on ground features... that would be interesting

This would be pretty... ugh... difficult to say the least. I agree though, it would be pretty interesting (and awesome). We would basically need to have most features of the environment we are trying to map through and update them regularly.

In Boris Chertok's "Rockets and People" vol 3 p 366[1], there's an aside about how Soviet ICBMs with MIRV did targeting by comparing on-board radar with a digital map of topographical features in the 70's.

[1] free to download from NASA: http://www.nasa.gov/connect/ebooks/rockets_people_vol3_detai...

I'm imagining some sort of giant feature-based hash table. What does "three oak trees, a light post, and a mailbox in relative positions [data vector]" hash to? That's an interesting problem. It also has to be some sort of nearest neighbor hash where the same hash without the mailbox component (or with additional preciously untagged components) allowed you to find the same stuff. So I guess this is starting to sound like sparse KNN.

You just invented FAB-MAP, though lower-level appearance-based features are used in real life:

http://ijr.sagepub.com/content/27/6/647.abstract

Google maps mashed up with Google image search.

Well, if you get people using it and then feeding their data to a server then that's a starting point.

>Now... navigation on or over land by performing SLAM on ground features... that would be interesting.

We are working on that exact problem at Visidraft (our site gives no hints about that actually). Except it's not just navigation, it's real time GIS overlay in AR on mobile.

Natural terrain only? Or does it work equally well in urban/indoor environments? </curious>

It's environmentally neutral. That's not to say that it doesn't work better in some environments, naturally environments with more persistent features work better. Unless previously mapped the sensor is naiive and builds as it goes, that's what it was designed for.

Generally speaking though, if it has "been there before" then it gives good registration everywhere.

Is there such a solution for phones? It seems like, given the magnetometer and accelerometer, you could get great accuracy even if the GPS signal is lost.

Had started nGPS - location using geomagnetic-field. But the concept never took off the drawing board. Limitations were mainly the inaccuracies with the consumer-grade sensors in smartphones.

http://thecodeartist.blogspot.com/2012/01/android-sensors-an...

With the current gen hardware in the phones.

1. Globally, nGPS is only good enough to act as a secondary source or an AGPS to reduce GPS time to inital fix.

2. Locally, it is already possible to map out the ambient magnetic-field of the terrain once and then rely on pattern matching to determine one's location within the terrain.

The tipping point here is the size of the terrain that needs to be mapped.

There's a lot of work in this area, in labs all over the world. Google's project Tango has funded some excellent work on this problem on a (very powerful) cellphone/tablet platform:

https://www.youtube.com/watch?v=44vppay5UDc

Todd Humphreys at The University of Texas Austin has been pushing for carriers to implement CDGPS since at least 2012.

That would be much more accurate just from the chipset point of view, but as they point out consumers aren't driving the need for such precision.

I have a feeling that the sensors in phones are not accurate enough to be really useful at all for this purpose.

Not for long periods of time, but I imagine they're sensitive enough to estimate where you are for a few minutes if your GPS signal is temporarily unavailable...

Then you would be surprised how bad they are. A great talk on using mobile sensors is here: https://www.youtube.com/watch?v=C7JQ7Rpwn2k

Long story short, expect something like 20 cm/s of position drift trying to do dead reckoning off of mobile sensors.

Reply on news.ycombinator.com