Pose Estimation

From Team 449 Wiki

This page details the derivation of the algorithm we use to draw profiles. It finds the next position of a 2-sided tank drive given the past position and the distance traveled by each wheel since that position. It assumes velocity was constant on that interval. In this description I'll be referring to each interval as a "tic."

Explanation

For the sake of these calculations, we treat the tank-drive robot as two wheels along an axis (corresponding to the center of the robot). During each tic, we assume the robot can be doing one of three things: driving in a straight line, turning along some circle, or standing still. The approximation of circular movement is convenient; it is easy to calculate and (assuming constant velocity) accurately accounts for robot movement with errors on the order of O(x^3).

If the robot is standing still, the next position is the same as the current position. If it's driving in a straight line, we just move its position in the direction it's facing by the measured distance moved. However, if it's turning, things get a bit more complicated. The robot is turning some angle around some point. We know that point must be in a line with the two wheels, but we don't know how far away it is (it can be between the wheels). The point it's turning around is known as the Instantaneous Center of Curvature, or ICC.

Variables

Diagram with labels showing the variables

<math>\phi</math> is the robot's previous heading (i.e. what angle it was pointed at at the beginning of the tic). Note that for the purpose of this article, all angles will be positive counterclockwise from the x-axis. If you are implementing this on a system that follows the opposite convention, simply swap "right" and "left" for all the math that follows.

<math>T</math> is the distance between the wheels

<math>D_{L}</math> is the distance traveled by the left wheel this tic

<math>D_{R}</math> is the distance traveled by the right wheel this tic

<math>r</math> is the radius of the circle the robot is turning on

<math>\theta</math> is the angle the robot is turning around that circle

Finding the Sector

First, we'll find the <math>r</math> and <math>\theta</math> that describe the sector traced out by the robot's path. First, we can find theta. The radius of the circle which the left side is following is <math>r-\frac{T}{2}</math>, and the radius of the circle the right side is following is <math>r+\frac{T}{2}</math>. So:

<math>D_L=(r-\frac{T}{2})\theta</math>
<math>D_R=(r+\frac{T}{2})\theta</math>
<math>D_R=\left((r-\frac{T}{2})+T\right)\theta</math>
<math>=(r-\frac{T}{2})\theta+T\theta</math>
<math>=D_L+T\theta</math>
<math>D_R-D_L=T\theta</math>
<math>\frac{D_R-D_L}{T}=\theta</math>

Determining <math>r</math> is a bit trickier. Something to note here is that if <math>\theta</math> is 0, the sector is actually just a rectangle so <math>r</math> is infinity. We ignore that case because it's easy enough to handle separately (the robot's just driving straight). The formula is

<math>r=\frac{T}{2} \cdot \frac{D_{R}+D_{L}}{D_{R}-D_{L}}</math>

To derive this formula, start with the observation that the ratio between the distances <math>(\frac{D_{R}}{D_{L}})</math> is equal to the ratio between the radii <math>(\frac{r+\frac{T}{2}}{r-\frac{T}{2}})</math>. To get this, simply divide the second equation in the previous derivation by the first. Then, solve for <math>r</math>:

<math>\frac{D_{R}}{D_{L}}=\frac{r+\frac{T}{2}}{r-\frac{T}{2}}</math>
<math>\frac{D_{R}}{D_{L}} \cdot (r-\frac{T}{2}) = r+\frac{T}{2}</math>
<math>\frac{D_{R}}{D_{L}} \cdot r - \frac{D_{R}}{D_{L}} \cdot \frac{T}{2} = r+\frac{T}{2}</math>
<math>\frac{D_{R}}{D_{L}} \cdot r - r = \frac{T}{2} + \frac{D_{R}}{D_{L}} \cdot \frac{T}{2}</math>
<math>r(\frac{D_{R}}{D_{L}} - 1) = \frac{T}{2}(\frac{D_{R}}{D_{L}} + 1)</math>
<math>r = \frac{T}{2} \cdot \frac{\frac{D_{R}}{D_{L}} + 1}{\frac{D_{R}}{D_{L}} - 1}</math>
<math>r = \frac{T}{2} \cdot \frac{\frac{D_{R} + D_{L}}{D_{L}}}{\frac{D_{R} - D_{L}}{D_{L}}}</math>
<math>r=\frac{T}{2} \cdot \frac{D_{R}+D_{L}}{D_{R}-D_{L}}</math>

