Sunday, March 28, 2010

Experiments with GPS

The biggest mystery in the universe is clearly the male brain. What happens if you leave my husband alone with a GPS receiver? He'll spend several hours measuring the position of a table. For what I'm concerned the table is on the patio. Besides this, I'm every product developers nightmare since instead of reading manuals or tutorials I randomly click or push buttons till I've figured out what they're good for. That's a good procedure to find out every single way to crash the system, but usually not particularly efficient to actually use the device or software. Stefan instead goes and reads the manual!

In this case, he's been playing around with a brand new Garmin etrex H GPS receiver. Among other things it allows you to store a time sequence of position measurements, a so-called track, which you can then upload on Google maps to see which part of the forest you've been straying around in. This cute high-tech gadget is shown in the photo. On the display (click to enlarge) you can see a schematic map of the sky with the GPS satellites in view, and the strengths of the signals received from these satellites indicated in the bars at the bottom of the screen. Moreover, the display says that the accuracy of the position measurement is 5 meters.

Now, Stefan wanted to figure out the meaning of this accuracy, and if it can be improved by averaging over many repeated measurements. So, he put the GPS receiver on said patio table, and had the device measure the position every second over a duration of a bit less than 3 hours. Then he downloaded the measurement series with several thousand data points, plotted them, and computed the average value.

Remarkably, this simple experiment delivered clear evidence that spacetime is discrete! Shown in the figure below is the longitude and latitude of the data points, transformed to metric UTM coordinates, as blue crosses. The yellow dot is the average value, and the ellipse has half-axes of 1 standard deviation. Several thousand measurements correspond to just 16 different positions.

This 3-d figure shows the weights of the data points from the above figure:

Of course, the position measurements in the time series are not really statistically independent, so one has to be careful when interpreting the result. If one repeats a position measurement after the short time interval of just one second, one expects a very similar result since the signals used likely come from the same satellites which haven't changed their position much. Over the course of time, however, the satellites whose signal one receives are likely to change. To see this effect, Stefan computed the autocorrelation function of the measurement series, shown in the figure below:



The autocorrelation function, a function of the time delay τ between two measurements, tells you how long it takes till you can consider the measurements to be uncorrelated. The closer to zero the autocorrelation function, the less correlated the measurements. A positive value indicates the measurements are correlated on the same side of the average value, a negative value that they're correlated in opposite directions.

How do we interpret these results?

The origin of the discreteness of the measuring points is likely a result of rounding or some artificially imposed uncertainty. (The precision of commercial devices is usually limited as to disable their use for military purposes.) It remains somewhat unclear though whether the origin is in the device's algorithm or already in the signal received.

The initial drop of the autocorrelation functions in the figure means that after roughly half an hour, the position measurements are statistically independent. But why the autocorrelation function does not simply fall to zero and instead indicates complete anticorrelation in the y coordinate (latitude) data for a delay of about 1.5 hours and seems to hint at a periodicity is not entirely clear to us - more data and a more sophisticated analysis clearly are necessary.

Anyway, finally, to finish this little experiment, Stefan uploads the graphs to blogger. And then asks his wife to weave a story around it. The biggest mystery in the universe...

42 comments:

Steven Colyer said...

Anyway, finally, to finish this little experiment, Stefan uploads the graphs to blogger. And then asks his wife to weave a story around it. The biggest mystery in the universe...

It was a dark and stormy night ...

The biggest mystery in the Universe is the male brain ?! In America, and possibly England since that's the country we get 90% of our culture from, no man reads instruction manuals. That's woman's work.

Of course there's always an exception, as in my marriage, which is like yours. Tell Stefan I think he would have made a terrific Engineer or Experimentalist. Physics is probably better though. Less money, more satisfaction.

The female brain is clearly the biggest mystery, Bee. Or was, because now we know why. There are more connections between the left and right sides of the female brain than the male brain. That means females can think of 20 deep thoughts in 20 minutes, while males with their focusing ability are challenged to think of more than two in that same timespan. Yin and yang, male and female, each completes the other, the two paisley shapes form a sweet circle when combined.

