Open source library to save path

[aviplot]

Hi,
I'm trying to build a cleaning robot. (like 'Roomba')
Right now, I'm programming the robot's brain.
The problem I'm facing with, is how to save the passes, wich the robot already goes.
Of course I can save each time where he is, but this will be a very big array,
and each time I have to choose where to go next, this will be very inefficient.


I'm trying to find a free library, that can handle two dimentions place,
that I can "mark", where the robot already cleaned, and where the obstacles, etc...

Thanks,
Avi.

[kev82]

What sensors do you have? How do you know where you are?

[aviplot]

Hi, I have 2 sensors (Camera & Encoders), but this is not the question.


Assume, that I know where am I relative to the start point.
What is the best way, to save where I already been?

Thanks.

[kev82]

How much memory do you have, the array doesn't strike me as being that big? If you spilt it into squares 10cmx10cm and you did it over a 50mx50m area, that is only 31K.

[aviplot]

I have a lot of memory, but I think that saving in array, is very bad idea.
The robot dimention: 40[cm] x 50[cm]
The movement resolution is 400[dpi]
wich meens, that if he moves 0.5 meter, I have to save 40*50*157 bits at least.
that is too much for me, and any calculation become massive.

[coder777]

That's an very interestiong task.

You don't need to store each position, just the positions where the robot stopped / hit an obstacle. To save even more memory you may count when the robot drives the same distance just shifted (perpendicular) by the predefined value (the cleaning area).

In a perfect rectangular room (from the very left to the very right) it'd take 3 values.

[kev82]

What's the justification for storing the array at the resolution of the sensor? For the task at hand, are squares of 10cmx10cm not accurate enough? If not, use square of 1cm by 1cm that's still only 3M for a 50mx50m area, and surely accurate enough I would have thought?

[aviplot]

OK, It's seems, that I will use cgrid, as my library.
This library contains most of what I need, including path finder.
(you can look at http://sourceforge.net/projects/qtamaze/develop for implementation)
Thanks all.