Calculating the location of a robot geometrically My team is looking to provide a piece of code that locates a robot on an X/Y grid with ~cm precision. The robot is equipped with a camera/servo combination which is used to uniquely identify columns with known positions which sit outside of the board that the robot can move on. 
The robot (R) can determine the angles between itself and any post (A, B, C, etc) via computer vision and measurement of the servo value that rotates the camera. It cannot determine the distance from itself to any post, but it knows the location (and therefore distances, angles) between any posts. This is a priori knowledge of the board that is programmed into the robot.
For a single triangle formed by ABR, it does not seem to be intuitively possible to locate a robot, because only one angle (R), and one distance (AB) is known. Thinking that we could solve the problem by including more points, we tried including BCR. This seems to intuitively provide enough points to definitely locate a robot, but the math we have done does not point to a single answer. This could be due to real-world assumptions that we have not been able to put in an equation form. For example, the robot never leaves the board, therefore no solutions outside of that box on the grid are valid.


*

*How can I calculate the position of robot R, given locations A, B, C, etc?

*What is the minimum number of columns needed to locate the robot?

*Do the "real-world" assumptions mentioned above, need to be taken into account in order to successfully locate the robot?



 A: You only need two posts with known positions to determine the robot's position as long as the two posts and the robot are not collinear. But you can always prevent this from happening by placing the posts in such a way that the line connecting them doesn't intersect the robot's grid.
Once you have a pair of posts that aren't collinear with the robot's position, pick an origin and an $x$-axis and $y$-axis. Suppose you have post $A$ at $(x_A,y_A)$ and post $B$ at $(x_B,y_B)$ and let $\theta_A$ be the angle that the robot $R$ makes with post $A$ and $\theta_B$ be the angle that the robot $R$ makes with post $B$, each measured from the positive $x$ direction.
Then the slope of the line that passes through the robot and post $A$ is $m_{AR}=\tan(\theta_A)$ and the slope of the line that passes through the robot and post $B$ is $m_{BR}=\tan(\theta_B)$.
So we can find the equation of the line that passes through the robot and post $A$ using the point-slope formula as
$$
y=m_{AR}(x-x_A)+y_A
$$
and the equation of the line that passes through the robot and post $B$ as
$$
y=m_{BR}(x-x_B)+y_B.
$$
We wish to find the simultaneous solution to this system of equations, so we have
$$
m_{AR}(x-x_A)+y_A=m_{BR}(x-x_B)+y_B
$$
so that the $x$-coordinate of the robot's position is
$$
x=\frac{y_B-y_A+m_{AR}x_A-m_{BR}x_B}{m_{AR}-m_{BR}}.
$$
Then, substituting our $x$-coordinate back into the first equation, we find the $y$-coordinate of the robot's position is
$$
y=m_{AR}\left(\frac{y_B-y_A+m_{AR}x_A-m_{BR}x_B}{m_{AR}-m_{BR}}-x_A\right)+y_A.
$$
A: As caveat says, if you have a general position, then you need 4 columns. In the case that is shown in the picture, however, where the straight lines through A and B and through B and C do not cross the admissible area for the robot, three columns are enough. 
The reason is that in this case, B and C will always be seen 'from the same side'. This means that you know the angle you measure between the robot and the lines to B and C will always be such that you know it's orientation. In the picture, the angle CRB will always be positive, because the ray RC is 'to the right of' the ray RB.
If this is known, then the geometrical place which describes all the possible positions of the robot under which the points B and C are visible under the specific oriented angle you measured ($\alpha$) is part of a circle (shown green below). That circle goes through B and C, see the picture. 