My own conclusion from that is that in a truly enlightened society, the women are the managers and the men the workers. Example: what happens when it's time to move the furniture?

Sunny said...

Great little experiment! I think a lot of the errors in consumer grade GPS receiver come from having a poor quality clock in the receiver. There is also a small error that comes because of the local ionosphere conditions through which the signal has to travel. Also, isn't there a small error coming from the general relativity effect? i.e., clocks on-board each satellite should tick just a tad faster. I do remember reading something about it and how this effect is mostly (but not fully) accounted for and can introduce 1 or 2 meter discrepancy.

Plato said...

How do we interpret these results?

To within "yards" for our American viewers and "ole time" Canadians. "Meters" for others.

You might turn Stefan onto Geo Caching to leave gifts for his sweety?:).

If you hadn't mentioned table it could have been "the chair" or the "barbecue by coordinates." Militarily there is better accuracy.,

Boy talk about the good ole days of mapping to one's destination by coordinates.

I guess that's progress.

Best,

Phil Warnell said...

Hi Stefan & Bee,

A nice piece regarding GPS and your thoughys on how it moght support the hypotisis that space is discrete at the fundamental level. To be honest I’ll have to look more closely at all you’ve offered here, with particular attention given to Autocorrelation of which I know nothing about. I just wanted to make one comment with that being that it’s not just in the military having very accurate instruments, yet also in commercial aviation, surveying in respect to the construction industries.

Perhaps the most poignant example of this is in the surveying techniques which were used in the building of the record setting Burj Dubai tower, with a comment taken from the cited article quoted below stating their equipment being accurate to a within a few millimetres, as opposed to meters. It would have me lead to believe it has more to do with the pre3cision of the receiver of the signal and the computing power of the instrument that receives it. Then again a few millimetres is a long way from the Plankian domain.


”Because of these difficulties, we decided to establish position using GPS. This has been refined a lot in recent years and now provides very good results at the millimetre level of accuracy,” says Sparks. Rather than employ a lone GPS receiver that produces single point positioning, the survey team set up a base station nearby with accurately-known coordinates. The resulting differential positioning allows the GPS receivers at the top of the tower to obtain a much more precise reading. Real Time Kinematics (RTK) are used to obtain a GPS figure that is updated every fraction of a second, to an accuracy level of 10 mm in the horizontal x-y axis for most of the day and 20 mm accuracy in the z vertical axis.”

Best,

Phil

P.S. This reminds me of one summer getting a job while in high school working with my brother on his surveying crew with the consulting engineering firm for which he worked. My function was that of the chain man with my brother sighting the transit and another on the target. We would walk around taking reading s for several hour, then return to a nearby restaurant where my brother would work on the calculations. Those were the days before hand held calculators, with everything done long hand assisted by a slide rule. This being an analog device rather than a digital one with having your calculated accuracy being limited only by the resolution or in other words one\s eyesight in conjunction with the marks on the rule:-)

Steven Colyer said...

Slide rules are still important, Phil. Say you're in the middle of the Saudi Arabian desert and the battery on your laptop or handheld calculator dies, and you still have to calculate stuff.

Steven Colyer said...

more data and a more sophisticated analysis clearly are necessary.

Have you contacted Mike Lazaridis or Richard Branson for some private grant money? That's what I would do.

Phil Warnell said...

Hi Steven,

I’m afraid pretty soon the only place you’ll find a slide rule is in a museum, as even the calculators are solar powered. However I do find this all leaving us vulnerable, as what if we had a solar flare or a gamma ray burst so intense it fried all our microchip technology (even the so called space hardened ones). Although admittedly a remote possibility, let’s suppose a star like Betelgeuse goes Supernova and while not being polar aligned enough for the gamma ray burst to be fatal yet, still strong enough to fry all the chips. This perhaps is where the developing world will find advantage, as they will be more able to cope. How’s that for a 2012 scenario. Just think of it Steven, it might come to be that old dinosaurs like us save the rest from extinction :-)

Best,

Phil

Phil Warnell said...

Hi Bee,