Finding the Vector

A diagram of the sector with the vector (blue) overlaid

Next, we want to turn the sector we found into a change in Cartesian coordinate values. To do this, we'll draw a vector pointing from the center of the where the robot was last tic to where it is now. We'll call this vector <math>\vec{a}</math>, and call the angle between it and the X-axis <math>\alpha</math>. To find <math>\left\|\vec{a}\right\|</math> (the magnitude or length of <math>\vec{a}</math>) and <math>\alpha</math>, we can draw an isosceles triangle with legs of length <math>r</math> and a base of length <math>\left\|\vec{a}\right\|</math>, with a vertex angle of <math>\theta</math> and therefore base angles of <math>\frac{\pi-\theta}{2}</math>, as shown in the diagram. Knowing everything about this triangle, we can then see that <math>\alpha=(\frac{\pi}{2}+\phi)-(\frac{\pi-\theta}{2})=\phi+\frac{\theta}{2}</math> because we take the angle between <math>\vec{a}</math> and the line connecting the robot's wheels last tic <math>(\frac{\pi-\theta}{2})</math>, and subtract this from the angle between that line and the X-axis <math>(\frac{\pi}{2}+\phi)</math>, yielding the angle between <math>\vec{a}</math> and the X-axis. Note that this is equivalent to simply taking the average of the current and previous robot headings.

Finding <math>\left\|\vec{a}\right\|</math> is even easier because we can just use Law of Sines:

<math>\frac{r}{\sin(\frac{\pi-\theta}{2})}=\frac{\left\|\vec{a}\right\|}{\sin \theta}</math>
<math>\left\|\vec{a}\right\|=r \cdot \frac{\sin \theta}{\sin(\frac{\pi-\theta}{2})}=r\cdot\frac{\sin{\theta}}{\cos{\frac{\theta}{2}}}=2\cdot r\cdot\sin{\frac{\theta}{2}}</math> (note that this can also be seen directly by bisecting <math>\theta</math> and considering the resulting right triangle)

Now all we have to do is turn this vector into a change in Cartesian coordinates, which we can do by splitting <math>\vec{a}</math> into it component vectors. In order to find the vectors for the left and right wheels, replace <math>r</math> with <math>r+\frac{T}{2}</math> and <math>r-\frac{T}{2}</math> respectively.

Practical Implementation

In practice, encoder measurements are not perfectly reliable indicators of robot movement: wheels can slip, such as during hard acceleration or a collision, de-coupling the measured wheel movement from the actual movement of the robot. For this reason, pose estimation works best when the robot is moving in a smooth, well-controlled manner, such as during autonomous (especially when following motion profiles that have been chosen to limit slip-causing factors such as jerk and acceleration).

Even under relatively ideal conditions, however, tank drives inevitably experience some degree of slippage due to "wheel scrub" during turns. In practical terms, this leads to the calculated value of <math>\theta</math> ending up somewhat larger than actual angular change of the robot.

A "first-order" correction for this problem can be achieved by substituting an inflated, "effective" value of <math>T</math> for the actual geometrical value, thus operating under the assumption that the effect of wheel scrub is to decrease <math>\theta</math> by some constant factor relative to the theoretical value. In order to determine a suitable "effective" value of <math>T</math>, rather than measuring the robot, one can run a motion-profile that spins the robot in place with each side of the drive moving a known distance, and measure the resulting angular change; <math>T</math> can then be back-calculated from the equations above. Repeating the test for a variety of distances and averaging the results may yield a better value.

While this correction works reasonably well given slow, well-controlled conditions, it is still highly imperfect. A better solution involves the use of a gyroscope to directly measure <math>\theta</math>. The simplest implementation is to simply neglect to calculate <math>\theta</math> from the encoders, and instead directly use the measured value from the gyro. The encoders are thus used only to determine the value of <math>r</math>; assuming that wheel scrub contributes only to angular error, and not to translational error, we instead calculate <math>r=\frac{D_{R}+D_{L}}{2\theta}</math>. Note that no value of <math>T</math> is needed at all for this method.

More complex solutions may involve fusing gyro and encoder estimates for <math>\theta</math> in more rigorous ways, such as through a Kalman filter.