Pathfinding Algorithm for Robot

Question

I have a robot that uses an optical mouse as a position track. Basically, as the robot moves it is able to track change in X and Y directions using the mouse. The mouse also tracks which direction you are moving - ie negative X or positive X. These values are summed into separate X and Y registers.

Now, the robot rotates in place and moves forward only. So the movement of the robot is ideally in straight lines (although the mouse tracking can pickup deviations if you veer off) at particular angles. A particular set of movements of the robot would be like:
A: Rotate 45 degrees, move 3 inches
B: Rotate 90 degrees, move 10 inches
C: Rotate -110 degrees, move 5 inches
D: Rotate 10 degrees, move 1 inch
But each time the mouse X and mouse Y registers give the real distances you moved in each direction.

Now, if I want to repeat the movement set going from A to D only, how can I do this using the information I have already gathered. I know I can basically sum all the angles and distances I feed into it already, but this would prove to be inaccurate if there were large errors in each movement orders. How can I use the raw information from my mouse? A friend provided an idea that I could continuously sine and cosine the mouse values and calculate the final vector but I'm not really sure how this would work.

The problem is that the mouse only gives relative readings so rotating or moving backwards, you are potentially erasing information. So yeah, what I am wondering is how you can implement the algorithm so it can continually track changes to give you a shortest path if you moved in zigzags to get there originally.

Answer 1

Not an answer to your question, but perhaps a cautionary tale... I did exactly this kind of robot as a school project a year back. It was an utter failure, though I learnt quite a bit while doing it. As for using the mouse for tracking how far you have driven: It did not work well for us at all, or any of the other groups. Probably because the camera in the mouse was out of focus due to the fact that we needed to have the mouse a few mm above the floor. The following year no group doing the same project used this methid. They instead put markings on the weels and used a simple ir-sensor to calculate how many revolutions the wheels made.

Answer 2

I think the basic algorithm you need to do is this:

currentX = currentY = 0;
heading = 0; // radians
while (true)
{
    deltas = SampleMouseDeltas();
    heading += deltas.Heading;
    currentX += Math.Cos(heading) * deltas.Distance;
    currentY += Math.Sin(heading) * deltas.Distance;
}

You are right in your idea that this won't be precise. It is called "dead reckoning" for a reason.

Where you can get your deltas.Heading based on the "X" coordinate (the formula will be (deltax in inches) / (mouse sensor distance in inches from center of rotation). Also, the deltas.Distance would come from the "Y" sensor, after you convert it from pixels to inches.

Then to perform the steps, you could do something like:

robot.RotateLeft();
heading = 0;
while (heading < 45 degrees)
    heading += SampleMouseDeltas.Heading;
robot.StopRotateLeft();

... etc ...

Answer 3

I know I'm somewhat necroing this thread, but if you wanted more accurate angle tracking, two optical mice would be ideal. Basically if you cancelled out the motion in the same direction, you would be left with the motion that the mice made relative to eachother. From there, it would just be some simple math to accurately determine how far the 'bot has turned.