Of course you know this is all a plot hatched by Stefan in an attempt to avoid the duties mandated by his vows. That is the next time you ask him to rearrange the furniture, according to your wishes, he will ask to be given their precise latitude and longitude. Then he will say it’s only on account of the discreteness of space that prevents him from even making the attempt. However what he doesn’t realize this won’t succeed as you’ll instruct him to move it around until it looks right:-)

Best,

Phil

Zephir said...

Women in fact doesn't use manuals, because they're uncapable to do so in simmilar way, like they cannot use the maps for navigation, etc. They even cannot read software instructions & dialogues from screen, as I realized many times.

Zephir said...

Anyway, the discreteness of space-time revealed is in good agreement with LQG theory - or not? I could falsify string theory as well - well, finally...

Steven Colyer said...

Forget Betelgeuse, Phil, I'm afraid of an EMP bomb going off and frying all the technology around us that we overly depend on.

IF that happens, then the most popular guys will be the ones with 1950's vintage cars they've kept alive, where the only electronics, electricity really, are the starter, alternator and battery.

The ones who have maps and a knowledge of local geography will be a plus.

ErkDemon said...

I guess that if you're trying to use statistical averaging to get below the official resolution, it might be an idea to try using positional jitter.

If you move the GPS unit aound a set of points centred on the centre of the table, then some of the time you might end up in one quantised patch, and some of the time another. The ratios of how often you appear in each patch then tell you your rough position from the centre of those patches.

I suppose that you could try to use the existing GPS system noise for this, but you won't know its time-variant characteristics. Moving the GPS receiver around, yourself, gives a guaranteed jitter to tickle the system in addition to whatever the satellite network might be doing.

Steven Colyer said...

THANK you, ErkDemon. Wonderful idea, I wish I'd thought of it first, and yet another reason for The King of Sweden or other rich folk to send some money Stefan's way for further experimentation.

I would ask: If you use a quantum mechanical apparatus and get quantum mechanical results, where's the surprise? But I'm not an expert in Loops so that's either an intelligent question or just damn silly.

Phil Warnell said...

Hi Steven,

In respect to this research of Stefan’s, pertaining to the question regarding the discreteness of space as to have it conform to the rules of the quanta, I would ask you a question inspired by one which Einstein asked his biographer, Abraham Pais; which would be do you really believe the patio table is where it is only when you look at iit, Now he asked Pais the same of the moon. yet I’m leaving you a little more leeway :-)

Best,

Phil

Uncle Al said...

1) A heavily used set of HP-15C batteries lasts about 25 years.

2) If it's chipped and especially if it's RFID (passports!),

http://www.emvelope.com/

3) Uncle Al has lost all faith in claimed dark matter detections if a patio table has the same counting statistics' confidence level.

4) It is socially activistic to claim working minds mirror the formulaic incapabilities of the bottom 99% residue.

Jérôme CHAUVET said...

@Steven: lol. You're theory of men and women differences is definitely hilarious, I can't stop laughing as it sounds so born from experience.

But be careful of stereotypes. E.g., my wife is a German and I am a French, though I am the one of us to be obsessed by putting things into order.

@Bee and Stefan:Concerning Stefan's discrete measurements, it is clear that a simple ceiling function in the GPS device can be used to truncate values, so unless you dismount the device and check if such a function is computed therein, you could not conclude to a theory that space "discreteness" can be measured with such a device... Or just lay things down to a paper and send to Nature journal, you will see what reviewers say about this...

Regards,

Ale said...

can you study monthly and yearly stability? This can have important applications for collecting mushrooms in a scientific way

Arun said...

LOL!

Will that GPS locate my brain for me?

:)

Steven Colyer said...

@Steven: lol. You're theory of men and women differences is definitely hilarious, I can't stop laughing as it sounds so born from experience.

Experience? Yes, I live in a world of women, of all ages. Mother, aunts, sister, daughters, wife. But never enough experience as I practice fidelity, so most of what I know comes from books like Anatomy of Love by Helen Fisher and the vocabulary-challenging The Moral Animal by Robert Wright. Very enlightening books.

Uncle Al wrote: 1) A heavily used set of HP-15C batteries lasts about 25 years.

