I have a setup, where a distance sensor, such as sonar or IR, rotates about 180 degrees and takes a distance measurement every few degrees. What I would like to do is to create a occupancy grid out of these measurements on an Arduino or, more specifically, I would like to compare two different algorithms, which create the grids.
One of these algorithms would be made by myself, but in order to make a solid comparison, I would like the other algorithm to be the one which is mentioned in occupancy grid materials and research papers, which utilizes a binary Bayes filter. Information about the algorithm and the implementation is available on Wikipedia and here (slides 9-13).
I'm not too familiar with the technical and the mechanical concepts involved in the binary Bayes filter and its implementation in the algorithm, so bear with me: The main problem for me is that the algorithm involving the binary Bayes filter takes into account "the robot poses", which, as I understand, pertains to the route which the robot has taken. However, my setup with the swiveling sensor is static - the sensor just rotates, but it doesn't change its position in space.
My question is this: if a have a "static" sensor, can I use the binary Bayes filter and the associated algorithm in order to create an occupancy grid? Would this require a small adjustment in the algorithm/math in this case? Would this be feasible on an Arduino? And does using this algorithm in a setup like this even make sense?
Perhaps, I have misunderstood the meaning of the robot poses; either way, any help would be massively appreciated!
How much storage do you have? One major problem with Occupancy Maps for the Arduino is that the Arduino has a very small amount of variable storage, where occupancy maps (OMs) can be large. When I did one a long time ago, I used a 1k by 1k map of bytes which used about 1 Megabyte per map. I had one map per room.
You cn experiment with smaller maps, but even a small map can use a lot of space. The UNO has 2k bytes of variable storage. A 10 by 10 map of bytes will take up 100 of the 2k. A 20 by 20 will take up 400 of the 2k, and a 40 by 40 will take up 1,600 bytes.
Sure, that is an issue, however, I have an SD card module for the arduino, where the map could be stored, and the map could also be stored in program memory of the arduino, which is much larger than the RAM.
The main issue now is if constructing this algorithm is feasible and whether or not it makes logical sense, which I have a hard time of evaluating due to inexperience with this subject.
DT makes some great points. This is not going to be easy with an Arduino. 2k of SRAM (really 1200 bytes after the Arduino stuff is loaded), 1K of EEPROM and a total of 32k of program EEPROM (which can only store program binary info as far as I know, so no help).
You could use 2 bits (unoccupied, occupied and unchecked) for each location which would multiply by four available memory. This would help you conserve memory which is pretty precious in this instance.
If you kept a 10x10 block in memory , you could use a scheme where you would write to the sd card every so often and then read from the sd card the new values for the map position the robot is sitting in. You would need to use encoders to figure out where you are via dead reckoning which is easy to get it confused. You would also have some degree of inaccuracy based on your readings from the ultrasonic which would not be calculated in. It would give you a rough idea, but certainly not down to a cm with any repeatability after it runs around for a half hour.
This is possible, but not easy. The bot would probably need to stop every so often as it is loading from the SD card so it wouldn’t be a very elegant solution. Why not move up the food chain to a Mega which would have more memory? That would be easier than playing all these games. That probably is going to be a bit of a problem too, but you have more memory to play with.
Firstly, as I mentioned in the OP, my ‘robot’ isn’t really a robot - it’s just a sensor on a servo, which rotates and takes measurements, but doesn’t move in space, which makes the problem a great deal easier and also eliminates any problems associated with dead reckoning.
Also I do have a Mega, it’s just that DT mentioned an Uno. Either way, an SD card and the program memory could be utilized.
Using booleans for the cells of the map grid would conserve space, but ultimately it’s going to be a headache in terms of accuracy, so I think using a single byte which would represent the probability of a cell of being occupied is the way to go.
I like your idea of the 10x10 ‘cache’ of the map, should probably make a few tests and see how much it improves performance and how large should it be.
I don’t think that it I don’t think that it possible to make a real occupancy map with just a static servo. I made a mistake in reading your post: I thought that your robot had one sensor, a sonar on a servo for rotation.
Unless you can move to various points it would be impossible to map a non-trivial room that way without some real hefty computing resources. If you have an empty room with no objects on the floor or walls, it should be possible to map half of it. It might be better to have a 360 degree servo or two sonars back to back so that you could measure the entirety of the room.
If you have some hefty resources and some sonar geniuses, you might be able to get more information from secondary bounces and so forth but I’ve never tried anything like that.
And for an occupancy map you might want to try a Teensy 3.1. They are only $20 and about the size of an Arduino Pro Mini, but has an ARM Cortex 4, with 64k of RAM and lots of pins, though you have to put headers in odd places to get to some of them. They run many of the Arduino sketches.
