================================================
Programmers note for the Line Follower Simulator
http://ostan.cz/LineFollowerSimulator/
================================================
Ondřej Staněk,
published 18.8.2010
The guideline is represented by an GeneralPath object from java.awt.geom package. Generally, this object holds straight lines, quadratic and cubic (Bézier) curves. Theoretically, every GeneralPath object can represent the line that is up to be followed by the model of the robot.
The model of the robot contains a line segment representing its sensor module. This sensor module is capable to distinguish the line position, i.e. the distance of a line from the centre of the sensor module (of course only just in case there is a line underneath). With respect to our model, we need to calculate intersection between the curve held in GeneralPath object (the path) and between a line segment (the sensor module). The line segment is actually an instance of Line2D class from the java.awt.geom package.
And here is the job for the BezierIntersection static class. This class has implemented a GetIntersection method, that takes GeneralPath and Line2D as arguments and returns all their intersections (as an arrayList of Point2D).
Java doesn’t provide any class for such operation, so I had to program the BezierIntersection class by myself. It is not trivial to calculate intersection points of a bezier curve and a line segment. In fact, there is deep mathematical background behind that. Now I will briefly describe the magic:
Each Bezier curve in a plane is uniquely determined by its four control points. If you transform these points, you also transform the curve. And these control points uniquely determine parametric equation for the Cubic curve. Let’s have a two-dimensional plane with a Bezier curve and a line. We can transform coordinates so that the line will be equal to the x axis. Now we take parametric equation for the transformed Bezier curve. The control points of the curve are related to the coefficients of a polynomial in the Bernstein basis, which is the parametric equation for Bezier curve. After finding the roots of the polynomial, we can return back to original parametric equation describing the non-transformed cubic curve and calculate intersection points. So, that’s all the magic! More on this topic on http://www.groupsrv.com/computers/about179364.html
So far there is only support for intersections with Bezier curves in my BezierIntersection class. As a result, if the GeneralPath object contains geometric elements other than Bezier curves, an exception will be thrown. Nevertheless, it is not difficult to implement intersection with other elements such as lines and quadratic curves.
An animation thread does the discrete (step-by-step) simulation of the robot movement. The animation framerate is set to 50Hz. That means each 20ms the speed of robots’ wheels is evaluated and robot moves a bit.
Apart from the animation thread, the robot runs its own thread that evaluates the line position and adjusts speeds of its motors in accordance with its PID regulator. This frequency can be adjusted in the GUI of the application. It is set to 30Hz by default. However, the changes in speed of a motor don’t manifest immediately. There is an “Acceleration” parameter that describes how quickly the motors will react to changes in speed.
In case the line is lost (there is no line under the sensor module, eg. the line segment doesn't cross the curve), the robot stops one of its wheels while the second keeps turning, so that the robot rotates in direction where the line was seen last.
About PID regulation from Wikipedia:
The PID controller calculation (algorithm) involves three separate parameters, and is accordingly sometimes called three-term control: the proportional, the integral and derivative values, denoted P, I, and D. The proportional value determines the reaction to the current error, the integral value determines the reaction based on the sum of recent errors, and the derivative value determines the reaction based on the rate at which the error has been changing. The weighted sum of these three actions is used to adjust the process via a control element such as the position of a control valve or the power supply of a heating element. Heuristically, these values can be interpreted in terms of time: P depends on the present error, I on the accumulation of past errors, and D is a prediction of future errors, based on current rate of change.
By tuning the three constants in the PID controller algorithm, the controller can provide control action designed for specific process requirements. The response of the controller can be described in terms of the responsiveness of the controller to an error, the degree to which the controller overshoots the setpoint and the degree of system oscillation.
More on this topic on http://en.wikipedia.org/wiki/PID_controller