Yes, I suppose. Well I remember 1974 when the first portable scientific calculator, the $250 (then!) Texas Instruments SR-50 (the SR is for Slide Rule) was new. Hyperbolic functions, wow! Now I see battery power has improved tremendously. But I don't care how you slice it, real slide rules force you to recognize the importance of significant digits; calculators require you to understand their importance.

Hey, Uncle Al, I really love your writing style. Here is my pathetic attempt to emulate it, and don't be mad rather I hope you realize imitation is the sincerest form of flattery:

The squeaky wheel is the first to be replaced. God committed suicide when he saw Eve bite the apple. A snake in the grass is worth one dead bird if the bird lands on the ground to eat a worm.

How'd I do?

Bee said...

Jerome:

Yes, it's what we also thought, see post. I think we'll restrain from sending it to Nature ;-) Best,

B.

Bee said...

Hi Phil,

Don't worry, I've put Stefan to good use by having him change the curtains ;-) Best,

B.

Phil Warnell said...

Hi Bee,

Good move as in this case he doesn’t need exact coordinates, as its a case of relative position; that is to the interior of the windows . By the way I noticed Stefan hasn’t piped in here lately, I hope he hasn’t got lost:-)

Best,

Phil

Phil Warnell said...

Hi Stefan % Bee,

Just to be a little more serious, couldn’t Stefan’s data be more indicative of the action of a chaotic system as opposed to one where random action is present. That being the oval could represent the strange attractor and the readings further out the limit imposed within such a system. So perhaps this might have more to do with what Edward Lorenz discovered within his weather data rather then having space as necessarily disctere.

Best,

Phil

Bee said...

Phil,

If the GPS system was chaotic, you couldn't determine a position with it. You'd shift the measurement device by an inch and get a completely different result. The oval has nothing to do with attractors, it's a measure for the uncertainty in the data. Best,

B.

Phil Warnell said...

Hi Bee,

Thanks for that as it means I have some way to go before I actually grasp what is presented here. I understand with what would happen if you moved the device yet don’t find in your description that you had actually done that. Anyway time to study it a little more further and comment a little less:-)

Best,

Phil

Bee said...

Hi Phil,

Sorry, if the explanation was a little short. I assumed everybody knows what the GPS system is, or if not, they could Google for it. The device determines the position using signals received from several satellites. These satellites are not in stationary orbits. If you leave the measurement device on a fixed place on the surface of the Earth, the satellites' positions will change relative to the receiver. If you make repeated measurements over the course of several hours, the signal received will change, and also the available satellites will change. This has the effect that the result does not stay entirely fixed, it isn't always the same, but has a slight variation to it since the precision of the measurement is limited. What Stefan did was running the measurement over an extended period of time, and then computed the average value to see if one could improve the precision of the measurement by that. The average value is the yellow dot. The yellow circle is on a distance of one standard-deviation from the average. Wikipedia tells you what that means here. Best,

B.

Steven Colyer said...

Well, first, thanks Bee. You and Stefan are terrific teachers. I didn't know what auto-correlation was, now I do. I am also puzzled why the auto-correlation doesn't go to zero over time. Too many variables?

For example, what about the wobble of the Earth on its axis? That's fairly chaotic, yes, to back up Phil's point? Also, these geosynchronous satellites aren't "perfectly" geosynchronous, are they? There may be some wobble there as well. I don't know. Do they have attitude jets for course corrections?

Whatever, the whole cell phone system is great for teachers teaching Special Relativity. There's a hands on real life example of how SR is not only true, but useful (except in certain cases, like 2 preteens sitting next to each other in the backseat of a car texting each other, etc.).

So much for the TOE crackpots who trash Einstein.

Btw, does Stefan like the color of the curtains? Doesn't matter, only women care. Any man who thinks his input matters regarding color will soon find out what is about to hit the fan. :-P

Arun said...

NYT reviews a bad book on male/female brain differences.

http://www.nytimes.com/2010/03/28/books/review/Bazelon-t.html

cecil said...

Bee:
The GPS can provide precise location on the earth using commercial receivers. Note precise but not accurate. Military receivers are much more accurate. GPS commercial receivers used for surveying give very accurate relative positions.

