Thursday, April 15, 2010

The Algorithm - 9 days left

I just realized I only have nine days to finish this project. *gulp*

Have to give some statement of the project next Tuesday -- so I should know if it's possible to finish by then.
(I am also working on this project for an IEEE sponsored competition on campus.. more details later. Flying under the radar in case of failiure :) )

Anyway - I drafted up my navigation algorithm at a high-level today on paper.

I did not consult any external resources to figure out this problem. I wanted to independently come up with a solution to this problem - and see if it might work. Future revisions might use commonly known algorithms - but for now maybe my thoughts will work.

At the highest level here is my algorithm for routing:

Given latitude / longitude as x, y:

You need two initial points:
Start: x1, y1
Finish: Xf, Yf

Based on the start - you move some distance, and sample the position.
This third location will be Xc, Yc (c is for current).

Based on x1, y1 and Xf, Yf, you can obtain the exact latitude and longitude of travel required.
The latitude X and longitude Y must be traveled to get from x1, y1 to Xf, Yf.

X, Y will always be the distance from your current position, to the final position Xf, Yf.

So the high level algorithm:

Starting at x1, y1 calculate the latitude (X) and longitude (Y) to the destination Xf, Yf.
Storing X, Y -> move some distance and acquire a new Xc, Yc.
Based on the new distances to destination X, Y -> calculate how much closer you are to the target.

You should move proportional to the initial X, Y ratio. If your unit of movement is greater than or less than the initially calculated ratio, you will need to steer to correct. (If you traveled too far in latitude, you want to travel less the next move -> so you will turn in the direction of longitude, etc.)

I am sure this is confusing to understand - it's hard to dump the thought. Once I have some code, I will post it.

In summary - based on the proportion of lat/lng traveled and the proportion from a previously known location to the target -> you can keep the car on course.

This will certainly lead to over corrections -> however steering can be based on the magnitude in difference of proportion. Hopefully I can retrofit the servo to control steering so that there are varying levels of left/right not just ON/OFF LEFT/RIGHT as it is out of the box.

Alright - that's all for now.. maybe I can take a photo of my notepad later!

Edit: Photo of notes added! I wrote this sitting outside in the nice weather today -- the bottom curvy line over the straight line is behavior I expect (in the best-case).

No comments:

Post a Comment