Introduction to PID Algorithms

Introduction:

Often times in robotics, you want to have your robot reach a desired sensor point, whether it is driving to a certain distance, or keeping an arm at a certain height. Let's assume that you want your robot to autonomously drive N meters. To accomplish this, one may run motors for a specific time in order to reach that desired place. However, there is too much variation on things like how much battery the robot has at the time, or the state of the motors, or the surface of contact with the drive, momentum and inertia, and more. Usually, if you have tried this method, you might have noticed that the robot goes over the desired distance (called "overshooting"). So, now let's assume you have attached an encoder to the chassis to measure the amount of degrees that have occurred since the beginning of movement. In the code, the robot moves forward until the encoder reads the goal sensor value. This method is better than not using any sensor, yet still causes overshooting because of the aforementioned physical limitations. The solution? A feedback loop that constantly changes the power of the drive motors.

P, I and D

There are 3 components to a PID controller. P, I and D respectively, stand for Proportional, Integral, and Derivative. In basic calculus, integral is just the area under a curve of some function, and derivative is the slope at a specific point on the graph of a function. The function that we work with in PID is called the error value, that, every iteration loop in the algorithm, updates itself to the new error value. The error value is a function that takes time as an input, and returns the setpoint minus the current sensor value, given by:
 .
With that established, let's dive into the proportional term (P). Proportional term is just taking the error value, and multiplying it by some constant (to weight it properly with the other three terms; this is how PID works fundamentally), so it would look something like this:
 ,
where kP is a nonzero floating point number.
Intuitively, as the P term increases, the further the robot has to move to get to the point, and as the P term decreases, the closer it is to the setpoint. You could technically just use a P controller without any I or D, but it would oscillate from overshooting to undershooting the goal sensor value, because we did not add any fine tuning with integrals or derivatives.
Now, lets get into the integral term (I). Integral is the area of the graph of the error function of t versus e(t). Mathematically,

where kI is another non zero constant. Intuitively, the integral term increases as the past errors made sum up to a significant amount.
Finally, lets see the derivative term. Again, it is multiplied by some kD constant, but this time it calculates the current slope of the error graph. The expression is as such:
.
Intuitively, the derivative term calculates the future possible error values! The slope can predict what the motor needed maybe three seconds into the future.

Putting It All Together:

Now that we have each individual term, we can establish a single function that sums up our very simple algorithm:
.
So our actual code will have to calculate the error value, and integral and derivative terms, and constantly set that value to the motor.
Finally, one of the hardest things of PID is tuning the constants so that your robot properly reaches it's setpoint. This may take hours, but there are some well known techniques to help you tune (like the Ziegler-Nichols Method).

ArrayList vs LinkedList

This is a simple performance test of arraylists vs linkedlists in the JCF. Linked lists' elements always have the previous element's position in memory's reference, and the next as well. Insertion yields O(1) time, while accessing yields O(n) time.