I suspecct the periodicity you are seeing in the autocorrelation results is due to the orbital changes in the satellites. The accuracy of position not only depends on the satellite location but how many are visible.

Plato said...

Bread Crumbs

Since unit is always searching in relation to different satellites I had thought to question one of my work mates who spends time in the mountains snowmobiling.

Good history for where you've been and places you've stopped. How you get back. I thought how easy it is to get lost amongst the trees if you go over the tracks a lot, you can loose the trail.

I was a little shocked when another mate thought to show a video of him cutting a path along a mountain ridge and coming back, to only go back again.

The video recorded the avalanche behind him and soon you could see the slight valley between the riders and the mountain fill with snow, machines covered in the end.

Lucky to realize he is here to show the video. There have been many deaths this year.

But yes to navigating by the older methods, in terms of an "emf pulse"
but also understanding how the sun's geomagnetic effects contributes to the "possibility of electrical damage on power systems" and why SOHO plays an important role for an advance warning system.

Why HelioSeismology is very interesting to me.

Best,

Plato said...

Oh I forgot to mention that such gps measures are used for boating, air planes, as well as used in the trucking industry to keep track of the deliveries.

Have my own software program that uses tracking to detail where we are in location too.

Best,

teawithbuzz said...

This was fascinating. I have just started playing with a Garmin etrex Legend HCx and I have found the manual and the website to be singularly unhelpful. I spent 1.5 hours yesterday trying to get the GPS to connect properly to the computer! Apparently it is all my fault for having a Mac. I did finally connect, but have yet to successfully upload a "track." Maybe later today...?
In any case, I would rather figure out where my front door is than where the table on the back deck is. Or maybe where the large rock is. I KNOW where the table on the back deck is, and I could give you cartesian coordinates for it assuming the origin is my front door.
Anyway, thanks for the fun post!

stefan said...

Hi teawithbuzz,

I have found the manual and the website to be singularly unhelpful. I spent 1.5 hours yesterday trying to get the GPS to connect properly to the computer! Apparently it is all my fault for having a Mac.

... I can fully relate to that! Fortunately, we did have a Windows PC with a serial port at hand, so I could use the standard RS-232 cable and free software to download the GPX file with the track data from the GPS device. GPX is an ascii file in XML format, so I could copy that file to my Mac and do the data analysis there, with a small Perl script.

I haven't tried yet to upload track data onto to device.


Hi Cecil, Steven,

I suspect the periodicity you are seeing in the autocorrelation results is due to the orbital changes in the satellites.

Well, I am really not sure what to make of the autocorrelation function - maybe this "periodicity" is completely spurious. Perhaps I will repeat the experiment some time again for a longer period of data taking.

Anyway, the orbital period of the GPS satellites is a bit less than 12 hours (half a sideral day), so one could expect to find a trace of this period in the autocorrelation, by not much shorter time scales?



Hi ErkDemon, Jerome,


well, it seems there is rounding in the algorithm of the receiver. Actually, latitude and longitude of the measured track points in parts of degree yield points on a square lattice. This was quite a surprise to me, as I was expecting a smooth distribution of points over the plane, maybe with a Gaussian profile...

Thanks for the hint with the Jitter!

Actually, I had thought about moving around the receiver. But the I have given up this ideas, because I wasn't very keen to run around on the patio with the receiver in my hands for several hours ;-)...


Cheers, Stefan

Exl Blogger said...

Consumer GPS units take a number of shortcuts to provide timely, useful information in the face of varying conditions. The big one is position hysteresis. That is, the GPS assumes that it is only going to move so quickly. Even if it can only see one or two satellites, it still tries to produce a 3D position. Since I hike in forested, mountainous areas, I often find that my path out is tens of meters away from my path back though I have actually hiked the same trail. Continuity trumps accuracy. If your GPS doesn't move, artifacts of the varying satellite signals as they rise and set can make it look like your GPS has moved a bit as the actual measurement gets worse, then moved back as the measurement improves.

