GPSD has a serious bug somewhere in its error modeling. What it effects is position-error estimates GPSD computes for GPSes that don’t compute them internally themselves and report them on the wire. The code produces plausible-looking error estimates, but they lack a symmetry property that they should have to be correct.
I need a couple of hours of help from an applied statistician who can read C and has experience using covariance-matrix methods for error estimation. Direct interest in GPS and geodesy would be a plus.
I don’t think this is a large problem, but it’s just a little beyond my competence. I probably know enough statistics and matrix algebra to understand the fix, but I don’t know enough to find it myself.
Hundreds of millions of Google Maps users might have reason to grateful to anyone who helps out here.
UPDATE: Problem solved, see next post.
My friend Gerry says you should post this to the gpsd-dev list, along with a pointer to the code, and he’ll nab it from there and take a look at it. These days, he does covariant-matrix methods for a living at NOAA.A.
He also says that, if you do it right, the error is not symmetric.
I might meet your qualifications, I have a PhD in Operations Research, and I write photogrammetric software professionally, including propagation of sensor error into ground space, which is all about covariance matrices.
>I might meet your qualifications
Excellent. I’ll write up a detailed description and send it to you.
Cool, you’ve got my email. I hope I can do what’s needed!
“affects”…
So, ESR is relying on unpaid developers (if and when they can) to help out with bugs in GPSD. Google is relying on ESR because Android uses GPSD.
So, users relying on Android are relying on someone who knows C and statistics *and* happens to be reading this obscure blog right now, *and* is willing and has time to help.
Isn’t open source great?
PS: And no, Google doesn’t have to send developers to help. In fact, I doubt they know about the bug in question at all. The reason they use GPSD instead of a home-grown solution is because they don’t want to deal with stuff like this. It’s the same reasoning as with subcontracting. But if they had subcontracted their GPS daemon to a real corporation, they would have a working GPS daemon now.
>But if they had subcontracted their GPS daemon to a real corporation, they would have a working GPS daemon now.
They have a working GPS daemon now. The bug is in the computation of error estimates when the device doesn’t supply them, not in the return of the primary time/location/velocity data. If it caused serious problems it would have been noticed long ago.
Your comment assumes that a “real corporation” would, absent GPSD’s existence, have built something as good as GPSD. I think this is highly unlikely, for several reasons.
1. Corporations generally will not budget for the kind and depth of testing I’ve built around GPSD. For this and other reasons, I would expect the defect rate of a proprietary GPSD equivalent to be orders of magnitude higher. (There are plenty of empirical comparisons of defect rates to back this up.)
2. In the corporate world, the incentive for one of GPSD’s most important features – on-the-fly autoconfiguration to every GPS reporting protocol in existence at any baud rate and stop bit combination – wouldn’t exist. They’d pick some narrow set of preferred types – probably just one – putting downstream constraints on design that systems integrators deploying GPSD never have to think about.
3. The corporate world doesn’t have me. Category-killers like GPSD don’t generally arise from throwing lots of ordinary software engineers at a problem; you need a really capable systems architect with experience and boldness of vision. Those are not common to begin with, and the corporate environment rarely allows them to flourish. These days, J. Random Megacorp would probably be trying to fire my expensive 56-year old ass so they could “save money” by replacing me with a trainee from Bangalore. Do you suffer from any delusion that GPSD could have been designed by that guy?
No. Google’s hypothetical proprietary alternative to GPSD wouldn’t be GPSD done better – given GPSD’s historical defect rate that’s barely even statistically possible. It would be mediocre, crappy, and brittle, designed by committee, with a defect rate that embarrassed them when they allowed themselves to notice it.
(and before someone says proprietary software has bugs too, sure, but the company has to fix them, they don’t tell you “just wait till someone who knows C and statistics happens to pass by my obscure blog”)
>“just wait till someone who knows C and statistics happens to pass by my obscure blog”
That point deserved a separate reply.
Obscure? My blog? Back when N.Z. Bear was keeping statistics it showed up respectably among the top 300 in the world – and my readership has increased a lot since (thanks in part to G+). Among blogs with a programmer audience its rank is probably much higher than that; I’d be surprised if it’s not in the top 100 and not very surprised if it’s in the top 20.
The odds that someone would turn up with the right expertise are correspondingly high. And, in fact, someone has.
You’re assuming the bug a) affects them at all (consider whether or not the GPS device used computes its own error estimates), b) is significant in their use (they may not care about the error estimate, or use it for anything critical), and c) is one a corporation could fix (they may well not have a statistician that speaks C on staff).
Further. you’re ignoring social network effects. Eric’s call for assistance is much more likely to turn up someone that can help, once passed around among interested people, than a corporation’s abilities, simply because a closed-source corporation is not going to disclose the nature of the bug in the first place until it’s fixed.
@ESR
What’s the rough likelihood that any given GPSD user is going to own a GPS that doesn’t produce position error estimates? If you exclude both cheap&nasty and old hardware does this likelihood reduce to basically zero?
Because I add (for completedness reasons) that history has ample evidence that this likelihood correlates well with the likelihood of a proprietary shop would care enough to actually design and release a fix, instead of say redefining their supported hardware to exclude these “clearly defective” GPSes. Even assuming they had every other detail the same.
For the peanut gallery’s benefit, since ESR basically taught this and i highly doubt kurkosdr cares, one of the big draws for open source software is that fixes that make no financial sense for the original proprietor can still happen so long as they make sense to someone with either the skill or the money to hire. Kurkosdr’s statement “but the company has to fix them” has no basis in historical fact. The company is well within its rights to say “sorry you’re out of luck” if they see no possible ROI on the fix.
>What’s the rough likelihood that any given GPSD user is going to own a GPS that doesn’t produce position error estimates?
The problem isn’t that it’s common to ship no error estimates. It’s that NNEA and most other reporting protocols do not in general expose the complete set that is computed internally.
Notably, it’s normal to get only an hdop which is the radius of a 95% confidence circle (combining x and y errors) and a vdop which is z-axis error. And in some cases (like Garmmins) the manufacturer doesn’t document the circular error probability associated with the hdop – Garmin’s is believed to be 50% rather than 95%, so you have to scale it.
What you really want in order to do 3D kinematics properly is xdop/ydop/zdop, plus the 2D circular error (hdop) and 95% and a 3D spherical error (all at the same 95% confidence).
GPSD’s policy is to trust whatever error bounds it can get from the device and pass them through, then compute the others from a covariance matrix of the satellite skyview. It’s that computation that may be buggy.
“3. The corporate world doesn’t have me.”
Uhm. Eric. Those who are uninformed about your abilities might take this as a series display of egotism…
>Uhm. Eric. Those who are uninformed about your abilities might take this as a series display of egotism…
Indeed that is so. But what would people that ignorant about me be doing on this blog?
Seriously, though. That paragraph wasn’t really about my individual abilities, it was about the shortage of competent senior architects and the troubles they have in a corporate setting. How many people have you known who could combine cutting-edge engineering (like the self-configuration stuff) with the ability to drive defect rates as low is GPSD’s are?
I don’t by any means think I am unique in this. But when I try to estimate the number of people with that competence, relative to the amount of software out there where errors could have catastrophic consequences, I get a crawly feeling between my shoulder blades. I just hope we stay lucky until we get AI strong enough to solve the general problem…
“The company is well within its rights to say “sorry you’re out of luck” if they see no possible ROI on the fix.”
In fairness, this happens in the open source world, too. After all, OpenOffice users have been waiting over 12 years for Normal View…
> and before someone says proprietary software has bugs too, sure, but the company has to fix them, they don’t tell you “just wait till someone who knows C and statistics happens to pass by my obscure blog”
Just to point that it might be not a bug, if its true that error estimates doesn’t need to be symmetric, just a lack of (technical) documentation.
@kurkosdr:
I believe that you are confusing two different, though related, issues. Open vs. closed, and unpaid vs. paid development.
As somebody who works in the “enterprise-y” software space, I can say with some confidence that the likelihood that a bug gets fixed is directly related to the amount of revenue associated with fixing it. In fact, it doesn’t even have to be a bug in order for it to get “fixed”.
Assuming that Google had decided to pay for a commercial GPSD-alternative, how much do you think that they would be willing to pay? Maybe 50k? Assuming that’s the case, why would they want to shell out more money for a new version with this issue addressed? If they aren’t going to pay for a new version, the original implementer wouldn’t have any reason to address this issue. How many people actually care about this particular issue? Not that many. How many would be willing to buy a new phone or a different device in order to address this issue? Not that many. In fact, you can measure the market share by looking at Google Play Apps for the number of GPS applications which sell and explicitly advertise as having addressed this issue, and then multiply the cost times the number of licenses sold. I’ll wait.
As a side note, I’d point out that non-bugs are also fixed if you pay enough money. On at least one of the projects I’ve worked on, we spent a good deal of effort on our architecture to work around the fact that the SunOS implementation of NFSv2 readdir didn’t follow the spec. Readdir cookies were supposed to be opaque. However, in a couple of cases we found that the client would silently zero-out the high bit (probably due to storage in a signed 32-bit int). Pointing out that the client was defective wouldn’t help our sales if a competitor’s products worked. We were paid to solve a problem, not to do it “right”. A similar issue resulted in another client misbehaving if the “opaque” cookies ever decreased in value when interpreted as integers.
Eric –
This is well beyond my skillset, but I’ve put the word out to my friends in the Math Department here at work. If anyone thinks they want to take a whack at it, I’ll “introduce” you and them via email.
– JDB
@kurkosdr, I’m not sure if you’re trolling or not (if you are, it was a subtle and succecssful troll).
If you’re not, consider: I’m currently awaiting a fix for a memory leak in the (proprietary, closed-source) software running on a device that is licensed from a well-known manufacturer of industrial control equipment. The expected timeframe is somewhere between “eventually, if we feel like it” and “you’ve already paid us, so sod off.” If I were a betting man, I’d bet on the latter.
Open Source would in fact be grand, here. As a side project I’m investigating the feasibility of porting a good FOSS implementation of Scheme to the device, so we can at least avoid most of the unpleasantness of dealing with their tech stack.
Eric:
I don’t have the skills to work on this one, but it sounds interesting. I am putting it a request for a summary of the outcome — or at least a pointer to a mailing list thread of what you found and what you did about it.
Thanks in advance,
Jim
I can’t help but think. Shouldn’t HDOP be three numbers, ?_x, ?_y and ?_x,y?
And then VDOP is another number, plus correlation between z-error and horizontal error?
Of course, you can’t forget velocity. That makes 18 separate numbers. Oi.
>That makes 18 separate numbers.
14. x, y and z components of position (x and y are lon and lat). x, y, and z components of velocity. 95% error bounds for position x, y, z. 95% error bounds for velocity x, y, z. Time, and 95% confidence time error.
If you want correlations, keep a history and do time series analysis in the client.
I suspect a hypothetical proprietary GPSD would simply report that the error estimates are not available and you should get a better device, rather than attempting to calculate them itself.