Get email delivery of the Cadence blog featured here
GPS is great. I can drive practically anywhere, with directions to get to almost anywhere, and there are apps on my phone that I can use to detect traffic, locate where police officers are hiding out, see potential hazards on the roads—even detect where the bad potholes might be. It works for me.
The Global Positioning System (GPS) is a network of about 30 satellites orbiting the Earth at an altitude of 20,000km. The system was originally developed by the US government for military navigation, but now anyone with a GPS device can receive the radio signals that the satellites broadcast. So, wherever you are on the planet, at least four GPS satellites are “visible” at any time, that is, they are reachable from your location from horizon to horizon. Each one transmits information about its position and the current time at regular intervals. These signals, traveling at the speed of light, are intercepted by your GPS receiver, which calculates how far away each satellite is based on how long it took for the messages to arrive.
Once it has information on how far away at least three satellites are, your GPS receiver can pinpoint your location using a process called trilateration.
Imagine you are standing somewhere on Earth with three satellites in the sky above you. If you know how far away you are from satellite A, then you know you must be located somewhere on the red circle. If you do the same for satellites B and C, you can work out your location by seeing where the three circles intersect. This is just what your GPS receiver does (although it uses overlapping spheres rather than circles, so it can also determine your altitude).
You must be in Kansas!
The more satellites there are above the horizon, the more accurately your GPS unit can determine where you are.
Side note: On these satellites are incredibly precise atomic clocks because they must be able to determine your location by measuring the speed of light from your device to the satellite. General and Special Relativity, however, predict that differences will appear between these clocks and an identical clock on Earth. General Relativity predicts that time will appear to run slower under stronger gravitational pull—the clocks on board the satellites will, therefore, seem to run faster than a clock on Earth. Amazing!
Now, that’s all very well and good, but what happens if your horizon is very small, like you’re in a big city with skyscrapers and the buildings get in the way of the satellite signal? Or if you’re somewhere in the mountains? GPS is accurate to within a few meters—what if you need more precise location information than the GPS can give you? There must be some alternative.
And there is.
This technology is called simultaneous localization and mapping, or SLAM.
SLAM is the computational problem of constructing a map in an unknown environment while simultaneously keeping track of a device’s position (location and orientation) within it. To do this, you keep track of six degrees of freedom (6DoF), which is composed of three degrees for position (up/down, back/forward, and right/left), and three for orientation (yaw, pitch, and roll).
Six degrees of freedom, or 6DoF
Computation for SLAM was typically done with a camera sensor as the only form of input. This was known as Visual SLAM (VSLAM). But in the past few years, with the suite of additional sensors becoming available, SLAM has evolved to using additional sensor input for robustness.
So, in practical terms, perhaps your GPS let you arrive at your destination, an office building at 123 Main Street. But you still don’t know where Suite B is in that space. To map out that building, you might need a robot to roll through the hallways—kind of like the Google maps car with the 360° camera on top—to plot out the walls, doors, exits, and so forth, and then upload that information to the cloud. Voilà, SLAM has just been used to give you an accurate map of the building, and you can find your way.
The applications that and do can use this technology are endless. Some examples that use SLAM are:
These examples are just those off the top of my head. I’m sure there are more.