Data and Information

Plan B For Navigation

A representation of how the Global Positioning System provides planet-wide navigation data.
GPS remains Plan A for navigation, but if it should fail, what is Plan B?

Anyone who has used a Global Positioning System (GPS) navigator has seen the system’s ability to tell you precisely where you are — and, most likely, has faced frustration when the device just doesn’t work. Yet for the military — which uses GPS data for such mission-critical applications as target tracking, missile guidance, and simply getting around in foreign areas — GPS failure can be a matter of life or death. That’s why military researchers, such as those at the Air Force Institute of Technology (AFIT) at Wright-Patterson Air Force Base in Ohio, have long been exploring alternatives to the Global Positioning System.

"Thirteen years ago, a lot of the [military’s] focus was still on getting GPS deployed into our systems, but we looked ahead and said, ‘what do we do if GPS isn’t available?’" says John Raquet, a professor of electrical engineering at AFIT who directs the institute’s Advanced Navigation Technology Center.

Because GPS relies entirely on satellite signals, which require a line of sight between several of the system’s earth-orbiting satellites and the receiver, GPS often fails underground or between tall buildings. Problems can arise even without obstruction, however: satellite signals are relatively weak, making them a target for malicious interference ("jamming") and spoofing attacks.

Of course, crude navigation options had been around for centuries before GPS came into use: the classic standby is dead reckoning, which enables voyagers to calculate their current position given the estimated distance traveled from a known starting point and the angle of drift. But even with fairly accurate motion sensors (accelerometers) and rotation sensors (gyroscopes), dead reckoning is notoriously unreliable, because its errors snowball rapidly. So although accelerometers and gyroscopes remain at the heart of modern inertial measurement units (IMUs, which report on a vehicle’s location, velocity, and direction), the need for greater accuracy has prompted researchers like Raquet and his students to augment IMUs’ data with additional clues about current position.

One promising approach, the basis of 46 master’s or Ph.D. theses in Raquet’s group so far, marries inertial sensors with visual sensors, cameras mounted on an aircraft to snap ever-shifting pictures as the plane moves. The method is more secure than GPS because, as Raquet puts it, "it’s tough to jam a camera." The researchers take existing hardware and sensors — creating what Raquet describes as "essentially a souped-up radio-controlled aircraft" — and create an algorithm to process the navigational data.

It’s the algorithm that makes or breaks such systems, says Todd Humphreys, director of the Radionavigation Laboratory at the University of Texas at Austin and a professor of Aerospace Engineering and Engineering Mechanics. If you’ve already got an area mapped out, he explains, you can use photogrammetry to match your camera’s images with these known locations, in which case inertial measurement isn’t even necessary. If you’re in an unfamiliar environment, you can use visual simultaneous localization and mapping (SLAM), a technique from robotics, to stitch together a map and contain the drift. "The real trick is building algorithms that can do this in real time," Humphreys says, "but right now, everything drifts and fails with enough exploration."

Another common approach, used by Raquet and many other researchers, is to listen for various "signals of opportunity," such as FM radio signals broadcast for purposes having nothing to do with navigation, but which provide useful location data nonetheless. The Earth’s magnetic field provides a naturally occurring signal of opportunity, although to be useful for military applications, the map of magnetic field variation would have to be much more detailed than its current form. "With natural signals, the world model tends to be very complex and require very large databases," Raquet says. "To create a large map, you’d almost have to just have a lot vehicles collecting a lot of [magnetometer readings] and building up a large database."

The ability to assemble such large collaborative databases is one of the enabling technologies that in recent years, Raquet says, have made new navigational tools easier to develop and test. Perhaps the biggest boon has been in increasingly small, low-power, and efficient sensors. "Think about cameras," Raquet says. "Twenty years ago, a digital camera would be hard to come by and expensive, and now most of us are carrying around a very good digital camera in our pockets within our cellphones."

In the meantime, signal processors have kept pace with Moore’s Law, so whereas 10 years ago image data had to wait to be processed until after all of it had been collected, these days some of the same image-processing algorithms can run in real time.

Every proposed solution has its drawbacks, and the right approach comes down to the characteristics of the environment, Raquet says. A camera may be tough to jam or spoof, but it isn’t much use through a cloud cover. That’s why it’s helpful for navigators to have access to multiple systems. "Let’s say you’re driving along in a vehicle, and you’re using GPS and it goes away," Raquet says. "Now maybe you can use signals of opportunity like FM radio or TV stations — but then you get to a region where you don’t have those stations available, so maybe you’d go back to more of a dead-reckoning system."

For all its weaknesses, though, GPS remains Plan A. "Another approach might be more secure, or more robust, but none of them are as global and as cheap and as precise as GPS," Humphreys says. "But if you can’t trust GPS, you end up having to settle."

Based in San Francisco, Marina Krakovsky is the co-author of Secrets of the Moneylab: How Behavioral Economics Can Improve Your Business.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More