It is only part of the circle, because in the remaining part you would see B and C under the angle of $180°-\alpha$ instead. If we didn't know about the orientation of the angle, then we would have to add the image of the green circle part when mirrored on line BC to our list of possible positions of the robot.
The same can of course be done with the angle you measured from R to A and B or from R to A and C. If you have 2 such circle parts and know their equations, you can calculate their points of intersection. Let's say you choose B,C and A,B. Because both circles go through B (which is impossible for the robot to be in), the only other possible point for the robot to be is the other point of intersection!
Now we need to determine the equation for the each circle. I'll do the math for B,C here. A circle's general equation is
$$(x-x_M)^2 + (y-y_M^2) = r^2,$$
where $(x_M,y_M)$ are the coordinates of the midpoint and $r$ is the radius of the circle. 
Let's start with the mid point M. Since the circle will always go through B and C, M will be located on the perpendicular bisector m of BC. You can calculate the midpoint X of B and C beforehand and also a unit vector ($u_m$) of the direction of m. Choose it in such a way that the unit vector points from X to the side in which the robot is. So we have now
$$x_M = x_X + t\cdot {u_m}_x, y_M = y_X + t\cdot {u_m}_y$$,
where $t$ is the (as of now) unknown length of XM.
If you remember some lessons about angles in a circle, you'll see that angle CMB is equal to $2\alpha$ and that angle CMX is again equal to $\alpha$. Finally, angle MCX is equal to $90°-\alpha$.
Since the length of CX is known (half the length of BC) we now get 
$$t={\rm length}(XM) =\tan(90°-\alpha)\cdot {\rm length}(CX) = \cot(\alpha)\cdot {\rm length}(CX)$$
If we put this into the above formula, we get finally values for the coordinates of our midpoint M!
I'll skip now on explaining why this formula stays correct even when we have an $\alpha > 90°$, where my above picture is no longer correct because then the midpoint M wanders to the other side of the line BC. But in this case our $\cot(\alpha)$ becomes negative and our calculated M also wanders to the other side of line BC.
So we now have the coordinates of our Midpoint M, we now only need the radius to get the complete equation. But the radius is the just the distance from any point on the circle to the midpoint, so just calculate the distance from M to B,C or R and you are good to go.
So where are we now? I have shown how to obtain the equation for the circle that contains the geometrical locus of all points under which 2 given points are to be seen under a given oriented angle.
Get 2 of those equations and determine the common points:
$$ (x-x_{M1})^2 + (y-y_{M1})^2  = r_1^2$$
$$ (x-x_{M2})^2 + (y-y_{M2})^2  = r_2^2$$
Take the difference of those 2 equations. All the quadratic terms in the unknown $x$ and $y$ will vanish, you are left with a linear equation. Transform that linear equation into the form $y=ax+b$ and plug it into on of the above equations for the circles. You will get a quadratic equation. One solution of it will be the common point that you choose for the angles (e.g, if you choose to use the angles between B,C and A,B, then B will be the common point). The other is the position of the robot

Now the above (as complicated as it is) is only the purely geometrical side of things. In reality, you will be confronted with
a) malfunctioning sensors that will, from time to time, produce just incorrect data, and
b) a limited accuracy of measurements.
Because of b) it is therefore much better not to just use the 3 columns that I said are necessary, but to use as many as possible/feasible. On top of these calculations you may need to do some calculation estimating how accurate your position is, taking into account the inaccuracy of the measurements.
For a), you may need to keep track of your calculated position and discard it if would show that you move 10cm in 1s when you can only move at have that speed, or somthing similar.
A: If the only measurement you can make is the angle form by 2 rays from the robots to 2 points, then 3 points are insufficient, but 4 is. This is due to a Mobius transformation of circle reflection $z\rightarrow 1/z$. Treat the plane as $\mathbb{C}$, with the unit circle at the origin to be the unique circle through 3 points (which exist unless 3 points are collinear, in which case line reflection show that there are 2 possible solutions). Then the circle reflection will fix all angle and the 3 points, while sending one solution to another. So with 3 points you can only pin down the possible position to 2 points. This should be enough if there are additional constraints (such as dead reckoning), but theoretically not sufficient.
So now let's say you assume there are 3 noncollinear points, and let $O$ be the center of the unique circle containing 3 points, then let $O$ be the origin and rescale your unit so that the circle is a unit circle, and assuming the robot always stay inside the circle. Let $a,b,c$ denote the position of $A,B,C$ treated as $\mathbb{R}^{2}$. Let $\alpha,\beta$ be the $\cos$ of angle $ARB,BRC$.
Now calculate $d=((a+b)/2)/\overline{(a+b)/2}$. Now solve for $t$ in $\alpha((a-td)\cdot d)^{2}=(a-td)\cdot(a-td)$ which is just quadratic, and make sure $t\leq 1$. This give $td$ the point $D$ such that $ADB$ is twice $ARB$. Do the same for $BC$ and $\beta$ to get $E$. Now intersect the circle centered at $D$ which contain $B$ with the circle centered at $E$ which contains $B$. They should intersect at $B$ and another point, which is what you need (find intersection of 2 circles you can look up the formula).
Of course, there are plenty of probably faster method, but this is the straightforward geometry way.