All GPS units quantize their results, but not for any sinister military reason. Originally, GPS satellites quantized time for the clear broadcast signal, but sent the complete time on encrypted channels. Clinton dropped this, so the signal you use is the same as the military gets. The reason your positions are quantized is because of the bit counters, the numerical analysis people. They looked at the data, looked at the algorithm and figured out how many bits were worth keeping. I don't even think the algorithm is done in floating point since early GPS units only had integer processors. Lower unit cost trumps higher precision.

Consumer units also cache the satellite position databases that the satellites slowly transmit along with their time signal. The GPS will use whatever consistent data it has to produce coordinates, even if it has to update them to compensate for new satellite data. Low first fix latency trumps accuracy.

Professional GPS units avoid these short cuts. It can take 10 or 20 minutes for your first fix. There's no output until they know where the satellites are. Professional units tend to have good, though sometimes bulky, antenna, so they catch more data, and they tend to use a more complex and computationally intensive position algorithm. The algorithm works by adaptive error minimization, so measurements accumulate to produce better results in static cases as with your table. Surveyors are willing to pay extra for accuracy.

Professionals also use differential GPS in which data from transmitters with known positions are combined for even better solutions. Consumer units don't let you configure for this.

It's an interesting field actually. GPS has had a big impact on navigation, though there is more that we'll see in the future. I remember one aviation conference where the big idea was pseudo-lights, radio transmitters so you could land aircraft by counting interference fringes. It would be like doing the Michelson-Morley experiment on the fly.

Plato said...

Exl Blogger: Even if it can only see one or two satellites, it still tries to produce a 3D position. Since I hike in forested, mountainous areas, I often find that my path out is tens of meters away from my path back though I have actually hiked the same trail. Continuity trumps accuracy.

Yes for sure, for safety sakes and for future explorers. Keeping aware of markers on one's own. Making Data points and keeping a good set of batteries.

My work mate mentioned the drain on color applications screens versus a standard screen? Also solar cell models?

Thanks for the info.

Plato said...
This comment has been removed by the author.
Plato said...

Nice.

Real-time satellite tracking

Phil Warnell said...

Hi Bee

Thanks for the explanation, yet my trouble doesn’t rest with not knowing how GPS works, as my story relating to my working as part of a survey crew as a teenager was meant to convey as except for using the time transmitted ( to calculated distance in respect to c) and satellites orbital position it boils down to triangulated positioning incorporating trigonometry So it’s not this I have trouble with or standard deviation, which is the qualifying part of any statistical data related analysis, yet what this Autocorrelation function is exactly and what significance it has in having you come to the conclusions regarding the nature of space. I recognize this as something I’ll have to work through .

Oh yes thanks also for that live Cern broadcast address in the side bar which I have on now. The beam has crashed twice yet now have it up again to 2,25 TEV waiting to get to 3.5 to then have them collide; cross your fingers

Best,

Phil

Phil Warnell said...

Hi Bee,

It's now at 3.5 TEV. I'm emembering that line from Ghost Busters about crossing the beams :-)

Best,

Phil

Phil Warnell said...

Hi Bee,

The beams have been aligned, collisions pending, we have contact,the Atlas has landed, awaiting data. A small crashing for a particle, a giant leap for Atlas and mankind!!!!!!!!!!!!!!!!!!!

Best,

Phil

Steven Colyer said...

Hey Stefan,

Thanks for getting back! We were worried you'd died of curtain asphyxiation or something. Glad to see you're fine, man. ;-)

What I get from this blog post in an offhand way, is, the importance of tabletop experimentation. I am particularly keeping in mind the upcoming Nordita conference that Bee will be running this summer. As you can see here, it's been on my mind, a lot. I wonder how many participants have considered value of "the third leg" of experimentation, rather than the first two which are the expensive astronomical satellites and super-expensive miles-long underground proton-smashers.

Which reminds me, today's THE day! Go LHC! Go CERN!

Science marches on, YES! Sweet!

Georg said...

Hi,

GARMIN hand-held receivers used to
have undocumented commands which allowed to download positions / velocities with higher resolution as well as pseudo range and carrier phase data. Antonio Tabernero Galan provides information and software on his web pages. It appears that the Etrex receivers feature these undocumented commands (in somewhat different form) as well.

Regards

Georg