Darpa to re-invent GPS navigation without the use of satellites | Hacker News Reader

Darpa to re-invent GPS navigation without the use of satellites

extremetech.com

80 pointsDiabloD350 comments

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.

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.

I'm sure there's a lot of novel stuff they're trying to do here, but the article seems to seriously skirt that inertial navigation systems are all around us and in fact predate GPS by a lot.

Doesn't seem to me they're re-inventing GPS, just making better INS.

yeah, that was the impression that I got to. Shame the article was 80% waffle.

Halfway through the 7th paragraph (of 8) and finally a vague answer to what the title promised.

Geographic location could fall out as a side-effect of increased use of passive radar. Whilst it hasn't happened yet, the UK is testing whether it can use passive radar for air-traffic control [1]. If a radar receiver can figure out the position of a target, it would be even easier (no losses due to reflection) for the target to receive the same signals and figure out its own position. With a wide-band receiver, using all available incidental sources, it would also be hard to jam, since an adversary would have to have control over the entire electromagnetic environment. It would be even harder to jam if the receiver was using a phased array to figure out directions to sources, allowing it to null interference.

[1] http://www.atc-network.com/atc-news/airbus-defence-and-space...

Sounds a lot like "VHF omnidirectional range" (VOR) which dates back to 1946.

http://en.wikipedia.org/wiki/VHF_omnidirectional_range

In so far as VOR is the locational analogue of traditional "rotating beam" radar, but there the similarity stops. VOR has a known structure to its intended transmissions. Passive radar relies on incidental transmissions, and the system learns about any structure in the received transmissions. Passive radar has potential for much greater accuracy (better than GPS??), as it can potentially use a huge bandwidth.

The interesting section:

> including novel inertial measurement devices that use cold-atom interferometry; chip-scale self-calibrating gyroscopes, accelerometers and clocks; and pulsed-laser-enabled atomic clocks and microwave sources

Would it be possible to depend on the earth's magnetic field for positioning ? Migratory birds use it but I don't know how precise it is.

So called 9 axis inertia guidance units exist (3 linear accelerometers, 3 axis gyroscope, and 3 axis magnetometer). The magnetometers are particularly useful for dealing with gyroscope drift. Once you reject stuff like mains hum, in most typical situations, human scale magnetic fields tend to be pretty constant for many timescales in most human situations.

It's rather susceptible to local perturbations. Still a possibility when combined with other things, though.

Could they be inclined to, sometime in the very far future, shut down GPS completely? Many other countries have realised that GPS is entirely US-owned, and launched their own GNSS services already.

Deleted comment

Wrap the phone in tinfoil.

Reply on news.ycombinator.com