Image Source: [Tech Only]
Written by: Tony Kerr
Now that we know how autonomous cars map their environments, let’s go over how they actually get from point A to point B within those environments.
At its heart, GPS relies on triangulation, or more correctly, trilateration to determine the receiver position. By knowing the distances between the user and some known reference points, the user’s position can be determined using geometry. The reference points used by GPS are of course the satellites, whose positions and orbits are known with a high degree of accuracy.
GPS satellites are grouped into 6 orbital planes with the original design calling for 4 satellites in each plane, although as of 2016 there are 32 satellites in total, which allows some redundancy and an improvement in accuracy. This means that, while four satellites are required for a GPS “fix,” at any one time at least 6 satellites
will be visible from any point on the earth’s surface and quite often more.
So, how do we measure the distance between the GPS receiver and the satellites? The technique is not unlike that used by RADAR. By measuring the time taken for radio waves to travel from the satellite to the receiver, the distance can be calculated. So, if we send a radio message to the receiver with the time that the message
was sent, the receiver can calculate the distance by subtracting the time of transmission, ToT, from the time of arrival, ToA, to get the time of flight, ToF, and multiplying that by the speed of light:
D=C(ToA-ToT)
The messages that the satellites transmit contain information about their orbital positions, known as their ephemeris, as well as a timestamp, which is the time the transmission was sent. Once the positions of the satellites are known, and their distances from the receiver are known, the position of the receiver can be calculated.
There is a problem, however, and it’s a big one.
Much like the problem with determining longitude I talked about last time, if the local clock on the receiver is not perfectly synchronised with the clock on the satellite, the time difference will not be correct. Because we are using radio waves that travel at the speed of light – 300 million metres per second – even a small error in the local clock will result in a large error in distance. If the local clock is off by just one millionth of a second, for example, the distance calculation will be out by 300 metres.
One solution is to use an extremely accurate clock that is set to the same time as the satellites – in much the same fashion as the marine chronometers of old were set to Greenwich time. The problem with this idea is that only atomic clocks are accurate enough. Atomic clocks are very expensive and tend to be big and heavy.
You won’t get a caesium clock to fit into your mobile phone, for example, and even if you could the phone would set you back over $50,000. We need a way to get around the problem that doesn’t involve having an expensive atomic clock in every receiver.
Fortunately, we can use a bit of geometric chicanery to solve the problem.
To begin with, we need to know the positions (x,y,z) of the satellites, as well as the time the transmissions were sent – we calculate these from the ephemeris data and the time of transmission in the satellite messages.
Our local position can be seen as a point in 4 dimensional space – x, y, z and T. The time dimension being the (unknown) difference between the local clock and the GPS standard used by the satellites. In order to calculate our position in 4 dimensional space, we will need 4 measurements, therefore at least 4 satellites.
Between the receiver and the satellites we have four pseudoranges, one for each satellite. These are distances that we can initially calculate from the time of arrival (according to our local clock) and the time of transmission. We know that the pseudoranges include range errors due to the time difference between the local clock and the GPS standard, among other things, which is why they are referred to as pseudo (false) ranges.
We can now get a bit mathematical. The four pseudoranges can be described using a set of four equations that relate the x, y and z positions of the four satellites, the x, y and z positions of the receiver and the range error. This set of equations can be rearranged and solved simultaneously (a mathematical technique, not “at the same time”!) to calculate the x, y, z and T co-ordinates of the receiver.
There are various mathematical techniques available to solve these equations, none of which are simple, but once reformulated the calculations can be performed very quickly by a microprocessor. Given the speed with which modern microprocessors run, you might be tempted to ask why a GPS receiver takes at least 30 seconds to obtain a “lock” on the satellites.
The answer is that space communications are tricky. You may have heard that the deep space probes out near the edge of our solar system send data back to Earth at an agonisingly slow pace, with data rates measured in hundreds of bits per second compared with the gigabits per second of your high speed internet connection. The reason is that the transmitter is not very powerful and the distance the signals have to travel is very long. The signal gets lost in noise along the way, so we have to use some trickery to recover it.
The same is true of GPS satellites. The signal at the Earth’s surface from each satellite is around 0.3 femtowatts (1/3 of a millionth of a billionth of a watt). To recover the signal, GPS uses a similar arrangement to CDMA (Code Division Multiple Access) that uses a mathematical technique known as autocorrelation. Autocorrelation relies on sending the same signal over and over and by adding all the copies together, the signal gets bigger while the noise averages out to zero (although the actual maths is more complex than this).
When all is said and done, each satellite has to repeat itself over and over so it takes 12 ½ minutes to send all 25 frames of its navigation message. Each frame of the navigation message is 1500 bits long and contains information about the satellite’s local time and clock offset, it’s ephemeris data, information about the ionosphere and the satellite’s status as well as a portion of the satellite almanac. The almanac is a list of all the satellites and their orbital information although it is not as accurate as the ephemeris.
Each frame takes 30 seconds to transmit, which is why a GPS fix takes at least 30 seconds to acquire – it takes that long for the satellites to tell the receiver where they are. Because the almanac is out of date after a few months, a receiver that has been switched off for some time will have to perform a “cold” acquisition, which takes at least 12 ½ minutes because the receiver must download the entire almanac.
So, just how accurate is GPS, anyway?
GPS was designed for use by the Military, and measures designed to deny the enemies of the USA access to highly accurate global positioning initially provided civilians with a location accuracy to within around 100 metres. Given that alternative navigation systems only provide accuracy to within a few kilometres, 100 metres was a significant improvement.
Today, however, the system is much more accurate, with high precision aerospace GPS units able to provide an accuracy of around 2 metres 95% of the time.
There are various sources of error such as the ionosphere that tend to degrade the performance of GPS, although its accuracy is improving all the time. In the 1970’s, initial estimates indicated that the accuracy of civilian GPS would probably not be much better than about 30 metres, although developments and improvements over the past few decades have brought that figure down to around 3 metres.
As with everything, you get what you pay for and more accurate GPS units tend to be more expensive.
With an accuracy somewhere between 3 and 10 metres, GPS isn’t quite good enough to tell the Google car exactly where it is on the road, but on a good day your car GPS can be good enough to tell you what lane you are in. When combined with Google’s mapping software, however, GPS becomes an essential tool that allows the Google car to navigate to its destination.
The astute will have realized that if it takes 30 seconds to transmit a frame with the satellite’s position, the receiver will only get an update every 30 seconds. 30 seconds between updates is a long time when you are driving at freeway speeds – in 30 seconds you could be well past the point where you need to turn. So how can GPS possibly be accurate when it is moving?
GPS receivers designed to be used in vehicles also use inertial navigation to perform short term dead reckoning between GPS fixes. By monitoring the vehicle’s acceleration, it is possible to determine with a reasonable degree of accuracy how fast and in which direction the car is traveling, so dead reckoning can be used to calculate the vehicle’s position. By adding a gyroscope and compass, the receiver can make quite good estimates of its instantaneous position and speed.
For example, if the car slows and turns left the accelerometer and gyroscope will detect the change in speed and direction and the receiver will know it has slowed down and turned left instead of traveling straight ahead at a constant speed. Combine this with the Google mapping software, and the GPS unit knows that you turned left into a side street, for example, and can update the mobile map accordingly.
Now, inertial navigation is not good over longer times – gyroscopes and accelerometers tend to drift with time and must be corrected. Even the compass in your mobile phone has to be recalibrated from time to time – but over short time periods, 30 seconds say, inertial navigation is just what the doctor ordered.
Without GPS and Google’s maps, the Google car would be able to avoid obstacles such as other cars, pedestrians, and the gutter, but would be completely unable to figure out where to go, how to get there and where to turn.
With it, however, the Google car can be a better driver than most of us.
Next time – the other senses.
Connect with us to learn more about how autonomous vehicles will shift the role of manufacturers, dealers, and the auto industry. Leave a comment below or reach out at info@smallworldsocial.com.
Comments are closed.