Can triangulation by measuring angles to 3 beacons to find location work over a large outdoor area

Question

To determine an outdoor location I think that I need to measure the angles between at least 3 beacons and take into account the order I sweep the beacons. Is this a workable solution to get positional accuracy of about 30cm in a house block sized area?

Rewrite of question, note no distance measurement is suggested only angle measurements. I am proposing that it might be possible to have a minimum of 3 local rf beacons and a robot device that sweeps an antenna through a circle identifying the angles between these beacons and to use this information and the order that the beacons are seen to find an absolute location. I tried to prove this geometrically and it seems that with the 3 beacons there is 2 unique solutions without knowing the order and 1 solution if the order is known. There would (I believe) be no need to try to find the distance to the beacons. My question is, could this be implemented for a reasonable cost with some nRF24L01 based transcievers and some sort of rotating antenna?

Answer 1

The theoretical answer is: yes. The pragmatic answer is: no.

If you know the location (xyz coordinate) of the three beacons in your inertial (fixed) reference frame, then all that is needed to determine the location of the device you would like to track is the straight-line distance from your device to each of the three beacons. More correctly, the distance information would narrow down the position of your device to exactly two locations.

Depending on the transmission technology of your beacons (RF, sonar, light), and the surrounding environment, it may or may not be practical to calculate the straight-line distance.

It is difficult with both sonar and RF to get reliable distance calculations because of reflections from the surrounding environment. Distance calculations using time-of-flight are very reliable and accurate. However, you need line-of-sight.

Take a look at this technology. It is the closest that I have encountered for practical location over a large area: http://www.ubisense.net/en/

Answer 2

You haven't said whether you need 2D or 3D positioning, but if you have only 3 beacons you will need to stick to 2D. Let's assume you know the XY position of the beacons and that the robot's sensor and the beacon emitters are at about the same height.

Geometrically, yes it can be done, with some limitations. Take a pair of beacons B1 and B2; suppose your robot sees them as A12 degrees apart. Now imagine that the beacons are pins stuck in a corkboard, and you have a cardboard triangle with one corner A12 degrees wide. You can press the cardboard between the pins and rotate while keeping the triangle edges against the pins. - marking where the point lies. Interestingly, this forms a circular arc between the pins (actually two arcs, forward and backward.

Now conceptually draw the equivalent with B2 and B3 and angle B23 - more circular arcs, which will intersect. And for good measure use B3 and B1 and angle B31 - it doesn't really give you more information, but it acts as an error check.

You'll find a few places where these arcs intersect. You can reduce the ambiguities using the order of the beacons as you scan (eg: clockwise sequence).

Besides the ambiguities, sometimes the arcs intersect close to right angles and give a sharp intersction point, but other times they are closer to tangent with each other which means that small errors in the angle result in large errors in position.

However, your proposed implementation is not going to work very well. The antennas for a nRF24L01 are not going to give a very sharp directionality. The patterns will almost certainly have multiple irregular but somewhat broad lobes that give you only a very loose sense of direction with additional ambiguities - and multipath reception will make that worse. If there are any obstacles that absorb RF, that will make it worse.

If you have unobstructed line of sight, you could do better with optical sensors - that's the appoach I've played with, on paper. Actually my original inspiration was how to tell where a photo was taken if it shows several towers on hillsides. If you can determine the location of each tower, and you can calibrate the camera's pixels with angles, then this becomes the same problem as you raise - but with far better angular resolution.

For robotics in a smaller space, you could use visible or infrared emitters and a camera on the robot; there is some complication in spinning the camera and combining several less-than-360 degree views to get large angles, but the geometry issue is the same.

And if you have more than 3 beacons, you can improve your accuracy: they are less likely to all be obscured, some combinations will more likely have good intersection angles, you can remove many of the ambiguities, and you can average multiple solutions using different triplets to reduce the errors.

I recall working out the circular arcs traced by the tip of the triangle algebraically some while ago (I was expecting something more complex and loved that it came out so beautifully simple), but I don't have that proof handy and would have to recreate it. However if you know that the location arc is circular, it's easy to compute the center and radius of the arcs from the location of two beacons and the angle between them.

Answer 3

There's a lovely theorem in mathematics: given three points $A, B, C$ on a circle, the angle $BAC$ subtended at $A$ by the arc $BC$ is exactly half the angle subtended by the arc $BC$ from the circle's center (i.e., the "angle between $B$ and $C$, as seen from the circle center").

Thus as @Zeph observes, knowing the angle between any pair of towers places you on a circle of a particular radius that contains these towers at a certain angular distance from each other on the circle... but there are two such circles. If you know the signed angle (i.e., "As I sweep counterclockwise, I see $B$ and then $C$, with the angle between them less than 180"), then you actually know which of the two circles you're on.

If you look in Bowditch's American Practical Navigator, you'll find that this technique has been known for some time. (Closely related: "doubling the angle on the bow").

The sensitivity of the computed position to angular noise is not pretty. If your three towers are very far apart (hundreds of miles), but distributed at 120 degrees angles around the center of your region of interest, then the angles measured from any point in your region will be very close to 120...so determining the exact location will be tough. If, at the other extreme, your three beacons are very near the center of your region, then the three angles will again tend to be almost equal from all points of view, so the computed position will be very sensitive to angle again. In the ideal case -- which is probably to have the beacons placed on a circle that's perhaps twice the size of your region of interest -- you can probably do OK...but you'll do hugely better if you put 15 beacons out there, and use something like a Kalman filter to update your position estimate at each moment. Greg Welch at UNC did something like this for tracking in virtual reality systems, back in about 1991 or 1992, I believe, but I could be off by a year or two.